0:00:00.000,0:00:04.262
Now that we've seen a few examples of[br]historic ciphers, all of which are badly

0:00:04.262,0:00:07.130
broken, we're going to switch gears and[br]talk about ciphers that are much better

0:00:10.122,0:00:13.115
designed. But before we do that, I want to,[br]first of all, define more precisely what a

0:00:13.115,0:00:17.432
cipher is. So first of all, a cipher is[br]actually, remember a cipher is made up of

0:00:17.432,0:00:21.694
two algorithms. There's an encryption[br]algorithm and a decryption algorithm. But

0:00:21.694,0:00:26.012
in fact, a cipher is defined over a[br]triple. So the set of all possible keys,

0:00:26.012,0:00:31.292
which I'm going to denote by script K, and[br]sometimes I'll call this the key space,

0:00:31.292,0:00:35.968
it's the set of all possible keys. There's[br]this set of all possible messages and this

0:00:35.968,0:00:40.365
set of all possible ciphertexts. Okay, so[br]this triple in some sense defines the

0:00:40.365,0:00:44.756
environment over which the cipher is[br]defined. And then the cipher itself is a

0:00:44.756,0:00:49.236
pair of efficient algorithms E and D. E is[br]the encryption algorithm; D is the

0:00:49.236,0:00:57.762
decryption algorithm. Of course, E takes[br]keys and messages. And outputs ciphertexts.

0:00:57.762,0:01:06.770
And the decryption algorithm takes[br]keys and ciphertexts. Then outputs messages.

0:01:06.770,0:01:12.282
And the only requirements is that these[br]algorithms are consistent. They satisfy

0:01:12.282,0:01:17.933
what's called the correctness property. So[br]for every message in the message space.

0:01:17.933,0:01:23.593
And every key. In the key space, it had[br]better be the case that if I encrypt the

0:01:23.593,0:01:29.185
message with the key K and then I decrypt[br]using the same key K I had better get back

0:01:29.185,0:01:34.711
the original message that I started with.[br]So this equation here is what's called the

0:01:34.711,0:01:39.974
consistency equation and every cipher has[br]to satisfy it in order to be a cipher

0:01:39.974,0:01:44.970
otherwise it's not possible to decrypt.[br]One thing I wanted to point out is that I

0:01:44.970,0:01:49.782
put the word efficient here in quotes. And[br]the reason I do that is because efficient

0:01:49.782,0:01:54.041
means different things to different[br]people. If you're more inclined towards

0:01:54.041,0:01:58.811
theory, efficient means runs in polynomial[br]time. So algorithms E and D have to run in

0:01:58.811,0:02:02.842
polynomial time in the size of their[br]inputs. If you're more practically

0:02:02.842,0:02:07.045
inclined, efficient means runs within a[br]certain time period. So for example,

0:02:07.045,0:02:11.474
algorithm E might be required to take[br]under a minute to encrypt a gigabyte of

0:02:11.474,0:02:16.073
data. Now either way, the word efficient[br]kind of captures both notions and you can

0:02:16.073,0:02:20.158
interpret it in your head whichever way[br]you'd like. I'm just going to keep

0:02:20.158,0:02:24.139
referring to it as efficient and put[br]quotes in it as I said if you're theory

0:02:24.189,0:02:27.964
inclined think of it as polynomial time,[br]otherwise think of it as

0:02:27.964,0:02:32.100
concrete time constraints. Another comment[br]I want to make is in fact algorithm E.

0:02:32.100,0:02:36.455
It's often a randomized algorithm. What[br]that means is that as your encrypting

0:02:36.455,0:02:40.981
messages, algorithm E is gonna generate[br]random bits for itself, and it's going to

0:02:40.981,0:02:45.676
use those random bits to actually encrypt[br]the messages that are given to it. On the

0:02:45.676,0:02:50.258
other hand the decrypting algorithm is[br]always deterministic. In other words given

0:02:50.258,0:02:54.558
the key and the ciphertext output is[br]always the same. Doesn't depend on any

0:02:54.558,0:02:58.970
randomness that's used by the algorithm.[br]Okay, so now that we understand what a

0:02:58.970,0:03:03.552
cipher is better, I want to kind of show[br]you the first example of a secure cipher.

0:03:03.552,0:03:08.364
It's called a one time pad It was designed[br]by Vernam back at the beginning of the

0:03:08.364,0:03:12.724
twentieth century. Before I actually[br]explain what the cipher is, let's just

0:03:12.724,0:03:17.383
state it in the terminology that we've[br]just seen. So the message space for the

0:03:17.383,0:03:22.221
Vernam cipher for the one-time pad is the[br]same as the ciphertext space which is

0:03:22.221,0:03:27.653
just the set of all ended binary strings.[br]This, this just means all sequences of

0:03:27.653,0:03:33.854
bits, of zero one characters. The key[br]space is basically the same as the message

0:03:33.854,0:03:40.134
space which is again simply the embed of[br]all binary strings. So a key in the one

0:03:40.134,0:03:46.290
time pad is simply a random big string,[br]it's a random sequence of bits. That's as

0:03:46.290,0:03:51.508
long as the message to be encrypted, as[br]long as the message. Okay, now that we've

0:03:51.508,0:03:56.726
specified kind of what's the cipher's[br]defined over we can actually specify how

0:03:56.726,0:04:02.010
the cipher works and it's actually really[br]simple. So essentially the ciphertexts.

0:04:02.010,0:04:07.812
Which is the result of encrypting a[br]message with a particular key, is simply

0:04:07.812,0:04:13.766
the XOR of the two. Simply K XOR M. [inaudible] see a quick example of

0:04:13.766,0:04:20.026
this. Remember that XOR, this plus[br]with a circle. XOR means addition

0:04:20.026,0:04:26.825
modulo two. So if I take a particular[br]message, say, 0110111. And it take a

0:04:26.825,0:04:33.871
particular key, say 1011001. When I[br]compute the encryption of the message

0:04:33.871,0:04:38.838
using this key, all I do is I[br]compute the XOR of these two

0:04:38.838,0:04:43.942
strings. In other words, I do addition[br]module or two bit by bit. So I get one,

0:04:43.942,0:04:48.645
one, zero, one, one, one, zero. That's a[br]ciphertext. And then how do I decrypt? I

0:04:48.645,0:04:52.893
guess they could do kind of the same[br]thing. So they decrypt a cipher text using

0:04:52.893,0:04:57.248
a particular key. What I do is I XOR the[br]key and the ciphertext again. And so all

0:04:57.248,0:05:01.819
we have to verify is that it satisfies the[br]consistency requirements. And I'm going to

0:05:01.819,0:05:06.443
do this slowly once and then from now on[br]I'm going to assume this is all, simple to

0:05:06.443,0:05:10.798
you. So we're gonna make, we're gonna have[br]to make sure that if I decrypt a cipher

0:05:10.798,0:05:14.893
text, that was encrypted using a[br]particular key, I had better get. Back the

0:05:14.893,0:05:20.481
message M. So what happens here? Well,[br]let's see. So if I look at the encryption

0:05:20.481,0:05:25.996
of k and m, this is just k XOR m by[br]definition. What's the decryption of k XOR

0:05:25.996,0:05:31.628
m using k? That's just k XOR (k XOR[br]m). And so since I said that XOR is

0:05:31.628,0:05:36.948
addition modulo two, addition is[br]associative, so this is the same as (k XOR k)

0:05:36.948,0:05:43.007
XOR m, which is simply as you know k XOR k is a zero, and zero XOR anything

0:05:43.007,0:05:49.066
is simply m. Okay, so this actually shows[br]that the one-time pad is in fact a cipher,

0:05:49.066,0:05:54.277
but it doesn't say anything about the[br]security of the cipher. And we'll talk

0:05:54.277,0:05:58.319
about security of the cipher in just a[br]minute. First of all, let me quickly ask

0:05:58.319,0:06:02.205
you a question, just to make sure we're[br]all in sync. Suppose you are given a

0:06:02.205,0:06:06.092
message m and the encryption of that[br]message using the one time pad. So all

0:06:06.092,0:06:10.522
you're given is the message and the cipher[br]text. My question to you is, given this

0:06:10.522,0:06:15.467
pair m and c, can you actually figure out[br]the one-time pad key that was used in the

0:06:15.467,0:06:20.588
creation of c from m?

0:06:20.588,0:06:23.030
So I hope all of you[br]realize that in fact, given the message in

0:06:23.030,0:06:25.473
the cipher text it's very easy to recover[br]what the key is. In particular the key is

0:06:25.473,0:06:30.241
simply M XOR C. Then we'll see that if[br]it's not immediately obvious to you we'll

0:06:30.241,0:06:35.238
see why that's, the case, a little later[br]in the talk, in the lecture. Okay alright

0:06:35.238,0:06:40.198
so the 1-time pad is a really cool from a[br]performance point of view all you're doing

0:06:40.198,0:06:44.656
is you exo-ring the key in the message so[br]it's a super, super fast. Cypher for

0:06:44.656,0:06:48.464
encrypting and decrypting very long[br]messages. Unfortunately it's very

0:06:48.464,0:06:52.768
difficult to use in practice. The reason[br]it's difficult to use is the keys are

0:06:52.768,0:06:56.907
essentially as long as the message. So if[br]Alice and Bob want to communicate

0:06:56.907,0:07:01.321
securely, so you know Alice wants to send[br]a message end to Bob, before she begins

0:07:01.321,0:07:06.011
even sending the first bit of the message,[br]she has to transmit a key to Bob that's as

0:07:06.011,0:07:10.536
long as that message. Well, if she has a[br]way to transmit a secure key to Bob that's

0:07:10.536,0:07:15.061
as long as the message, she might as well[br]use that same mechanism to also transmit

0:07:15.061,0:07:19.439
the message itself. So the fact that the[br]key is as long as the message is quite

0:07:19.439,0:07:23.490
problematic and makes the one-time pad[br]very difficult to use in practice.

0:07:23.490,0:07:28.040
Although we'll see that the idea behind[br]the one-time pad is actually quite useful

0:07:28.040,0:07:32.590
and we'll see that a little bit later. But[br]for now I want to focus a little bit on

0:07:32.590,0:07:36.918
security. So the obvious questions are,[br]you know, why is the one-time pad secure?

0:07:36.918,0:07:41.195
Why is it a good cypher? Then to answer[br]that question, the first thing we have to

0:07:41.195,0:07:45.191
answer is, what is a secure cipher to[br]begin with? What is a, what makes cipher

0:07:45.191,0:07:49.759
secure? Okay, so the study, security of[br]ciphers, we have to talk a little bit

0:07:49.759,0:07:54.962
about information theory. And in fact the[br]first person, to study security of ciphers

0:07:55.150,0:08:00.076
rigorously. Is very famous, you know, the[br]father of information theory, Claude

0:08:00.076,0:08:05.042
Shannon, and he published a famous paper[br]back in 1949 where he analyzes the

0:08:05.042,0:08:10.603
security of the one-time pad. So the idea[br]behind Shannon's definition of security is

0:08:10.603,0:08:15.182
the following. Basically, if all you get[br]to see is the cypher text, then you should

0:08:15.182,0:08:19.379
learn absolutely nothing about the plain[br]text. In other words, the cypher text

0:08:19.379,0:08:23.413
should reveal no information about the[br]plain text. And you see why it took

0:08:23.413,0:08:28.047
someone who invented information theory to[br]come up with this notion because you have

0:08:28.047,0:08:32.517
to formulize, formally explain what does[br]information about the plain text actually

0:08:32.517,0:08:37.653
mean. Okay so that's what Shannon did and[br]so lemme show you Shannon's definition,

0:08:37.653,0:08:42.841
I'll, I'll write it out slowly first. So[br]what Shannon said is you know suppose we

0:08:42.841,0:08:48.029
have a cypher E D that's defined over[br]triple K M and C just as before. So KM and

0:08:48.029,0:08:53.411
C define the key space, the message space[br]and the cypher text space. And when we say

0:08:53.411,0:08:58.404
that the cypher text sorry we say that the[br]cypher has perfect secrecy if the

0:08:58.404,0:09:03.592
following condition holds. It so happens[br]for every two messages M zero and M1 in

0:09:03.592,0:09:08.684
the message space. For every two messages[br]the only requirement I'm gonna put on

0:09:08.684,0:09:13.831
these messages is they have the same[br]length. Yeah so we're only, we'll see why

0:09:13.831,0:09:19.106
this requirement is necessary in just a[br]minute. And for every cyphertext, in the

0:09:19.106,0:09:25.221
cyphertext space. Okay? So for every pair[br]of method messages and for every cipher

0:09:25.221,0:09:31.118
text, it had better be the case that, if I[br]ask, what is the probability that,

0:09:31.357,0:09:37.096
encrypting N zero with K, woops.[br]Encrypting N zero with K gives C, okay? So

0:09:37.096,0:09:43.551
how likely is it, if we pick a random key?[br]How likely is it that when we encrypt N

0:09:43.551,0:09:49.819
zero, we get C. That probability should be[br]the same as when we encrypt N1. Okay, so

0:09:49.819,0:09:54.920
the probability of encrypting n one and[br]getting c is exactly the same as the

0:09:54.920,0:09:59.955
probability of encrypting n zero and[br]getting c. And just as I said where the

0:09:59.955,0:10:04.658
key, the distribution, is over the[br]distribution on the key. So, the key is

0:10:04.658,0:10:10.157
uniform in the key space. So k is uniform[br]in k. And I'm often going to write k arrow

0:10:10.157,0:10:15.390
with a little r above it to denote the[br]fact that k is a random variable that's

0:10:15.390,0:10:20.491
uniformly sampled in the key space k.[br]Okay, this is the main part of Shannon's

0:10:20.491,0:10:25.892
definition. And let's think a little bit[br]about what this definition actually says.

0:10:25.892,0:10:30.965
So what does it mean that these two[br]probabilities are the same? Well, what it

0:10:30.965,0:10:36.304
says is that if I'm an attacker and I[br]intercept a particular cypher text c, then

0:10:36.304,0:10:41.577
in reality, the probability that the[br]cypher text is the encryption of n zero is

0:10:41.577,0:10:46.798
exactly the same as the probability that[br]it's the incryption of n one. Because

0:10:46.798,0:10:52.219
those probabilities are equal. So if I[br]have, all I have the cypher text C that's

0:10:52.219,0:10:57.639
all I have intercepted I have no idea[br]whether the cypher text came from M zero

0:10:57.639,0:11:03.196
or the cypher text came from M one because[br]again the probability of getting C is

0:11:03.196,0:11:08.651
equally likely whether M zero is being[br]encrypted or M one is being encrypted. So

0:11:08.651,0:11:13.286
here, we have the definition stated again.[br]And I just wanna write these properties

0:11:13.286,0:11:17.749
again more precisely. So let's write this[br]again. So what [inaudible] definition

0:11:17.749,0:11:22.326
means is that if I am given a particular[br]cipher text, I can't tell where it came

0:11:22.326,0:11:27.125
from. I can't tell if it's, if the message[br]that was encrypted. Is either N zero or N

0:11:27.125,0:11:32.090
one and in fact, this property is true for[br]all messages. For all these N zero, for

0:11:32.090,0:11:37.117
all N zero and N ones. So not only can I[br]not tell if'c' came from N zero or N one,

0:11:37.117,0:11:42.144
I can't tell if it came from N two or N[br]three or N four or N five because all of

0:11:42.144,0:11:47.109
them are equally likely to produce the[br]cypher text'c'. So what this means really

0:11:47.109,0:11:52.074
is that if you're encrypting messages with[br]a one time pad then in fact the most

0:11:52.074,0:11:56.729
powerful adversary, I don't really care[br]how smart you are, the most powerful

0:11:56.729,0:12:02.530
adversary. Can learn nothing about the[br]plain text, learns nothing about the plain

0:12:02.530,0:12:09.624
text. From the cypher text. So to say it[br]in one more way, basically what this

0:12:09.624,0:12:16.315
proves is that there's no, there's no[br]cypher text-only attack on a cypher that

0:12:16.315,0:12:23.263
has perfect secrecy. Now, cypher attacks[br]actually aren't the only attacks possible.

0:12:23.263,0:12:29.440
And in fact, other attacks may be[br]possible, other attacks may be possible.

0:12:32.160,0:12:36.772
Okay. Now that we understand what perfect[br]secrecy, means, the question is, can we

0:12:36.772,0:12:41.327
build ciphers that actually have perfect[br]secrecy? And it turns out that we don't

0:12:41.327,0:12:45.517
have to look very far, the one time[br]pattern fact has perfect secrecy. So I

0:12:45.517,0:12:50.719
want to prove to you this is Shannon's first[br]results and I wanna prove this fact to

0:12:50.719,0:12:55.858
you, it's very simple proof so let's go[br]ahead and look at it and just do it. So we

0:12:55.858,0:13:01.061
need to kind of interpret what does that[br]mean, what is this probability that E K M

0:13:01.061,0:13:06.200
Z is equal to C. So it's actually not that[br]hard to see that for every message and

0:13:06.200,0:13:11.022
every cyphertext the probability that the[br]encryption of N under a key K the

0:13:11.022,0:13:16.161
probability that, that's equal to C, the[br]probability that our random choice of key

0:13:16.161,0:13:23.720
by definition. All that is, is basically[br]the number of keys. Kay, instruct Kay.

0:13:24.758,0:13:31.533
Such that, well. If I encrypt. And with k[br]I get c. So I literally count the number

0:13:31.533,0:13:37.207
of keys and I divide by the total number[br]of keys. Right? That's what it means, that

0:13:37.207,0:13:42.833
if I choose a random key, that key maps m[br]to c. Right. So it's basically the number

0:13:42.833,0:13:47.707
of key that map n to c divided by the[br]total number of keys. This is its

0:13:47.707,0:13:53.406
probability. So now suppose that we had a[br]cypher such that for all messages and all

0:13:53.406,0:13:58.967
cypher texts, it so happens that if I look[br]at this number, the number of k, k, and k,

0:13:58.967,0:14:04.391
such that e, k, m is equal to c. In other[br]words, I'm looking at the number of keys

0:14:04.391,0:14:09.259
that map m to c. Suppose this number[br]happens to be a constant. So say it

0:14:09.259,0:14:14.079
happens to be two, three, or ten or[br]fifteen. It just hap, happens to be an

0:14:14.079,0:14:19.332
absolute constance. If that's the case,[br]then by definition, for all n0 and n1 and

0:14:19.332,0:14:24.747
for all c, this probability has to be the[br]same because the denominator is the same,

0:14:24.747,0:14:30.097
the numerator is the same, it's just as[br]constant, and therefore the probability is

0:14:30.097,0:14:35.644
always the same for all n and c. And so if[br]this property is true, then the cypher has

0:14:35.644,0:14:43.616
to have, the cypher has perfect secrecy.[br]Okay, so lets see what can we say about

0:14:43.616,0:14:48.804
this quantity for the one time pad. So the[br]sec-, so, the question to you is, if I

0:14:48.804,0:14:54.770
have a message in a cipher-text, how many[br]one time pad keys are there [inaudible]

0:14:54.770,0:15:00.381
map, this message ends, so the [inaudible][br]C? So, in other words, how many keys are

0:15:00.381,0:15:06.101
there, such that M XOR K is equal to C?[br]So I hope you've all answered one. And

0:15:06.101,0:15:12.683
let's see why that's the case. For the one[br]time pad, if we have that, the encryption

0:15:12.683,0:15:18.303
of K of M under K is equal to C. But[br]basically, well, by definition, that

0:15:18.303,0:15:24.885
implies that K XOR M is equal to C. But[br]that also simply says that K has to equal

0:15:24.885,0:15:31.766
to M XOR C. Yes, I just X over both[br]sides by M and I get that K must equal the

0:15:31.766,0:15:37.561
M XOR C. Okay? So what that says is[br]that, for the one time pad, in fact, the

0:15:37.561,0:15:43.707
number of keys, in K, shows the EKM, is[br]equal to C. That simply is one, and this

0:15:43.707,0:15:49.852
holds for all messages in cipher text. And[br]so, again, by what we said before, it just

0:15:49.852,0:15:54.987
says that the one time pad has, perfect[br]secrecy. Perfect secrecy and that

0:15:54.987,0:15:59.093
completes the proof of this [inaudible][br]very, very simple. Very, very simple

0:15:59.093,0:16:03.644
lemma. Now the funny thing is that[br]even though this lemma is so simple to

0:16:03.644,0:16:08.194
prove in fact it proves a pretty powerful[br]statement again. This basically says for

0:16:08.194,0:16:12.328
the one time [inaudible] there is no[br]cypher text only attack. So, unlike the

0:16:12.328,0:16:16.393
substitution cipher, or the vigenere[br]cipher, or the roller machines, all those

0:16:16.393,0:16:20.778
could be broken by ciphertext-only attack.[br]We've just proved that for the one-time

0:16:20.778,0:16:25.110
pad, that's simply impossible. Given the[br]cyphertext, you simply learn nothing about

0:16:25.110,0:16:29.281
the plaintext. However, as we can see,[br]this is simply not the end of the story. I

0:16:29.281,0:16:33.131
mean, are we done? I mean, basically,[br]we're done with the course now, cuz we

0:16:33.131,0:16:37.359
have a way. To encrypt, so that an[br]attacker can't recover anything about our

0:16:37.359,0:16:41.206
method. So maybe we're done with the[br]course. But in fact, as we'll see, there

0:16:41.206,0:16:45.261
are other attacks. And, in fact, the one[br]time pad is actually not such a

0:16:45.261,0:16:49.316
secure cipher. And in fact, there are[br]other attacks that are possible, and we'll

0:16:49.316,0:16:54.075
see that shortly. Okay? I emphasize again[br]the fact that it has perfect secrecy does

0:16:54.075,0:16:58.785
not mean that the one time pad is the[br]secure cypher to use. Okay. But as we said

0:16:58.785,0:17:03.733
the problem with the one time pad is that[br]the secret key is really long. If you had

0:17:03.733,0:17:08.071
a way of. Communicating the secret key[br]over to the other side. You might as well

0:17:08.071,0:17:12.253
use that exact same method to also[br]communicate the message to the other side,

0:17:12.253,0:17:16.652
in which case you wouldn't need a cypher[br]to begin with. Okay? So the problem again

0:17:16.652,0:17:21.105
is the one time pad had really long keys[br]and so the obvious question is are there

0:17:21.105,0:17:25.450
other cyphers that has perfect secrecy and[br]possibly have much, much shorter keys?

0:17:25.450,0:17:30.136
Well, so the bad news is the Shannon,[br]after proving that the one-time pad has

0:17:30.136,0:17:34.945
perfect secrecy, proved another theorem[br]that says that in fact if a cypher has

0:17:34.945,0:17:39.878
perfect secrecy, the number of keys in the[br]cypher must be at least the number of

0:17:39.878,0:17:44.935
messages that the cypher can handle. Okay,[br]so in particular, what this means is if I

0:17:44.935,0:17:51.037
have perfect secrecy. Then necessarily the[br]number of keys, or rather the length of my

0:17:51.037,0:17:56.309
key, must be greater than the length of[br]the message. So, in fact, since the one

0:17:56.309,0:18:00.834
time pad satisfies us with equality, the[br]one time pad is an optimal, cipher that

0:18:00.834,0:18:04.862
has perfect secrecy, okay? So basically,[br]what this shows is that this is an

0:18:04.862,0:18:09.056
interesting notion. The one time pad is an[br]interesting cipher. But, in fact, in

0:18:09.056,0:18:13.360
reality, it's actually quite hard to use.[br]It's hard to use in practice, again,

0:18:13.360,0:18:17.790
because of these long keys. And so this[br]notion of perfect secrecy, even though

0:18:17.790,0:18:21.840
it's quite interesting, basically says[br]that it doesn't really tell us the

0:18:21.840,0:18:26.279
practical cyphers are going to be secure.[br]And we're gonna see, but, as we said, the

0:18:26.279,0:18:30.994
idea behind the one time pad is quite good.[br]And we're gonna see, in the next lecture,

0:18:30.994,0:18:33.547
how to make that into a practical[br]system.