This is a simplified overview of how public-key cryptography works. It is meant to be a supplement to my other article, Asymmetric Encryption, which you might want to read first. What you are about to read involves some high-school-level math. If that's not your thing, feel free to skip this one!
Also note, I'm going to cover specifically how RSA encryption works. This system is slowly being replaced by others, like elliptic curve cryptography, but it's the oldest and still the most popular.
The principle reference for this explanation are my notes from my university discrete mathematics class. I have simplified it a bit, but not by much - turns out this is already pretty easy to get!
There are three mathematical concepts that you need in order to understand how and why this system works: exponentiation, modular arithmetic, and prime numbers.
Exponentiation is simple; it's just the number of times you multiply a number by itself. For example, 23 = 2 * 2 * 2 = 8.
Modular arithmetic is even simpler. It is when you take a number and count up to that number, but reset as you hit another number called the modulus. Loosely, it is the integer remainder after a division.
This is sometimes known as "clock counting", since clocks are a great example of this. In the case of a clock, our modulus is 12. If someone tells you that it's 14 o'clock (or 1400 hours), you know that they mean 2 o'clock, since you counted up to 12, then another 2 hours after that. If, for some strange reason, someone told you it was 26 o'clock, that would also mean 2 o'clock, since you counted up to 12 twice before finally counting another 2 hours.
In many programming languages, the modulo operation is written with a percent sign: 14 % 12 = 2. Mathematicians would say "14 is congruent with 2 mod 12", and write: 14 ≡ 2 (mod 12). Other examples include: 55 ≡ 11 (mod 22), 31 % 4 = 3, and 6 % 91 = 6.
Prime numbers are whole numbers that can only be evenly divided by one or itself. In other words, it has no other factors. Seven is a great prime number - seven is only evenly divisible by 1 and 7. You cannot divide it by 2, 3, 4, 5, or 6 without getting some remainder.
There are an infinite number of prime numbers. Because computers can calculate so quickly, the prime numbers that they use for encryption are very long (hundreds of digits).
The other important thing to know is that every integer has a unique prime factorization. This means that if I take two prime numbers and multiply them together, no other pair (or any combination) of prime numbers will multiply together to get that same product. Multiplying two prime numbers together - even very big ones - is easy and fast. Finding out which prime numbers were multiplied together to result in a given number can be difficult and slow.
Now that we have those concepts down, let's do some cryptography! For this demonstration, I will use really small numbers. Like I mentioned earlier, computers would use numbers that are several hundred digits long.
First, we need three prime numbers, which we will call, \(q_1\), \(q_2\), and \(p\). Other than needing to be prime numbers, the only condition is that \(p \geqslant q_1 q_2\). Also, we define \(n\) to be \(q_1\) times \(q_2\). The process of picking these prime numbers needs its own separate article, so here, I'm just going with prime numbers that look nice. So I will pick
\[ q_1 = 13\\ q_2 = 17\\ p = 223\\ n = q_1 q_2 = 221\]
So far, so good. \(p\) is the public key. The "public lock" is the combination of the numbers \(n\) and \(p\), which in this case is \((221, 223)\). These two numbers are needed to encrypt a message. Right away, I can give these two numbers to my friend or anyone else. They can encrypt a message, but they will not be able to decrypt the message. That will require the private key. Often, the term public key is used interchangeably with public lock.
\[ \text{public lock} = (n, p) = (221, 223)\]
Alright. Getting the private key is a little more complicated. We'll need a number \(r = (q_1 - 1)(q_2 - 1)\). As a side note, the greatest common divisor between \(r\) and \(p\) is 1. In other words, they are "relatively prime", or "co-prime". It's not important to know that here, but it's part of the reason that this whole thing works.
Next, we need a number \(x\) which is a "modular multiplicative inverse" of \(r\) so that \(x r \equiv 1 \pmod{p}\). There's a relatively straightforward algebraic way to calculate it (see the extended euclidean algorithm on wikipedia), but I just stuck the numbers into wolfram|alpha. \(x = 187\).
Now we need \(a = -x \pmod{p}\), which is \(a = -187 \pmod{223} = 36\).
Finally, we need a \(b\), where \(b p = a r + 1\). This is simple: \(b = \frac{a r + 1}{p} = \frac{36 (192) + 1}{223} = 31\).
\(b\) is the private key.
Let's suppose our message \(M\) is "7". This could have been the letter "g" encoded into "7" (since we always use numbers) - doesn't matter. What's important is that the message is smaller than \(n\), and since in our demonstration we're using really small numbers, my message has to be small as well. If a message is bigger than \(n\), then you could break the message into chunks and encrypt each chunk separately.
To encrypt a message \(M\) into a ciphertext - which we'll call "m-hat", \(\hat{M}\) - simply set \(M\) to the power of \(p\), and mod it by \(n\). Recall that the two numbers, \((n, p)\) is the "public lock" (or "public key"), and that's all that the sender has.
\[ \hat{M} = M^p \pmod{n}\]
In our example, the ciphertext will be \(\hat{M} = 7^{223} \pmod{221} = 175\). So the sender will send "175" to the receiver.
Decrypting is just as simple, but uses the private key, \(b\), instead.
\[ M = \hat{M}^b \pmod{n}\]
The receiver plugs the numbers in, and gets the original message back: \(M = 175^{31} \pmod{221} = 7\).
Let's try with another message - this time, "9".
\[ M = 9\\ \hat{M} = M^p \pmod{n} = 9^{223} \pmod{221} = 87\]
\[ \hat{M} = 87\\ M = \hat{M}^b \pmod{n} = 87^{31} \pmod{221} = 9\]
Awesome. Asymmetric Encryption.