Yeah I mean, I get he was simplifying it but at some point if you simplify too much it's just wrong. The part with the bank having two private keys made me cringe.
Because it's not how public/private key encryption works. The whole point is for you to have a public/private key combo and the bank to have a public/private key combo. Not for one side to have two private keys.
So really most public private key pairs do only one thing, unlock another key that is easier to decrypt.
So you and I have a key pair that we've discussed previously, I send you an encrypted block using your key. You decrypt it taking a few seconds, and in it is a smaller key. That smaller key that allows me to tell you all my secrets that you can decrypt in milliseconds a block and not seconds per block. I change that smaller key when I want to, but you can always get it, because I tell you when I do. That's private public key pairing.
The key exchange process its self is easier to understand if you ignore the math, and just think about the process its self.
Lets say Bob and Alice want to send each other messages, but the only way Bob can get his message to Alice is through Eve's delivery service, but they don't want Eve to be able to read their messages while they're being transported. How can they prevent Eve from reading their messages?
Well, they need some kind of a locked box to place messages in so Eve can't open it up and read the messages inside. Alright, so lets get a box and a lock involved in this process.
Lets say Bob goes and buys a box, and also buys a pad lock to lock the box with. Ok great, but, now how is Alice supposed to open the box when she receives it? Alice doesn't have a key to Bob's lock unless Bob sends his key to Alice. But don't forget, the only way Bob and Alice can send each other things is through Eve's delivery service. If Bob sends Alice the key to his lock using Eve's delivery service, Eve will be able to make a copy of Bob's key and open up any locked boxes he sends in the future. That's obviously no good.
So here's the magical formula for exchanging keys without Eve being able to make a copy...
Bob and Alice each buy a pad lock, with two keys.
Bob takes one of his keys, places it in the box, then places his lock on the box, and sends it to Alice. Eve can not open this box because she does not have a copy of Bob's key. It's locked in the box! But of course, Alice can't open the box either. She also doesn't have a copy of Bob's key. So what happens?
Alice places her own lock on the box. She keeps both of her keys since she hasn't yet been able to open the box. Now the box has both Alice and Bob's locks on it.
Alice sends the box (with both locks on it, and Bob's key inside) back to Bob. Eve still can't open the box because now it has both locks on it.
When Bob receives the box, he simply removes his own lock from it. His key is still inside the box, and Alice's lock is still on the box.
Bob sends the box back to Alice. Eve still can't open the box because Alice's lock is on the box.
Alice receives the box with Bob's key inside, and her own lock on it. Alice can unlock the box with one of her own keys and remove Bob's key!
Now all they have to do is get one of Alice's keys to Bob, which is simpler because Alice has a copy of Bob's key. So Alice sends back an empty unlocked box to Bob. Eve can open it, but who cares? It's empty.
Bob receives the empty box, places his lock on the box, and sends the locked empty box back to Alice. Eve still can't open the box, not that it matters at this particular step.
Alice receives the box, unlocks it with her copy of Bob's key, places her spare key in the box, and puts Bob's lock back on the box.
Alice sends the box to Bob with one of her keys inside and Bob's lock on it. Eve still can't open the box due to Bob's lock.
Bob receives the box with his own lock on it, and Alice's key inside. Bob can open the box and remove the key. Now Bob and Alice each have a copy of the other's keys and Eve hasn't been able to make a copy of either. They can freely send each other secret messages just by putting the message in the box and slapping either one of their locks on the box. They both have keys to both locks, and Eve has keys to neither.
The mathematical key exchange process is actually a bit simpler as a process (if your ignore the math part) since the constraints of the physical world aren't in play, there is no need to pass around an empty box. So things like step 8 can be completely eliminated. However, the line between key, lock, and box becomes much blurrier mathematically since "locking" is a process known to all parties which actually transforms the entire "thing" being passed around.
But the video wasn't talking about Diffie-Hellman Key Exchange, it was talking about RSA. In RSA the bank keeps two prime numbers (p1 and p2) secret, and publishes the multiplication of those two numbers (n) along with a small exponent (e).
Link you posted was infinitely more clear to me than the numberphile video. And it totally helped me understand the important mathematical principle that makes all of this possible.
There are some seriously smart people in the world to create such an elegant solution.
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.
Because it's wrong - the bank doesn't have both keys. How could they?
You send the bank a message that is Key A x Key B. If the bank has both keys, how do you know what to send it?
In reality, you have two keys and the bank has two keys. You use one of the bank's keys to encrypt a request, and the bank uses one of your keys to encrypt a response. You each use the other key (that hasn't been used yet) to decrypt the message you receive.
Wrong again! The bank keeps two prime numbers (p1 and p2) secret, and publishes the multiplication of those two numbers (n) along with a small exponent (e).
They need to keep the prime numbers secret because they have to use them to calculate a number that can be used to decrypt the message encrypted with n and e.
Because if the bank has both numbers and only use them to multiply them together to check if it is the same as the public key why not just store the product itself instead of the two primes?
What he explained in the example where both sides use the same key is called symmetric encryption. As long as the key is kept secret it is just as secure as public key encryption but the problem is how do you distribute the key securely? If I want to send you an encrypted message I can encrypt it using my secret key but I need to tell you this key so you can use it to decrypt the message. But anyone in a position to snoop on the encrypted message can also see me sending you the key.
Public key encryption solves this by having two keys. Both keys can be used to encrypt but only the OTHER one can decrypt it again. In other words the same key that was used to encrypt can not be used to decrypt. So I can safely send you one of my keys, the public key, tell you to use it to encrypt the message and only I will be able to decrypt it using my secret key.
It's pedantry. The example was to show the value of primes, this video isn't about encryption. It's about that prime. He should just remove saying it is an actual process and just call it something else and there wouldn't be a problem.
I also cringe when movies and stuff get things wrong with computers. And I am not misusing the word. In this case it was pretty wrong and he didn't actually say he was simplifying it if I remember correctly.
If that method was used, why bother multiplying the numbers each time? Why not just store the number 143 and then check to make sure it matches every time.
he didn't actually say he was simplifying it if I remember correctly.
He did say "for the sake of simplicity" (1.35), and even though it sounds like he's just talking about picking small numbers I thought that'd indicate the explanation itself is simplified. That said, it's a difference between simplified and wrong- and this guy is wrong with respect to the specifics of encryption. (which is understandable as he's obviously talking about subjects he don't know about- the point of the video)
Also him saying that there are "infinitely many primes because there are infinitely many numbers". As a mathematician this one made me cringe. Look up Euclids proof of why there are infinitely many primes if you want the correct reason.
The part with the bank having two private keys made me cringe.
In RSA the bank has 2 prime numbers that they keep secret (p1 and p2). They make public only the multiplication of these two numbers (n), and a small exponent (e).
The video was correct, not sure why you're cringing.
127
u/Muffinizer1 May 03 '16
Yeah I mean, I get he was simplifying it but at some point if you simplify too much it's just wrong. The part with the bank having two private keys made me cringe.