Let $n=pq$ be the RSA module and at least one of $p,q$ is a weak prime.It is proved that the number of such $1024$bit $n$ is at least $2^{759}$. With lattices we can factor these $n$ in a second (I implemented it). Are you know the methods that are more powerful than this method?
$\begingroup$
$\endgroup$
4
asked Dec 30, 2015 at 11:33
-
1$\begingroup$ In RSA the assumption is that $p$ and $q$ are close together $>2^{\log_2\left(n\right)/2-0.5}$. If it isn't then factoring get's easier. I fail to see how this is a lattice-based attack. $\endgroup$– Artjom B.Commented Dec 30, 2015 at 13:19
-
$\begingroup$ It is a new($2015$) and very interesting lattice based attack.In this method we convert numbers to polynomial and then we factor that polynomial with lattices. For more detail you can see "Factoring RSA moduli with weak prime factors". $\endgroup$– Meysam GhahramaniCommented Dec 30, 2015 at 13:34
-
3$\begingroup$ Unless someone finds a way to sharpen the attack, it would appear to be impractical when factoring an RSA modulus. $2^{759}$ sounds large, but given that there are circa $2^{1003}$ 1024-bit RSA modulii, that means that a random modulii has a probability of around $2^{-244}$ of being vulnerable. $\endgroup$– ponchoCommented Dec 30, 2015 at 15:12
-
2$\begingroup$ I think maybe some people are misunderstanding something here. AFAICT the OP states that there are at least $2^{759}$ RSA moduli (i.e. semiprimes) of length 1024 bit that have at least one weak prime as a factor. As poncho stated, the chance of hitting them at random is low. If somebody doesn't know the paper at question is ia.cr/2015/398 $\endgroup$– SEJPMCommented Dec 30, 2015 at 19:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This is not quite an answer, because what I'll discuss is only about as powerful as the attack in the question, which refers to section 3 onwards in: Abderrahmane Nitaj and Tajjeeddine Rachidi, Factoring RSA moduli with weak prime factors (preliminary 2015-05 eprint).
The method I'll discuss is acknowledged in section 2.3 of the above article. It was exposed in the seminal: Don Coppersmith, Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known, in proceedings of Eurocrypt 1996; and in section 11 of his Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities in Journal or Cryptology, 1997 (paywalled; or try blind Googling).
The idea is to consider RSA moduli $N=pq$, with $N$ of $n$ bits, $p$ and $q$ prime, perhaps $q<p<2q$; and within that consider the moduli with a "weak prime factor" $p$ having the top $n/4$ bits matching some known arbitrary value (that also works with the low bits). Using a lattice attack (that is, based on the Lenstra-Lenstra-Lovász lattice basis reduction algorithm), $N$ is factored in polynomial time, and efficiently so for common RSA key sizes.
A preliminary version of Nitaj and Rachidi article stated (page 9 below table 2) that for $N=pq\in[2^{1024},2^{1026}]$, the $\ge2^{759}$ moduli that their new method can factor
is much larger than the number of RSA moduli with a weak Coppersmith prime factor in the same interval, which is actually $N^{0.25}\approx2^{256}$.
Fact is, the authors had grossly miscounted; their exponent $256$ in this quote is too small by a factor of nearly $3$. We get $>768$ is we assume all integers are prime (which in the circumstance is a fine approximation); or $>751$ if we consider that among 513-bit integers, one in about $2^{8.5}$ is prime. So the new method is at best claimed to improve Coppersmith's by a mere $8$ bits. Further, the set of weak Coppersmith prime factors can be trivially extended by a factor of $2^k$ by varying the low $k$ bits of the known arbitrary value.
As noted by poncho, neither method is likely to succeed for randomly seeded $p$ and $q$, for there are $>2^{1008}$ RSA moduli in the interval considered, and odds that a weak one is selected by chance are entirely negligible (in the order of $2^{-248}$).
What's notable with Nitaj and Rachidi's method is that it extends Coppersmith's attack to a more flexible set (not a much wider set) of RSA moduli; and has found applications in factoring more moduli actually deployed (that have been poorly generated) than in: Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange: Factoring RSA keys from certified smart cards: Coppersmith in the wild aka smartfacts, initially in proceedings of Asiacrypt 2013.
Update: the issue pointed above was promptly corrected in a revised version: Abderrahmane Nitaj and Tajjeeddine Rachidi, Factoring RSA moduli with weak prime factors (2015-12-31).
