# Factoring Anderson's RSA backdoor

In 1993, Anderson  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?

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

• btw, P' and Q' may be backdoored recursively Mar 4 at 15:27

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'$$

1. 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.

• thanks for your answer. My question regarding 2. was if this particular construction of N' makes it vulnerable to a certain factorization method that can solve this faster. As I understand CADO-NFS is a state-of-the-art general factorization method. Mar 4 at 14:49
• That is a tricky question since It may not be the fastest in all ranges. It is good at the current top. Mar 4 at 14:51

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.

• thanks, but how can I deduct P or P' (or one of the k's) if I know A? Mar 5 at 8:14
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.

• thanks, I already tried factoring N' using Fermat in an example I made up with but it didn't work. How would I guess a and b (or k1 and k2 in my notation) if I don't know P' and Q'. Assume that I know A (and N). Mar 4 at 16:01
• @spore234 The factorization that I write about is factorization of N, not N', by somebody who knows only N. Mar 4 at 20:12