I’m really good at math and I have a decent grasp of computer science. I understand that multiplying two prime numbers to get a huge number is easy, but checking out if a huge number has only two prime factors is a monumental task for a computer. What I don’t get is how this is used for encryption and coding and decoding messages. I keep reading about this in books and they keep talking about how one side is the key or whatever but they never really explained how it all works. Every book seems to love explaining the whole large-numbers-take-a-lot-of-time-to-factorise concept but not how it actually works in encryption. I understand basic message coding–switch around the alphabet, add steps that changes a message into a mess of letters; then the recipient has to do all those steps backwards to change it back. How do prime numbers and huge numbers fit into this? How does knowing a pair of factors enable me to code a message and how does knowing the product enable my recipient to decode it?
Schnutzel: So, this kind of encryption revolves around [modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic). In modular arithmetic, you have some number called the modulus (“M”). Whenever you perform a certain arithmetic operation (such as addition or multiplication), you divide the result by M and keep the remainder. For example if M = 17 then 12 + 9 = 21 = 4 (mod M), because when dividing 21 by 17, the remainder is 4, and similarly 12 * 9 = 108 = 6 (mod M) because the remainder of 108/17 is 6.
Certain operations in modular arithmetic aren’t easily reversible. Normally, if I have two numbers n,y and I want to find the x such that x^n = y, then it’s just a matter of taking the nth root of y to find x. However in modular arithmetic, if I have n,y and modulus M, and I want to find the x such that x^n = y (mod M) then there’s no easy way of doing it – the easiest way is no better than “guessing” different values of x until we find the right one.
It turns out that in modular arithmetic, the operation x^n is reversible if I know the prime factors of n (this is based on [Euler’s theorem](https://en.wikipedia.org/wiki/Euler%27s_theorem)). This means that if I have n,y and M and I know the factors of n, then I can find the x such that x^n = y (mod M). So how do I use this to encrypt a message? I choose a pair of prime numbers p,q, and use them to calculate n=p*q. Then I also choose a large number M > n. So M,n are my public key, and M,p,q are my private key. Now, anyone can take my public key and use it to encrypt a message – they need to convert the message to a number x, and then calculate y = x^n (mod M) and send me the result. Since only I know p,q, only I can calculate the original x from y.
This is basically how the [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) encryption algorithm works. In reality, this system isn’t used directly for encryption because it’s too complicated, however it is used for [key exchanges](https://en.wikipedia.org/wiki/Key_exchange) and [digital signatures](https://en.wikipedia.org/wiki/Digital_signature).
cuby87: ELI5 version: All data is stored as numbers. Using “*” but it’s not a multiplication of course, just to simplify.
1. Alice wants to send 5 to Bob
2. Alice does 5 * BobsPublicKey = 42 and sends 42 to Bob
3. Bob does 42 * BobsPrivateKey = 5
The key idea is to choose a mathimatical operation “*” where:
– BobsPublicKey * BobsSecrectKey is an easy operation, meaning decoding 42 to 5 is easy
– knowing 42 and BobsPublicKey, it would take a huge amount of computer power to find 5.
Not_The_Truthiest: Other’s have answered your specific questions. If you’re interested in more though, I suggest The Code Book by Simon Singh.
Warning – Simon Singh is a very addictive author, and you’ll probably buy Fermat’s Last Theorem and Big Bang pretty soon after. 🙂
Docdan: There’s a lot of different things you can do with large prime numbers (and their product), since they have many interesting properties. The main idea is that you need to find some structural element that says something about the two prime factors of your large number, so that you can use the knowledge of those factors as a key to solving the encryption.
Here is one simple example: If you look at numbers in modulo p (p being a prime number), for example, 7, you will find the following property: When taking the n-th power of every number 1, 2, 3, 4, 5 or 6, it will eventually loop around and return to the original number.
2^2 =4, 2^3 =1, 2^4 =2; 3^2 =2, 3^3 =6, 3^4 =4, 3^5 =5, 3^6 =1, 3^7 =3, etc. (modulo 7)
The important part here is that this means that one step before you loop around, you will reach 1. If you try this out with enough numbers, you will notice that the length of every single loop is either p-1, or a number that divides p-1 (in the case of p=7, this means that all loops are either length 1, 2, 3, or 6). This brings us to the fact that, no matter which prime number “p” you pick, and no matter which number “a” you pick as your base, the following statement is always true: a^(p-1)=1 mod p.
Now, from this, you can also prove a similar statement for the more general case if you don’t have a prime number, but rather the product of two prime numbers N=p*q:
a^(p-1)*(q-1) =1 mod N.
Add 1 more to the exponent, and you will be back at your original a.
And this is the important part for your encryption method. Let a be the message you wish to encrypt. All you have to do is openly give someone a public exponent (known by everyone) and the corresponding N that they should use to encrypt messages towards you. Everyone knows N, but nobody except you knows the factorization p and q. And in order to complete the loop, you can’t use N, you need to know (p-1)*(q-1).
So everyone has access to the tools they need to send you a message, but only you have access to the information needed to loop back to the original message.
Note: I hope I didn’t get anything wrong for the theorems, it’s been a while since I looked into Field Theory, but this is the general idea how these things work. There are many theorems that describe a hidden property of N that depends solely on its prime factors p and q, and any such theorems are potentially useful for cryptography.
bumnut: Any chunk of data handled by a computer is technically just a number. This could be a file on a disk, or a string in a database, or a packet sent over a network, it’s just a sequence of ones and zeros. Interpret that as binary, and you have a number.
The simplest kind of encryption is that you have a secret large prime number. You multiply your data (which is a number) by that secret number, and you get a new “encrypted” number. Since, as you say, multiplying (and dividing) by large primes is easy but factorising is hard, anyone who gets hold of your encrypted number can’t easily factorise it, i.e figure out what the two original numbers were (your secret and your data). But anyone with the secret prime can do a simple division and get the original data out.
In reality, it’s more complicated in ways that i don’t even understand. The algorithms are much more complicated than just multiplying by the secret prime. There’s one way hashes and assymetrical encryption with public and private keys. But to basic principle is that all of your data is a number, multiplying is easy and factorising is hard.
YellowFlowerBluePot: I want to lock my locker. I have a lock, but not one of those spin-it-right, pass 0, spin-it-left kinds of locks. My lock is a sort of combination lock. You know, the ones with the 0-9s on them? I go to the first dial and pick a 0-9, then go to the next dial and pick a 0-9, and so on until I have a combination, something like 2187, that is unique to my lock.
My encryption lock is like this combination lock, but instead of a bunch of 0-9 dials, there are only 2 dials. And on these dials there are prime numbers, so many that you’d need a dial the size of a ferris wheel and numbers printed so small you’d need a magnifying glass to read them.
Now, choosing a combination is easy. I take my magnifying glass and find a number on the ferris wheel. That’s my first prime number, which we call p, and the first number in my combination. I need another number, so I turn the ferris wheel some and use my magnifying glass to find one. This number is my second prime number, called q, and the second number in my combination. I take the lock, set the combination with my p and q, and lock my locker.
I don’t need any more numbers, so I give the ferris wheel a mighty spin and everyone on it mighty motion sickness. I don’t know where my p and q are on the wheel anymore, but I wrote them down so I don’t need to search again. I also multiplied them together to get a third number, which we call n, that someone can use to make another lock just like mine. Just as I finish up, my friend Oiler who plays hockey in Canada walks into the room. Before he can ask how I got a ferris wheel through the door, I hand him a magnifying glass and say “Unlock my lock.”
ELI5ing a topic like encryption is tricky. u/Schnutzel offered a great explanation that dives deeper into the matter. I had fun writing this so I hope you enjoy it and that I didn’t dumb it down too much.