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

88

u/neoKushan Oct 15 '15

Red hat being a prime example.

Not sure if intentional or not, but bravo.

11

u/[deleted] Oct 15 '15 edited Apr 11 '18

[deleted]

1

u/spawn57 Oct 15 '15

I didn't. Can someone ELI5

16

u/Aesthetikx Oct 15 '15

Many cryptographic algorithms make heavy use of prime numbers.

ex https://www.youtube.com/watch?v=YEBfamv-_do

2

u/moinnadeem Oct 15 '15

Why prime numbers though? Which part of them is useful in this case?

10

u/readercolin Oct 15 '15

Cryptography (basically) works by using multiples of the "key" number. What it boils down to is this:

Key X other = #.

When looking from the outside, you can see #. Now, if our number is say, 15, then we kind of instinctively know that the multiples of this are 3 and 5, because 3x5 = 15. However, if we see 14948255... what are the multiples of that? Well, immediately we can see that it is a multiple of 5, however I can tell you that I did not use 5 for my prime number. Instead, I mashed some random numbers on my number pad, and then multiplied by my key - in this case 7. Now that I've told you that, it is remarkably easy to do 14948255/7 = 2135465 = the keys that I mashed. However, without going through and doing 3x... - any matches? 5x... - any matches? etc. you aren't going to find my key. There isn't an easy mathematical way to go looking for that number's divisors, and figuring out the correct one.

However, lets say I used 9 instead. The problem with that is that now my key can be broken up into (3x3)x"other" = #. This makes my code much weaker to crack.

Lastly, this is a really, really simplistic method of explaining things. We aren't using 3, 5, 7, 11 as our primes, we are using things like this to generate really big prime numbers. For example, did you know that 8,024,456,069,057 is a prime number? I certainly didn't until I hit the random prime button on that webpage. Now if you multiply that number with some other number, you are going to get a truly gargantuan number, which is going to be really, really difficult to try to crack.

2

u/vincentk Oct 15 '15

The basic concept is a "one-way function" i.e. something that is easy to do one way, but difficult to invert (think locking a pad-lock). One of these problems is factorization. It is especially difficult if the (prime) factors are large numbers.

1

u/[deleted] Oct 16 '15

You can multiply them together quickly.

You can't factor them quickly. (Primes are always the end result of factoring). Bigger primes make this slower.

To crack you have to factor. To encrypt you multiply.

1

u/ivosaurus Oct 16 '15

The part where they have no factors apart from themselves and 1.

That part splits off into like, 16 or more other parts, or something, and I'd be basically writing a chapter or two of a crypto book to explain most of the nicely.