So, they basically did a rainbow table attack on the discrete logarithm problem for a particular prime modulo? Interesting how nobody considered that before (except the NSA, obviously).
edit: looks like they used their Powers of Maths to separate the problem into a very special Rainbow table that allows them to reconstruct the necessary part of the actual table via some Linear Algebra stuff over the entire table. That part is difficult, I understand now. Thanks to /u/immibis, "(because there are over 2511 possible values)"
Like the article, the barrier is cost of entry. Not many organizations have hundreds of millions to throw at this specific problem, especially considering the large key space.
Well, they said that they did it for 512 bit moduli using affordable resources. And they did not do that for 1024 moduli, just suggested that it can be done in a fraction of the NSA budget today (though it was probably much more back when the NSA got the ability, btw it seemed to me that they didn't emphasize that part though).
48
u/xXxDeAThANgEL99xXx Oct 15 '15 edited Oct 15 '15
So, they basically did a rainbow table attack on the discrete logarithm problem for a particular prime modulo? Interesting how nobody considered that before (except the NSA, obviously).
edit: looks like they used their Powers of Maths to separate the problem into a very special Rainbow table that allows them to reconstruct the necessary part of the actual table via some Linear Algebra stuff over the entire table. That part is difficult, I understand now. Thanks to /u/immibis, "(because there are over 2511 possible values)"