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.
Latest Answers