1 00:00:00,000 --> 00:00:03,800 Intro to cryptography, so this is 
what we ended our week on. 2 00:00:03,800 --> 00:00:06,700 What is cryptography? 3 00:00:06,700 --> 00:00:09,700 That's a good question, 
cryptography can be viewed as the 4 00:00:09,700 --> 00:00:13,066 practice or study of secure communication. 5 00:00:13,066 --> 00:00:16,000 That's basically what cryptography is. 6 00:00:16,000 --> 00:00:19,166 The idea is that I want to send 
secure messages to somebody that I 7 00:00:19,166 --> 00:00:22,766 possibly know or don't 
know. So for example, 8 00:00:22,766 --> 00:00:24,266 if I want to talk to a bank. 9 00:00:24,266 --> 00:00:27,700 I might not necessarily 
know who I'm talking to 10 00:00:27,700 --> 00:00:30,266 in the bank or exactly, you know, 11 00:00:30,266 --> 00:00:32,966 who's on the other end, but 
I do know that it's the bank 12 00:00:32,966 --> 00:00:34,933 that I'm trying to communicate with, okay? 13 00:00:34,933 --> 00:00:39,233 And they communicate… or the bank 
knows me but doesn't really know me, 14 00:00:39,233 --> 00:00:41,500 you know, I mean they don't know 
that I want to communicate. 15 00:00:41,500 --> 00:00:44,533 So there has to be some way that I can 
tell the bank, “Hey I'm ready to talk now,” 16 00:00:44,533 --> 00:00:46,633 and then we can try to talk, okay? 17 00:00:46,633 --> 00:00:47,233 18 00:00:47,233 --> 00:00:49,000 So you can imagine 
like a phone call, 19 00:00:49,000 --> 00:00:52,566 but of course we were in the digital age, right? 
We have the internet and things like that, so 20 00:00:52,566 --> 00:00:55,533 you can imagine doing online 
banking stuff and things like that. 21 00:00:55,533 --> 00:00:56,866 22 00:00:56,866 --> 00:01:00,000 And we talked a little bit about private 
versus public key cryptography. 23 00:01:00,000 --> 00:01:02,333 So the idea behind private key cryptography is that 24 00:01:02,333 --> 00:01:04,166 a private key is shared 
between two people. 25 00:01:04,166 --> 00:01:07,500 So the example that we use is 26 00:01:07,500 --> 00:01:10,966 the story of Caesar and the 
Romans. So Caesar would encrypt 27 00:01:10,966 --> 00:01:13,633 messages using something 
called the Caesar Cipher, 28 00:01:13,633 --> 00:01:16,366 and he took letters 
and shifted them by 3. 29 00:01:16,366 --> 00:01:17,900 30 00:01:17,900 --> 00:01:21,100 So for example, a mapped to… what is it? 31 00:01:21,100 --> 00:01:24,000 a is 0 so 1, 2, 3, b, c, d. 32 00:01:24,000 --> 00:01:28,333 So a mapped to d, b mapped to e, 
c mapped to f and so on and so forth. 33 00:01:28,333 --> 00:01:30,400 And he did the loop around as well. 34 00:01:30,400 --> 00:01:34,333 So for example, x mapped to a, y mapped to b, and z mapped to c. 35 00:01:34,333 --> 00:01:35,266 36 00:01:35,266 --> 00:01:38,566 This worked very well in Rome because 
well most soldiers were illiterate 37 00:01:38,566 --> 00:01:41,866 so even if it was written in Latin or 
whatever language they used, 38 00:01:41,866 --> 00:01:44,000 they probably wouldn’t be able to read it anyways, 39 00:01:44,000 --> 00:01:46,166 but then the few 
soldiers who were literate 40 00:01:46,166 --> 00:01:48,800 still couldn't read it because 
they shifted the letters by a bit 41 00:01:48,800 --> 00:01:51,900 so they just would, you know, they wouldn't - 
instead of trying to read the messages, 42 00:01:51,900 --> 00:01:53,700 they would just rip them up and burn them. 43 00:01:53,700 --> 00:01:56,266 They could have gained a lot 
of information if they knew 44 00:01:56,266 --> 00:01:59,133 how the messages 
were encrypted. 45 00:01:59,133 --> 00:02:00,400 46 00:02:00,400 --> 00:02:03,733 That's the idea behind private key cryptography, however of course 47 00:02:03,733 --> 00:02:05,866 the problem with this is that you 
have to somehow exchange 48 00:02:05,866 --> 00:02:09,133 to another person that oh 
hey this is my private key. 49 00:02:09,133 --> 00:02:11,900 But if I don't really know the other 
person, like if it's just some big bank, 50 00:02:11,900 --> 00:02:15,400 I can't just, you know…I guess 
I could from where I am…but 51 00:02:15,400 --> 00:02:18,333 you know, you can imagine this being a very, very long and 52 00:02:18,333 --> 00:02:20,233 arduous procedure to watch to the bank 53 00:02:20,233 --> 00:02:22,833 and be like, “Hi, this is my private 
key that I'm going to use today,” 54 00:02:22,833 --> 00:02:26,266 then go back home and then try to 
communicate online. I mean that's kind of… 55 00:02:26,266 --> 00:02:27,500 that's slow, 56 00:02:27,500 --> 00:02:29,733 and if you imagine doing 
this with like a billion people, 57 00:02:29,733 --> 00:02:32,133 you're storing at least a 
billion private keys. That's 58 00:02:32,133 --> 00:02:34,433 a lot of keys to keep in mind. 59 00:02:34,433 --> 00:02:36,366 60 00:02:36,366 --> 00:02:39,900 But public key cryptography is the 
idea that we don't need to do this. 61 00:02:39,900 --> 00:02:40,933 62 00:02:40,933 --> 00:02:43,566 Or at least we can limit 
how much we do this. 63 00:02:43,566 --> 00:02:46,933 The idea is the padlock analogy. So 
remember from, let's say high school right, 64 00:02:46,933 --> 00:02:49,200 when you would lock your locker up with a lock. 65 00:02:49,200 --> 00:02:50,266 66 00:02:50,266 --> 00:02:53,133 To lock it is very easy, right? If I gave 
you an open padlock, you would 67 00:02:53,133 --> 00:02:56,000 put it in your lock and 
then close it, okay? 68 00:02:56,000 --> 00:02:58,366 So it's very easy to lock a padlock, 69 00:02:58,366 --> 00:03:00,800 but to unlock it, you actually need to know the key. 70 00:03:00,800 --> 00:03:01,700 71 00:03:01,700 --> 00:03:04,633 And that's the idea behind 
public key cryptography. 72 00:03:04,633 --> 00:03:06,666 You make certain information public, 73 00:03:06,666 --> 00:03:09,066 you make the encryption process public, 74 00:03:09,066 --> 00:03:12,000 but you make the 
decryption process private. 75 00:03:12,000 --> 00:03:13,800 76 00:03:13,800 --> 00:03:16,000 So let's see the general scheme, 77 00:03:16,000 --> 00:03:18,900 and we'll talk about this 
a lot more with the RSA 78 00:03:18,900 --> 00:03:20,666 cryptography scheme. So 79 00:03:20,666 --> 00:03:24,000 Alice produces a private 
key, d, and a public key, e. 80 00:03:24,000 --> 00:03:26,266 The idea is that the public key is for everyone to know, and the private 81 00:03:26,266 --> 00:03:29,233 key is used for decryption 
and only Alice knows it, okay, 82 00:03:29,233 --> 00:03:31,066 83 00:03:31,066 --> 00:03:34,733 and the idea is that there's some eavesdropper, 
Eve, that's watching all the communication. 84 00:03:34,733 --> 00:03:37,566 So Eve can see this 
public key, e. Okay? 85 00:03:37,566 --> 00:03:38,866 86 00:03:38,866 --> 00:03:42,200 I use Eve instead of Oscar. 
Personal preference by the way. 87 00:03:42,200 --> 00:03:44,833 Now Bob uses this public key, e, to take a message M, 88 00:03:44,833 --> 00:03:49,133 he does something to M with e and 
encrypts it to get some ciphertext, C. 89 00:03:49,133 --> 00:03:52,500 So let's say my message is “Hello” 90 00:03:52,500 --> 00:03:56,433 and the public key tells me to, I don't 
know, scramble the letters around, 91 00:03:56,433 --> 00:03:58,700 and so I get my ciphertext 92 00:03:58,700 --> 00:04:00,400 let's say, “OLLEM” 93 00:04:00,400 --> 00:04:03,433 or “OLLEH” let's say. 94 00:04:03,433 --> 00:04:05,466 It doesn't have to be just a 
rearrangement, it can be like you 95 00:04:05,466 --> 00:04:08,466 changed letters, like we did in 
the cipher or the Caesar Cipher, 96 00:04:08,466 --> 00:04:09,433 97 00:04:09,433 --> 00:04:11,833 I'm trying to give you an example. 98 00:04:11,833 --> 00:04:14,366 Bob then sends C over an 
insecure channel to Alice. 99 00:04:14,366 --> 00:04:17,766 So again, Eve can see C, so 
Eve sees e and Eve sees C. 100 00:04:17,766 --> 00:04:19,400 101 00:04:19,400 --> 00:04:23,100 Then Alice decrypts C to M 
using d. So the idea is that 102 00:04:23,100 --> 00:04:26,733 the eavesdropper doesn't know d, 
so they can't - and hopefully decrypting - 103 00:04:26,733 --> 00:04:29,733 finding M from just C and 
e is actually difficult. 104 00:04:29,733 --> 00:04:31,566 That's the hope here. 105 00:04:31,566 --> 00:04:32,700 106 00:04:32,700 --> 00:04:36,533 What are the key important facts to this? Encryption 
and decryption are inverses to each other. 107 00:04:36,533 --> 00:04:39,266 So Bob is trying to 
send a message to Alice, 108 00:04:39,266 --> 00:04:42,766 so Bob takes some message, 
encrypts it, sends it to Alice. 109 00:04:42,766 --> 00:04:46,600 You need to decrypt it to get back 
to the message, M, that Bob had. 110 00:04:46,600 --> 00:04:48,300 They must be inverses. 111 00:04:48,300 --> 00:04:51,600 If Alice decrypts it and gets some 
message that's not M, that's a problem, 112 00:04:51,600 --> 00:04:54,300 okay, so encryption, decryption must be inverses. 113 00:04:54,300 --> 00:04:56,800 d and e are different 
numbers. It would be silly if 114 00:04:56,800 --> 00:05:01,066 your public key was the same as your 
private key, then everyone could decrypt it. 115 00:05:01,066 --> 00:05:03,400 Only d is secret, okay? 116 00:05:03,400 --> 00:05:05,166 So only your private key is secret. 117 00:05:05,166 --> 00:05:06,300 118 00:05:06,300 --> 00:05:10,100 So we'll see how to actually do this 
using modular arithmetic with RSA. 119 00:05:10,100 --> 00:05:10,900 120 00:05:10,900 --> 00:05:13,433 But for now, just kind of 
keep the general framework 121 00:05:13,433 --> 00:05:16,900 in mind of public key cryptography and when we see RSA in next week's video, 122 00:05:16,900 --> 00:05:18,900 it'll give you a little bit of context. 123 00:05:18,900 --> 00:05:19,966 124 00:05:19,966 --> 00:05:22,900 Last thing I want to talk about is the Square and Multiply Algorithm. 125 00:05:22,900 --> 00:05:25,366 Compute 5 to the 99 mod 101. 126 00:05:25,366 --> 00:05:29,333 So if you haven't seen this, this is actually somewhat of an optional topic in Math 135. 127 00:05:29,333 --> 00:05:30,100 128 00:05:30,100 --> 00:05:32,233 At least it was when 
when I taught it in 129 00:05:32,233 --> 00:05:34,900 the year 2015-2016. 130 00:05:34,900 --> 00:05:36,533 This could be different now. 131 00:05:36,533 --> 00:05:37,233 132 00:05:37,233 --> 00:05:39,633 Compute 5 to the 99 mod 101. 133 00:05:39,633 --> 00:05:43,466 So the first thing I'd like you to do is actually 
try this. Try to compute 5 to the the 99, 134 00:05:43,466 --> 00:05:46,500 and if you haven't seen the Square and Multiply 
Algorithm, let me give you just the baseline of it 135 00:05:46,500 --> 00:05:48,766 or what's going to happen. 136 00:05:48,766 --> 00:05:52,000 What we're going to do is we're going 
to compute 5 to the powers of 2. 137 00:05:52,000 --> 00:05:54,633 So we're going to compute 5 
to the 1, 5 squared, 5 to the 4, 138 00:05:54,633 --> 00:05:58,433 5 to the 8, 5 to the 16, 5 
to the 32, and 5 to the 64. 139 00:05:58,433 --> 00:05:59,266 140 00:05:59,266 --> 00:06:02,000 Once we do that, we're 
going to write 99 in binary, 141 00:06:02,000 --> 00:06:05,000 so we're going to write 99 
as a sum of powers of 2. 142 00:06:05,000 --> 00:06:06,700 143 00:06:06,700 --> 00:06:10,200 Once you write 99 as a sum of powers of 2, we're 
going to combine those two pieces of information 144 00:06:10,200 --> 00:06:12,366 together and get a result 145 00:06:12,366 --> 00:06:14,400 for 5 to the 99 mod 101. 146 00:06:14,400 --> 00:06:15,166 147 00:06:15,166 --> 00:06:17,266 Pause the video, give it a shot. 148 00:06:17,266 --> 00:06:17,833 149 00:06:17,833 --> 00:06:21,400 Once you're done, or hopefully you've at least tried the problem, 150 00:06:21,400 --> 00:06:22,466 151 00:06:22,466 --> 00:06:24,466 let's take a look at the answer. 152 00:06:24,466 --> 00:06:25,100 153 00:06:25,100 --> 00:06:28,233 So as promised, we're going to 
compute successive powers of 5. 154 00:06:28,233 --> 00:06:31,033 So we're going to square them, this is 
the squaring part of “square and multiply”. 155 00:06:31,033 --> 00:06:34,233 So 5, 5 squared, then 5 
squared squared, right, 156 00:06:34,233 --> 00:06:37,566 that's 5 to the 4, 25 squared. 157 00:06:37,566 --> 00:06:42,333 5 to the 4 squared, that's 5 to the 8. So we're going to take the 19 and square it. 158 00:06:42,333 --> 00:06:44,766 It's going to give us 58…apparently. 159 00:06:44,766 --> 00:06:47,100 These numbers are big so you 
probably want to use a calculator, 160 00:06:47,100 --> 00:06:49,066 I guess I should have mentioned that. 161 00:06:49,066 --> 00:06:54,633 5 to the 8 squared, 5 to the 16, that's 
58 squared, that's the same as 31. 162 00:06:54,633 --> 00:06:58,500 5 to the 16 squared, that's 5 to the 
32, that’s 31 squared, that’s 52, 163 00:06:58,500 --> 00:07:02,066 and 5 to the 64 is 52 squared, that’s 78, okay? 164 00:07:02,066 --> 00:07:03,500 165 00:07:03,500 --> 00:07:04,400 166 00:07:04,400 --> 00:07:06,333 Yeah so I mean, a 
calculator here is important. 167 00:07:06,333 --> 00:07:08,800 Why am I saying to use a calculator? 168 00:07:08,800 --> 00:07:09,833 169 00:07:09,833 --> 00:07:11,766 The reason why I want us to use a calculator is because 170 00:07:11,766 --> 00:07:13,800 because this is actually used when 
you have like, let's say for example, 171 00:07:13,800 --> 00:07:16,500 well 101 happens to be prime, but if you have non prime moduli, 172 00:07:16,500 --> 00:07:19,200 this is actually how you can compute very large powers very quickly. 173 00:07:19,200 --> 00:07:21,166 You don't need to do 
too many operations. 174 00:07:21,166 --> 00:07:24,666 Naively, you would have to 
do 5 to the 99 operations, 175 00:07:24,666 --> 00:07:28,433 and you'd have to mod by 101 each 
time so the numbers don't get too big. 176 00:07:28,433 --> 00:07:30,600 What the Square and Multiply Algorithm is doing 177 00:07:30,600 --> 00:07:33,800 is it's actually saying hey instead of 
doing this operation 5 to the 99 times, 178 00:07:33,800 --> 00:07:36,866 let's be a little bit clever and 
split this up into powers of 2, 179 00:07:36,866 --> 00:07:39,066 and then pick the correct powers 
of 2 to multiply together. 180 00:07:39,066 --> 00:07:41,733 So if you look right now, how many operations have we done? 181 00:07:41,733 --> 00:07:45,100 I'd say 1, 2, 3, 4, 5, 6, 7 mod 101… 182 00:07:45,100 --> 00:07:48,000 let's ballpark it at 14 operations. 183 00:07:48,000 --> 00:07:49,700 184 00:07:49,700 --> 00:07:53,266 Then now what we're going to do is we're 
going to write 99 as a sum of powers of 2, 185 00:07:53,266 --> 00:07:57,200 so in binary. So if you don't know how to 
write things in binary, I suggest googling this. 186 00:07:57,200 --> 00:07:59,466 But the main idea is taking 99, 187 00:07:59,466 --> 00:08:01,733 finding the highest power of 2 less than it, 188 00:08:01,733 --> 00:08:04,400 subtracting it from that number, 
and then repeating that process. 189 00:08:04,400 --> 00:08:08,333 So the highest power of 2 less than 99 is 64, so 99 is 64 plus… 190 00:08:08,333 --> 00:08:12,233 and then subtract off that 64 power 
and find the highest power left in 191 00:08:12,233 --> 00:08:14,000 35, that's 32. 192 00:08:14,000 --> 00:08:17,633 Subtract 32 from 35, that's 
3. Highest power left is 2. 193 00:08:17,633 --> 00:08:20,800 Subtract 2 from 3 is 1, subtract 1. 194 00:08:20,800 --> 00:08:22,033 195 00:08:22,033 --> 00:08:25,900 So we have 2 to the 6, plus 2 to the 5, 
plus 2 to the 1, plus 2 to the 0 equals 99. 196 00:08:25,900 --> 00:08:28,866 So now if I look at 5 to 
the 99, well 5 to the 99, 197 00:08:28,866 --> 00:08:32,766 just by this operation here, is 5 to 
the 64, times 5 to the 32, times 198 00:08:32,766 --> 00:08:34,200 5 squared times 1. 199 00:08:34,200 --> 00:08:36,700 But we know all of these numbers. We know 5 to the 64, 200 00:08:36,700 --> 00:08:41,000 we know 5 to the 32, we know 
5 squared, and we know 5. 201 00:08:41,000 --> 00:08:44,966 So if we multiply all those numbers together, we see that we get 81 mod 11. 202 00:08:44,966 --> 00:08:45,833 203 00:08:45,833 --> 00:08:50,000 So this binary operation thing, let's 
say it adds another 3 or 4 operations, 204 00:08:50,000 --> 00:08:52,533 and let's say this 5 to 
the 99 thing, we have 205 00:08:52,533 --> 00:08:56,233 3 more multiplications, one
more reduction maybe, 206 00:08:56,233 --> 00:08:58,133 say about 20 operations. 207 00:08:58,133 --> 00:08:59,200 208 00:08:59,200 --> 00:09:01,600 Normally the number of operations 
would be, like I said right, 209 00:09:01,600 --> 00:09:05,300 99 let's say times 2, be 
a little bit, you know… 210 00:09:05,300 --> 00:09:07,466 rounding error, let's say 
about 200 computations 211 00:09:07,466 --> 00:09:09,866 and we turned that to about 20 computations, okay? 212 00:09:09,866 --> 00:09:12,700 So we're saving by a factor 
of 10, that's a lot, okay? 213 00:09:12,700 --> 00:09:14,600 So naively, it would take 214 00:09:14,600 --> 00:09:16,500 I believe linear amount of time, and 215 00:09:16,500 --> 00:09:19,266 using the Square and Multiply Algorithm takes logarithmic amount of time. 216 00:09:19,266 --> 00:09:23,200 So huge savings in the time that 
it takes to compute these things. 217 00:09:23,200 --> 00:09:23,766 218 00:09:23,766 --> 00:09:28,866 This is important because we use the 
Square and Multiply Algorithm in RSA. 219 00:09:28,866 --> 00:09:32,000 It'll turn out that computing 220 00:09:32,000 --> 00:09:35,400 number exponents, or numeric 221 00:09:35,400 --> 00:09:36,033 222 00:09:36,033 --> 00:09:39,366 exponentiation, is actually an 
important operation in RSA 223 00:09:39,366 --> 00:09:41,533 and we want that operation to be quick. 224 00:09:41,533 --> 00:09:45,066 So that is…that's why we have this. 225 00:09:45,066 --> 00:09:46,000 226 00:09:46,000 --> 00:09:48,400 Okay, I think that's all I 
have to say for today. 227 00:09:48,400 --> 00:09:51,700 Thank you very much for listening to 
Week 8 and good luck in your studies.