How does being able to factor large numbers easily allow someone to crack a password or cypher?

In: 7

Multiplying prime numbers is one of those things that’s just super easy to do, but more difficult to undo… Especially if you don’t know the original numbers. I want to give you an example. Try to multiply 503*401 it’s not something you’re likely to be able to do in your head, but you’re allowed to use a calculator.

Now tell me, what are the prime factors of 224,971 (you’re still allowed to use a calculator, but not one like Wolfram Alpha where you just ask it what are the prime factors). There are some things we can do to make somewhat better than random guesses. For instance, the final digit is 1, so our prime numbers will either end in (1,1) (3,7) or (9,9) since those are the only numbers you can multiply to get a result ending in 1. Even with educated guesses, there is no algorithm that is guaranteed to take you immediately to the right answer. You just have to try dividing by all the prime factors until one leaves no remainder.

This is an amazing thing for cryptography because the thing we want in a password is the ability to very quickly verify if their password is correct, but storing their password is a bad idea. So we do a little math to their password and store the result. Then, of they type their password incorrectly, the math will not match the stored result. However, during a data breach, if they find the result. It’s way more difficult to reverse engineer what the password was that made this result. So they’re no better off than just guessing passwords. Now they’re just guessing prime numbers basically… And the biggest prime numbers we’ve found so far has nearly 25 million digits. I’d rather try to guess the password.

It’s almost the same story for encryption. If we have the key (we know the right numbers) it’s very simple to unlock the information. But the encrypted information requires you to guess and check prime numbers to figure out what the data actually says.

There are very sophisticated ways to actually encrypt the data, but let’s just show a really simple one for eli5. The message “Hi” in binary is 16 bits long. (2 bytes), if we just read all 16 bits back to back like it was a number, and converted it to decimal, that number is 18,537. Now, I’m going to multiply it by a large prime number to get 285,154,671. In this case, it’s actually easier to find the data than it is to find the prime number. Since the data is not a prime number already, there are even smaller numbers that can divide evenly our result. However, it’s *still* just a guess and check until you find the right numbers to divide. Once you do that, you can convert the data back to binary and read it on any computer.

However, if I hand you the prime number I used (15,383) it takes almost no effort in any calculator to do the division, convert to binary, and read the data.

In public key cryptography, the key to encrypt a message (the Public Key) is different than the key used to decrypt that message (the Private Key). There are other encryption systems (symmetric) where the same key is used for both.

In some public key systems, the public and private keys are related by the process of multiplying two large numbers. It’s quite easy to multiply two large prime numbers, but quite difficult to come up with those unique factors just knowing the product.

So the public key is made out of that product. Anyone has access to it, so that anyone can send an encrypted message to the owner. The private key (for decryption) is made out of the two large numbers that were multiplied together to get the product. So it’s really hard for an attacker, who knows the public key (large product) to figure out what the private key is, because factoring that large number is hard to do.

You would think that with computers it wouldn’t be that tough. If the numbers being used are *very* large, that’s simply not true. Although there are some algorithms to help, it’s essentially like a trial and error process. If the numbers are very large, there are a *lot* of numbers to try and even a very fast computer will take a long, long time to sift through them all.

[removed]

For RSA cryptography, the private key is mathematically calculated from the factors of the modulus which is part of the public key. The public key is broadcasted everytime you visit a secure website site so being able to factor the public key and get the private key would allow someone to falsify website credentials and even decrypt all communication to the site.