2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ btw, P' and Q' may be backdoored recursively $\endgroup$
    – Fractalice
    Mar 4 at 15:27
1
$\begingroup$
  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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – spore234
    Mar 4 at 14:49
  • $\begingroup$ That is a tricky question since It may not be the fastest in all ranges. It is good at the current top. $\endgroup$
    – kelalaka
    Mar 4 at 14:51
1
$\begingroup$

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.

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

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – spore234
    Mar 4 at 16:01
  • $\begingroup$ @spore234 The factorization that I write about is factorization of N, not N', by somebody who knows only N. $\endgroup$
    – Fractalice
    Mar 4 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.