Header menu link for other important links
Cryptanalysis of an RSA variant with moduli N=prql
Published in Walter de Gruyter GmbH
Volume: 11
Issue: 2
Pages: 117 - 130
In this paper we study an RSA variant with moduli of the form N = prql (r > l ≥ 2). This variant was mentioned by Boneh, Durfee and Howgrave-Graham [2]. Later Lim, Kim, Yie and Lee [11] showed that this variant is much faster than the standard RSA moduli in the step of decryption procedure. There are two proposals of RSA variants when N = prql. In the first proposal, the encryption exponent e and the decryption exponent d satisfy ed = 1 mod pr-1ql-1(p-1)(q-1),whereas in the second proposal ed = 1 mod (p-1)(q-1). We prove that for the first case if d < N1-(3r+l)(r+l)-2, one can factor N in polynomial time. We also show that polynomial time factorization is possible if d < N(7-2¶7)/(3(r+l)) for the second case. Finally, we study the case when few bits of one prime are known to the attacker for this variant of RSA. We show that given min( l r+l , 2(r-l) r+l ) log2 p least significant bits of one prime, one can factor N in polynomial time. © 2017 Walter de Gruyter GmbH, Berlin/Boston.
About the journal
JournalData powered by TypesetJournal of Mathematical Cryptology
PublisherData powered by TypesetWalter de Gruyter GmbH
Open AccessNo