On the Improvement Attack Upon Some Variants of RSA Cryptosystem via the Continued Fractions Method

Abstract

Let N = pq be an RSA modulus where p and q are primes not necessarily of the same bit size. Previous cryptanalysis results on the difficulty of factoring the public modulus N = pq deployed on variants of RSA cryptosystem are revisited. Each of these variants share a common key relation utilizing the modified Euler quotient (p2 - 1)(q2 - 1), given by the key relation ed - k(p2 - 1)(q2 - 1) = 1 where e and d are the public and private keys respectively. By conducting continuous midpoint subdivision analysis upon an interval containing (p2 - 1)(q2 - 1) together with continued fractions on the key relation, we increase the security bound for d exponentially.

Keywords

• Algebraic cryptanalysis
• continued fractions method
• integer factorization problem
• RSA-variants