Cryptanalysis of variants of RSA with multiple small secret exponents

In this paper, we analyze the security of two variants of the RSA public key cryptosystem where multiple encryption and decryption exponents are used with a common modulus. For the most well known variant, CRT-RSA, assume that n encryption and decryption exponents (el, dpl, dql), where l = 1, …, n, are used with a common CRT-RSA modulus N. By utilizing a Minkowski sum based lattice construction and combining several modular equations which share a common variable, we prove that one can factor N when (Formula presented) for all l = 1, …, n. We further improve this bound to (Formula presented) for all l = 1, …, n. Moreover, our experiments do better than previous works by Jochemsz-May (Crypto 2007) and Herrmann-May (PKC 2010) when multiple exponents are used. For Takagi’s variant of RSA, assume that n key pairs (el, dl) for l = 1, …, n are available for a common modulus N = prq where r ≥ 2. By solving several simultaneous modular univariate linear equations, we show that when (Formula presented), for all l = 1, …, n, one can factor the common modulus N.