Well I thought it would be fun to talk
about the problem of playing poker over
the- over mail or over the phone. You know, deck
of cards, we can shuffle them. And I want
to deal you five cards, I want to deal me
five cards;
that all works nice and fine for face to
face, like we are now - how do we do this
over the mail? You know if I'm going to
put them in envelopes and mail them to
you know, obviously I might just peek.
I might just switch the hands here
because you've got ace high and I've got
king high and, you know, we'll do it this way.
- (Brady: You wouldn't cheat like that, would you?)
I might I might. You want to put
cards in envelopes and ship them around
and have a fair deal. And that's a model
for what we can do over the Internet.
That after we see what happens with
postal mail we can try to see can we do
the same thing over the internet. Yeah
how are we gonna do this? So somehow you
need to choose five cards, I need to
choose five cards. Your five cards have
to be different than my five cards. You
shouldn't know what my five cards are; I
shouldn't know what your five cards are.
So we're going to add at least a little
bit of pseudo-cryptography here that is
locks. We're gonna mail you all the cards.
So I'm gonna take each card and put it
in an envelope, but you're not going to
be able to see them because I'm going to
put a lock on each one. So that you can
receive these envelopes in some random
order the way the post office delivers
them. And you get an envelope that looks
like this, with your name on it of course.
It's got a card in it, you can't see what
the card is. And we'll do that 52 times.
So I'll put a card - there's the five of
clubs, put that in an envelope,
lock it up, there we go. Okay, locked up. I'll keep
the key, and there's your second card.
I've got the key to all of them so we're
gonna have 52 of these. In random order,
you have no idea what card is in which
envelope, and they're all shuffled by
this whole process of getting them to
you in locked
envelopes like this. And so you've got 52
envelopes, or boxes; each with one card in
it; they're all shuffled you don't know
the order and you're not gonna open them -
you can't open them actually because you
don't have the key to these locks. So the
next thing we're going to do is you're
going to ship them all back to me with
an additional lock on each one. So you're
gonna put a lock on the other corner of
the envelopes here and then they'll be
double locked and I'll get all the
envelopes back in random order
each doubly locked. So let's do that. Yeah
these locks are just like the original
ones, except that you have the key
instead of me having the key. So you've
got the key now, you can unlock all these
second locks, and we've got them here.
These are different colors so we know
these are Brady locks as opposed to Ron
locks. You putting black
on the envelopes - should be clear these
are your hands not my hands doing the
work here. - (Brady: These are mine, these are mine.)
I like these problems, these are good. So
at this stage we're at a very interesting
situation. We've got all the envelopes
sent to you with a lock on them, in this
case the silver locks that I know how to
unlock. And now you've taken the envelopes,
shuffled them up, and put your own locks
on each one - one black lock per envelope
as you see here. And you have the keys
for the black locks, I have the keys for
the silver locks; and all of these get
mailed back to me in some random order.
52 envelopes, each doubly locked, well
shuffled and I can open half the locks, you
can open half the locks. Nobody can get
to the cards on their own. It takes both
of us to fully open one of these
envelopes. So let's go to the next step. I
want to give you the card that's in this
envelope, without me knowing what it is. I
don't know what it is now, in order for
you to see it we have to take both locks
off. So I can take my lock - works fine.
Now we have an envelope with just your
lock on it, and I can mail that back to
you. I don't know what the card is. You
receive this in the mail and you know
that's one of your cards for your hand
of poker. And I'll do that five times. So
I'll take my keys and I'll unlock five
of these envelopes, removing my lock from
five of them with the lock on and there we
go. And now you've got all five of your
cards; I have not seen these cards.
Whenever I have my hand on these cards
they've been locked with your lock. - (Brady: Alright let me do it.)
(Let me see what I got. D'you wanna be cameraman?) - Sure
- (Okay, here's my first one.) - First one, good. Don't tell me.
(Brady: Awh yeh I don't want you to know do I?)
(But I'll show the people at home.)
(Alright let's see what else I've got)
You've got your hand and the next thing we've got
to do is give me my hand and I've got 47
cards doubly locked. I pick five of them
out of a pile; here's the first one,
here's the second one. Each of them has
two locks on it, so I can't open them, you
can't open them fully. But I'm gonna take
them, those are my five that I've chosen for
my hand. I'm gonna mail them back to you.
So I put them in the post, stamped for
speedy delivery. - (Brady: This is the professor's)
(hand but I can't see what it is cos he's)
(still- it's still got his lock on it. So)
(I'm allowing him to see his hand without)
(me getting to see it.)
(So I'll take my looks off. So here's the)
(professor's hand.) - Please mail it back to
me. - (Here you go.) - So I got my hand and
they're locked with locks that I can
open. Let's see what I got; and then we'll
see who won. The last card- I've opened up
all five envelopes and I got a hand-
almost a flush even. But I got ace, king
and you've got Queen, Jack. Ten, nine - if
you had an eight you would've had a streak.
(Brady: Yeah, if only.)
What we achieved was playing
poker over the mail. We dealt the cards
out in a way that you never saw what
cards I had, I never saw what cards you
had; until we finally opened them up but
individually then we could disclose them.
Or maybe we'll have a round of betting
first. And you can see that, yeah I've won
and it was a fair game, right? Even though
we played it over the mail, and you'd think
it might be impossible to play poker
over the mail - how do you deal the cards?
In fact you can deal the cards as long
as you have locks that only I can open,
and locks that only you can open. This is
an interesting example of what we might
call a cryptographic protocol. We want to
do something over the internet, it's got
certain properties you want to achieve;
and I think a poker game is is
emblematic of lots of other things you
might want to have happen with bidding
or other kinds of things on the Internet.
Here we needed to have some special
properties, what we call commutativity. The
fact that you could put your lock on and
then I could put my lock on and then you
can take your lock off and then I can
take my lock off. It's kind of unusual in
mathematics where you're sort of applying
one function then applying another
function then undoing the first function
and then undoing the second function. So
these operations of locking and
unlocking actually commute with each
other. So, we can do the same thing with a
bit of math and make playing poker over
the Internet feasible then. So we need
some function that represents locking. So
a card is no longer a physical card, it's
some kind of bit string or number that
represents that card. I can still write
it maybe as queen of spades - there we
go there's a queen spades. So that's a bit
string or character string that
represents that card. We want to somehow
encrypt that to give us the equivalent
of adding a lock to it. So we got a lock
here we want- what what does it mean to
put a lock on that bit string?
Well I'm gonna apply some function. We
can imagine just taking it to some power k.
So k is a number I know
so k is my key. And I'll remember that
and I'll take that bit string and I'll
raise it to a power,
maybe modulo some prime or something.
These are big numbers, these P might be
100 digits, it might- you know, like
that. So and K could also be a very large
number. So these are numbers you can't
guess, you can't know. We can agree on P
but you don't know k. That's just like an
envelope with one lock on it. Take the
number that represents the Queen of
Spades and raise that to the kth power and
k is a big number here, so raising a
number to a big power is itself an
interesting operation. Turns out to be
something that's one of the most
important operations in cryptography. And
it's something you can do efficiently. So
even if k is a 100 digit number or
200 digit number we can do this very
quickly. Taking the remainder mod P at
every step, and ending up with a result
which is just Q to that kth power modulo P.
So remainder after dividing by P. That's
what- this is the computer representation
of it, this is the- what we had for the demo
with an envelope. That's the first
encryption. We've done that just by
raising to a power and dividing the
results by P, taking the remainder. So now
we want to raise have the other party,
encrypt it again; and that's raising to
another power. So we can take Q to the k
and raise that to some new power J mod P.
So the other party knows another
secret key. So J is Brady's key. So you've
taken that, you've raised it to the Jth
power. - (Brady: So I've taken the big confusing)
(number you've sent me-?) - Yeah, you've taken
that. Raised that to the Jth power, divided
by P, taking the remainder. And so this is
the result we have. The nice thing about
this is, you know, we can take the locks
off in either order here. We can actually
take these exponents off in either order
as well after I get this result. This is
equal to, by the laws of exponents; Q to
the J to the k mod P. Fully equivalent,
they're mathematically identical. k can
be on the inside or could be on the
outside. J times k is the same as k
times J - commutativity of multiplication
gives us exactly what we need here. So
now we've got this. So you've sent me back a
doubly locked value. Queen- Queen to the k
to the J. And so now I want to take the,
my key, off so I can mail you back your
hard. So I can just multiply by k inverse
in the exponent - Q to the J to the k
raised to the power k inverse. So k
inverse we have to compute in a way that
I can explain later, but it really is
just the multiplicative inverse of k
when we're dealing in the exponents like
this. And so k times k inverse cancels
and we get this is equal to Q to the J
mod P, which is to say the k lock has been
taken off. So
how we take off the first lock and the J
lock remains. The k lock has been taken
off. And now you can do the same thing. To
remove your lock Q to the J to the J
inverse. There's a value - is J inverse
up in the exponent. We take the remainder
mod P and that's just equal to Q; because
J times J inverse is 1. So mod P. So this
is this and you could get your card
Queen of Spades. So this is an example of
what you might call a cryptographic
protocol.
So it's an example where I have some
information, you have some information, we
want to share information. There might be
some complicated rules for how we share
information, who gets to know what when.
That's exactly the kind of thing we have
here. That happens all the time. For
example, it might be an auction. We want
to bid for an oil field or something
like that and cryptographic protocols do
get used for these kinds of things where
we're bidding, you have to commit to a
value and then later you have to reveal
the value. So it's very much like we saw
here where we lock things and later
unlock them and so on. So, so that's
another example. Various kinds of
economic transactions happen all the
time like this.
I think auctions are maybe the most
interesting example. - (Brady: Seems like it would be)
(a hard thing for the computers to do, these)
(huge calculations) - Yeah so there's a
trick here, which is called repeated
squaring and it's a wonderful trick. It
allows raising to large powers to be
done efficiently. And computers are doing
this all the time, especially in
cryptography. Let's take an example. So
suppose you want to raise Q to the 11th
power. So 11 is not a big number
particularly, but let's take that as an
example. So that's just Q times Q to
the 5th squared, right? Cos Q to the 5th,
squared, the 2 times 5 is 10; times another
Q that gives us 11 Qs so that gives us
Q to the 11th. What I've done here is
I've taken the problem, doing two
operations - one a squaring operation and
a multiplication. I've reduced the
problem to something of sort of half the
size. So instead of having to worry about
computing Q to the 11th I'm now worried
about computing Q to the 5th. So I
compute Q to the fifth first, I square that,
and I multiply by Q and I get Q to the
11th. And Q to the 5th, how do we
get that? Well that's just Q times Q
squared, squared. And Q squared
it's just Q times Q. So by building a
chain like this, increasing by a power-
factor of two every time we can build up
very large numbers quickly. The number of
squarings and multiplications you do is
just equal to the bit length of the
exponent. So if you had a hundred bit
exponent you're essentially
doing 100 squarings and hundred
multiplications. [Preview] ...with a proper attack;
big computers - it will still take them
thousands of years to factorise that
number into its original prime numbers.
Now hidden in the details for this code...