Dealing Cards with Cryptography (with Ron Rivest) - Numberphile

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