These 184 keys include 103 keys that share primes and that are efficiently factored by a batch-GCD computation. This is the same type of computation that was used last year by two independent teams (USENIX Security 2012: Heninger, Durumeric, Wustrow, Halderman; Crypto 2012: Lenstra, Hughes, Augier, Bos, Kleinjung, Wachter) to factor tens of thousands of cryptographic keys on the Internet.
The remaining 81 keys do not share primes. Factoring these 81 keys requires taking deeper advantage of randomness-generation failures: first using the shared primes as a springboard to characterize the failures, and then using Coppersmith-type partial-key-recovery attacks. This is the first successful public application of Coppersmith-type attacks to keys found in the wild.Category / Keywords: public-key cryptography / RSA, smart cards, factorization, Coppersmith, lattices Original Publication (in the same form): IACR-ASIACRYPT-2013 Date: received 16 Sep 2013 Contact author: tanja at hyperelliptic org Available format(s): PDF | BibTeX Citation Version: 20130919:123719 (All versions of this report) Discussion forum: Show discussion | Start new discussion