Comments: RSA keys - crunchable at 1024?

Don't panic. Discrete logarithms mod p (where p is a Sophie-Germain prime that is (p-1)/2 is also prime) seems to be, in the light of these same developments, considerably harder than factorization. The same Number Field Sieve can be used for both, except that the resources for the matrix step are squared, and with them pretty much the cost.
Also, it seems that SHA1 (and even MD5) can be fixed. The number of "problematic" blocks seems to be small and they seem to be easily detectable, meaning that it is possible to construct MD5+ and SHA1+ that give the same hash for most data (which does not contain problematic blocks) while being resistant to the collision attack. So not all is lost.
I'll dig up the references next week.

Also, if you have to hog some $1M hardware for almost a year in order to break one key, then you need to be very determined to follow through. It's still a very expensive excercise, in short. Assuming $1M being the marginal cost, NSA may spend, say, $10G (given a very generous budget) to build 10k such machines, which, given the months spent on each individual key, is still not terribly many.

Posted by Daniel A. Nagy at September 14, 2005 08:35 PM
Post a comment









Remember personal info?






Hit Preview to see your comment.
MT::App::Comments=HASH(0x564d1fbb4c40) Subroutine MT::Blog::SUPER::site_url redefined at /home/iang/www/fc/cgi-bin/mt/lib/MT/Object.pm line 125.