# 22. Cryptography: Encryption

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=9TNI2wHmaeI
**Transcript page:** https://www.withtranscript.ai/video/9TNI2wHmaeI

## Chapters

- 0:00 — Chapter 1 (0:00)
- 5:37 — Chapter 2 (5:37)
- 11:46 — Chapter 3 (11:46)
- 16:21 — Chapter 4 (16:21)
- 21:18 — Chapter 5 (21:18)
- 24:34 — Chapter 6 (24:34)
- 33:01 — Chapter 7 (33:01)
- 42:47 — Chapter 8 (42:47)
- 45:50 — Chapter 9 (45:50)
- 48:42 — Chapter 10 (48:42)
- 50:21 — Chapter 11 (50:21)
- 53:42 — Chapter 12 (53:42)
- 1:00:19 — Chapter 13 (60:19)
- 1:07:39 — Chapter 14 (67:39)
- 1:10:11 — Chapter 15 (70:11)
- 1:15:10 — Chapter 16 (75:10)
- 1:17:54 — Chapter 17 (77:54)
- 1:19:52 — Chapter 18 (79:52)

## Transcript

**[0:00]:** The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseware at ocw.mit.edu.

**[0:21]:** All right, good morning, everyone. So, more of the same in terms of cryptography and cryptographic techniques, um similar to Tuesday's lecture. So, if you liked it, you'll like this one. If you didn't like it, well, it's going to be more of the same. Uh so, sorry. Uh but, uh what we're going to do today is um do a couple of things a little bit differently. I we're going to talk about encryption. So, we talked about hashing, which of course you know about from uh the use of dictionaries. We haven't really talked about encryption in 046 or even in 006 uh previously. But, uh we'll look at uh two different kinds of encryption algorithms. Spend a little bit of time on symmetric key encryption, which is really something that um was used in encoding machines, including the Enigma from uh World War II that uh you probably saw if you saw The Imitation Game.

**[1:23]:** So, there you have um a shared secret. And it's a single what's called symmetric shared secret. Both parties know the secret. And uh very quickly we'll talk about uh uh what it means to actually exchange a secret. So, we'll talk about key exchange, and then uh I move to asymmetric key encryption, which I alluded to a little bit when we talked about digital signatures last time. I talked about public keys and private keys. But, we're going to actually look at a couple of different public key encryption algorithms today. The classical algorithm, the very first algorithm really that uh stayed um secure, the RSA algorithm. Stands for Rivest, Shamir, and Adleman, the initials of the three inventors, invented at MIT in 1977. And uh still in use today. And the last part of today's lecture is going to be um looking at hardness. So, in encryption, if you don't know the secret key, it should be hard for an adversary to discover what the message corresponds to.

**[2:32]:** The adversary sees what's called the ciphertext, which is the encrypted text. Um the adversary does not know the secret key. Uh if uh he or she knows the secret key, game over. But, assuming the adversary does not know the secret key, it should be computationally hard to uh discover the message, right? That makes sense. So, there's clearly a relationship between this hardness and NP-complete problems, which are computationally hard. And it's not surprising that uh people have tried to build what are called cryptosystems, which are essentially cryptographic techniques, based on the hardness of NP-complete problems, including graph coloring and knapsack and so on and so forth. But, it turns out there's a real subtle um difference between the kinds of problems that uh have been uh useful uh in terms of building secure cryptosystems like RSA and NP-complete problems. And we'll talk about that uh at the end of the lecture.

**[3:36]:** We'll probably spend a bunch of time on that. So, let's get started with the symmetric key encryption, which is at some level kind of boring from a mathematical standpoint. So, we won't spend a lot of time on it. Um it's definitely very useful. Uh it essentially assumes that um there's a secret key K, and you can think of this as a 128-bit number. Uh some people want it to be larger, 256. Uh but, uh suddenly uh 64 at this point is probably not enough, uh even though 2 raised to 64 is still a fairly large number. Uh with parallelism and with uh uh with the fast computers, um uh it's a little worrisome that um uh the adversary only requires 2 raised to 64 work to enumerate all possible secret keys of 64 bits, right? So, 128 2 raised to 128 is is is much better.

**[4:33]:** And uh this is a shared between um Alice and Bob. So, uh uh we'll think about the protagonists here um as being um Alice and Bob, and they want to exchange information. And uh typically the adversary is is Mal for malicious. Uh so, but uh there's other ways uh you could obviously name adversaries. So, uh the basic equation here is really straightforward. Uh it's a C, which is the ciphertext. So, a little terminology here. Ciphertext. M is the is the plaintext or the message. And uh plaintext means you can just read it. Ciphertext means it's scrambled. Uh K is of course the secret key. That's up here. And the E is the encryption function.

**[5:37]:** Now, in symmetric key cryptography, uh basically the requirement is that you have to be able to get back the plaintext from the ciphertext given a public decryption function and knowledge of the secret key. And this should be a straightforward operation, right? So, uh E by the way, E of K M, this is a polytime computation. It's not uh constant time. It's typically linear time. And you don't really want it to be um quadratic time even, uh because you want to do this very fast. You know, streaming. You need to send streams of messages, uh many uh gigabits potentially, that are all encrypted. And this is actually what happens when you get uh stuff from your satellite. And you're you're downloading movies, that's exactly what happens. Right? So, it's symmetric key encryption of a lot of data. So, backwards would be D K C. Right? And the only difference here is that everything else stays the same.

**[6:39]:** This is our decryption function.

**[6:44]:** All right. So, um that's uh what a symmetric key encryption is, and there's a requirement of reversibility here. So, it's a lot different from one-way hashes uh that we talked about last time, uh because here while you want uh going from um C to M to be hard, it's only hard if the adversary doesn't know K. Uh if the if anybody knows K, it should be easy. In fact, um uh E and D are going to be virtually identical in terms of complexity and sometimes implementation. It's just you run it in reverse, and uh you get back what you encrypted. That's the way you want to think about it. So, really what happens is that you need reversible operations uh in order to build E or D, which are the encryption and the decryption functions. So, permutation, for example, is reversible. You can always take something and permute it, and you can go backwards, right?

**[7:54]:** So, you could you could do something like that. And the permutation the the reverse looks like that. This is uh What is this supposed to be? Uh it's it's the fact that I have three bits here, and they turn into uh uh three bits uh over there. And obviously, if I uh reverse the permutation, I and if I just had a simple thing where it was ABC, uh and I'm going to convert it to CBA, then uh you know, CBA can go back to ABC through the reverse permutation. So, clearly, this is a reversible operation. Uh but, there are other operations that are reversible as well. All right, plus uh can be uh reversed by negation, right? Um and uh exclusive or uh is is simply exclusive or, because if you do uh A exclusive or B, uh and then you get C, uh and uh imagine if you uh did uh B again to that, you

**[8:49]:** get A back, right? That's what I mean by reversal, uh because you have A essentially A exclusive or A cancels out. Uh and so, something like A exclusive or B exclusive or B again uh would give you would give you A. So, uh if you go look at uh AES, for example, which is the Advanced Encryption Standard, which is really only about four lines of code, maybe it's eight lines of code, uh but, this is uh uh a well-used It's been around for a while. Symmetric key cipher uh that uh runs in 128-bit mode as well as um 256-bit mode. And uh it's like I said, uh a few lines of code, and you'll see operations like this, uh permutations, and you'll see hat symbols uh if you see a C program, which is exclusive or, and uh you you can see the encryption and the decryption are identical in implementation.

**[9:44]:** You're just going to run it one way, and you run it again, and you get back the the result, because these permutations are reversible, and the hats are reversible, and the they're all signed integers, so you're just sort of adding them up, and it's comp- two's complement arithmetic. So, that looks the same as well. All All right. So, encourage you to go take a look at AES. I'm not going to spend more time on it. The key idea here is of symmetry and reversibility. Um we're going to move away from that. I clearly we didn't talk about that when we talked about one-way hash functions, etc. That was a different uh situation where we had no secrecy, but here we wanted symmetry. Uh the big question that you would ask and you should ask yourself uh when you see this, you say, "Okay, great. I can build um symmetric key encryption algorithms.

**[10:30]:** Uh they're actually I would say somewhat easier to do uh than to build hash functions which have a whole lot of more uh interesting properties and hard to obtain properties like um collision resistance, but um uh the question really is, how do Alice and Bob share the secret key K? Right? So, you need that. You need this 128-bit number in order for there to be a channel, a secure channel that Alice can communicate to Bob with, right? And vice versa. And so now you could say Alice sends Bob a letter. A- and but, you know, Mal could intercept that letter. Uh and even worse, what Mal wants to do is uh look at the letter, actually deliver the letter, uh which is the best thing for him, um I and and and and Alice and Bob think that they have a secure channel. That's sort of the best case scenario for Mal.

**[11:24]:** Right? So, um you could have Mal in the middle here. Uh and uh you got to worry about stuff like that, right? So, uh key exchange. Let's uh move on to talk about uh key exchange.

**[11:46]:** And how does the secret key

**[11:54]:** K get shared? You can't put this out on a website. Right? So, it has to be the case sharing is uh a something that has to be secure uh in in the sense that there can't be any eavesdroppers. Right? So, here's my uh favorite example of um of a puzzle that uh most of you've probably heard about, uh but uh those of you who haven't, it's really pretty cool. And those of you who have, it's still pretty cool. Uh and worth uh recalling. Uh and there's actually a something that you probably haven't thought about very much, even if you've heard about this puzzle. That's the mathematical assumption made in the solution of this puzzle that will be interesting to you. But the puzzle is a pirate puzzle. Right? So, you got Alice and Bob. Uh let's call it the Caribbean, because that's my favorite ocean.

**[12:53]:** Um and uh Alice and Bob are in two different islands, and we all know they're pirates in the Caribbean, right? Um and so Alice and Bob want to uh communicate uh with each other. And uh what Alice has uh are a bunch of boxes and locks and keys uh for those which she's got the keys for her locks and nothing else. And the same thing with uh with Bob. So, Bob has boxes, locks, uh keys for his boxes. I'm sorry, keys for his locks that he can put on his boxes. And uh in this case Alice wants to send a message to Bob. Right? And Alice wants to exchange a key with Bob so they can eventually communicate uh in a secure way uh regardless of the pirates or whoever else is listening. So, uh the problem here of course is that um if you just send a message on a boat, so the pirates are kind of nice in a way that they will uh deliver messages.

**[13:58]:** Uh but uh they are uh curious, right? You know, so they're very curious, and they will uh open up boxes. And so, that's supposed to be a boat, by the way, not a box. Uh little mast there, right? Uh So, um I'm not a sailor. Uh but uh you have you have these boxes that go are going to get delivered. And and the deal is this. Uh if there's an open box, uh the pirates will open the box. And if there's any message in it, they might read it, they might throw it away. Right? So, there's uh clearly a a secret key a clearly a secret key can't be exchanged by just putting an uh a box with a message in it if you don't lock it. Uh they will not uh be able to open uh or they'll not touch, and they will deliver a locked box.

**[14:46]:** But if they ever see a key, they'll keep it. All right. If they ever see kind of a key on the boat, they'll just grab it and keep it. And then the next time around they see a locked box, they'll they'll they'll stick the key in and and try and open it. All right. So, so how do Alice and Bob securely exchange a secret where security is based on this notion of piracy, I guess, with the pirates having a certain amount of um uh um uh of uh capability uh in terms of storing keys and opening up the locks, but they will not touch a locked box. All right. So, so that's the puzzle. How many of you heard of this puzzle before? Right? So, all of you keep quiet. Uh someone who hasn't uh heard of this puzzle before, uh think for a few seconds here and see if you if if if a solution occurs to you with respect to uh going back and forth, so that's the

**[15:42]:** hint, going back and forth, and being able to securely exchange a message, which could be a secret key, 128-bit secret key written on a little note, uh between Alice and Bob. Right? Yeah, back there. Are they allowed to pass locks uh such that So, if you see a lock, they'll throw away the lock, too. Uh if the lock is on the box, th- uh then uh sure, they will deliver that box. Uh but if a key is outside of the box, then they'll keep the key. Um

**[16:21]:** No, uh this is this is a difficult puzzle. Yeah. Um Alice could lock the box and send it to Bob. Yep. And then Bob could also lock Mhm. the box. Yep. And then? At that point? Uh you're on the right track. Keep going. Just push it a little more. Right? Couple of more boat rides and we're done. Right? Yeah. And then if Bob sends So, there's now two locks on the box. Yes. And and and Bob has two locks on the box. Right? And so, what's Bob going to do next? What's the logical thing for Bob Bob to do next? Send it back to Alice. Send it back to Alice. And now now's the the key inside, which is Alice now sees two locks on the box, and one of the locks is Bob's, and the other is hers. His hers. He can unlock the box.

**[17:19]:** She can unlock the box and send it back to Bob. Right? And all of this time, the only thing that's gone in transit is a locked box. No keys have gone into in transit, whether they're inside the box or whatever. But the only thing that's moved is a locked box, right? Um so, that's good. You're you're exactly right. So, that gets you uh that gets you a Frisbee. Um Oops, sorry. Uh you Yeah, we need a secure exchange there. Yeah, that's good. Um So, uh that is exactly right. So, just to uh recap, um Alice locks box with um KA, and that's the key for the lock, sends it to Bob. Uh Bob locks box with KB, sends it to Alice. And Alice unlocks. Oh, I should have said that Alice puts message in box.

**[18:32]:** Uh and and that message uh has the secret key inside of it. Um Alice unlocks KA um and sends uh box to Bob. And then Bob unlocks KB and reads message. All right. So, that's good. That's all good. Um Let's look at it a little more deeply. Um and think about it from a mathematical standpoint, uh not a physical standpoint, or you could think about it from a physical standpoint as well. What is the relationship between this locking, this uh sequence, in this case a pair of locks, that we require here in order for this to physically make sense? Right? I mean, there's different ways that you could add two locks to a box, right? There's many different ways. What's uh one way is to have a box uh that is locked if I lock it over here, uh and it doesn't open because the lid doesn't open.

**[19:39]:** I got suitcases like that. And then there could be another spot here that locks it as well, right? Uh and so so uh that could be one way. Well, what's another way of of uh having two locks? Yeah. Putting a box within a box. Yeah, putting a box within a box. That's great. Um so, if you put it if you put a box within a box, uh then does this work? It doesn't work, right? So, nested locks actually don't work because uh what happened here is that KA was put first,

**[20:14]:** then KB, and if in fact you had KA and then KB out there, then um uh you can't remove KA without removing KB. And this would be the case where you have nested locks. Right? So, the mathematical operation that we require is commutativity between the locks. Uh and uh the locks need to commute. I want to put KA uh in first uh like I described and the physical realization could simply be a suitcase with uh two different positions for the two locks and any one of those positions locks the suitcase. So, you put KA here, KB here, and then you can take KA out, right? And it's still locked because you have KB. Right? So, this commutativity between

**[21:18]:** the locks and essentially the keys uh is what's required. Right? And so, now let's move away from pirates and go into the cryptography domain, pure mathematical domain, and see how this turns into what's called Diffie-Hellman key exchange, which is a key exchange algorithm or a protocol that uh uh under certain conditions uh gives you exactly what you see here. It gives you a secure key exchange. And uh there's one issue associated with it uh that will be kind of clear once we write it out here that we'll get back to. But uh Diffie-Hellman key exchange assumes that you have commutative locks, and uh this is how it works. You'll see what the what commutes when I give you the equations associated with Diffie-Hellman key exchange. And this was also in the '70s uh described in described in the '70s. So, what we're going to do is we're going to work in uh a finite field FP star, and um the finite field means that we're going to be doing mod P, where P is prime.

**[22:41]:** And uh the star means uh we're going to be only looking at um invertible elements only. So, we drop the non-invertible elements. These things aren't particularly important.

**[22:57]:** And so, we'll drop zero and we'll be looking at 1 2 to P minus 1. So, all the numbers that you see are going to be 1 through P minus 1. Now, what is um the analog of this this uh protocol that Alice and Bob in our pirate puzzle operated on or ran? What is the analog in the mathematical domain or in the finite field domain? Well, here's what happens. Alice I is uh going to select a random A.

**[23:43]:** And we're going to assume that G is public, so she just shouts that out uh to uh Alice can see Bob from her house. Um so, she shouts out G and shouts out P. They're all public. She doesn't care if the pirates can hear this. Um and I Alice is going to select A, which is random, and compute uh G of A. I and this is in the finite field uh capital G. So, you're going to do your mods. And it's just she's just going to send over uh G of A uh over to Bob. Now, what Bob does is select B, and uh computes

**[24:34]:** uh G raised to B, and sends that over. Uh so, this is G raised to A is being sent over, G raised to B is being sent over, sent over to Alice. So, Alice gets G raised to B. Um and the key realization here is that Alice can compute G raised to B raised to A because she knows A, and uh that's all going to be mod P, and we're going to call that K. And thanks to the fact that exponentiation commutes, Bob computes G raised to B, I'm sorry, G raised to A raised to B because Bob knows B, which is also exactly K. All right. Uh I should say mod P. Over here. Everything is mod P.

**[25:33]:** So, so that's it. That's Diffie-Hellman key exchange. Um you have now created a shared secret based on the commutativity of exponentiation, and the part that's still missing here with respect to the analogy is the fact that G of A is essentially the locked box. So, uh what G of A is hiding is A because you want A to be hidden here. And the same thing with the G of B. It needs to hide B. So, the problem that the the the the the pirates had was they couldn't open up the box. Uh the problem that the adversary, let's call them Mal, has uh is that he has to invert G of A uh uh in in order to discover A. And um in this particular finite field, and uh there uh many such finite fields, you can think of this as being what's called a discrete logarithm problem, right?

**[26:37]:** So, we all know how to compute logarithms in the continuous domain, and there's tables and it's pretty easy to do. But this is what's called a discrete logarithm problem because we're in a finite field, and we obviously want integers. A is an integer, so we need to discover what uh that integer is. And uh because we're doing the mod Ps, etc., and P is typically a a large number, um it's actually a hard problem computationally to um do a discrete log. So, when you see G of A, um if you don't know you know G, you know you know P, but trying to figure out what A produced that G of A uh is a difficult problem. And people have looked at this for 30-40 years, and there's not a a great algorithms to solve this problem, certainly not anything that's polynomial time solvable. Uh they're all kind of sub-exponential, and you can make the numbers large enough such that G of A is secure in the sense that it doesn't give away what A is.

**[27:36]:** All right? So, so that's the insight here uh that um uh Diffie and Hellman had, uh which comes down to um the discrete log problem um is hard, and what this simply means is given G of A, the discrete log problem is compute A. And the same thing for B, of course. Um there's one other thing that um you want uh to say to be precise, to sort of just cover the spectrum with respect to how this could break. And uh that is uh what's called the Diffie-Hellman problem uh for one of the better names, and since these were the folks who first came up with it. And the Diffie-Hellman problem is simply that given G of A and G of B, which is what the the pirates see and what the adversary Mal sees, uh we we should not be able to compute G of uh

**[28:40]:** um A times B. Which is exactly what we get here. G of A raised to B is G of A times B. So, given those two things, if there's a way of computing G of A times B, um even though you potentially haven't discovered A and B precisely, G of A times B uh is your the secret key that Alice and Bob exchanged. So, you're you're host if Alice and Bob are host if um Mal can do this, right? So, there's two things going on here. Uh you want the Diffie-Hellman problem to be hard, and you want the discrete log problem uh to be hard. Okay? So, generally, this is how cryptography works. Um you um set up protocols, and uh there's some information that's bound to be exposed. You want this information uh to be um hard to reverse to get the crucial information.

**[29:32]:** That requires a computational hardness assumption, like the two that we've made here, and uh then you're off and running. Um your system will break if your computational hardness assumptions are incorrect, and they may be correct for a particular time, for example, the 1970s for particular parameters, but they may end up being incorrect assumptions at least for those parameters uh in at a later point of time, simply because computers got faster, right? It's like 2 raised to 40 was this huge number, like you know, when I was your age, right? Now it's like nothing, right? So, that's basically part of the game, but the good systems are those that scale where you increase the parameter size and at the system and the protocol stays the same, and so you just increase P, for example, in this case, and the discrete log problem is still hard for modern computers, right?

**[30:26]:** So, those are the good protocols and the good crypto systems that stand the test of time, not necessarily the ones that have exactly particular parameters, you know, that's hard to do because as I said, Moore's law and the computers have been getting really exponentially faster. All right. Um so, there's one main problem with the Diffie-Hellman protocol and the solution to our pirate puzzle. And so, can someone tell me and and it could be just for the sake of the Diffie-Hellman problem or just in the context of the Diffie-Hellman problem, but also in the context of the pirate puzzle, what assumption are we making here that's as yet unstated uh with respect to this secure key exchange being actually secure? Someone? Yeah. Um the pirates could like intercept the message in the middle and send something of their own back. What does that mean? They have a locked the pirates see a locked box.

**[31:26]:** So, the first step of the protocol, Alice is sending a message inside a locked box with a single lock in it. Um what could the pirates do? You're kind of on the right track. What could the pirates do in order to break this protocol? I we've kind of made an assumption here and I might have said it explicitly. Yeah, go ahead. They could just throw the box away. They could just throw the box away, but that doesn't break the security of the protocol. That breaks the functionality of the protocol, right? Yeah, go ahead. Put their own lock on it. Ah, that's exactly right. Put their own lock on it. You know, if you put their if they had locks, these pirates don't have locks, right? We're making that assumption. If they had their own lock with a key, right? If they just had a lock that locks and they didn't have the key for it, they still wouldn't be able to break the security of the protocol, right?

**[32:15]:** But if they had a lock and a key for that uh lock, then they can pretend to have delivered this to Bob and there's no authenticity here with respect to Alice doesn't quite know whether she's communicating with Bob or not. She's at the mercy of the pirates to deliver these boxes, right? So, if the pirates had uh had had a lock and a key for the lock, then we're in a situation where Alice may have exchanged a key with the pirates, right? And she thinks she's exchanged it with Bob and she's in fact communicating with the pirates, right? So, there's a man-in-the-middle attack

**[33:01]:** which corresponds to the pirates uh having their own locks and keys and it's even more trivial uh in the case of our picture here uh because assuming the pirates know mathematics, they can generate a random number and the number could be C, for example, and just send back G raised to C, right? And for all you know, they could actually get Bob uh to send G raised to B back, but they would intercept it and replace it with G raised to C. And they know what C is, right? So, what's happening now is you can see the sort I won't go through all of the the math here, but you can kind of kind of see it, I hope, where you end up if you're Alice exchanging a secret key uh with um uh with with the pirates as opposed to Bob and the way you can set this up is the pirates actually will uh get into a situation where Alice and Bob think that they're communicating

**[34:06]:** with each other in a secure fashion, but the pirates can listen to all of the messages, right? They can decrypt all of the messages because they know what the what the secret key K is, okay? And remember that the secret key K is something that is probably going to be used in a symmetric key encryption scheme uh eventually to send real messages, right? So, you're going to have ciphertext with that secret key capital K over there and if if the pirates or Mel get to know what the secret key K is through a man-in-the-middle attack, you got problems. All right. So, the man-in-the-middle attack is something that we have to worry about. What we're going to talk about next is something that addresses this problem and it may not seem like it's directly addressing the problem, but fundamentally what's going on here is you need to have authenticity in who you're communicating

**[35:04]:** with. Alice has to somehow authenticate Bob and Alice has to know somehow that G raised to B is something that came from Bob, right? It's not G raised to C that came from somebody else who's in the middle. And that's where asymmetric key cryptography and public keys come in, where you have a certified public key associated with yourself. So, you say and maybe you need Verisign or you need the DMV or the Registry of Motor Vehicles RMV to do this for you, but you create a certified public key which is associated with your identity and it's public. You can put it on a website uh and everyone can access it using HTTPS, so they know they're going to the exact website that you put up and that gives you a way of identifying yourself, all right? And if you can do that, you can protect against the man-in-the-middle attack using asymmetric key cryptography, okay?

**[36:04]:** So, that's the kind of the final uh part of this this puzzle that's associated with uh uh with with authentication and secret key exchange and all of that. Once we do that, you'll know what the functionality is that we require and then we'll have to talk about how we can build such systems.

**[36:26]:** All right. Cool. Any questions so far? How we doing? Okay. So, public key encryption, let me just do a little setup. I said some of this last time, but to make sure we're on the same page, what we have here is we really want a message plus a public key and you want to obtain ciphertext

**[37:01]:** using this operation and this plus is not uh arithmetic addition, it's just that we're putting these two things together into an algorithm, a public key encryption algorithm that produces ciphertext, all right? And this public key, just to reiterate what I just said, uh is going to be if Alice is producing the message and Bob is getting the ciphertext, this is going to be Bob's public key. And the fact that it's Bob's public key is something that Alice should be able to authenticate using Verisign, using the Registry of Motor Vehicles, what have you. That's what's going to protect against the man-in-the-middle attack, okay? I'm not going to talk a lot about how you can get a certificate. Your MIT certificate is something which corresponds to your your MIT ID. It's got information what year you are, what your name is, and when you generate that certificate, you are getting a certificate of authenticity that you're you.

**[38:04]:** Now, of course, you give that away and you hand it to someone else, someone can pretend to be you as well, but that's what what's happening when we talk about public keys and you owning public keys, all right? Uh we're not going to as I said, get into that very much more. I'm more interested in describing this algorithm for public key encryption. We'll look at a couple that produces a ciphertext given a message and a public key. Now, of course, what Bob needs to do is to take the ciphertext and this is what Bob's doing and uh Bob has a private key that is distinct from the public key and needs to get back exactly the message using a decryption algorithm that corresponds to the message that Alice sent, okay? And this whole thing is going to work provided

**[39:09]:** knowing the public key, let's call it PK, and the private key, we can't call it PK as well, obviously, so we call it SK, uh knowing the PK does not reveal anything in a mathematical sense about SK. But obviously, in order for this whole thing to work, PK and SK have to have some a relationship, right? And the different crypto systems, including RSA and we look at a knapsack crypto system, all have different algorithms for encryption and decryption, and they have different mathematical relationships between PK and SK. And for each of these relationships, you have to show that the adversary has to solve a computationally hard problem in order to discover PK, excuse me, discover SK given PK, right? And it turns out that for most of these systems, it's symmetric in the sense that these algorithms you could use, at least for RSA, you could use um uh either one of these interchangeably.

**[40:25]:** And there's issues associated with that, so we really won't go too deep into that, but what I said should hold, which is you give you have one, it shouldn't tell you anything about the other. Right? There has to be a computationally hard problem associated with discovering one of these only given the one other. All right? And we'll talk about what those hardness assumptions are, certainly for RSA and also for another crypto system, a knapsack. So, we're going to present RSA, which is this real magical algorithm. It's amazing it works. Every time I I prepare for this lecture, I got to relearn some things. And that's because it's you know, there's there's one subtle aspect of this. It's all about number theory, and number theory can get pretty subtle. But it's also intricate enough that I forget the details. So, let's get started on that. Basically, RSA is based on uh primes and factoring numbers into primes and using um uh using number theory to make sure that you can actually accomplish what this is trying to do.

**[41:48]:** Uh the functionality of RSA should be distinct from the security of RSA. Right? When we talk about the functionality of RSA, we're saying for any message, if Alice uses Bob's public key to encrypt it, the ciphertext resulting from that should be decryptable into exactly the message that Alice sent given Bob's private key. Right? That's the functional requirement of a public key encryption algorithm or a public key crypto system. The security requirement of a public key crypto system is what I wrote up there. It's the knowledge of SK should be hidden even given the knowledge of PK, and there's precise computational hardness assumptions that are associated with each crypto system. Right? So, let's separate out functionality from security. We're going to talk about functionality for the next few minutes.

**[42:47]:** Alice is going to pick

**[42:52]:** two large secret primes,

**[42:59]:** P and Q. So, what I'm going to describe here are Alice generating her public key and her private key. She's going to then publish her public key and keep her private key secret. Bob does the same thing. And then after that, they have to register, and this is not something we'll spend time on beyond me saying it one more time, they have to register their public keys with the VeriSign or the RMVs like I talked about. All right? So, everyone knows that Alice's public key is this long number. But no one knows Alice's private key. Um so, Alice picks two large secret primes. So, so these are eventually going to result in the creation of her private key. And then Alice computes um N equals PQ. Okay? So, she just multiplies those out. Um she chooses an encryption exponent

**[44:00]:** E uh which satisfies this little equation, uh which says that it's relatively prime in relation to P minus 1 times Q minus 1. And she knows P and Q, so she can compute P minus 1 times Q minus 1. So, the GCD of E and P minus 1 Q minus 1 is 1. And you can certainly accomplish this simply by choosing E to be a a prime, right? Because then GCD of a prime with anything else is is 1. And And it turns out that RSA uses This is all going to be public, by the way. Um E is going to be public, so you can just fix that. And most RSA algorithms just fix that to be the small number. The encryption exponent is a small number, and the reason it's a small number is because you're worried about performance, and we're going to exponentiate using E, and the smaller it is, the faster the encryption is going to go.

**[45:00]:** Right? So, if you want to encrypt fast and decrypt more slowly, unfortunately, that's the trade-off here. You would pick a small E, and then we're going to compute our decryption exponent, which obviously is going to have to be private. Uh because that's part of our private key. But that's going to be bigger if E is small. And that's just a trade-off. It's symmetric in the sense that while it's an asymmetric algorithm, it's kind of symmetric in the mathematical sense that the private keys and the the public key operations are symmetric. All right? So, what is Alice's public key? Well, Alice's public key, which she can then publish, um is simply N {comma} E. Okay? Um and

**[45:50]:** And now the fun starts. We have to figure out what the private key is going to correspond to. And it turns out, and this is one of those things where how did they ever think of this? And that's still true 40 years later. You get the decryption exponent using the extended Euclidean algorithm.

**[46:23]:** Um and this is done by Alice secretly, where you what you want is to have the relationship that E times D is 1, and this is mod P minus 1 Q minus 1. And uh there's there's algorithms out there uh that would find the inverse uh that corresponds to D for E or vice versa, and they're polytime algorithms as long as you know this number here mod P minus 1 Q minus 1, and you know that Alice knows that, you can get your decryption exponent. Right? And typically, if E is small, as I said, D is going to be large. Um By the way, the numbers here P and Q are going to be roughly 1,000 bits long. Right? So, that's essentially we're talking about huge primes here. Uh and so N would be 2048 bits in that case. So, the private key, Alice's private key,

**[47:26]:** um you can think of as DPQ. All right? So, So, now it's clear as to what's public and what's private. N and E are public, DP and Q are private. All right? So, that's the setup for RSA, and uh it's not at all clear that RSA accomplishes either of the two things that we need. The first of which is functionality, the fact that encrypting and then decrypting a message should get you back that message. So, that's the first thing we need to look at. And the security part is actually a little bit easier, because you can see we're going to have to make assumptions about um factoring primes and so on and so forth. Right here, you can just see that immediately the the biggest assumption made by RSA from a computational hardness standpoint is simply that if the adversary sees N, uh that they should not be able to factor it into into

**[48:27]:** P and Q. Because if they can do that, it's over. Right? So, that's the that's actually easier than the functionality um argument. So, why does this work?

**[48:42]:** And amazingly, we can actually do this in about 10 minutes and explain to you why this works in 10 minutes. And the only theorem that we'll require on top of this, which I will not prove because Fermat proved it centuries ago, is Fermat's little theorem uh that says uh that when you have P being a prime, this is a You can think of this as a special case.

**[49:21]:** Um that you you have you take M, and M is an arbitrary number, and if P is a prime,

**[49:32]:** then this relationship holds. So, you raise it to the P minus 1 to and you get one. Right? Mod P. So, that's uh Fermat's little theorem that's going to be required, and that's pretty much the only thing that you have to invoke uh beyond sort of standard uh mod arithmetic to show that RSA works. Uh so, what's going on here? Let's call fee P minus one times Q minus one. Uh obviously, that's showed up a couple of times and uh may as well represented using a smaller, simpler symbol. So, we'll call that fee. And we are going to uh say that ED equals one mod fee is given to us.

**[50:21]:** Um and uh it therefore, we can say that ED equals one plus K fee. Okay? So, that's it. Uh that's uh all I'm saying is the remainder when you took the mod with respect to fee was uh was one, so the actual number was one plus K times fee, where K is some integer. Uh think of it as a positive integer. Um remember that um I we we now have the P and the Q are over there, and P and Q are primes. So, P and Q are primes. And given that that's the case, uh we really have two cases to analyze. Um Oh, uh I'm sorry. I missed one crucial point which uh

**[51:12]:** I should have told you. Which is I gave you this, but I didn't actually tell you uh what is going on. I mentioned it in passing, exponentiation, uh but I didn't tell you exactly what the encryption algorithm was and the decryption algorithm was, and obviously, you need that in order to prove their correctness. I mean, it'd be wonderful if you could prove correctness of this there exists an algorithm uh that um uh it it's such that uh uh you know, RSA works or uh uh public key encryption works. So, uh it turns out it's it's extremely straightforward. C equals M raised to E, and that's part of the usefulness and the power of RSA. Uh which is uh C, you take M and you exponentiate it. Uh and you take uh C and you exponentiate it. And uh the first is the encryption. S- you get the C through encryption, as you can see over there, the ciphertext.

**[52:10]:** And the M is the plaintext, and you get that back. Right? So, so our goal here is to show that um uh that um uh it's uh you have uh uh essentially something where um when you exponentiate M raised to ED right? Should give you M. For these choices that we have of E and D, we've set up the D in such a way that M raised to ED, cuz if you just go do en- encryption followed by decryption, you are doubly exponentiating. Right? That makes sense? Ask me questions if this doesn't make sense. This is important. Uh M raised to ED should give you back M. Right? That's uh and if you can show that for any M, uh you're done. That's the functionality of RSA. All right? So, um so, that's uh encryption and decryption. And so, now let's go back to where we we're here.

**[53:10]:** Uh uh uh Now, ED equals one mod fee because I've set that up. This is how I discovered uh D given E. So, that's a given to me. That's part of the what's called the uh the key generation phase of RSA. And uh th- that's the mathematical relationship that I keep harping on uh in terms of the relationship between the public key and the private key. So, uh given that P and Q are primes, I have two cases.

**[53:42]:** Right? Um the the first case is that GCD of M {comma} P is uh exactly one. Right? So, which means that the message M, so what I'm comparing here, the two cases is I have the message, and I'm going to break up the messages into two different categories. That's it. There are all kinds of messages that are possible. These are arbitrary numbers. I'm going to break them up into two uh categories. One of which where the message is relatively uh prime in relation to the to the prime P. Uh and it's not a multiple of P. That's the way you want to think about it. Uh obviously, GCD MP uh would be two if if M were 2P. Right? So, so the case I'm looking at is uh GCD of MP equals one. And and then the other case is going to be uh trivial, actually, which is GCD of MP uh equals um equals P.

**[54:37]:** Right? Did I say two when I when I said GCD of 2P {comma} P equals two? Come on, you know. Right? Wake up. Well, that's it. Perfect. Wake up. Okay. So, um GCD of 2P and P is is P. Right? So, those are the two cases. Uh all right. So, by Fermat's little theorem, this is really Fermat's theorem, and because he had a last theorem, for some reason, some people call this the little theorem. Uh but it's Fermat's theorem, and we know uh we we know what that is. I just wrote that out there. Uh you can now write uh something that uh uh says, "What I'm going to do is I'm going to just take um uh M raised to uh to P minus one, which is one. Right? So, this thing is one. And then I'm going to raise it to K times Q minus one.

**[55:37]:** You'll see why I'm doing this in a second, because I want to get uh the one plus K fee factor here. So, I'm taking one, and I'm raising it to this power, which obviously is going to give me one back. Right? So, all of that is uh uh it is is straightforward. Uh and then I'm going to multiply this by M. Okay? And uh this is clearly uh uh the same uh as M mod P. Right? Because all I've done is multiply it by uh multiplied by one. All right? So, why did I do this? Well, I did this because I want to group together uh these two uh exponents, and since I've run out of room here, uh let me just erase and finish this properly. The other case is easy, anyway. Uh and so, I can write this as one plus K uh P minus one Q minus one.

**[56:30]:** Uh and that, of course, is uh exactly M raised to ED. Right? Uh and so, so what I've done here is uh this, because it's one times M, is clearly M. But if I look at this, this is M uh it raised to ED, so that's that's clearly that's clearly M. Right? That's it. Um just to just figured out that uh when I have um K fee here, uh that's going to turn into one. Basically, when you exponentiate it. Uh so, that's this that's the the hard part, actually, as it turns out, uh of uh proving RSA's correctness, uh just introducing this uh this uh one raised to something. And then the uh the easier part is simply uh the case where uh the M is actually a multiple of P. So, you have GCD M {comma} P equals P. And in this case, you know that M mod P is actually zero.

**[57:31]:** Uh because M is a is a multiple of P. Right? So, you're basically exponentiating uh zero. What do you do with zero? You're going to get zero on both sides. Uh and so, you're you're sending a message that's uh that's essentially zero mod P, and uh when you decrypt it on that side, you you get zero. But the the one last line here is is simply that uh M raised to ED um is M trivially. All of this mod P if M is zero. So, so that was the that was the easy case. So, it was really pretty straightforward. In one case, we took one and we exponentiated it and showed the result in a couple of steps. In the other case, you had messages that were zero mod P. Right? So, it's very pretty. It it works. Uh and um uh so, what happened here?

**[58:20]:** I said that M raised to ED equals M. And uh what I did here, of course, was I did everything, so it's not quite done. Um little sleight of hand here as I switched over and talked about mod P. Right? So, I had uh mod P over here, and I said P and Q were primes, and I looked at the I looked at P first. Uh but what I need to do, just to finish this off, uh let me do this over here, uh is I have to do the same argument for Q. And I'm going to uh put it together uh for uh for N. And the reason for that is simply that I have N over here. Right? So, remember N equals P times Q. The uh encryption and that decryption uh are going to be uh done mod M. Certainly, the encryption has to be done mod M, because N is the only public number that you have that you can mod with.

**[59:16]:** Correct? So, what I've done here, this analysis is for P. Can do the same uh uh for Q. It's exactly the same. Because P is a prime, and Q is also a prime. Um but uh I have to just do one last thing, which is put these two things together and and say that n equals p times q, so the math is all going to work out. Right? Let me just write that out. And it's not too difficult to explain once I have this up here. So, in both cases of p and q, so when I say both cases, I mean the p case and the q case, uh, I have m raised to ed equals m mod p and m raised to ed is the same as m mod q. Right? Um, and since p and q are distinct primes,

**[1:00:19]:** um, we we can say that m raised to ed equals m mod n. And that essentially says c raised to d, uh, if you really want to put it all together, which is m raised to e raised to d equals m mod n. Which, of course, is what we want here. And this thing was also mod n. This is mod n, mod n, mod n. All right? So, that's RSA. That's your first public key algorithm, the first public key algorithm, at least that's stood the test of time, still in use today. Uh, it's, uh, it from a standpoint of computation, uh, this is the hardest part. Uh, you have to exponentiate and you have these large numbers, and, um, as the years have rolled by, uh, RSA has, as I said, withstood the test of time, but the parameters have increased. Way back then, in the '70s, they were thinking about 512-bit uh, primes.

**[1:01:28]:** In fact, I can't recall whether n was 512-bits or p and q were 512-bits, but if p and q were 512-bits, then n would be 1024. And now, uh, NSA recommends 8192-bits for, uh, for n. So, there's been an increase. But, the nice thing is that, uh, it's not like, um, there's an exponential uh, increase in the computation because the computation is polynomially related to the number of bits. Okay? So, maybe it's, uh, if you double it, uh, I think if I recall correctly, decryption is going to be the cube of that, or actually verifying signatures is probably the cube of that. But, uh, don't don't worry too much about that. Uh, the bottom line is that as you double the uh, the uh, size of the exponent, uh, you're going to have a fairly small increase in the time required to decrypt or to verify a signature, uh, etc.

**[1:02:26]:** Right? But, it has grown from 512 or 1024 uh, to 8192. Um, and so, hopefully you all understand, uh, how RSA works to some extent. Um, I just will leave it at uh, the hardness assumptions here are, like in the case of Diffie-Hellman, uh, uh, uh, uh, uh, twofold. And the first one is uh, kind of immediately obvious. Uh, just like it was the case with, uh, Diffie-Hellman, where you had g raised to a flying about, and obviously that has to hide a. Here, you got n, capital n, uh, being published. And if anybody could take n and factor it, uh, and there may be multiple factorizations, but let you you're going to get a unique prime factorization. So, that's what you want, that unique prime factorization of n. And if you get that, then you've broken uh, the the system because you know what p and q are.

**[1:03:26]:** Right? And so, this is all public in the sense that uh, this algorithm is public. If you're using RSA, this is what you're following. So, the person is trying to figure out what the two primes are that together get multiplied to form capital n. Right? So, that's a factorization problem. And so, RSA the hardness assumptions are

**[1:03:49]:** uh, given n, hard to factor into p {comma} q. Uh, and this is factoring. Uh, and then, uh, one other thing, which is, uh, given e, so you're not actually breaking the entire cryptosystem, but you're breaking the privacy associated with a particular message. Okay? And so, you could break the privacy associated with a particular message. You're given e because that's public. And, um, uh, you know, you don't know what p and q are, uh, but, you know that, uh, uh, uh, that, uh, e is relatively prime with respect to, um, uh, p minus 1 q minus 1 because that's the RSA algorithm, and that's uh, publicly known. And you also know c, uh, which is the ciphertext. Uh, and so, what you're doing is you're trying to discover m. So, you're trying to break a particular encryption that was created by the RSA algorithm, and you haven't discovered the private key here.

**[1:04:55]:** That's only discoverable through the factoring problem, but you could, uh, uh, break security if you can find m such that m raised to e is c mod n. So, you're doing there searching uh, for an m. So, you're trying to discover an m that you can exponentiate to get what you have on the right-hand side because clearly you can compute what's on the right-hand side. Right? So, this is uh, simply called the RSA problem.

**[1:05:29]:** So, those are the two computational assumptions that you need to make in order for RSA to be secure. All right? Cool. Any questions?

**[1:05:40]:** Can we authenticate the identity of the sender? Uh, so that's anonymity. Uh, yes, uh, there's uh, ring cryptography, and uh, there's a whole host of protocols. I actually did some of them based on RSA, where you can, uh, figure out by collecting a bunch of private keys together, you can, um, uh, essentially set it up so uh, it can be verified that, um, uh, the message came from a collection of people, but you can't tell which, uh, person the message came from. Right? So, there's just a whole host of things. Uh, there's thousands of papers written. It's a wonderful field. I encourage you to look into it, um, if, uh, your interests are inclined this way. And it's just gone on and on. It's become more important with the internet. Um, RSA, the company was probably founded in the late '70s, and they they struggled for a while, and then eventually they were used for secure socket layer in Netscape, which was their big break.

**[1:06:37]:** And then, of course, the Netscape meant the internet was around, and so it's really the internet made RSA what it is today. Right? And so, just a whole host of, uh, wonderful algorithms out there, uh, some of which are based on RSA, and and some that are broken. Right? And so, let's talk for the last few minutes about all of the the the the fits and starts that, uh, occurred in cryptography. And, uh, precisely, uh, what, uh, I'd like to focus on for the time we have left is hardness. So, uh, we spent a lot of time talking about hard problems, and we talked about, um, NP-complete problems that, uh, are hard, but they're hard in the worst case. Right? So, uh, you you have a situation where um, you have NP-complete problems.

**[1:07:39]:** And I'd like to talk a little bit about the relationship between NP-completeness and crypto uh, because we've made these assumptions about hardness. Now, what's interesting here is that is n composite is clearly in NP, but unknown if NP-complete. Right? So, this is very interesting. The tried and trusted algorithm for public key encryption relies on a computational assumption where the problem associated with that assumption is not even known to be NPC. All right? So, so that's kind of wild. It's like, how does this work? Or, why does this work? Now, if you if you take other problems, like is the graph uh, three-colorable?

**[1:08:29]:** And so, what does that mean? Uh, well, you have, uh, three colors, and, uh, you're you're not allowed

**[1:08:38]:** to, uh, reuse uh, the same color on two, um, uh, ends of an edge. So, if you put, uh, red over here, uh, you can put red here, but you can't put red here and there. Right? And so, that graph is three-colorable, but if you had a clique, um, then, you know, this would not be three-colorable. Right? Because, uh, you have all these edges. You got three edges coming out. And so, clearly the degree uh, from a vertex is going to tell you what you have. So, if you have a four clique over there, immediately it's not three-colorable. But, a graph, checking whether a graph is three-colorable is NPC. And you can show that from a reduction uh, uh, uh, or you can, you can use three-sat as, um, as a way of showing that. Um, so, uh, you can say, "Oh, wow, maybe I shouldn't be worried about RSA.

**[1:09:31]:** I I should just be building crypto systems based on three-colorability because it seems like a much simpler problem than all this grungy math that you have out there." Actually, beautiful math that you have out there. Okay. Uh, so, uh, that's something that's a perfectly reasonable question to ask. And then we have knapsack where, uh, knapsack is simply you got a bunch of items and, uh, you just want to figure out whether you can get this particular sum S. Knapsack, uh, is is NPC as well.

**[1:10:11]:** And you got a bunch of weights given to you and, uh, the BI are going to have to be 01. So, you just want to discover a particular assignment of the BIs such that you pick the appropriate items to put into the knapsack. Right? That's it. That's a perfectly reasonable problem to potentially use as a basis for computational hardness to go build crypto systems. Right? And people did that. People did that for years. They tried and they tried. And they produced crypto systems, public key crypto systems based on knapsack that uh, looked fantastic and they worked from a functionality standpoint in the sense that you would, uh, use this knapsack, and I'll give you a sense of how this is done in a minute. You'd use the knapsack problem uh, to, uh, to encrypt. And then you'd use a different kind of knapsack problem to decrypt.

**[1:11:05]:** And when you encrypted and decrypted, you did get that same message back except the whole world knew what the message was because, uh, the problem associated with the knapsack was, uh, wasn't hard enough. Right? So, the computational hardness was what broke the knapsack schemes. And then you come down to asking why is it that, um, this problem that's not in NPC seems to have stood the test of time, but all these other problems, like knapsack and three-colorability, which is even worse than knapsack, um, when people have built crypto systems based on this, they've all been broken very quickly. And so, why is that? What What What do you think the the reason is, right? Sort of at a high level. What does NP-completeness say?

**[1:11:59]:** What What when we talk about complexity, what are we worried about? Most of the time, what are we talking about when we talk about complexity of an algorithm, or in this case, in in the case of a problem, what what what adjective do we put in front of run time, for example, when we compute complexity? Worst case, right? Worst case, right? In the worst case, uh, you're going to be able to create random graphs where it takes exponential time to discover whether they're three-colorable or not. But in the average case, all you do is if you have a large graph, if you had if there's one little four-clique in the graph and you can find it, instantly you know that it's not three-colorable. Right? So, it turns out that three-colorability is just the worst thing ever when it comes to cryptography because the larger the graph, and you need this graph to be large because anything that small is constant time, right?

**[1:12:55]:** Because so what if it's exponential? It's constant time. So, you need the graph to be large. When you have a random graph that's large, the chances that you're going to find a four-clique in a 2,000 vertex graph is pretty high. And so, if you just go scan and look for a four-clique, instantly you know that this graph is not three-colorable. Right? So, in the average case, three-colorability is easy. It's It's easy to solve in the average case. And, um, the wonderful thing about factoring is as long as the numbers are large, it doesn't matter what the numbers are, it's hard to factor in the average case. Right? So, that's the big difference. If you're going to take anything away from the rest of this, it's the difference between problems that uh, cryptographic systems are based on and, uh, the systems have stood the test of time, they're based on problems that are

**[1:13:47]:** hard on the average. And, um, the NP-complete problems, like the simple ones here, are hard in the worst case, right? And this is also true, uh, for, uh, for knapsack. All right? So, so that's the essence of it. Um, I'll just give you a a sense. I'm not going to You can read the notes. Uh, there's a way of generating secret keys and public keys using knapsack that I think is kind of interesting that is worth looking at even though all of these systems are broken. It It's just kind of cool. You know, how would you get encryption out of a knapsack, right? I mean, you're putting things into a knapsack and taking things out. How can you set it up so you get an asymmetric uh, key system, a public key system through a knapsack problem. So, I'll just give you a sense of that and you can read, uh, I won't finish, but I'd like to do what we did here, uh, it, uh, for RSA to, uh, in the time that I have left

**[1:14:45]:** for for knapsack. Because that's that is kind of cool. You You get a sense of the variety of different public key crypto systems that are out there by looking at something that is very different from RSA. All right. Um, so, in in the knapsack problem, the general knapsack problem

**[1:15:10]:** um, is is what's hard. That is NPC. There's a super-increasing knapsack problem

**[1:15:22]:** that's easy. That can be solved uh, in linear time. Right? What What is a super-increasing knapsack? Well, a super-increasing knapsack is something where I have WJ

**[1:15:43]:** has this property. So, an example of that is 2 3 6 13 27 52. Right? So, the weights are super-increasing. 2 + 3 is less than 6. 2 + 3 + 6 is less than 13, and so on and so forth. Do you see why super-increasing knapsack is easily solvable? Right? I mean, what is a knapsack? I got a limit on the amount of stuff I can put into the knapsack and, uh, I want to make sure to be able to say yes or no in terms of whether it fits exactly or not just, uh, in terms of our definition. So, what would I do here in, uh, super-increasing knapsack? Yep. What you do I take from the biggest to the smallest to figure out what I can take. Exactly, right? I mean, there's a linear time algorithm that basically solves the problem and you know that, um, uh, you can you can do that and you would get the correct answer, right?

**[1:16:40]:** So, that's pretty much what what you got. Uh, that'll give you the highest weight, right? Uh, you don't want to put If you have 13 exactly, uh, you know you can't put 52 and 27, you can get 13. There's no point in putting two and three and six, uh, because that's not going to give you, uh, the 13. Right? So, So, that's clearly easy. So, we got an interesting case here where, assuming this is all going to work out from an adversarial standpoint, which unfortunately it doesn't, you kind of look and say, "Ah, um, I want encryption to be the super-increasing knapsack uh, because that should be easy to do. Uh, and I want that decryption not knowing the uh, the the private key to be as hard as knapsack. Okay? So, that's the kind of thing that you could do, uh, if you, uh, built a Merkle and Hellman.

**[1:17:31]:** Hellman is the same guy, the second name in Diffie-Hellman. They, uh, proposed this particular system that, uh, ended up, uh, being broken soon after. But the idea is that you create a private key um, and the private key is a super-increasing knapsack.

**[1:17:54]:** And then you use a private transform

**[1:18:02]:** in order to get a hard and this is really I put in quotes because uh, this was the bug. Uh, hard knapsack problem. And this corresponded to, uh, the the public key.

**[1:18:24]:** All right. Um, and so, what you do is you wouldn't actually have to solve knapsack for encryption, uh, the hard problem. Uh, the encryption would just simply take the public key, which was which was completely public, and, uh, you would, uh, create, uh, the encryption of a message, uh, using this, uh, this particular uh, public key in a polynomial, uh, way, polynomial in polynomial time, and but the inversion, uh, not knowing the private key, uh, you would force the adversary to solve a hard uh, what you think was hard general knapsack problem to actually break the scheme, uh, to get the the decryption. And so, let me show you really quickly how, um, this works with numbers and, uh, you won't have to worry about, um, symbols and things like that. So, just give me a couple of extra minutes here. So, let's say that I had a message.

**[1:19:20]:** Um, Oh, before I do that um let me look at Let's say that we chose n equals 31 and m equals 105. This is This is actually the message.

**[1:19:36]:** No, I'm sorry. M is not the capital M is not the message. These are public parameters. Um and we're going to take This is the transform.

**[1:19:52]:** Oh, I'm sorry. These are not public. These are private. My bad. So, what I'm going to show you is I'm going to take a super increasing knapsack and that's exactly what I have up there. So, that's corresponds to an easy knapsack problem. I'm going to convert it using these private parameters n equals 31 and m equals 105 and so our private key is our super increasing knapsack which is 2 3 6 13 27 and 52. And the public key um is I What I'm going to do is simply take I multiply each of these I two times m and I'm going to take um mod m. So, for each of those values I multiply by n which is 31 and take the mod of 105 and I end up getting 62 93 81 88 102 and 37. All right? So, um I You can get a private key and a public key using this private transform.

**[1:21:03]:** Um I'll let you look at the notes, but basically what happens is when you take a particular message m what you end up doing is you want to encrypt it using the public key which is this quantity over here and the way you encrypt that is simply by I taking a particular message and let's say that the message is written as 011000. Then all you do is add up 93 and 81 because those are those two and you say this is going to get encrypted by 174. Right? So, the message encryption is simply a simple operation where you add up weights of the knapsack. Um so, you end up getting 174 out here and um the the hope is of course that when an adversary sees 174 and this is the part where things get a little iffy. Uh the the adversary sees 174 that it's hard Uh you have to think about lots of numbers here of course.

**[1:22:01]:** It's hard for the adversary to figure out uh that 174 is actually 93 plus 81. Okay? Um that So, the reverse is not necessarily an easy problem. And that's exactly what knapsack is, right? I tell you what the sum is over there which is s and I tell you what the weights are and it's hard for you to figure out what the bis are. Right? So, now you see why this didn't work. Right? So, you have to have a situation where in the average case whatever you produce for the cipher text here right? You're sending out the cipher text according to the crypto system which is 174 and you want to make sure that that the adversary can't figure out that this is actually 93 plus 81. Right? Amazingly people thought they could build systems using this assuming these numbers were much larger than they are here, but that that certainly wasn't the case because in the average case you end up being able to break these systems.

**[1:23:01]:** Um the last thing is of course you don't want to necessarily solve the hard knapsack problem associated with um uh with this. So, what ends up happening is you end up using n equals 31. So, if you want to decrypt you have n equals 31 and m equals 105 and what you're going to do is take this and multiply it by n inverse mod m. All right? So, um rather than doing times n mod m you divide by n mod m. And you can do this operation relatively simply and you can go back from 174 uh to uh uh to figuring out what the actual message was by uh uh computing this this quantity. All right? So, I'll stop there. I didn't quite get to everything that I wanted to cover, but uh take a look at the notes, get a sense for why the difference exists between NP-complete problems and problems that were used in crypto systems and happy

**[1:24:07]:** to stick around and answer questions.

**[1:24:12]:** Is this a non
