Author |
Topic: Efficiently cracking RSA (Read 1910 times) |
|
teekyman
Full Member
Gender: 
Posts: 199
|
 |
Efficiently cracking RSA
« on: Feb 15th, 2012, 11:31pm » |
 Quote  Modify
|
Long time no post!
Say you had n unique RSA keys, i.e. product of two large primes, and say n was large, ~100 million.
The random number generator in the RSA implementation was a little sloppy, and a singificant percent, ~.2%, of these keys share one of their prime factors with some other key in this list. We'll call these the "bad keys".
How do you factor *all* the bad keys in reasonable time?
The answer is cute, and the problem is shockingly real:
http://www.nytimes.com/2012/02/15/technology/researchers-find-flaw-in-an -online-encryption-method.html
For the real world data in the article, "reasonable time" meant on the order of hours.
Assume arithmetic is O(1), even for very large numbers. In practice, it is fast enough.
| hidden: |
The best completely correct algorithm I have is O(#bad keys * n).
Under the assumption that no number shares both of its primes with other primes (or if I dont care about finding such numbers), I can do it in O(n) time. |
|
| « Last Edit: Feb 16th, 2012, 1:11am by teekyman » |
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Efficiently cracking RSA
« Reply #1 on: Feb 17th, 2012, 7:58am » |
Quote Modify
|
You still have to compare the keys pairwise. That woudl be O(n*n).
O(#bad keys * n) looks suspicious, it would mean it is easier the less bad keys there are.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print