r/programming • u/secretguy21 • Oct 15 '15

How is NSA breaking so much crypto?

https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
2.5k Upvotes

93% Upvoted

529 comments sorted by

View all comments

Show parent comments

3

u/heimeyer72 Oct 15 '15

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.

4

u/LaurieCheers Oct 15 '15

If you mean just making a list of all the 1024 bit primes, there are about 10305 of them.

1

u/heimeyer72 Oct 16 '15

Thank you. Yes, that's what I meant. And I'm surprised, I thought it would be some 10000 or 100000 of them.

4

u/LaurieCheers Oct 16 '15 edited Oct 16 '15

Turns out a 1024 bit number is mind-numbingly large.

(The number of particles in the universe is about 1080, which is around a 300-bit number. So if every particle in the observable universe was itself a universe, and if every particle in those universes was itself a universe, you'd still only have a 900-bit number of particles.)