4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – took
    Jul 13 '20 at 18:56
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Jul 13 '20 at 20:09
2
$\begingroup$

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

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.

[1] 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

$\endgroup$

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.