A generalized attack on RSA type cryptosystems

Let N = pq be an RSA modulus with unknown factorization. Some variants of the RSA cryptosystem, such as LUC, RSA with Gaussian primes and RSA type schemes based on singular elliptic curves use a public key e and a private key d satisfying an equation of the form ed - k(p(2)-1)(q(2)-1) = 1. In this paper, we consider the general equation ex - (p(2)-1)(q(2)-1)y =z and present a new attack that finds the prime factors p and q in the case that x, y and z satisfy a specific condition. The attack combines the continued fraction algorithm and Coppersmith's technique and can be seen as a generalization of the attacks of Wiener and Blomer-May on RSA. (C) 2017 Elsevier B.V. All rights reserved.