Cryptology ePrint Archive: Report 2010/650

Cryptanalysis of the RSA Subgroup Assumption from TCC 2005

Jean-Sebastien Coron and Antoine Joux and Avradip Mandal and David Naccache and Mehdi Tibouchi

Abstract: At TCC 2005, Groth underlined the usefulness of working in small RSA subgroups of hidden order. In assessing the security of the relevant hard problems, however, the best attack considered for a subgroup of size 2^{2k} had a complexity of O{2^k}. Accordingly, k=100 bits was suggested as a concrete parameter.

This paper exhibits an attack with a complexity of roughly 2^{k/2} operations, suggesting that Groth's original choice of parameters was overly aggressive. It also discusses the practicality of this new attack and various implementation issues.

Category / Keywords: public-key cryptography / RSA moduli, hidden order, subgroup, cryptanalysis.

Publication Info: An extended abstract will appear at PKC 2011. This is the full version.

Date: received 21 Dec 2010

Contact author: mehdi tibouchi at normalesup org

Available formats: PDF | BibTeX Citation

Version: 20101221:152922 (All versions of this report)

Discussion forum: Show discussion | Start new discussion