Consequence of $p\bmod e=2$ in RSA prime generation

When generating a prime $$p$$ for use in an RSA modulus with public exponent $$e$$, it is necessary that $$\gcd(p-1,e)=1$$. When $$e=3$$, and since $$p$$ is a large prime, that implies $$p\bmod e=2$$.

Assume an RSA key generation procedure for 1024-bit primes used for a 2048-bit modulus is written to always generate primes with $$p\bmod e=2$$, for both factors, including for large $$e$$ supplied as a parameter at key generation.

For what values of $$e$$ does this have any dire consequence?

Note: I know no circumstance making this assumption hold, not even a CTF. And that would not be a subtle way to rig the key generator, since that's externally detectable from the public key because $$N\bmod e=4$$ always holds.

• Do you assume any upper bound on $e$ (e.g. $e < 2^{256}$ as in FIPS186-4)? For very large $e$ (i.e. $e > 2^{512}$) you should at least be able to use Coppersmith's.
– took
Jul 13 '20 at 18:56
• @took: the only assumption I made so far is the one stated. Since the situation is totally hypothetical, anyone's free to make further assumptions. The lower the $e$ allowing attack, the better.
– fgrieu
Jul 13 '20 at 20:09

Very large exponents $$e$$

Assuming that $$e > 2^t$$ where $$t > 514$$ we may use Coppersmith's attack to factorize $$N$$ efficiently. By this answer I only intend to exemplify that for some public exponents $$e$$ the given condition on the primes makes it significantly easier to factorize the RSA modulus. In particular it is worth noting that public exponents $$e$$ that conform to the FIPS 186-4 standard are less that $$2^{256}$$, and are therefore not susceptible to the following.

The following (essentially) appears in .

Theorem (Coppersmith) Let $$N$$ be an integer of unknown factorization which has a divisor $$b \geq N^\beta$$, $$0 < \beta \leq 1$$. Let $$0 < \epsilon \leq \frac{1}{7}\beta$$. Furthermore, let $$f(x)$$ be a univariate monic polynomial of degree $$\delta$$. Then we can find all solutions $$x_0$$ of the equation $$f(x) \equiv 0 \bmod b$$ such that $$|x_0| \leq \frac{1}{2}N^{\beta^2/\delta - \epsilon}$$ using a LLL-reduction on a lattice of dimension $$\leq \frac{\beta}{\epsilon} + \frac{1}{\beta}$$.

We will apply this theorem for $$\beta = 1/2$$, $$\delta = 1$$, $$b = p$$ where $$p$$ is the larger of the two prime factors of the public RSA modulus $$N = pq$$, and $$\epsilon = (t - 514)/2046$$. To find a suitable polynomial $$f$$ we note the following.

Note that $$p \bmod e = 2$$ implies that there is some integer $$x$$ such that $$p = ex + 2$$. If we can find this $$x$$ we can determine $$p$$. Now, note that $$ex + 2 = p \Rightarrow e_0 ex + 2e_0 = e_0 p,$$ where $$e_0$$ is the modular inverse of $$e$$ modulo $$N$$ (which is expected to be easy to determine), say $$e_0 e = 1 + \ell N$$. Furthermore, note that the right hand equation may be rewritten as $$x + 2e_0 = e_0 p - \ell N x$$ which implies $$x + 2e_0 \equiv 0 \bmod{p}$$. Hence, we have that any solution $$x$$ to $$p = ex + 2$$ must also be a solution to $$f(x) \equiv 0 \bmod{p}$$ where $$f$$ is the monic degree 1 polynomial defined as $$f(x) = x + 2e_0.$$

Now, applying Coppersmith's theorem, with the given parameter values, we get that we find all solutions $$x_0$$ such that $$|x_0| \leq \frac{1}{2} N^{1/4 - (t-514)/2046}$$ using a LLL-reduction of a lattice of dimension $$\leq \frac{1023}{t-512} + 2$$.

Finally, we want to show that the $$x$$ such that $$p = ex + 2$$ is among the solutions found above. For this we have to show that such an $$x$$ must satisfy $$|x| \leq \frac{1}{2} N^{1/4 - (t-514)/2046}.$$ We can do this by noting that since $$p = ex + 2$$ we have $$x \leq p/e \leq 2^{1024-t}$$. Now, $$N = pq > 2^{2046}$$ and thus $$2^{1024-t} \leq \frac{1}{2}N^{1/4 - (t-514)/2046},$$ as desired. Hence, one of the solutions $$x_0$$ found by the LLL-reduction in Coppersmith's theorem is the sought after $$x$$. To determine which solution is the correct one all we have to do is a trail division of $$N$$ by each $$ex_0 + 2$$.

Remark: We can at least do some small improvemets to the above, e.g. by noting that $$x$$ has to be odd so really we may start with an equation of the form $$p = 2ey + e + 2$$ instead.

 May A. (2009) Using LLL-Reduction for Solving RSA and Factorization Problems. In: Nguyen P., Vallée B. (eds) The LLL Algorithm. Information Security and Cryptography. Springer, Berlin, Heidelberg