JP Journal of Algebra, Number Theory and Applications
Volume 23, Issue 2, Pages 131 - 148
(December 2011)
|
|
NEW WEAK RSA KEYS
Abderrahmane Nitaj
|
Abstract: Let be an RSA modulus with In this paper, we analyze the security of RSA with the class of the exponents e satisfying an equation with
and
where is the greatest integer less than or equal to x. Using the continued fraction algorithm and Coppersmith’s lattice reduction method for solving polynomial equations, we show that such exponents lead to the factorization of N in polynomial time. Additionally, we show that the class of such weak exponents is large, namely that their number is at least where is a small constant depending only on N. |
Keywords and phrases: RSA, cryptanalysis, factorization, continued fraction, Coppersmith’s method. |
|
Number of Downloads: 406 | Number of Views: 942 |
|