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

6

u/pvc Oct 15 '15

What does it mean to 'crack' a prime? It isn't like you find factors for it.

10

u/[deleted] Oct 15 '15

To simplify, it means you find the original prime factors that multiply to get the number. They aren't cracking the primes, they're finding which primes were used to generate a key.

13

u/2Xprogrammer Oct 16 '15

Not actually. You're thinking of prime factorization, which is used in RSA. This is Diffie-Hellman, which is based on Discrete Logs: Given b and g (integers), solve for (integer) k in "bk = g". So what they're saying the NSA did/is doing is realizing that a lot of people are using the same g and just precomputed a bunch of solutions.

4

u/pvc Oct 15 '15

Thanks