-
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.