CRYPTANALYSIS OF RSA WITH CONSTRAINED KEYS
Abstract
Let n = pq be an RSA modulus with unknown prime factors of equal bit-size. Let e be the public exponent and d be the secret exponent satisfying ed ≡ 1 mod ϕ(n) where ϕ(n) is the Euler totient function. To reduce the decryption time or the signature generation time, one might be tempted to use a small private exponent d. Unfortunately, in 1990, Wiener showed that private exponents smaller than are insecure and in 1999, Boneh and Durfee improved the bound to n0.292. In this paper, we show that instances of RSA with even large private exponents can be efficiently broken if there exist positive integers X, Y such that |eY - XF(u)| and Y are suitably small where F is a function of publicly known expression for which there exists an integer u ≠ 0 satisfying F(u) ≈ n and pu or qu is computable from F(u) and n. We show that the number of such exponents is at least O(n3/4-ε) when F(u) = p(q - u).
Remember to check out the Most Cited Articles! |
---|
Check out new Number Theory books in our Mathematics 2021 catalogue |