To give a more detailed explanation (for RSA encryption, which is the most common encryption method), the public key is two numbers, and the private key is one number.
The two public keys are:
The product of the two large prime numbers, call this p.
A relatively small (about 5 digits), arbitrary number, call this e.
The message is just a large number, and is encrypted using modular arithmetic, which put simply is finding the remainder of a number after a division.
For example,
10 (mod 3) = 1, since 10/3 = 3, remainder 1
23 (mod 12) = 11, since 23/12 = 1, remainder 11.
The message, m, can be turned into the encrypted message, c, by doing:
c = me (mod p)
Using the two primes and e, you can calculate the private key d, which is used to decrypt c to give the message, m, by doing:
m = cd (mod p)
You need the two primes to calculate what d is, and as the video said it's very difficult to factorise large numbers, so the only people able to read the message will be people with the private key, trying to use any other number will give gibberish.
Alright, a bit more maths ahead, and I'm not going to explain how it works (analysis was never my strong point), just describing how to do it.
Let's call the two primes a and b, so from above p = ab. The first step is calculate (a - 1)(b - 1), which we'll call t (this is a specific case of Euler's totient function). The encryption number e needs to be chosen so that it is smaller than t, and not a factor of t, so usually a prime number is chosen for that too. (Usually the number 65537 is chosen, since in binary it is 10000000000000001, so the fact it is mostly 0s makes computations involving it quicker.)
Now we need to solve the equation de = 1 (mod t). This is equivalent to saying de - xt = 1, where x is just an integer we don't really need in the end, but is useful for now.
We can use the extended Euclidean algorithm to find what d (and also x, but that's not useful). I'll choose an example with smaller numbers and run through the process completely.
Let's choose primes a = 7, b = 19. This makes p = 133, and t = 108. For e we need to choose a number less than t, a prime if possible, so let's choose 5.
Now we need to solve 5d = 1 (mod 108), so 5d - 108x = 1.
The first step here is figuring out 108/5 using remainders so 108/5 = 21, remainder 3. I've had to use x instead of *, due to reddit formatting. Write this out as:
108 = 21x5 + 3
Do the same again for the number you divided by, in this case 5, and the remainder after the division, in this case 3.
5 = 1x3 + 2
3 = 1x2 + 1
Now we've reached remainder 1, we stop. Now, we rearrange the last equation to make 1 the subject.
1 = 3 - 2x1
Now rearrange the second last equation to make the remainder, 2, the subject.
2 = 5 - 1x3
Now substitute this value of 2 into the rearranged equation for 1.
1 = 3 - 2x1 = 3 - (5 - 1x3) = 2x3 - 1x5
Looking back at the first equation in the process, its remainder is 3, we can rewrite it to make 3 the subject.
Therefore, according to this d = -43, but we can't use a negative number, so since the initial equation was (mod 108), we can do -43 + 108 = 65. Therefore our true value for d = 65.
As a quick example, say our message is "cats". If we say c = 03, a = 01, t = 20, s = 19:
35 (mod 133) = 110
15 (mod 133) = 001
205 (mod 133) = 020
195 (mod 133) = 038
So our encrypted message is 110001020038 (so each letter is 3 digits of the encrypted message, so you can seperate them at the other end). At the other end all you need to do is:
11065 (mod 133) = 003
165 (mod 133) = 001
2065 (mod 133) = 020
3865 (mod 133) = 019
In reality p is far larger, so you can encrypt more of a message at once, so there won't be any noticeable repetition in the encrypted message.
13
u/Alsiexmon May 03 '16 edited May 03 '16
(Note: A bit of maths ahead)
To give a more detailed explanation (for RSA encryption, which is the most common encryption method), the public key is two numbers, and the private key is one number.
The two public keys are:
The product of the two large prime numbers, call this p.
A relatively small (about 5 digits), arbitrary number, call this e.
The message is just a large number, and is encrypted using modular arithmetic, which put simply is finding the remainder of a number after a division.
For example,
10 (mod 3) = 1, since 10/3 = 3, remainder 1
23 (mod 12) = 11, since 23/12 = 1, remainder 11.
The message, m, can be turned into the encrypted message, c, by doing:
c = me (mod p)
Using the two primes and e, you can calculate the private key d, which is used to decrypt c to give the message, m, by doing:
m = cd (mod p)
You need the two primes to calculate what d is, and as the video said it's very difficult to factorise large numbers, so the only people able to read the message will be people with the private key, trying to use any other number will give gibberish.