A Generalized Attack on Some Variants of the RSA Cryptosystem

摘要

Let N = pq be an RSA modulus with unknown factorization. The RSA cryptosystem can be attacked by using the key equation ed - k(p - 1)(q - 1) = 1. Similarly, some variants of RSA, such as RSA combined with singular elliptic curves, LUC and RSA with Gaussian primes can be attacked by using the key equation ed - k (p~2 - 1) (q~2 - 1) = 1. In this paper, we consider the more general equation eu - (p~2 - 1) (q~2 - 1) v = w and present a new attack that finds the prime factors p and q in the case that u, v and w satisfy some specific conditions. The attack is based on Coppersmith's technique and improves the former attacks.