Now that we've seen a few examples of historic ciphers, all of which are badly
broken, we're going to switch gears and talk about ciphers that are much better
designed. But before we do that, I want to, first of all, define more precisely what a
cipher is. So first of all, a cipher is actually, remember a cipher is made up of
two algorithms. There's an encryption algorithm and a decryption algorithm. But
in fact, a cipher is defined over a triple. So the set of all possible keys,
which I'm going to denote by script K, and sometimes I'll call this the key space,
it's the set of all possible keys. There's this set of all possible messages and this
set of all possible ciphertexts. Okay, so this triple in some sense defines the
environment over which the cipher is defined. And then the cipher itself is a
pair of efficient algorithms E and D. E is the encryption algorithm; D is the
decryption algorithm. Of course, E takes keys and messages. And outputs ciphertexts.
And the decryption algorithm takes keys and ciphertexts. Then outputs messages.
And the only requirements is that these algorithms are consistent. They satisfy
what's called the correctness property. So for every message in the message space.
And every key. In the key space, it had better be the case that if I encrypt the
message with the key K and then I decrypt using the same key K I had better get back
the original message that I started with. So this equation here is what's called the
consistency equation and every cipher has to satisfy it in order to be a cipher
otherwise it's not possible to decrypt. One thing I wanted to point out is that I
put the word efficient here in quotes. And the reason I do that is because efficient
means different things to different people. If you're more inclined towards
theory, efficient means runs in polynomial time. So algorithms E and D have to run in
polynomial time in the size of their inputs. If you're more practically
inclined, efficient means runs within a certain time period. So for example,
algorithm E might be required to take under a minute to encrypt a gigabyte of
data. Now either way, the word efficient kind of captures both notions and you can
interpret it in your head whichever way you'd like. I'm just going to keep
referring to it as efficient and put quotes in it as I said if you're theory
inclined think of it as polynomial time, otherwise think of it as
concrete time constraints. Another comment I want to make is in fact algorithm E.
It's often a randomized algorithm. What that means is that as your encrypting
messages, algorithm E is gonna generate random bits for itself, and it's going to
use those random bits to actually encrypt the messages that are given to it. On the
other hand the decrypting algorithm is always deterministic. In other words given
the key and the ciphertext output is always the same. Doesn't depend on any
randomness that's used by the algorithm. Okay, so now that we understand what a
cipher is better, I want to kind of show you the first example of a secure cipher.
It's called a one time pad It was designed by Vernam back at the beginning of the
twentieth century. Before I actually explain what the cipher is, let's just
state it in the terminology that we've just seen. So the message space for the
Vernam cipher for the one-time pad is the same as the ciphertext space which is
just the set of all ended binary strings. This, this just means all sequences of
bits, of zero one characters. The key space is basically the same as the message
space which is again simply the embed of all binary strings. So a key in the one
time pad is simply a random big string, it's a random sequence of bits. That's as
long as the message to be encrypted, as long as the message. Okay, now that we've
specified kind of what's the cipher's defined over we can actually specify how
the cipher works and it's actually really simple. So essentially the ciphertexts.
Which is the result of encrypting a message with a particular key, is simply
the XOR of the two. Simply K XOR M. [inaudible] see a quick example of
this. Remember that XOR, this plus with a circle. XOR means addition
modulo two. So if I take a particular message, say, 0110111. And it take a
particular key, say 1011001. When I compute the encryption of the message
using this key, all I do is I compute the XOR of these two
strings. In other words, I do addition module or two bit by bit. So I get one,
one, zero, one, one, one, zero. That's a ciphertext. And then how do I decrypt? I
guess they could do kind of the same thing. So they decrypt a cipher text using
a particular key. What I do is I XOR the key and the ciphertext again. And so all
we have to verify is that it satisfies the consistency requirements. And I'm going to
do this slowly once and then from now on I'm going to assume this is all, simple to
you. So we're gonna make, we're gonna have to make sure that if I decrypt a cipher
text, that was encrypted using a particular key, I had better get. Back the
message M. So what happens here? Well, let's see. So if I look at the encryption
of k and m, this is just k XOR m by definition. What's the decryption of k XOR
m using k? That's just k XOR (k XOR m). And so since I said that XOR is
addition modulo two, addition is associative, so this is the same as (k XOR k)
XOR m, which is simply as you know k XOR k is a zero, and zero XOR anything
is simply m. Okay, so this actually shows that the one-time pad is in fact a cipher,
but it doesn't say anything about the security of the cipher. And we'll talk
about security of the cipher in just a minute. First of all, let me quickly ask
you a question, just to make sure we're all in sync. Suppose you are given a
message m and the encryption of that message using the one time pad. So all
you're given is the message and the cipher text. My question to you is, given this
pair m and c, can you actually figure out the one-time pad key that was used in the
creation of c from m?
So I hope all of you realize that in fact, given the message in
the cipher text it's very easy to recover what the key is. In particular the key is
simply M XOR C. Then we'll see that if it's not immediately obvious to you we'll
see why that's, the case, a little later in the talk, in the lecture. Okay alright
so the 1-time pad is a really cool from a performance point of view all you're doing
is you exo-ring the key in the message so it's a super, super fast. Cypher for
encrypting and decrypting very long messages. Unfortunately it's very
difficult to use in practice. The reason it's difficult to use is the keys are
essentially as long as the message. So if Alice and Bob want to communicate
securely, so you know Alice wants to send a message end to Bob, before she begins
even sending the first bit of the message, she has to transmit a key to Bob that's as
long as that message. Well, if she has a way to transmit a secure key to Bob that's
as long as the message, she might as well use that same mechanism to also transmit
the message itself. So the fact that the key is as long as the message is quite
problematic and makes the one-time pad very difficult to use in practice.
Although we'll see that the idea behind the one-time pad is actually quite useful
and we'll see that a little bit later. But for now I want to focus a little bit on
security. So the obvious questions are, you know, why is the one-time pad secure?
Why is it a good cypher? Then to answer that question, the first thing we have to
answer is, what is a secure cipher to begin with? What is a, what makes cipher
secure? Okay, so the study, security of ciphers, we have to talk a little bit
about information theory. And in fact the first person, to study security of ciphers
rigorously. Is very famous, you know, the father of information theory, Claude
Shannon, and he published a famous paper back in 1949 where he analyzes the
security of the one-time pad. So the idea behind Shannon's definition of security is
the following. Basically, if all you get to see is the cypher text, then you should
learn absolutely nothing about the plain text. In other words, the cypher text
should reveal no information about the plain text. And you see why it took
someone who invented information theory to come up with this notion because you have
to formulize, formally explain what does information about the plain text actually
mean. Okay so that's what Shannon did and so lemme show you Shannon's definition,
I'll, I'll write it out slowly first. So what Shannon said is you know suppose we
have a cypher E D that's defined over triple K M and C just as before. So KM and
C define the key space, the message space and the cypher text space. And when we say
that the cypher text sorry we say that the cypher has perfect secrecy if the
following condition holds. It so happens for every two messages M zero and M1 in
the message space. For every two messages the only requirement I'm gonna put on
these messages is they have the same length. Yeah so we're only, we'll see why
this requirement is necessary in just a minute. And for every cyphertext, in the
cyphertext space. Okay? So for every pair of method messages and for every cipher
text, it had better be the case that, if I ask, what is the probability that,
encrypting N zero with K, woops. Encrypting N zero with K gives C, okay? So
how likely is it, if we pick a random key? How likely is it that when we encrypt N
zero, we get C. That probability should be the same as when we encrypt N1. Okay, so
the probability of encrypting n one and getting c is exactly the same as the
probability of encrypting n zero and getting c. And just as I said where the
key, the distribution, is over the distribution on the key. So, the key is
uniform in the key space. So k is uniform in k. And I'm often going to write k arrow
with a little r above it to denote the fact that k is a random variable that's
uniformly sampled in the key space k. Okay, this is the main part of Shannon's
definition. And let's think a little bit about what this definition actually says.
So what does it mean that these two probabilities are the same? Well, what it
says is that if I'm an attacker and I intercept a particular cypher text c, then
in reality, the probability that the cypher text is the encryption of n zero is
exactly the same as the probability that it's the incryption of n one. Because
those probabilities are equal. So if I have, all I have the cypher text C that's
all I have intercepted I have no idea whether the cypher text came from M zero
or the cypher text came from M one because again the probability of getting C is
equally likely whether M zero is being encrypted or M one is being encrypted. So
here, we have the definition stated again. And I just wanna write these properties
again more precisely. So let's write this again. So what [inaudible] definition
means is that if I am given a particular cipher text, I can't tell where it came
from. I can't tell if it's, if the message that was encrypted. Is either N zero or N
one and in fact, this property is true for all messages. For all these N zero, for
all N zero and N ones. So not only can I not tell if'c' came from N zero or N one,
I can't tell if it came from N two or N three or N four or N five because all of
them are equally likely to produce the cypher text'c'. So what this means really
is that if you're encrypting messages with a one time pad then in fact the most
powerful adversary, I don't really care how smart you are, the most powerful
adversary. Can learn nothing about the plain text, learns nothing about the plain
text. From the cypher text. So to say it in one more way, basically what this
proves is that there's no, there's no cypher text-only attack on a cypher that
has perfect secrecy. Now, cypher attacks actually aren't the only attacks possible.
And in fact, other attacks may be possible, other attacks may be possible.
Okay. Now that we understand what perfect secrecy, means, the question is, can we
build ciphers that actually have perfect secrecy? And it turns out that we don't
have to look very far, the one time pattern fact has perfect secrecy. So I
want to prove to you this is Shannon's first results and I wanna prove this fact to
you, it's very simple proof so let's go ahead and look at it and just do it. So we
need to kind of interpret what does that mean, what is this probability that E K M
Z is equal to C. So it's actually not that hard to see that for every message and
every cyphertext the probability that the encryption of N under a key K the
probability that, that's equal to C, the probability that our random choice of key
by definition. All that is, is basically the number of keys. Kay, instruct Kay.
Such that, well. If I encrypt. And with k I get c. So I literally count the number
of keys and I divide by the total number of keys. Right? That's what it means, that
if I choose a random key, that key maps m to c. Right. So it's basically the number
of key that map n to c divided by the total number of keys. This is its
probability. So now suppose that we had a cypher such that for all messages and all
cypher texts, it so happens that if I look at this number, the number of k, k, and k,
such that e, k, m is equal to c. In other words, I'm looking at the number of keys
that map m to c. Suppose this number happens to be a constant. So say it
happens to be two, three, or ten or fifteen. It just hap, happens to be an
absolute constance. If that's the case, then by definition, for all n0 and n1 and
for all c, this probability has to be the same because the denominator is the same,
the numerator is the same, it's just as constant, and therefore the probability is
always the same for all n and c. And so if this property is true, then the cypher has
to have, the cypher has perfect secrecy. Okay, so lets see what can we say about
this quantity for the one time pad. So the sec-, so, the question to you is, if I
have a message in a cipher-text, how many one time pad keys are there [inaudible]
map, this message ends, so the [inaudible] C? So, in other words, how many keys are
there, such that M XOR K is equal to C? So I hope you've all answered one. And
let's see why that's the case. For the one time pad, if we have that, the encryption
of K of M under K is equal to C. But basically, well, by definition, that
implies that K XOR M is equal to C. But that also simply says that K has to equal
to M XOR C. Yes, I just X over both sides by M and I get that K must equal the
M XOR C. Okay? So what that says is that, for the one time pad, in fact, the
number of keys, in K, shows the EKM, is equal to C. That simply is one, and this
holds for all messages in cipher text. And so, again, by what we said before, it just
says that the one time pad has, perfect secrecy. Perfect secrecy and that
completes the proof of this [inaudible] very, very simple. Very, very simple
lemma. Now the funny thing is that even though this lemma is so simple to
prove in fact it proves a pretty powerful statement again. This basically says for
the one time [inaudible] there is no cypher text only attack. So, unlike the
substitution cipher, or the vigenere cipher, or the roller machines, all those
could be broken by ciphertext-only attack. We've just proved that for the one-time
pad, that's simply impossible. Given the cyphertext, you simply learn nothing about
the plaintext. However, as we can see, this is simply not the end of the story. I
mean, are we done? I mean, basically, we're done with the course now, cuz we
have a way. To encrypt, so that an attacker can't recover anything about our
method. So maybe we're done with the course. But in fact, as we'll see, there
are other attacks. And, in fact, the one time pad is actually not such a
secure cipher. And in fact, there are other attacks that are possible, and we'll
see that shortly. Okay? I emphasize again the fact that it has perfect secrecy does
not mean that the one time pad is the secure cypher to use. Okay. But as we said
the problem with the one time pad is that the secret key is really long. If you had
a way of. Communicating the secret key over to the other side. You might as well
use that exact same method to also communicate the message to the other side,
in which case you wouldn't need a cypher to begin with. Okay? So the problem again
is the one time pad had really long keys and so the obvious question is are there
other cyphers that has perfect secrecy and possibly have much, much shorter keys?
Well, so the bad news is the Shannon, after proving that the one-time pad has
perfect secrecy, proved another theorem that says that in fact if a cypher has
perfect secrecy, the number of keys in the cypher must be at least the number of
messages that the cypher can handle. Okay, so in particular, what this means is if I
have perfect secrecy. Then necessarily the number of keys, or rather the length of my
key, must be greater than the length of the message. So, in fact, since the one
time pad satisfies us with equality, the one time pad is an optimal, cipher that
has perfect secrecy, okay? So basically, what this shows is that this is an
interesting notion. The one time pad is an interesting cipher. But, in fact, in
reality, it's actually quite hard to use. It's hard to use in practice, again,
because of these long keys. And so this notion of perfect secrecy, even though
it's quite interesting, basically says that it doesn't really tell us the
practical cyphers are going to be secure. And we're gonna see, but, as we said, the
idea behind the one time pad is quite good. And we're gonna see, in the next lecture,
how to make that into a practical system.