The Million-Key Question—Investigating the Origins of RSA Public Keys
summary
Analysis of 60 million keys from 22 libraries and 16 smartcards finds that specific prime-generation choices (manipulating prime MSBs, avoiding small factors, length restrictions, provable-prime construction, incrementing by 2, etc.) leak bits into public moduli; the team identifies 7 implementation choices that create detectable biases. They build a nine-bit mask classifier and a precomputed classification matrix, publish datasets and a web tool, and test on 10 million TLS keys and 1.4M PGP keys: one key yields ~40% top-1 accuracy, five keys ~78%, ten keys ~85% top-1.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:17Question
- 1:54Methodology
- 2:51Heatmap
- 5:38Implementation Choices
- 7:18Classification
- 9:05Results
- 12:01Classification Accuracy
- 19:30Impact
- 21:28Defense
- 22:48Technical Report
- 23:44Limitations
- 24:25Conclusion
related talks
29mHow Prime Numbers Keep the Internet Secure
01h 26mTLS Cryptography for Programmers
01h 00mCS Fundamentals: Why SSL and SSH are Secure
58mKeynote: Crypto means Cryptography!
52mAsymmetric Encryption: A Deep Dive
01h 13mHow Diffie-Hellman Fails in Practice
24mFinding insecure cryptographic keys in DKIM, DNSSEC, OpenID Connect & elsewhere
48mRSA is Dead. Long Live BB84!