Factoring Anderson's RSA backdoor

Question

In 1993, Anderson [1] proposed a backdoor to the RSA key generation algorithm. This backdoor requires that a backdoor key (prime) $A$ be implanted within the key generation portion of the RSA algorithm.

Instead of the usual way, primes $P$ and $Q$ are generated using the following algorithm:

First define a backdoor prime $A$ and two smaller random primes $P'$ and $Q'$.

Let $k=1$

$ \text{If} \ \ isprime(A\cdot k + P'):\\ \quad P = A\cdot k + P' \\ \text{else}: k = k+1$

The analog is performed for $Q$ using $Q'$.

This algorithm was also described here Is there any more information on this RSA backdoor?

This backdoor allows to calculate $N′= N \mod A$ and then factor $N′$ into $P′$ and $Q′$. Still $N'$ needs to be factored, but this is now a much easier problem as $N'$ is only about a fourth in size of $N$.

Please note that in my algorithm above I used $k=1$, the original implementation by Anderson suggests starting value $k=P'$ and iteratively increasing $k$ by one until $P$ is prime. In my algorithm I start with $k=1$.

My questions are:

1. does starting the iteration from $k=1$ instead of $k=P'$ make a difference?
2. in the way $N'$ is generated, what is the best way to factor $N'$ given the information how it is generated? Is there a certain factoring algorithm that makes factoring $N'$ very easy?

[1] Ross Anderson. Practical RSA Trapdoor. Electronic Letters. 29(11): 995, 1993.

Answer 1

1. does starting the iteration from $k=1$ instead of $k=P'$ make a difference?

If you start iteration from $k=P'$ then you get;

$$P = A\cdot (P'+i) + P'$$ where $ i = 0,1,2,\ldots$. Take modulo $A$

$$P = A\cdot (P'+i) + P' \pmod A$$

$$P = P' \pmod A$$

Therefore it will still work to reveal the $P'$

2. in the way $N'$ is generated, what is the best way to factor $N'$ given the information how it is generated? Is there a certain factoring algorithm that makes factoring $N'$ very easy?

The current factoring record in the open literature is 829-bit, however, the recommended key size is at least 2048, i.e each factor has 1024-bits. Therefore the size of $A$ must be around $1024$-bit. Once you set $A$, then you can seek $P = A\,k_1 + P'$ where $P$ is prime.

There is nothing that prevents one to generate small primes for $P'$ and $Q'$. The $P'$ and $Q'$ doesn't add much to $P = A\,k_1 + P'$ since they are added. The $A$ and $k_1$ is important.

Therefore you can choose $P'$ and $Q'$ as below as $829$-bits.

You can use the CADO-NFS to factor the $P'\cdot Q'$. Here some notes about it, too.

Answer 2

If you start at $k=1$, we expect you to end the loop at some smallish $k_P$ (and smallish $k_Q$). Note that this makes $P-Q=(k_P-k_Q)\cdot A+(P'-Q')$ so that it is not uncommon to have $k_P=k_Q$ so that $P\approx Q$ and factorization of $N$ is facilitated. If you collect many, many backdoored $N$, you may succeed sometimes. (I know that still $P'-Q'\gg1$, but at least certainly $P'-Q'\ll \sqrt N$). Even iv you deliberately avoid $k_P=k_Q$, they are still small-ish and make $\frac PQ\approx \frac{k_P}{k_Q}$, which also facilitates factorization (with the same caveat).

If this way you manage to factor several $N$ and are surprised that $\frac PQ$ is always near some simple fraction $\frac{k_Ü}{k_Q}$, you may find that the numbers $\frac P{k_P}$ and $\frac Q{k_Q}$ are suspiciously of the same size for all your factored numbers. It may be possible to extract $A$ with less effort than hoped.

Answer 3

1. does starting the iteration from k=1 instead of k=P′ make a difference?

Then both primes $P$ and $Q$ will be very close to small multiples of $A$ and it would be easy to factor without knowing $A$.

For example, after guessing those factors $a,b$ such that $P=aA+P',Q=bA+Q'$, we could run Fermat's method on $abN=abPQ=(baA+bP')(baA+aQ')$. Note the difference of factors is $bP' - aQ'$ which is small. In the extreme case when $P,Q$ are roughly $O(\sqrt{A})$ (larger values would overflow $A$ and would be hard to factor using the backdoor), this can probably still be broken using Coppersmith's techniques.