wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Efficiently cracking RSA
        
(Message started by: teekyman on Feb 15^th, 2012, 11:31pm)

Title: Efficiently cracking RSA
Post by teekyman on Feb 15^th, 2012, 11:31pm

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.

[hideb]
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.[/hideb]

Title: Re: Efficiently cracking RSA
Post by Grimbal on Feb 17^th, 2012, 7:58am

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.