Consequence of $p\bmod e=2$ in RSA prime generation - Cryptography Stack Exchange most recent 30 from crypto.stackexchange.com 2022-01-26T18:16:19Z https://crypto.stackexchange.com/feeds/question/81895 https://creativecommons.org/licenses/by-sa/4.0/rdf https://crypto.stackexchange.com/q/81895 4 Consequence of $p\bmod e=2$ in RSA prime generation fgrieu https://crypto.stackexchange.com/users/555 2020-07-12T22:40:38Z 2020-07-13T22:52:24Z <p>When generating a prime <span class="math-container">$p$</span> for use in an RSA modulus with public exponent <span class="math-container">$e$</span>, it is necessary that <span class="math-container">$\gcd(p-1,e)=1$</span>. When <span class="math-container">$e=3$</span>, and since <span class="math-container">$p$</span> is a large prime, that implies <span class="math-container">$p\bmod e=2$</span>.</p> <p>Assume an RSA key generation procedure for 1024-bit primes used for a 2048-bit modulus is written to always generate primes with <span class="math-container">$p\bmod e=2$</span>, for both factors, including for large <span class="math-container">$e$</span> supplied as a parameter at key generation.</p> <p><strong>For what values of <span class="math-container">$e$</span> does this have any dire consequence?</strong></p> <p><sup>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 <span class="math-container">$N\bmod e=4$</span> always holds.</sup></p> https://crypto.stackexchange.com/questions/81895/consequence-of-p-bmod-e-2-in-rsa-prime-generation/81907#81907 2 Answer by took for Consequence of $p\bmod e=2$ in RSA prime generation took https://crypto.stackexchange.com/users/81388 2020-07-13T22:37:18Z 2020-07-13T22:52:24Z <h2>Very large exponents <span class="math-container">$e$</span></h2> <p>Assuming that <span class="math-container">$e &gt; 2^t$</span> where <span class="math-container">$t &gt; 514$</span> we may use Coppersmith's attack to factorize <span class="math-container">$N$</span> efficiently. By this answer I only intend to exemplify that for <em>some</em> public exponents <span class="math-container">$e$</span> the given condition on the primes makes it significantly easier to factorize the RSA modulus. In particular it is worth noting that public exponents <span class="math-container">$e$</span> that conform to the FIPS 186-4 standard are less that <span class="math-container">$2^{256}$</span>, and are therefore not susceptible to the following.</p> <hr /> <p>The following (essentially) appears in .</p> <p><strong>Theorem (Coppersmith)</strong> Let <span class="math-container">$N$</span> be an integer of unknown factorization which has a divisor <span class="math-container">$b \geq N^\beta$</span>, <span class="math-container">$0 &lt; \beta \leq 1$</span>. Let <span class="math-container">$0 &lt; \epsilon \leq \frac{1}{7}\beta$</span>. Furthermore, let <span class="math-container">$f(x)$</span> be a univariate monic polynomial of degree <span class="math-container">$\delta$</span>. Then we can find all solutions <span class="math-container">$x_0$</span> of the equation <span class="math-container">$f(x) \equiv 0 \bmod b$</span> such that <span class="math-container">$$|x_0| \leq \frac{1}{2}N^{\beta^2/\delta - \epsilon}$$</span> using a LLL-reduction on a lattice of dimension <span class="math-container">$\leq \frac{\beta}{\epsilon} + \frac{1}{\beta}$</span>.</p> <p>We will apply this theorem for <span class="math-container">$\beta = 1/2$</span>, <span class="math-container">$\delta = 1$</span>, <span class="math-container">$b = p$</span> where <span class="math-container">$p$</span> is the larger of the two prime factors of the public RSA modulus <span class="math-container">$N = pq$</span>, and <span class="math-container">$\epsilon = (t - 514)/2046$</span>. To find a suitable polynomial <span class="math-container">$f$</span> we note the following.</p> <p>Note that <span class="math-container">$p \bmod e = 2$</span> implies that there is some integer <span class="math-container">$x$</span> such that <span class="math-container">$p = ex + 2$</span>. If we can find this <span class="math-container">$x$</span> we can determine <span class="math-container">$p$</span>. Now, note that <span class="math-container">$$ex + 2 = p \Rightarrow e_0 ex + 2e_0 = e_0 p,$$</span> where <span class="math-container">$e_0$</span> is the modular inverse of <span class="math-container">$e$</span> modulo <span class="math-container">$N$</span> (which is expected to be easy to determine), say <span class="math-container">$e_0 e = 1 + \ell N$</span>. Furthermore, note that the right hand equation may be rewritten as <span class="math-container">$x + 2e_0 = e_0 p - \ell N x$</span> which implies <span class="math-container">$x + 2e_0 \equiv 0 \bmod{p}$</span>. Hence, we have that any solution <span class="math-container">$x$</span> to <span class="math-container">$p = ex + 2$</span> must also be a solution to <span class="math-container">$f(x) \equiv 0 \bmod{p}$</span> where <span class="math-container">$f$</span> is the monic degree 1 polynomial defined as <span class="math-container">$$f(x) = x + 2e_0.$$</span></p> <p>Now, applying Coppersmith's theorem, with the given parameter values, we get that we find all solutions <span class="math-container">$x_0$</span> such that <span class="math-container">$$|x_0| \leq \frac{1}{2} N^{1/4 - (t-514)/2046}$$</span> using a LLL-reduction of a lattice of dimension <span class="math-container">$\leq \frac{1023}{t-512} + 2$</span>.</p> <p>Finally, we want to show that the <span class="math-container">$x$</span> such that <span class="math-container">$p = ex + 2$</span> is among the solutions found above. For this we have to show that such an <span class="math-container">$x$</span> must satisfy <span class="math-container">$$|x| \leq \frac{1}{2} N^{1/4 - (t-514)/2046}.$$</span> We can do this by noting that since <span class="math-container">$p = ex + 2$</span> we have <span class="math-container">$x \leq p/e \leq 2^{1024-t}$</span>. Now, <span class="math-container">$N = pq &gt; 2^{2046}$</span> and thus <span class="math-container">$$2^{1024-t} \leq \frac{1}{2}N^{1/4 - (t-514)/2046},$$</span> as desired. Hence, one of the solutions <span class="math-container">$x_0$</span> found by the LLL-reduction in Coppersmith's theorem is the sought after <span class="math-container">$x$</span>. To determine which solution is the correct one all we have to do is a trail division of <span class="math-container">$N$</span> by each <span class="math-container">$ex_0 + 2$</span>.</p> <hr /> <p><strong>Remark</strong>: We can at least do some small improvemets to the above, e.g. by noting that <span class="math-container">$x$</span> has to be odd so really we may start with an equation of the form <span class="math-container">$p = 2ey + e + 2$</span> instead.</p> <p> May A. (2009) <em>Using LLL-Reduction for Solving RSA and Factorization Problems</em>. <strong>In</strong>: Nguyen P., Vallée B. (eds) The LLL Algorithm. Information Security and Cryptography. Springer, Berlin, Heidelberg</p>