Intro to cryptography, so this is what we ended our week on.
What is cryptography?
That's a good question, cryptography can be viewed as the
practice or study of secure communication.
That's basically what cryptography is.
The idea is that I want to send secure messages to somebody that I
possibly know or don't know. So for example,
if I want to talk to a bank.
I might not necessarily know who I'm talking to
in the bank or exactly, you know,
who's on the other end, but I do know that it's the bank
that I'm trying to communicate with, okay?
And they communicate… or the bank knows me but doesn't really know me,
you know, I mean they don't know that I want to communicate.
So there has to be some way that I can tell the bank, “Hey I'm ready to talk now,”
and then we can try to talk, okay?
So you can imagine like a phone call,
but of course we were in the digital age, right? We have the internet and things like that, so
you can imagine doing online banking stuff and things like that.
And we talked a little bit about private versus public key cryptography.
So the idea behind private key cryptography is that
a private key is shared between two people.
So the example that we use is
the story of Caesar and the Romans. So Caesar would encrypt
messages using something called the Caesar Cipher,
and he took letters and shifted them by 3.
So for example, a mapped to… what is it?
a is 0 so 1, 2, 3, b, c, d.
So a mapped to d, b mapped to e, c mapped to f and so on and so forth.
And he did the loop around as well.
So for example, x mapped to a, y mapped to b, and z mapped to c.
This worked very well in Rome because well most soldiers were illiterate
so even if it was written in Latin or whatever language they used,
they probably wouldn’t be able to read it anyways,
but then the few soldiers who were literate
still couldn't read it because they shifted the letters by a bit
so they just would, you know, they wouldn't - instead of trying to read the messages,
they would just rip them up and burn them.
They could have gained a lot of information if they knew
how the messages were encrypted.
That's the idea behind private key cryptography, however of course
the problem with this is that you have to somehow exchange
to another person that oh hey this is my private key.
But if I don't really know the other person, like if it's just some big bank,
I can't just, you know…I guess I could from where I am…but
you know, you can imagine this being a very, very long and
arduous procedure to watch to the bank
and be like, “Hi, this is my private key that I'm going to use today,”
then go back home and then try to communicate online. I mean that's kind of…
that's slow,
and if you imagine doing this with like a billion people,
you're storing at least a billion private keys. That's
a lot of keys to keep in mind.
But public key cryptography is the idea that we don't need to do this.
Or at least we can limit how much we do this.
The idea is the padlock analogy. So remember from, let's say high school right,
when you would lock your locker up with a lock.
To lock it is very easy, right? If I gave you an open padlock, you would
put it in your lock and then close it, okay?
So it's very easy to lock a padlock,
but to unlock it, you actually need to know the key.
And that's the idea behind public key cryptography.
You make certain information public,
you make the encryption process public,
but you make the decryption process private.
So let's see the general scheme,
and we'll talk about this a lot more with the RSA
cryptography scheme. So
Alice produces a private key, d, and a public key, e.
The idea is that the public key is for everyone to know, and the private
key is used for decryption and only Alice knows it, okay,
and the idea is that there's some eavesdropper, Eve, that's watching all the communication.
So Eve can see this public key, e. Okay?
I use Eve instead of Oscar. Personal preference by the way.
Now Bob uses this public key, e, to take a message M,
he does something to M with e and encrypts it to get some ciphertext, C.
So let's say my message is “Hello”
and the public key tells me to, I don't know, scramble the letters around,
and so I get my ciphertext
let's say, “OLLEM”
or “OLLEH” let's say.
It doesn't have to be just a rearrangement, it can be like you
changed letters, like we did in the cipher or the Caesar Cipher,
I'm trying to give you an example.
Bob then sends C over an insecure channel to Alice.
So again, Eve can see C, so Eve sees e and Eve sees C.
Then Alice decrypts C to M using d. So the idea is that
the eavesdropper doesn't know d, so they can't - and hopefully decrypting -
finding M from just C and e is actually difficult.
That's the hope here.
What are the key important facts to this? Encryption and decryption are inverses to each other.
So Bob is trying to send a message to Alice,
so Bob takes some message, encrypts it, sends it to Alice.
You need to decrypt it to get back to the message, M, that Bob had.
They must be inverses.
If Alice decrypts it and gets some message that's not M, that's a problem,
okay, so encryption, decryption must be inverses.
d and e are different numbers. It would be silly if
your public key was the same as your private key, then everyone could decrypt it.
Only d is secret, okay?
So only your private key is secret.
So we'll see how to actually do this using modular arithmetic with RSA.
But for now, just kind of keep the general framework
in mind of public key cryptography and when we see RSA in next week's video,
it'll give you a little bit of context.
Last thing I want to talk about is the Square and Multiply Algorithm.
Compute 5 to the 99 mod 101.
So if you haven't seen this, this is actually somewhat of an optional topic in Math 135.
At least it was when when I taught it in
the year 2015-2016.
This could be different now.
Compute 5 to the 99 mod 101.
So the first thing I'd like you to do is actually try this. Try to compute 5 to the the 99,
and if you haven't seen the Square and Multiply Algorithm, let me give you just the baseline of it
or what's going to happen.
What we're going to do is we're going to compute 5 to the powers of 2.
So we're going to compute 5 to the 1, 5 squared, 5 to the 4,
5 to the 8, 5 to the 16, 5 to the 32, and 5 to the 64.
Once we do that, we're going to write 99 in binary,
so we're going to write 99 as a sum of powers of 2.
Once you write 99 as a sum of powers of 2, we're going to combine those two pieces of information
together and get a result
for 5 to the 99 mod 101.
Pause the video, give it a shot.
Once you're done, or hopefully you've at least tried the problem,
let's take a look at the answer.
So as promised, we're going to compute successive powers of 5.
So we're going to square them, this is the squaring part of “square and multiply”.
So 5, 5 squared, then 5 squared squared, right,
that's 5 to the 4, 25 squared.
5 to the 4 squared, that's 5 to the 8. So we're going to take the 19 and square it.
It's going to give us 58…apparently.
These numbers are big so you probably want to use a calculator,
I guess I should have mentioned that.
5 to the 8 squared, 5 to the 16, that's 58 squared, that's the same as 31.
5 to the 16 squared, that's 5 to the 32, that’s 31 squared, that’s 52,
and 5 to the 64 is 52 squared, that’s 78, okay?
Yeah so I mean, a calculator here is important.
Why am I saying to use a calculator?
The reason why I want us to use a calculator is because
because this is actually used when you have like, let's say for example,
well 101 happens to be prime, but if you have non prime moduli,
this is actually how you can compute very large powers very quickly.
You don't need to do too many operations.
Naively, you would have to do 5 to the 99 operations,
and you'd have to mod by 101 each time so the numbers don't get too big.
What the Square and Multiply Algorithm is doing
is it's actually saying hey instead of doing this operation 5 to the 99 times,
let's be a little bit clever and split this up into powers of 2,
and then pick the correct powers of 2 to multiply together.
So if you look right now, how many operations have we done?
I'd say 1, 2, 3, 4, 5, 6, 7 mod 101…
let's ballpark it at 14 operations.
Then now what we're going to do is we're going to write 99 as a sum of powers of 2,
so in binary. So if you don't know how to write things in binary, I suggest googling this.
But the main idea is taking 99,
finding the highest power of 2 less than it,
subtracting it from that number, and then repeating that process.
So the highest power of 2 less than 99 is 64, so 99 is 64 plus…
and then subtract off that 64 power and find the highest power left in
35, that's 32.
Subtract 32 from 35, that's 3. Highest power left is 2.
Subtract 2 from 3 is 1, subtract 1.
So we have 2 to the 6, plus 2 to the 5, plus 2 to the 1, plus 2 to the 0 equals 99.
So now if I look at 5 to the 99, well 5 to the 99,
just by this operation here, is 5 to the 64, times 5 to the 32, times
5 squared times 1.
But we know all of these numbers. We know 5 to the 64,
we know 5 to the 32, we know 5 squared, and we know 5.
So if we multiply all those numbers together, we see that we get 81 mod 11.
So this binary operation thing, let's say it adds another 3 or 4 operations,
and let's say this 5 to the 99 thing, we have
3 more multiplications, one more reduction maybe,
say about 20 operations.
Normally the number of operations would be, like I said right,
99 let's say times 2, be a little bit, you know…
rounding error, let's say about 200 computations
and we turned that to about 20 computations, okay?
So we're saving by a factor of 10, that's a lot, okay?
So naively, it would take
I believe linear amount of time, and
using the Square and Multiply Algorithm takes logarithmic amount of time.
So huge savings in the time that it takes to compute these things.
This is important because we use the Square and Multiply Algorithm in RSA.
It'll turn out that computing
number exponents, or numeric
exponentiation, is actually an important operation in RSA
and we want that operation to be quick.
So that is…that's why we have this.
Okay, I think that's all I have to say for today.
Thank you very much for listening to Week 8 and good luck in your studies.