CS 100 (Learn) — CS 100 (Web) — Module 11
NOTE: If your internet access is restricted and you do not have access to YouTube, we have provided alternate video links.
Note: This video transcript has been slightly modified. Corrections are marked with strikethrough, and alternative wording has been placed in [square brackets] to correct some of the awkward or confusing phrasing in the videos.
In this video we are going to explore what we call "key exchange" between two computers on the internet.
If you recall our problem is: I want to send a secret number to my friend on the internet without someone in the middle intercepting what that message is.
To do this, we are going to need a little bit of mathematics, and the mathematics we are going to explore is something called a one-way function.
A one-way function is really easy to do in one direction, but very hard to do in another direction.
A real world example might be scrambling an egg: it is really easy to break an egg and scramble it... it is really hard to take that egg, unscramble it and put it back in its egg shell.
We want something like that in the world of computers.
I am going to do a little bit of high school math review. Hopefully you are aware of a thing called factoring. It may [have been] a while since you have done this, but the idea is to take a look at a number like 14 and break it up into say two numbers that when multiplied together become 14.
There is a certain type of number called a prime number which cannot be factored.
It cannot be broken up into two other numbers other than one and itself.
There are no two whole numbers that can be multiplied together to get seven, other than one and seven.
These are all the prime numbers that are between one and a hundred.
[For] our first one-way function, I am going to take two prime numbers, multiply them together and get the result.
I am going to give you the result and you have to try to figure out what the original two prime numbers [were].
This particular example is pretty easy: if I give you 14, you can figure it out that it is 2 times 7.
Let's make it a little bit harder: I am going to give you the number 589. I will let you even pause this video and go back and look at all the two-digit primes [from] a couple of slides ago... and see if you can determine which of those two multiplied together will become 589.
I will give you a second right now...
Did you figure it out? 19 times 31.
Now you might think to yourself... well this must be easy for a computer... [it] can just try all the possible combinations.
You are right, but the problem is that computers do not scale up very well. If I give you a really large number and I tell you it is two eight digit primes multiplied together it will take you a very very long time, but it will still take a computer a pretty good amount [of time] of because there is no simple trick to be able to figure this out. The computer has to try to brute-force it.
If I make the number really really really big then even all of the world's computers running for a hundred years will not be able to figure it out.
(In case you are curious, those two prime numbers [on the screen] multiplied together will become that really big number [on the screen]).
This is our example of a one-way function that a computer can use.
I am actually going to introduce one more one-way function.
For the next one-way function, we are going to have to do something called modulo arithmetic, or as you may know it, simply "remainders"
If I take the number 1337 and divide by 10, what I end up with is 133 but I also have 7 remainder. That 7 remainder is actually the number we are really interested in.
The way we write that in computer speak is 1337 mod 10 is 7.
We are only interested in the remainder, so if I take the same number and do modulo 100 then you can see the result is going to be 37.
In practice we are going to be wanting to work with prime numbers again, so if I take 1337 mod 17 we are going to end up with the number 11.
The way the one-way function works is: I am going to tell you that 3 raised to some number that is less than or equal to 17 divided by 17 is going to have a remainder of 2.
You have to try to figure out what that mystery number is.
Just like working with prime numbers, this is actually very difficult for a computer to do.
It is really easy to do one way but really hard to do another way.
3 to the 14 is a fairly big number (4782969), now I divide that by 17 and then I find out the remainder is 2.
A couple things are going on here: we are going to have a base (the three), we are going to have the modulo (17), and then we are going to raise 3 to some power, in this case 14.
Just like with the prime numbers we are not going to be dealing with very small numbers like 3 and 17... we might be doing something like this: 19 raised to some power mod 86606119 is going to have this big number [on the screen].
What we are going to do is transmit that final number. It is going to be really hard to deduce that the original number (that we raised 19 to the power of) is.
In this case, it was the number 12345.
Let's see how we can actually defeat our evildoer on the internet using this technique.
We are going to give out some public information. We are going to tell the whole world (including the evildoer) that what we are going to exchange information.
Raising 3 to some number (let's call it X) and then dividing by 17 and getting the remainder.
[My] destination and the evildoer can fully know that this is the system we are going to use.
Then, me and the recipient both pick a random number less than 17 and we will do it completely at random. I choose 7 and my destination picks 15.
We are the only people who know these numbers... I do not know that he picked 15, and he does not know that I picked 7.
No one will know that information (our evildoer cannot know that information).
Next, we are going to do the calculation that I mentioned before: I will raise 3 to 7 mod 17 and that turns out to be 11. The destination will take 3 to the 15 mod 17 and that number is 6.
We are going to freely transmit our two special numbers 11 and 6: note that our two special numbers (7 and 15) are actually still hidden, but we have now given out the public information that my number is now 11 and his number is now 6.
What can we do with that information?
It turns out with a bit of a trick of arithmetic, if I take their number 6 and then raise that to the special number 7 that I picked I will get a new number 14.
If the destination does the exact same thing... so they take my special number 11, raise it to their secret number 15, and do the same process, we both end up with the exact same number.
The math is fairly straightforward, but we do not need to go into it any more than we need to.
The key here is that we both come up with this secret number 14 that the evildoer has no way of knowing, even though the entire world can know that we did 3 to the X mod 17 my number was 11 his number was 6... no one (unless they have a supercomputer) can determine what the actual secret number of 14 is going to be except me and the destination.
Now we have our secret number (14) we can now use that to encrypt our messages and no one in the middle can actually intercept what we are doing, even though they have all the information needed to perform the calculation.
This method is known as key exchange and we will explore in our next video why they are called keys.