Information about RSA key pair generation with backdoor?

Question

Someone posted an article on Reddit a few days ago, and I haven't found much about it except for links back to the same page.

And for a brief summary, essentially, it's possible to introduce a backdoor during RSA key generation. For example, to generate a backdoored RSA-1024 key. (Assuming $\text{getPrime}(x)$ will return a random $x$-bit prime number)

\begin{align} A &= \text{genPrime}(384)\\ P^\prime &= \text{genPrime}(128)\\ Q^\prime &= \text{genPrime}(128)\\ P &= Ak_1 + P^\prime \end{align}

Where $k_1$ is incremented until $P$ is prime, starting with $k_1 = P^\prime$.

\begin{align} Q = Ak_2 + Q^\prime \end{align}

$k_2$ is is calculated similarly for $Q^\prime$.
$P$ and $Q$ are then used as the prime numbers for the rest of the key generation algorithm, and $A$ is kept as the backdoor key. $A$ can be generated based off of a predictable per-user value, like a MAC address or user ID.

To use the backdoor, the attacker (or in this case, developer) recalculates $A$ in the same way it was originally calculated (or just looks it up in a database) and then calculates $N^\prime = N \mod A$ and then factors $N^\prime$ into $P^\prime$ and $Q^\prime$. This will take the complexity of factoring a 256-bit number, which is well within reach of most organisations concerned with implementing backdoors. $P^\prime$ and $Q^\prime$ can then be used to calculate $P$ and $Q$ in the same way as above, and thus generate the entire private key.

Is there any more information about this? Possible attacks? (besides the obvious one in the case that $A$ is leaked) It seems intuitive that this would lower the security of RSA, considering it's lowering the key space from 1024-bit to 256-bit, but I don't see how it can be broken without knowing $A$.

Answer 1

Actually, if the RSA key generation is malicious, there are even more subtle ways that can someone can leak the key.

The cleverest way I've seen works like this (assuming that we're generating an RSA-1024 key; for RSA-2048, we just use a larger curve):

• The attacker generates an EC public/private key pair; using a 192 bit curve for RSA-1024 is good. He keeps the EC private key secret; he'll install the EC public key into the program below.

• To generate a key, the program selects a random 192 bit seed $R$.

• It uses that seed to see a process that selects a random 512 bit prime $P$.

• It encrypts the seed $R$ using the EC public value (perhaps using EC-ElGamal), resulting in a 384 bit value $E$.

• It then selects a 512 bit prime $Q$ with the constraint that $Q \equiv P^{-1}(2E+1) \pmod{2^{385}}$

• The product $PQ$ is the RSA modulus (and the rest of the RSA key pair is generated normally)

Then, the attacker can easily factor this RSA key (by extracting $E$ directly from the bit pattern of the RSA modulus, using the EC private key to decrypt it resulting in $R$, and then using R to recover $P$. And, no one without the EC private key has any advantage to factor this, even if they know the exact procedure used to generate the RSA key; both $P$ and $Q$ were chosen fairly, and the additional constraints on $Q$ do not help the attacker at all.

The moral of this story: if the attacker can control your RSA key generation process, you may have no security.

Answer 2

The field of cryptography that you are looking for is called Kleptography. In kleptography, we are dealing with a setting where the device performing your cryptographic tasks is potentially malicious. Now this device tries to leak information to some attacker that allows this attacker to break the used cryptographic scheme. If I am not mistaken that scheme was proposed in the original work by Young and Yung. I did not check this but this paper is definitely a good starting point to get more information and contains at least two proposals for "RSA backdoors".

Answer 3

RSA modules factoring are not hard in general case. In special cases we can factor numbers easily. One of these special cases is weak prime number, if at least one of two RSA modules primes is weak we can factor it easily. It is interesting that number of such $1024$ bit modules are at least $2^{750}$ and for $2048$ bit is $2^{1500}$. Your mentioned RSA backdoor is special form of this weak prime number. So we can easily factore this number with lattice based attack (even if we dont know $A$).

for more detail about weak prime number you can see "Factoring RSA moduli with weak prime factors".