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. © Springer International Publishing Switzerland 2015.