Re:Flaw found in online encryption method
by jalapeno_dude on Tuesday February 14, 2012 @03:37PM
(#3591702)
They didn't describe the technique, but the fact that the paper has the keyword "Euclidean algorithm" makes it pretty obvious--they just gathered a list of public keys, took the gcd of all the pairs, and whenever they found a gcd not equal to one, they'd cracked both keys out of that particular pair. See my earlier comment.
I took the 'the straightforward approach would require
about ten core-years and would not scale well' to mean they had a more efficient method.
Re:Flaw found in online encryption method
by tptacek on Tuesday February 14, 2012 @05:46PM
(#3592152)
They do, but does it matter? Ten core-years is not a forbidding threshold.
Not really - it does make a difference between amateur attackers and professional, but the potential value is high enough that there will probably be plenty of well funded attackers.
Somewhat disappointing, but not surprising that they did not describe their actual calculation technique for finding the connected primes. It strikes me that there isn't a good excuse for having bad random numbers with the computation power we now have. A simple bitwise addition of various sources of supposedly random numbers is strictly stronger than any subset of its components. So we can combine lots of questionable strong sources and get a very strong source.
Generating the primes locally with insufficient independence seems more understandable than that the same primes are used by independent parties. That hints at a more severe problem with random number generation. Regardless, assuming this is confirmed, it is a significant problem that needs to be hunted down.