# R11. Cryptography: More Primitives

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

## Chapters

- 0:00 — Chapter 1 (0:00)
- 1:42 — Chapter 2 (1:42)
- 4:18 — Chapter 3 (4:18)
- 6:58 — Chapter 4 (6:58)
- 8:27 — Chapter 5 (8:27)
- 9:10 — Chapter 6 (9:10)
- 11:27 — Chapter 7 (11:27)
- 12:27 — Chapter 8 (12:27)
- 13:55 — Chapter 9 (13:55)
- 15:35 — Chapter 10 (15:35)
- 17:39 — Chapter 11 (17:39)
- 20:07 — Chapter 12 (20:07)
- 21:43 — Chapter 13 (21:43)
- 23:23 — Chapter 14 (23:23)
- 25:26 — Chapter 15 (25:26)
- 26:10 — Chapter 16 (26:10)
- 28:10 — Chapter 17 (28:10)
- 29:51 — Chapter 18 (29:51)
- 35:25 — Chapter 19 (35:25)
- 37:31 — Chapter 20 (37:31)
- 38:12 — Chapter 21 (38:12)
- 39:55 — Chapter 22 (39:55)
- 41:51 — Chapter 23 (41:51)
- 42:45 — Chapter 24 (42:45)
- 45:41 — Chapter 25 (45:41)

## Transcript

**[0:00]:** the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT open courseware at ocw.mit.edu all right so finally it's our last recitation and finally it's my favorite topic cryptography cuz I work in this area so I have probably a little bit more than what's required to tell you uh so this recitations is uh like say more

**[0:50]:** Primitives so uh we'll introduce several more Primitives that may be useful to your future work or study and and so the first one is digital

**[1:10]:** signature so we have briefly mentioned digital signatures in the lecture but mainly as an application of hash right so now I'm going to introduce it as a standal along primitive so as you may have already known digital signature um is used for verifying message authenticity and it's a pair of

**[1:42]:** function s and verify so sign takes a secret key and a message it outputs uh uh signature which we refer to as Sigma and verify takes a public key a message and a signature and output um either true or false I either accepts the signature or reject so uh we use secret key to sign and public key to verify that means so if I want to send a message I should be the only one uh who is able to sign it and everyone can verify that this message indeed comes from me right so what properties do we want from digital

**[2:47]:** signatures yeah any any thoughts on

**[2:54]:** that go ahead a signature and a message how to get the super key okay that's definitely one yeah uh I'll put um gen more General uh description of what you just

**[3:15]:** said any other answers only one signature

**[3:25]:** mhm have one sign okay uh so what's her name um e says one me a message should only have one signature okay let's think about whether that's necessary so if if my algorithm is a randomized one that uh for for the same message I output many possible signatures so yeah why is that bad so for any of them they will verify if that's how my algorithm works I think that's that's fine that's okay it's not a bad thing actually randomized signature uh is considered more secure they are less

**[4:18]:** efficient any other

**[4:24]:** thoughts you about speed at all it that's definitely one but we haven't have we haven't got any scheme yet so we care about functionality first there are faster signatures and slower ones okay so the first one is actually very trial we first want correctness what does that mean that means if this Sigma is indeed generated by this design function that verify better outputs one right otherwise it should call output zero that's actually the first and the most basic property we want okay I I don't want to write it because it's uh okay so the other one uh so your answer is very close that you don't want to extract the secret key but to make it more general what we really want is unforgeability

**[5:36]:** that means if I have the secret key and someone else an adversary who does not have the secret key should not be able to sign the message to pretend to be me right so they should not produ be able to produce M Star Sigma star such that okay such that it verifies make sense uh so what you said is a special case of this so if they can extract somehow extract the secret key then of course they can forge my signature on any other messages right but we do want to also prevent the attack where they do not they cannot EX the secret key but they somehow can forge another signature but usually we want to make the uh adversary adversary more powerful because well then we have higher confidence that uh we won't be attacked so an adversary it's totally reasonable for it to see a bunch of messages from

**[6:58]:** me right because I am signing messages and output it to the world so an adversary may have seen some of the message signature pairs I generated right but still we do not want it to create a forgery then how is that defined because he can definitely send one of these back that's a valid message signature pair so our unforgeability requirement is defined to be uh he should not be able to send such a pair where M Star is different from any message he has already seen there is no way to prevent the adversary from sending one of the message signature pairs he had seen

**[7:55]:** before okay so far uh pretty St

**[8:02]:** forward now how can we get um digital signatures so in the early days uh researchers and it's actually great computer scientist they propose digital signature can be

**[8:27]:** implemented as the inverse of public key

**[8:38]:** encryption what does that mean uh so I use RSA as

**[8:46]:** example so RSA encryption is m to the E mod n right decryption is C to the D mod

**[9:10]:** n so the first attempt is we will just use this as our sign function and use this as our verify function okay so now this symbol is a little bit confusing so now I'm signing a message uh I call C okay okay let me let me actually change it this is RSA encryption I'm going to transform it into signature scheme where sign signs a message and verify raise the signature Sigma to the power of v and checks uh whether or not I get back my message

**[10:03]:** so this actually makes a lot of sense why because think of it think of M as a cipher text then if I decrypt it and then reencrypt it I should get back my Cipher text right so correctness we have correctness and why is it unforgeable because an attacker does not have the secret key so he should should not be able to decrypt this this m here you cannot run this algorithm right that's the reasoning behind it so far so

**[10:52]:** good but unfortunately it is broken and so I'll give you say several minutes to think about it can you come up with an attack a forgery you can see a bunch of messages and then output a forgery for a message you have you haven't seen

**[11:27]:** before

**[11:43]:** is the algorithm

**[11:57]:** clear

**[12:27]:** that

**[12:36]:** uh can you speak louder if you take the product of any messages exactly okay so if an adversary has seen a bunch of messages because RSA has this Sometimes good sometimes nice sometimes bad property that it's multiplicative homomorphic or well use a less fancy word malleable so if an adversary sees this messages it can set M Star to be M1 * M2 and sigma star to Sigma 1 * Sigma 2 right you can check this is a valid signature message signature

**[13:23]:** pair right you take this entire thing raised to D and that's the raised to D individually and then multiply together and that's exactly this message

**[13:36]:** here Attack One okay there's actually another

**[13:42]:** attack that's even simpler and tells you the scheme is even more

**[13:55]:** broken so all I want to do is that come up with a sigma when it raised to e that's equal to M right okay so I'm going to select the sigma

**[14:11]:** compute M Sigma ra to e because e is my public key mod N I can do that right and then output Sigma M oh sorry M Sigma okay I select the signature first and I raise it to the power of E I get a very strange message but doesn't matter that's my

**[14:41]:** forgery okay so now you can see the scheme is well basically totally broken but they actually come from our well several renowned scientists why is that the case because actually that definition didn't exist when they were trying to when when they were working on this problem and so that definition looks obvious today but it's actually not obvious at all and I think it's this uh this algorithms come in the 70s 78 and in 82 gold warer and mikali two professors from MIT proposed the definition for Signature encryption and basically everything in cryptography and they want another touring word for that okay so let's try to fix

**[15:35]:** it any any

**[15:41]:** ideas we do not want to change the uh framework let's still use RSA and combine it with some other primitive you have seen to try to fix it

**[16:27]:** for what do we want to do we want to break this uh multiplicative

**[16:36]:** property right and we want to break this or this step whatever it's called go ahead can we

**[16:49]:** change change this end yeah okay right now just to remind you it's a product of two primes okay PQ mhm it's a product of two two prime sorry that's how RSA works so what's your idea uh go ahead we get the function it exactly uh okay let's just make a small change so s will be hash of M raised to D and verify will be yeah just ver oh okay let check whether has of m equals signature ra to

**[17:39]:** e this indeed fixes the uh these attacks why because now you need well if you do this hash of M M1 times hash of M2 is not going to be hash of M Star right hash is supposed to be Sol random that's not going to work and here uh what the attacker need to do is to find Hash of M such that it's ra uh Sigma raised to e it can still do this but it does not know what this message is because of the one-wayness of hash function if we use a good hash function there then it indeed fixes both the attacks but we have seen in the lecture that this hash function also needs to be Collision resistant right remember that okay question isn't the message public yeah the message oh okay good

**[18:46]:** point oh no but okay you are talking about this attack right so the attacker needs to find the public message but all you can do is select the sigma and raise it to e that's going to be it's hash of M right and then he cannot figure out what this m is what about the other way I mean if he has two messages he can still get and then get uh okay so he then he gets hash of M1 he gets hash of M2 but you need to find the M Star such that it's hash is the multiplication of these two and yeah he does not know how to find that message

**[19:33]:** okay so if the hash is uh not multiplicative one way and collision resistant then it seems that we have fixed all the attacks we know however how do we know there are no other attacks so actually indeed this is a good idea um we have several national standards that just use this but slightly differently I can well it's just this is just for your

**[20:07]:** information and so there's a standard called NC okay whatever X through 9 3.5 sorry .1 it uses RSA on this

**[20:27]:** weading

**[20:33]:** so it takes the hash of the message and pad with this uh Hax string well and prepend it and pend another Hax string okay why why do they do that they don't know either but they just think it's probably more secure than only using a hash right there's another standard that has a different string and a different string here and okay doesn't matter so that's indeed a weakness of these types of approaches so their security is what we called ad hoc they do we do not know how to break them but we do not know how to prove they are secure either yet that's what people do in practice so unfortunately that's uh all I can tell you today so how not to construct the digital signature I cannot tell you how to construct the secure digital signature because that's the that's out of the scope of this class and it's uh major Topic in

**[21:43]:** cryptography any questions so

**[21:52]:** far go ahead the function here is the one way uh yes yes it's one way Collision resistant and so what is theuse of us the we just only function then um okay good question so okay let me let's be clear what you're saying okay okay can you answer your own question so my question was why do we have to use the r why we have the function mhm so ADV

**[22:31]:** yeah how how does it create the fery yeah just answer your own question let everyone else know maybe they have the same question sorry answer your own question so my answer is so aders you can't just choose random message and hash it yeah what's the problem the problem is that a hash function is a public function that everybody can compute right so the attacker just choose a message compute this hash and so using the hash is it's not a signature but good point I'm actually coming to that uh so so far we have seen three major

**[23:08]:** Primitives private key encryption public key encryption and digital

**[23:23]:** signature so if we categorize them little bit so these two are asymmetric key right they have public key and secret key this one is symmetric key and these two are uh for

**[23:48]:** secrecy they are trying to hide the message and this one is for integrity meaning the message is uh what the sender sends okay so you can see we are missing one primitive here right what if the two parties they do share a secret key and uh one party wants to verify the other party the message indeed comes from the other party okay so indeed we do have a A Primitive for that it's called message authentication code so it definition is basically exactly the same as uh digital signature okay um just going to change it here except that it has only one key so the sign function is replaced by a Mac and there's no notion of secret key and public key we have only one key and how do we verify okay okay so verify function basically just becomes uh the other guy also recomputes the Mac of the message and check whether the that's the

**[25:11]:** signature so verifier just

**[25:18]:** recompute and

**[25:26]:** compare okay correct uh we also want correctness we also want unforgeability and it's defined exactly in the same

**[25:37]:** way now actually I would have asked this question here uh is Hash uh valid

**[25:50]:** Mac the answer is still no right because Mac is a public function everyone can compute and it's trivial to come up with a forgy okay so thank you for asking that question but the hash is actually very

**[26:10]:** close

**[26:18]:** Okay how can we get a message authentication code so several ideas can we just hash the key concatenated with the message right then some other random attacker who doesn't have the key does not know how to compute this thing right that's a reasonable idea but well if we can do it this way how about we do the message concatenate with the key or if you want you can do key conc with message and then conatin with the key

**[27:00]:** so it turns out uh this doesn't work for some very Advanced reasons and this one may or may not for sha one uh it doesn't work unfortunately and for sha three that's the replacement for sha one and Sh sha two it actually works so the simple simplest Mac we can imagine is just to choose shot three as the hash function and input uh is the key and then the message okay but not the other way that's also just FYI purpose oh by the way there's another reasonable thought that is how about we encrypt the hash right now everyone can compute the hash but they don't know how to encrypt if I use say secret key encryption oh this turns out to be wrong as

**[28:10]:** well okay that's digal digital signature and Mac uh but one cave it here our unforgeability is defined this way a little bit strange but makes sense uh but it indeed has some weak Ness in some applications so imagine say I sent you a message uh today's recitation is cancelled and it has my signature on it right so you can verify it indeed comes from me but once I sent that message every of you has that message right so next week one of you can send that message again saying today's recitation is canceled then you have no idea whether it's indeed me sending the message again or someone doing a April four day joke so how do we how do we prevent that well of course one thing I can do is if I'm smart I'll say today like parenthesis May the 8th recitation is canceled right then you cannot repeat that message but uh we

**[29:14]:** want to protect human dubil right that's the whole point of uh cryptography so one thing we could do let's see

**[29:42]:** very simple modification when I sign a

**[29:51]:** message I'll sign one concatenated with my message right next time I sign two concatenate with my message and then three four and just have this counter that keeps incrementing okay that Tri fixes so you can verify if you receive um uh the same message with the same counter then you know it's someone else who is resending it okay so that's uh one thing we need to do for Signature in practic practical use now uh consider another totally different application so say I think everyone uses Google Drive Dropbox something like that right you store a bunch of

**[30:48]:** files um well this Cloud Server and you you you are here you have a say cell phone and you can access your files but how do you know when you read a file it is indeed your file unmodified how do you know maybe Google messes with you or there's someone in the middle who changes your file so okay usually most the people do not care about that but well in cryptography we do care about that so in that case Mac and signatures do not help us why because if you uh just store a Mac uh alongside each file what went

**[31:50]:** wrong um okay but if they modify the file they do not know how to generate a Mac for their version of the file right but what they can do is you have this file and then you come and write it and you generate a new Mac when you read it they give you the old version that has the valid signature or Mac on it because you generated that for

**[32:20]:** it see uh you all see the problem you haven't seen the problem okay what do you mean they give you the okay so you have this file right you generate the Mac but you some uh at some point you want to update the file okay you want to you update this file to this file Prime and generate a new Mac right maybe then file double Prime Mac double Prime uh in this application we want freshness right when you read this file you want the latest version of the file so it should be the it should be what you wrote there last time right but when you're trying to read the file an attacker can give you this pair right if you check the Mac it's going to match this is also a valid message Mac pair okay now everyone sees the problem okay so what can we do uh well one thing we could do

**[33:19]:** is store all these Macs here on your phone right Mac one Mac 2 a Mac for every single file but if you do that in fact we do not need Mac anymore or we can just use

**[33:40]:** hash okay so I'll say Sigma I'll use sigmas but they mean hashes well this is probably good enough in practice so I'll say these files are X1 X2 X3 X4 and you just create a hash for each of them and store them locally and the model here is that an an attacker cannot modify files on your own computer or on your own phone and then you can download the file match uh Compares it with the latest version of the hash and then you are convinced that it's the latest version right this is probably a good enough solution uh the only downside is that we do have to store a lot of hashes if you need a if you have a lot of files or in our algorithmic

**[34:42]:** terminology we say your space complexity is over n right uh here I mean your local space

**[34:59]:** so can we somehow reduce the space comp local space

**[35:06]:** complexity well one thing we could do is to concatenate all the files together generate a single hash and store that one

**[35:25]:** hash so everything in one try then we do have of one space but there's a bigger problem can anyone tell

**[35:48]:** me uh okay I think I think you are thinking in the uh right thing so how do I verify if I want to I cannot verify a single file I have to download all the files and recompute the hash to verify so the time complexity is o n and also if I want to update this file I have to recompute the hash right that involves again downloading all the files and feed them into that

**[36:25]:** hash and we do have a better solution than both of them which is called a hash tree or merco tree it's invented by mle what we will do is so first for every file we're going to create a

**[36:47]:** hash okay uh okay let me again use Sigma because H is unclear whether it's a hash value or a hash function Sigma 2 Sigma 3 Sigma

**[37:02]:** 4 so I said a h tree and you guess what the what's the next step to do yeah exactly we're going to create a okay Sigma 5 which is the hash of Sigma 1 concatenated with Sigma 2 okay so we do the same thing here

**[37:31]:** so you all know what it is right I don't need to write it and keep going until we get a root

**[37:44]:** hash and then we are going to store this thing locally on this

**[37:55]:** side so what's the local storage complexity of one we only storing one hash locally so what's the time

**[38:12]:** complexity okay so how do I verify MH yeah login yeah how do I verify I need to so first verify if this hash matches and then read this hash and verify whether this link matches and verify whether this one matches and then I'm done right if I want to update I also need to update this hash then it causes this hash to change and then that hash to change but it's always some path in that tree it doesn't affect anything globally question but you're not storing signal uh say again you're not storing signal F I am not yeah I have to go ahead and read it from where from um Google drive or Dropbox so are we sure that that is secure okay yeah so that's that's the next thing we're going to do is this secure or in other words can an adversary changes one of the files and somehow maintain the same root

**[39:16]:** hash right that's your

**[39:25]:** question of course we assume the hash is Collision resistant or I should say if the hash is Collision resistant then this hash3 is Collision

**[39:40]:** resistant any

**[39:55]:** intuition oh anyone wants to prove

**[40:03]:** it go ahead so like the root I eventually one of thead will be different because you change it yeah now if you want the root to be the same then the other has to be different but there no I it's hard to find the other yeah correct so okay so uh I'll just repeat what you said but I'll start with the leaf because that's easier for me to think about so say I change this one this block now I claim this hash here will change right if it doesn't then I have found a condition right because this X4 Prime has the same hash as the original X4 okay so if this Sigma 4 changes then Sigma 6 will change otherwise I have found a c uh because this Sigma 3 concatenate with the new Sigma 4 is my C right so same argument either this one changes or I have found a c I repeat

**[41:01]:** the argument on all the way to the

**[41:07]:** root okay any question about that what like changes like two functions for example1 and2 M but uh Sigma one and sigma 2 changes stay the okay so then we have found a CIS that is Sigma Sigma one concatenate with Sigma 2 that's a coll with the new Sigma one concatenated with the new Sigma

**[41:41]:** 2 make

**[41:51]:** sense and com oh so if the conc stay the same that means both of them are the same

**[42:02]:** right so I'm not sure if I understand your question so concatenation is basically just a bunch of bits Then followed by another bunch of bits right if this entire thing is the same that means this part is the same and this part is the same right and if your Sigma one new Sigma one is the same as your old Sigma 1 that means I have found the colation here because you changed it but your Sigma doesn't change

**[42:33]:** all

**[42:45]:** right so lastly um going to I'm going to do a quick review of the napsack problem CU I think in the lecture uh really run out the time and didn't measure and

**[43:09]:** everything okay so if you record the napsack crypto system uh it says we have a napsack problem uh our cor U1 to un and then we're going to transform it okay this is a super increasing sequence I'm going to transform into a general one by multiplying a n and then mod M right so this is a easy problem and that is a hard problem so how do I encrypt I'm going to uh take a subset sum which is MI wi where Mi I is the I bit in the message so how do I decrypt I'll take this uh transform this s back to the to the super increasing domain by multiplyer inverse of n okay so that's going to be inverse of n multiplied by this Mi I wi so that's how I encrypted and then each wi is n times

**[44:40]:** UI so good okay so that gives me Mi itimes UI Sigma of course every step is modulo M so the first thing I'm going to claim is that M has to be larger than Sigma UI right if that's the case then the T my T is just this uh subset sum right so if I solve this napsack problem I get the same answer as solving the original the general napsack problem right if my m is not that large if m is too small then I have a problem because then my T will be this subset sum minus Su multiple of M right then it's a different problem I do not get the same message

**[45:41]:** back okay then uh we have a problem so because we define density to be n over the log of Max UI does everyone remember this part so each UI is in the range of 1 to M or maybe zero to M if I have a bunch of them then Okay this not super rigorous if I have a bunch of them chances are that some of them are uh very close to M right because it's unlikely that all of them are uh small so so this thing is roughly n over log of

**[46:37]:** n so then we have a dilemma if we set M to be a small number then my density is fine but that means all of my UI needs to be small right because M needs to be greater than the sum of them or if all all the uis are small then I have a very limited choices of them then actually an attacker can just guess what UI I chose by a Brute Force algorithm or or something like that and if my I choose M to be large or if I choose all the uis to be large to choose choose them from a large range then my m is is going to be very large and this density is low and that's vulnerable to the low density attacks and so how low a density is considered low so uh some several people proposed that well based on hers that if this density is less than 0.45

**[47:37]:** then it's considered low density and it can be attacked and this threshold is had been uh improved all right so but while most of the napsack crypto systems are broken there are a few that have so far still the test of time so they are still interesting because napsack problems napsack crypto systems will be much faster than RSA or any number Theory based it's the we are just adding numbers here right and RSA have this operation where m is a 1,000 bit number and E is also a 1,00 bit number and take this exponentiation is actually very slow so nap napsack crypto system are still interesting however their original motivation turned out to be unsuccessful the original motivation is to base uh uh cryptography on the NP complete problem that's not going to work because MP problems are hard only in the worst case and we need cryptography to be hard in the average case

**[48:44]:** why because if they are only hard in the worst case that means there are several instances of the this problem that are hard so either you pick a secret key that doesn't correspond to to a hard problem or you pick a secret key that's that corresponds to a hard problem but everyone else picks the same secret key because everyone wants to be secure that's the reason why it's unlikely to get cryptography from MP hard problems okay that's all for today's recitation and thanks everyone for the entire semester thank you for your participation

**[49:28]:** can
