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 (e_l,d_(pl),,d_(ql)), 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 iV when d_(pl),d_(ql) ＜ N 2n-3/8n+2 for all l = 1,… ,n. We further improve this bound to d_(pl)(or d_(ql)) ＜ N 9n-14/24n+8 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 (e_l, d_l) for l = 1, … , n are available for a common modulus N = p~r q where r ≥ 2. By solving several simultaneous modular univariate linear equations, we show that when d_l ＜ N(r-1)/(r+1)~(n-1/n) , for all l= 1,…,n, one can factor the common modulus N.
展开▼
