ZK Hack Study Group – MoonMath Manual 2024 – Week 1

Transcript

yeah can you guys see my screen now okay okay okay let me start with some public key cryptography let's go so um uh after you learned the Triple M uh chapter 3 you have pretty good foundation for learning public key cryptography you know so I think it's pretty nice opportunity to to include it here uh the main reference for this talk is uh introduction to mathematical cryptography the book also uh the cryptography course by dan bu okay so cred go to

them so first we are going to review some mathematical background um some pretty important uh Concepts zma MZ which is the set of uh from Z to n minus one right it is the ring of integers module M uh you can do two binary operations in a ring which is addition and multiplication so they are denoted as way oh nothing um so for the notation usually I prefer uh Z mod and Z right but some people just write ZM so they are exactly

the same um so this notation uh mathematically it is the qution ring of Z by principal ideal mg but what does it mean it doesn't matter you will learn more about that in chapter four oh wait I I I can't hear anything oh wait can can you just type type in the wow sorry about that oh I thought is a question no

okay let me continue so uh for example uh Z mg and example is when the m is five uh you have zma 5 Z right so it only has five elements which is uh um 0 1 2 3 and four and you can do addition and multipli uh and multiplication here both in mod five right so a course bounding concept is the unit group um which is just adding a star on here so zma MZ star means you pick all the co-prime

elements with the modulus so gcd am equals 1 so these are the elements that have modular inverse in zma and Z so the elements here are called Unit and this uh this group is called the the unit group right uh for example Z 24z you have 24 elements from Z to 23 um for the unit group you just have a few elements these are the elements that have a modular inverse right so 24 case is a composite so not all elements have inverse but for zma pz in in particular

Z 70 case every element other than zero has an inverse so the zal 70 unit group is all the elements from 1 to six you can see the number of element is like P minus one where P equal z uh I mean p equal 7 so this uh this is like a special case which is very important to understand right a more pz case uh moving on the zop pz is also denoted as FP which is a finite field uh this is a theorem you have to prove but but but I will omit that you

know um zma pz star is also denoted as FP Star right so this notation they are same they are same and they are the same okay uh do we have question so far no questions I'm going to continue okay so a super important theorem it's a firmalo theorem you will see that a lot in cryptography uh the theorem says like uh PBA Prime so pick any element from the uni group of zma PG you will have this x

to the P minus Oneal one M right this is a way to to compute um any element from the unit group to the p p minus one power right so for example in P equals to five you have uh 3 to the 4th equal 81 which is Mod Five it becomes one right so uh this formula holds for every element in the unit group so for the application of format little theorem you have uh you have many applications but I'm going to talk about two of them so for uh first one is you actually can compute

modular inverse with u formal theorem how is it done is uh you take the statement from the formula then uh factor x out right you factor One X out and then multiply X inverse on both side uh X inverse exists because uh every element in m p has inverse other than zero right so um in the end you will have a formula for computing in modular inverse in m p so this is a Formula you can do that but it's less efficient than you cing algorithm so in general case you CLE uh

I mean extended equilibrium algorithm works for all numbers so for Malo theorem you can only do the mod P case not mod n in general where n might be a composite so the other application of formal theorem is uh you can generate a prime this is not uh recommended but theoretically you can do it so how it works is for example you want to gen generate a random P for example in RSA the length is ,24 uh your goal is to uh generate a large random Prime first you pick pick any integer not

necessarily a prime just a random integer from this interval two to the, 24 and ,25 minus 1 you take any integer from the interval you try a form a theorem on it with base two to the P minus P minus one power if it uh the result is one more P you know that P is a prime otherwise you just repeat actually there's a a a solow thing here is for my little theorem never says the only I mean uh you never know the p is actually Prime but with high probability that it

is prime so there's a theorem you can prove is uh getting a false positive uh the probability is negligible so you can uh so I mean the the algorithm is trustworthy but not 100% you know uh but the probability of getting p is a composite this way is super small so we can ignore the the the fading case you know let me see the questions uh yes foral theorum has many many applications I'm just like randomly Pi some

yeah and yeah I'm sure is it works for exponentiation yeah okay so moving on uh let's discuss the structure of the unit group in the m p case so there's a theorem by Oiler saying uh the unit group M my P is a cly group so uh so what is a cly group it means there is a uh is a generator in the set which generates everything so uh the identity element

one is just G to the P minus one therefore in the set we don't include this element because one and G2 P minus one they are equivalent right so um the zma pz uh unit group contains elements of one generator generator multiply generator you know just keep multiply G until you reach to this and then you mul multiply G one more time you go back to one this is a cly group you can visualize as like a clock you know uh so you just go one Circle and then another Circle another Circle they just repeat themselves right so G

is called the generator of the unique group for example uh take p p = to 7 case three is a generator because you can compute 3 to 1 3 to2 3 to 3 everything it covers everything in the group so there are uh Z zma 7z has seven elements zma 7z unit group contains uh P minus one element right so six element uh using three as a generator covers everything so they are all distinct right so uh three is a generator but it doesn't mean every element is a generator for example if we take two we

can see uh if we take gals 2 then the thing just repeat themselves so one 2 4 1 2 4 it only covers one 2 4 it doesn't cover the other elements so two is now a generator okay and moving on a very important application of the elementary number Theory we learn is orer five function so this is using RSA heavy right so I'm going to introduce it here um what is the five function five function is the number of element in the

zma andz unic group so so this thing is pronounced like the number of so the number of elements in this unit group is to um they are the same right just a number in this set the set contains all the element that have co-prime elements right so for example we can compute five of 24 equals eight we just I think we did it somewhere somewhere about okay uh I think here right there are eight

elements so five of this uni group is eight you can see eight elements here um for the SE z7 Z case you you will have 5 p = p minus one this is pretty important this is using RSA right uh because every element has an inverse every uh so every element has a co-prime prop property so this holdes in general uh some computational discussion so how to compute more complicated F if the number

is p to the a where p is a prime you have this formula okay so you can Factor P2 da out and it becomes like this this is super easy to compute right you also have the the I don't know what is called feels uh I think it's called some some linear property you know so five of a * Bal 5 a * 5 b oh yes I bilinear pairing okay so so for example if we take uh a is a prime B is a prime so we have five um P * Q equals to uh P - 1 * Q -

one yeah that one is using RSA right so for a more General case uh by fundamental theorem of arithmetic you can Factor any integer into a like the product of prime Powers okay so this uh uh the theorem implies you can Factor everything so let's do some simple algebra and Factor P1 uh P1 to the U1 out and then you just Factor this out Factor this out and move everything to the lab then this thing compus to n

right so in the end this is like a general formula for computing uh f n when n is any positive integer so there's also a important uh theorem by Oiler saying uh pick any element from the unit group then x to the FN power equals 1 n you can try that with a few example you know this is always true okay so that's the end for this subsection do we have any question uh what's the name of

five what's the name of five the name of five is five this is called five oh or is called like the toan function I I just call it five function yeah yeah yeah uh I think in textbook yeah something like fire five function yeah yeah yeah yeah the name of fire just F okay no question so far so let's move on to Dy Helman so this is a pretty short introduction okay so uh you know in traditional symmetric crypto

cryptography you will have a secret key uh so Alice and Bob they will be using the same secret key so the question is for example Alice and Bob are two people on the internet they they don't have a reliable way of key uh of exchanging the key you know so they have to keep the secret key secret um so before D Helman you you will have like a third party to do that you know you have to give the key to the trusted uh third party and then they distribute the key to Alice and Bob but ify Helman solve a

problem uh that you don't have to uh rely on a third party you can just let Alice and Bob communicate with each other and then following this algorithm they can exchange a key on the internet which is a and uh like insecure channel right so uh in the key generation phase there says uh you still uh you still have like a third party publishing a large p and a uh like a generator G so this phase you can think of as a uh like a government uh agency they post like a standard you know you follow the standard you have to trust the standard has no back door so um

the key gen phase is I you follow the standard and then this G is a having a large Prime order in the the uni group of the the zma pz field uh so that they can just BR force it right you have to have a large Prime order so once you decide uh what PNG G is Alis and Bob simultaneously Al Alis Pi a secret a so this is the the secret key of Alice this is uh probably I shouldn't call it secret key you know it's just like a secret uh large integer I think right so L is compute capital aals G to

a m p by compus Bal to g g to the p m p so there is some kind of symmetry going on you know they are just like using the same formula and then over the internet Al send a to Bob and Bob send b to Alice they exchange uh the the encrypted thing and then Alice can compute B to the a m p by comput a to b m p so another symmetry so uh we claim that in the end they have a same share secret so this

number is the same as this number how to prove it super easy take from uh capital B to the a so capital B is g to the B power G to the B to the A and because A and B are just integers uh they are communative you can swap the order and then go back go back so you prove they are the same so in the end Al is and Bob we have the same share secret use a simple simple algorithm any question with that oh no I'm not going to talk about

the broadcast attack yeah that one is yeah that will take too much time uh yeah I will probably go like more uh 20 minutes more Maxima yeah yeah but if you guys interested in the I I can cover in the next session maybe you so uh the security of DV Helman uh there is a problem name d Helman problem DP oh not oh wait wait wait not the lp the HP the lp is a theare log problem uh so let P be a prime and G be an

integer this def problem is just a formalization of the the the protocol we just talk about right so uh for like if stubber Eve she cannot compute uh G to the ab power based on capital A and capital B yeah because over like a internet if can just capture the communication between above right so um Eve Knows A and B which is g to the a g to the B she knows these two equations but she has to solve the

discre log problem in order to recover either A or B to compute the final share secret which is g to the ab power right so uh the challenge for Eve uh is she has to solve the this G log problem so this is a passive attack scenario right so uh in a passive attack you can assume the is secure but in like active uh active attack for example so this guy will be named like malery right so malery will be the man in the middle and intercept this communication and provide

some some fake exponent here you know so so and manipulate the the protocol D Helman is vulnerable to to to man in the middle attack yeah but that's another story we are not going to investigate that today okay so any question about that no questions maybe okay so no questions on the com right we all understand everything right let's move on to RSA then oh wow this one is pretty

long okay so uh a little bit background recall that we just talked about for my little theorem it says for any Prime P you know you have this a to the P minus uh P minus one power equal one p of course uh this case only holds for the case that P does not divide a because if p divid a you will have a equals to zero for everything and a raised to any power is still uh I mean zero here you know zero z z zero yeah yeah zero here um so for my little theorem uh is only

for Prime P module P case so that's uh so is the theorem true for non Prime M so composite M case so in general the answer is no but uh for learning RSA we can generalize the format theorem to the case where m equals P * Q where they are two distinct pre and so without proving the theorem first we can just go over to examples one example is oh no I mean just one one one example here so uh for example uh M = 15 15 = 3 * 5 so p = 3

and Q = 5 uh in such case you can and try that a to reach to the fourth power uh so about like half of the elements satisfy this equation so the other half satisfy this equation and you can see like a pattern here is when the gcd of a and 15 = 1 so they are all co-prime you will have something similar to formal theorem but not the others you know you can you can kind of tell the pattern

here so the idea behind this is just you can say uh basically this equation is equivalent of saying 15 divid uh a to 4th minus one okay so they are kind of equivalent and you can look at the the decompositions where uh m 3 and M 5 case you can translate the the m 3 case into 3 a 4 minus one and this is 5 a 4us 1 if we can prove that they are true then combining these two information we can

say 15 divid 8 to4 minus one which is equivalent saying uh this equation is true right uh so you can verify that a little bit um so for the equation one the mo three case you can use format theorem to say a to four is a square then Square again and inside the parth parentheses we have a p minus one power and by format this is one the other equation is easier to prove this is just a to the P minus one power so you can use like

formal theorem twice to prove um the decompositions are true and then the the original statement is true right so this is the idea and yeah this is true if you can prove that uh the thing is a multiple of P minus one for one decomposition and then the other right so you can combine the information and prove the the original statement so in general you will have this big Oiler formula for p *

Q so basically yeah yeah just this equation p and Q are dising prime just in RSA and uh G satisfy a certain condition and then you can have something similar to a formal proof it is like a generalization but is only for the P time skill case uh formal theorem is not true for the for General composite and you know so yeah this one is a nice thing to know uh it will be used in uh the RSA proofs but yeah it's not super important if you don't

understand you can just SK it uh so any questions so far wow what are you guys talking wow RSA meme oh my God what is this ah anyway I'm going to continue so uh the security of RSA relies on solving the congruence X ra to the E power equals the cyer tax m n where n is p * Q so there is a misconception that people always say oh the difficulty of RSA relies on the factorization of

integer that's perfectly true so be uh because if you factor in into p and Q you can compute the the oiler F thing you know you can break RSA easily but in the original statement x to the E is the encrypted message so this is the the uh uh the expression for for the for the encrypted message which is the sephar text okay so if's job is to compute the E the the E square root yeah because we are solving for x right now

now so the main TX of the the attacker is to recover X is not Factor n although factoring n can help breaking the system okay um so there are a few things to talk about first if n is prime it is pretty easy to recover X so basically the proposition is this one uh is wait hold on okay so um this proposition is a formalized version of this statement so you cannot have n equals to I

prime okay so yeah if N is a prime it is super easy to compute the inverse and yeah let's say like for example just let this P equals n and then you will have D * eal one mod n minus one because you already know n so n is like a public uh public information you can get from the internet you know so you can easily compute this modulus and then do the modular inverse computation and then you recover this D which is the the the decre uh the

decryption component in RSA right so first thing n cannot be prime so n must be uh the product of two large primes P * Q so uh yeah I'm saying here that attacker if the attacker can Factor the modulus then is super trivial to break RSA because once I know p and Q I can compute the five function the F Nal P min-1 * Q - one we just proved right so after that I got the F

information I can come here and say oh so this is f in so I can just compute the modular inverse this is super fast right I can compute for D which is the de uh the decryption information and and I can uh do that on C which is the SE text so this so the idea is once I factor in is it is super trivial to to recover the message right so this proposition is just a formalization of the statement here so don't worry about so this one kind of uh proves the correctness of RSA because you have to prove that when you recover D you have to have a unique solution

otherwise it becomes like a non-deterministic algorithm right so for for encryption we want to like uh uh decrypt one Seer text to one PL text we cannot have multiple Solutions so so so this proposition proves that it has a unique solution so we know that one SE has corespond correspond to one plint Tex right so uh here is the uh the the actual uh protocol of RSA okay let's go through that uh Bob Alice and Bob talking to each other first Bob choose a secret primes they

must be large large primes p and Q okay so also Bob picks a encryption exponent e which sa satisfy this condition why is that it doesn't matter it has something to do with this proposition right so has to pick a special e um then Bob publishes uh the the public key pair NE on the internet so n is the product of the large primes p and Q they must be random also right uh random primes uh nals P * q and also e this is the public key so this goes on the internet the security of this is

um relies on the factorization hardness right so once I publish this on the internet I assume attacker cannot Factor my end in polinomial time right so so so they are secure uh also e has nothing to do with the decryption so I can safely publish that on the internet right so after that uh Alice we go into the encryption phase Alice Picks a PL text uh M so this is the secret message she wants to send to Bob so what Alice does is she used a b public keypad which is n and e i compute a saer text super simple

it just write uh like reads the message to the E power and I do that in module n so n and E they are information provided by Bob's public key so I just use his public key and Compu my sa text okay so after that I send the sa text back to Bob so this is the the encrypted message I send it to Bob okay so when I send this uh Cipher Tex on the internet uh it can be seen by anyone so for example attacker Eve she can capture the S text but this is pretty secure because she has to compute the E root of this

congruence and we assume this is hard because we don't have a uh like division algorithm for computing the East rout uh so um when Bob sends this public key to Alice he assumes the hardness of integer factorization so this information he assumes uh this information is secure okay so when Alice sends the safe attacks back to Bob she assumes attacker cannot do like taking the East root from this congruence okay so that's two hardness assumption here okay so in the end Bob Rees the CER tax

uh he can compute D which is related to the the the the E is the encryption thing right so she can I mean he can compute that why because Bob has information about p and Q so this one is like a trapo function so what is trapo function it means uh when I have a certain information I can compute the function but without the information it is impossible to compute it right so the reason why Bob can compute the decryption exponent D is he has information of about p and Q if any

attacker wants to compute the same thing uh attacker has to do the factorization which is assumed to be hard right so in the end I can compute I'm Prime which is uh I I I raise the saer tax to the power and do that in mod n the recovered uh message should be the same as the original message because it is proved in this proposition okay so uh do we have questions so far wow oh I see the question saying if we pick three primes then then compute N I

think is not safe because uh uh for example you have more more primes that means each prime component is smaller right so it is easier to factor everything uh that's what I'm thinking so so for example there's a famous uh CTF challenge saying uh for example we have n equals like the product of 10 primes then you can just go on Factor DB like the the factor database and and look uh like look up right yeah because n is fixed if you have more component making up that that

n then each component is smaller okay um so this is the last part of this talk wow we we we are hour and 20 minutes already okay let's go over this fast so um the security analysis I just covered that actually so the setup is PQ are two random large primes and is the product of them and e e is the encryption uh uh the exponent and C is the cipher t and they are represented in integers okay so the problem is I have to solve the congruence x to the E power equals

the cipher tax mod in I need to recover X so uh oh wait hold up okay so uh recall that in the Dy Helman problem we were assuming that the discrete log problem was hard so uh you can see kind of a symmetry here you know we are dealing with congruences in both Dy Helman and RSA but in Dy Helman we worry about the exponent in in the RSA the exponent e is actually public we only worry about the

base number which is the the message X right so yeah it's kind of fun here to to see like a symmetry between two two protocols uh so in RSA case we assume taking the E root of this congruence is hard uh that's the security assumption uh I just talked about this so Bob if Bob knows p and Q which he does and he can easily solve for x so this is the trap door function I just talked about right so without this trapo function so for any other people uh for example teer called Eve uh

she she does not know p and Q so she cannot solve for x this is the trapo uh function difficulty uh the Assumption made by the RSA crypto system so if you can break that assumption RSA system is broken okay and have a little bit more discussion on on the r is a the first one is the choice of e so it is obvious that when E equals one Cipher tax equals PL tax so this one has no encryption at all you can just take that cyer text it is actually in

plain text format okay so e equal 1 does not work uh how about E equals 2 in that case the gcd of e and and five five n is not one so here we are making a condition that saying when you pick e you have to satisfy the E has to be co- Prime to f n right so eal 2 does not work how about eal 3 it works uh in fact I think eal 3 case is pretty secure uh but some people will argue that although they cannot

come up with like a an algorithm to tag the equals 3 case you know so this one is pretty secure but it's not commonly used so what is commonly used is E equals to 65537 so this one is commonly used this is the like the go standard of RSA you know and so when you if you are building uh like a lib you you want to follow this standard so just pick this e okay and the second remark is if Eve knows p+ Q she can break RSA so why uh we can see that uh the the

objective of Eve is Computing this decryption exponent d right so the formula for D is this so this is five uh f n d = 1 mod FN we can expand that formula a little bit uh you can see it is p * Q minus P minus Q then you group them together is minus parentheses p plus Q uh P time Q is just n this is a public knowledge you have that right so if you know the answer of p plus Q it is equivalent to breaking the RSA system okay uh and also

here's a fun proof that uh I claim that knowing p+ Q is equivalent to knowing p and Q why is that because consider you take a polinomial with some X this x is just a variable okay so x² minus P plus Q parentheses * X Plus P PQ so you can can use that famous quadratic formula to uh to compute that uh uh there are two rules of this polinomial okay so uh yeah you can see p equ to this and Q equals to this or just swap the order

uh actually doesn't matter okay um you can see from the expression that uh p+ Q if you know the information of p plus Q This n is a public knowledge so you can solve for p and Q fairly quickly okay yeah this is just a fun proof that uh saying the equivalence of p+ Q and pnq but uh you don't have to do that because once you know p+ Q you can just compute this F this okay so the last thing for

today uh I think I just talk about this yeah this one is saying uh the difficulty of RSA is taking the the E root is not factoring in although factoring in can break the system as well right so um an attacker Eve she can if she can take each root she can recover this x directly without Computing P or Q right so so that's saying uh if I can compute the E root of this congruence even though I have no knowledge about p and Q I can break the

system so uh if some people just claim like the the security of RSA depends on Integer factorization that's not 100% correct okay so this is what I see on the internet right I capture this message this encrypted message if I can take each route I can just recover message without Computing pnq okay okay so that's all for today uh wow that was a pretty long session okay so for future research I'm sharing this number theory note from uh Stanford apply crypto group also uh I learned many attacks from from Dan bu's

uh paper okay there's a survey paper talking about all types of attacks and uh unas if you are interested in RSA attacks you can go to crypto hack I encourage you to solve all the questions there okay so pretty high quality cpf challenges okay wow that was long session we finished ECC invalid curve deack wow that was long that was long oh my God you are welcome I would like to present this uh wait wait wait let me read this question uh no so e uh ECC in valid curve Act is

not the uh it's not like the well-known signature Mal ability attack no uh the idea is if the attacker no I mean if the code does not verify the points sent by user are are actually on the curve so so you know that uh in tic curve you have to verify thing uh for example the the user sent you a point you have to check that the point actually satisfy the r stress equation yeah other VI Alice can send you some fake points that lies on other curves right so if she decides to do

that she can send you some points from like small subgroups she can repeat that process for for example for n = 2 N = 3 Nal 5 Nal 7 for all the Primes uh recall that in Chinese remainder theorem we say if I know a of congruences in that form all the modulus are co-prime then I can solve for a solution in the in the large modulus which is the product of everything so in that the curve attack the idea is just I collect a a system on congruences and then each modular pair I

mean each modulus pair is co- Prime and then in the end I can solve for the answer so the idea is if I repeat that process for large enough times I can get like a huge list of uh uh congruences right so the product of all the modulus they become a huge capital N so my solution so the solution is the servers private key the private key compared to the large modulus it is actually small so I want to make sure that the the private key is smaller than

the modulus so when I solve for Chinese Remer theorem the secret key is just that key you know yeah do you understand that is like um so my my modulus is large my private key is relatively small so when I Sol for that congruence my solution only in the first Circle so without the plus k d plus K in part you know so so so that's the idea of the invalid curve attack yeah D buet is a legend yes I have a question about your final

remark of wait wait I I can't hear anyone clearly please just leave your question in the comment yeah I think I'm having some uh some internet issue next time I'm going to let someone else record a video yeah yeah today is like a messed up wow I'm not Legend far away from that but I'm becoming a legend in the future so people come complain about the B course is too theoretical I don't

think so actually uh I I think is is pretty applied already because I have taken more theoretical cryptography class yeah so so you can Google that for example something like the the IM cryptography class taught by gaser that one is more theoretical yeah so yeah then bu course is super helpful I encourage like like I recommend you to to do it like right now yeah yeah that one is a must uh also probably

uh the book called The a mathematical introduction to no I mean uh an introduction to mathematical cryptography that's my main reference okay okay I see question saying uh if Eve can solve for the congruence that mean you can bre the D no no no no no no they are different uh think about this so in RSA we are solving for X okay we are solving for the base number X we are not

solving for E because e is already public okay so in RSA the hard problem is you can compute like compute the the E root yeah I will just type in the in the comment so in RSA the the hardness is cannot compute e Square [Music] e SC in D Helman is you cannot solve for the the exponent to

a yeah so they are distinct problems even though you can solve the RSA problem doesn't mean you can solve the V helment problem plus the name of problem uh I think in RSA it called the the the problem is modular and through in D Helman it is just discre lock yeah solving crypto hack challenges are

pretty time consuming so yeah I never have time for that okay so seems I don't have more questions how about we call your day and see you guys next week yes I'm going to share the notes yes yes yes I'm going to uh upload it to my GitHub and share the links yes of course

okay I will see you guys next week