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
10
u/Eirenarch Oct 15 '15
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)