Attacking RSA Using an Arbitrary Parameter

In this paper, we introduce a parameter u that is related to N via an arbitrary relation. By knowing the parameter along with RSA public key pairs, (N, e), we conduct two new attacks on the RSA cryptosystem. The first attack works on the equation [Formula: see text] where [Formula: see text] is the best known lower bound of [Formula: see text]. It combines the continued fraction method and Coppersmith’s method to factor N in polynomial time. The second attack shows that given [Formula: see text] for [Formula: see text] and a fixed X, we can simultaneously factor the k RSA moduli. It manipulates the result from diophantine approximation to enable the conditions of Coppersmith’s method. These attacks show that there are more possible weak RSA key pairs.