# Can linear congruential generator be used in public-key cryptography?

The question is not about generating pseudo-random numbers with linear congruential generator.

I'm exploring the possibility of using a Linear Congruential Generator (LCG) in the context of public-key cryptography. Specifically, consider the LCG defined by:

$$X_{n+1} = (a X_n + c) \mod m$$

Suppose the private key consists of four 64-bit integers: $$a$$, $$c$$, $$m$$, and $$n$$. Seed $$X_0$$ is publicly known. The public key is $$X_n$$, where $$X_n$$ is generated using the LCG, and previous ($$X_{n-1}, X_{n-2}, ...$$) or following ($$X_{n+1}, X_{n+2}, ...$$) values are not known to the attacker.

Given this setup, can this LCG be used effectively for public-key cryptography operations such as generating a public key from a private key, and performing signing and verification? Specifically, how would someone use the public key $$X_n$$ (and the known seed $$X_0$$) to encrypt or verify signatures, while requiring the private key components $$a$$, $$c$$, $$m$$, and $$n$$ for decryption or signature generation? Is it secure to use LCG in public-key cryptography? Is it vulnerable to attacks?

And the last but not least question: can I prove LCG insecurity in public-key cryptography using satisfiability modulo theories solver (SMT solver)? How?

• For the reasons in this answer we can't use the LCG as the basis of even symmetric cryptography, much less as the basis of public-key cryptography. However we can use an LCG as a component of a cryptosystem (public-key or not), even to the point that if we remove the LCG the cryptosystem falls apart. I conclude that what's asked is not specific enough.
– fgrieu
Commented Jul 23 at 7:43
• Thank you for your answer! I have clarified that $X_{n+1}$ or $X_{n-1}$ is not known to the attacker. Commented Jul 23 at 11:44
• I think I'm confused about something here: you refer to the parameters of the LCG as a "private key" and its output as a "public key" - are you proposing to use an LCG itself as some sort of public-key cryptographic system? How would you envision this working in practice? Commented Jul 23 at 12:05
• @nneonneo, you have understood the question correctly, but I am not proposing but asking what will happen if LCG used as some sort of public-key cryptographic system. Commented Jul 23 at 12:20
• For a public key operation, someone with the public key would need to do something (encrypt, verify a signature). How would someone use the knowledge of $X_0, X_n$ (and nothing else) to do that (so that, someone else would need knowledge of $a, c, m, n$ to do the other half (decrypt, generate a signature)? Commented Jul 23 at 13:18

I'll look at the issue, not from an LCG perspective, but from a public key operation perspective.

Alice generates a private and a public key; she gives the public key to Bob. This public key allows Bob to perform some operations (most commonly public key encryption or signature verification) while Alice's private key allows her to do the complementary operation (public key decryption or signature generation).

Now, this public key (plus any fixed global parameters) is all Bob knows about the private key. If there were multiple private keys that all corresponded to the same public key, Bob would not know which private key Alice had. Hence, for the complementary operation to be correct, they all must perform the same operation on Alice's side (that is, they all must be able to decrypt Bob's ciphertext or all generate signatures that validate with Bob's public key).

What this means is that if we were able to craft a private key that corresponded to a specific public key, we have effectively recovered the private key. Even if the bits of this 'recovered' public key weren't the same as what Alice originally generated, that doesn't matter, because it must be able to do the same things as Alice's original private key.

Now, when you look at what you propose as the public key ($$X_n$$) and global parameters ($$X_0$$), what someone could do is select $$a, c, m, n$$ values that are consistent with $$X_0, X_n$$. One obvious approach would be to select $$m$$ to be a prime larger than $$X_0, X_n, n=1, a=1$$, and $$c = X_n - X_0 \bmod m$$. This works as a private key, and so will act just like the "real" private key, hence demonstrating that whatever system you have around this is insecure.

• Can I prove that the use of LCG in public-key cryptography is insecure using SMT solver, like z3? How? Commented Jul 23 at 17:09
• @IvanStepanov: I believe I outlined such a proof. Let us consider the public key encryption case; Bob encrypts a message based on $X_0, X_n$, and there is a public procedure that, given $m, n, a, c$ values that correspond to the public $X_0, X_n$ values to recover the message (and Alice uses that procedure). What an attacker can do is generate his own $m, n, a, c$ values (based on what I outlined) and then use that same public procedure, which must also recover the message. Because this attack process is practical, the proposed public key system is insecure. Commented Jul 23 at 17:51
• I have tried your solution and it works! So, the complexity of this problem is just a matter of finding correct $m$. Thank you for understanding the question. Commented Jul 24 at 12:13

There are extremely efficient ways to break a linear congruential generator even with those parameters unknown, so the private key can be recovered. I hadn't known about how to recover $$m$$ so duplicating that here.

If none of $$a, b, m$$ are known, one can still break a linear congruential generator, by first recovering $$m.$$

Define $$t_n= X_{n+1} - X_n$$ and $$u_n= |t_{n+2} t_n- t^2_{n+1}|;$$

With high probability you will have $$m= gcd(u_1, u_2, ..., u_{10}).$$ 10 here is arbitrary; if you make it $$k$$ then the probability that this fails is exponentially small in $$k$$.

After this it is easy to solve for $$a,b.$$ See here for details.

• Please clarify what does $s$ mean? I guess it is $X$. So lets define that public key is $X_n$, how can someone get two next "public keys" $X_{n+1}$ and $X_{n+2}$ without brute force, if public key is only known as $X_n$? Commented Jul 23 at 11:01
• I don't think I understand - if $X_{n-1}$ is not known, it may as well be random, and at that point why are you bothering with an LCG to generate $X_n$? Just use the random $X_{n-1}$? Commented Jul 23 at 12:02
• @nneonneo I don't understand your question. It is a question about using LCG not as pseudo-random number generator. Commented Jul 23 at 12:14

If something hasn't been made into a cryptographic algorithm, then it means that it can't achieve the supposed security while being efficient. LCG is one such example. It's not to say there aren't RNG in crypto, it's just LCG isn't used in the field.

There are indeed public-key algorithms based on being able to generate pre-image-resistant bit-strings - i.e. cannot compute $$X_{n-1}$$ from $$X_n$$. Hash-based digital signatures such as SPHINCS, XMSS, LMS.

Finally, I think the discussion here is lengthy. And due to a mis-placed belief that LCG can be used as a PKC Keygen algorithm, we've had two parallel effert to both refute such use, and LCG being non-crypto RNG in general. I've therefore provided the feedback that this isn't a well-drafted question in the form of a downvote.

Don't feel down though, many people, including me, get downvoted. But hey, 1 upvote can undo 5 downvotes!

• "it's just LCG isn't used in the field" - so LCG should not be used in combination with true random source to XOR it to make another number? In other words, it should not be used to make cryptographically secure pseudorandom number generators (CSPRNGs)? Commented Jul 23 at 17:03
• "Don't feel down though, many people, including me, get downvoted." - thank you for your kind words! It always happens when you answer completely different point of view or when asking "strange" questions like this one. Commented Jul 23 at 17:27
• As for your downvote I have updated the question formulation to make it more clear. Commented Jul 23 at 17:34
• Don't feel down if this question will be deleted because of downvotes. Commented Jul 23 at 17:40

Can the Linear Congruential Generator be used in public-key cryptography?

From the question (v2) it follows that the public key $$X_n$$ would be at most 64-bit.

But there is no known public-key cryptosystem with such a small public key (the minimum appears to be twice the target security level, and provably the public key can't be much smaller than the target security level, and most often it's at least twice as much). This size consideration is enough to rule out what's asked.

More fundamentally, there is no public-key cryptosystem using a LCG as it's mathematical basis, regardless of size.

Can I prove LCG insecurity in public-key cryptography using satisfiability modulo theories solver (SMT solver)?

Note that in Satisfiability Modulo Theories the word modulo means "with respect to", and has essentially nothing to do with reduction modulo $$m$$.

We can prove the insecurity of the question's process to produce the public key $$X_n$$ of some public key cryptosystem from a random private key $$a$$, $$c$$, $$m$$, $$n$$ even with these parameters assumed to be much larger than in the question. And an SMT solver can be made part of it, but it's neither necessary nor particularly useful.

One way to make this proof is: proving that for any public key (here $$X_n$$) and any other public parameters (here $$X_0$$ and the size of parameters including $$m$$) it's possible to find a private key (here $$a$$, $$c$$, $$m$$, $$n$$) matching that public key. That's enough to break any sound asymmetric cryptosystem for encryption or signature (that is one that allows decryption or verification for any choice of public/private key pair and any message).

It turns out that we can most easily give this proof for $$n=1$$, which simplifies. I'll do this. We now want to find $$a$$, $$c$$, $$m$$ such that $$X_1=(a\,X_0+c)\bmod m$$ for some given $$X_1$$ and $$X_0$$ such that there is a solution, and all variables below some size.

If we use only the constraints in the question, we can set $$a=0$$, $$c=X_1$$, and $$m$$ the largest possible. That's a bit of a cheat, because an LCG usually requires $$\gcd(a,m)=1$$ and some extra conditions. But we can set $$c=(X_1-a\,X_0)\bmod m$$ for any $$a$$ and $$m>X_1$$ matching all the conditions.

If we want to introduce an SMT solver: the equation $$X_1=(a\,X_0+c)\bmod m$$ means $$0\le X_1 and $$\exists k\in\mathbb Z$$ such that $$k\,m+X_1=a\,X_0+c$$ (by definition of the$$\bmod$$ operator). That allows to express that equation conveniently in an SMT framework, and it's something an SMT solver can tackle, at least for given $$X_1$$ and $$X_0$$ and 64-bit limit to variables.

Variable $$n$$ is a complication that I won't address.

Note: proving the insecurity of the LCG as a pseudo-random number generator involves, given a number of outputs $$X_j$$ for $$j>n$$ (usually for consecutive $$j$$), finding some information about some other(s) $$X_j$$. In the question $$X_0$$ is assumed a given and $$a$$, $$c$$, $$m$$, $$n$$ are assumed secret. More usually $$X_0$$ is secret, perhaps $$c$$, more rarely $$a$$, seldom $$m$$ which order of magnitude can't be hidden for otherwise sound parameters, seldom $$n$$ which usually is $$0$$, or small and perhaps known from context. Such problem can be expressed as an SMT problem (introducing a variable $$k_j\in\mathbb Z_n$$ for each equation linking $$X_{j+1}$$ and $$X_j$$ to express the modular reduction), but not one that common SMT solvers will solve for parameters of interest, I'm afraid.

• Sure $X_n$ would be 64 bit. It is the a matter of scaling numbers in LCG. 64 bit here is to make question less complicated without involving big integers. Commented Jul 23 at 12:12
• "the minimum appears to be twice the target security level" - from the 'nits-R-us' department - Gravity-Sphincs has public keys the same size as the target security level (and so a security level of 128 bits gives us a 16 byte key). This does mean that it loses some security due to multitarget attacks... Commented Jul 23 at 13:12
• "Proving the insecurity of the LCG involves, given a number of outputs $X_j$ for $j>n$..." - I think I stated clear that I am asking about insecurity of using LCG in public key cryptography, not about insecurity of using LCG as random number generator... Maybe I do not understand something? Commented Jul 24 at 11:38
• @IvanStepanov: I had misunderstood what you ask in the end of the question. I hope I now answer it. Update: I now realize that a similar reasoning is made in the accepted answer
– fgrieu
Commented Jul 24 at 12:55