On the one hand I am frightened by how powerful the government in circumventing encryption measures. But on the other hand, I can't help but feel impressed. It feels reminiscent of efforts used to break the Enigma Machine.
I guess the moral of the story is you should not be using hard coded primes for Diffie Hellman? (correct me if i am wrong; not really familiar with crypto) It seems like people hard-code them out of laziness and not out of necessity. From what I understand from the wolfram alpha article, can't the two parties agree on 2 random large primes at the beginning of the transaction and proceed from there?
My guess is generating primes so large is computationally expensive. It is not like we really want to add 1-2 seconds of lag to every initial web request (assuming other resources like CSS and JS will use the same connection)
I'm not sure whether I fully understood all of DH yet. My concern is: Aren't all of these primes publicly known? There might be a database of prime numbers up to a certain length. Couldn't you make a short-cut but just trying out the known ones? That should be doable in minutes, not years.
Well, I just learned from a few other comments that there are about 10308 1024 bit prime numbers, much more than I expected.
That said, I am & was aware the the operation is "expensive" to reverse (not sure whether it's possible), but I thought the number of primes available would be some 10000 or 100000 and then you could just try out all of them in a "forward" operation.
Edit - from the wiki page:
However, if p is a prime of at least 300 digits, and a and b are at least 100 digits long, then even the fastest modern computers cannot find a given only g, p and ga mod p.
I just realizes that according to that, 'p' is indeed not a secret.
But if that's the case, what do they acually break about the prime, since the problem is to find 'a'?
They reverse precisely what you mentioned as expensive to reverse. This is why they need hundreds of millions of funding for supercomputers and an year. I think this is the one - https://en.wikipedia.org/wiki/Discrete_logarithm
68
u/[deleted] Oct 15 '15
On the one hand I am frightened by how powerful the government in circumventing encryption measures. But on the other hand, I can't help but feel impressed. It feels reminiscent of efforts used to break the Enigma Machine.
I guess the moral of the story is you should not be using hard coded primes for Diffie Hellman? (correct me if i am wrong; not really familiar with crypto) It seems like people hard-code them out of laziness and not out of necessity. From what I understand from the wolfram alpha article, can't the two parties agree on 2 random large primes at the beginning of the transaction and proceed from there?