Number theory and cryptography

A small recap on some number theory basics and applications on RSA

1. Number Theory and RSA attacks A brief overview of attack on RSA

2. Modular Arithmetic Modular arithmetic or Clock arithmetic is a circular system that increases until a specific point called modulus then rest to zero again. Definition Let be a set of all non-negative integers that are smaller than : where is a positive integer. In order to find the value of integer (mod ) we can use the following equation: where: is integer and is the remainder  

3. Modular Arithmetic Examples: Congruence modulo: To explain it in a simple way lets see the representation for all integers , all integers in slice gives a remainder , we can say that those integers are in the same equivalence class , which can be represented as .  

4. Congruence modulo and Equivalence relations If we looked at the previous chart, we could notice that the difference between any two integers in the same slice can be represented as multiple of 5. We can write the congruence mod as any of the following: for integer  

5. Congruence modulo and Equivalence relations The figure have the following properties: Every pair in the same slice are related We can never find the same integer in 2 slides If we collected all the slices, we will get all the numbers. Which means that the congruence modulo is equivalence relation.

6. Congruence modulo and Equivalence relations Why do we even care whether it’s an equivalence relation or not? It’s simple, so we can apply the equivalence relation properties: (reflexive) (symmetric) then (transitive)  

7. Operations on Modular Arithmetic Addition: Subtraction: Multiplication: Exponentiation:  

8. Modular Inverses In basic arithmetic we know that the inverse of a number since But in Modular arithmetic we don’t have a division operation, so the inverse would be : which is means is coprime to  

9. Modular Inverses Calculating mod inverse: the native method is brute forcing all the number from 0 to until we find a number that makes This method is sow slow and we need a faster method.  

10. The Euclidean Algorithm The Euclidean Algorithm is a quick method to calculate the GCD of two integers. Let’s use Example to describe it: GCD( 270 , 192 ): 270 = 1 * 192 + 78 192 = 2 * 78 + 36 78 = 2 * 36 + 6 36 = 6 * 6 + We got 0 so our GCD is the last value before 0 which is 6.

11. Caesar cipher Caesar cipher is the first substitution cipher ever, substitution ciphers are mainly about mapping the characters into other characters and use this map to (encode/decode) In Caesar cipher we was shifting any number by three for encode for EX: ABC -> DEF We can change just pick any key instead of three and do the same operation, as we mentioned in the Modular arithmetic, we will always do the full turn then back again to the character A

12. Caesar cipher Let’s call then encryption function enc(m) and the decryption dec(m) Enc(m) = for c in m: (c + k) mod 26 Dec(m) = for c in m: (c - k) mod 26 Where: k is our key c is each character in the string 26 is number of characters in English alphabet As you can see it’s so related to figure we showed earlier in the modular arithmetic.

13. Public key cryptography After we learned a basic mathematics, we will start to introduce one of the most used application to secure our communications, which is the Public Key Cryptography. As we shown in Caesar cipher, the same key was used for encryption and decryption, which can be unsecure and if the sides of communication are far away which will force them to share it through a channel, which may lead to leak it and expose the communication. So, in public key crypto both sides of the conversation will have 2 keys, public key and private key, the public key can be shared and the private key remains as a secret.

14. Diffie- hellman key exchange Diffie-Hellman key exchange is a method for securely exchanging the keys of encryption without being exposed to the public channel, it’s named after Whitfield Diffie and Martin Hellman and published in 1976. The method is simple, let’s explain it by example: Assume that alice wants to send massage to bob, and we have eve watching the public channel between them.

15. Diffie- hellman key exchange Now alice wants to share its key without, letting eve know it, so first both alice and, bob will choose a public generator and prime modulus . Now each of them will choose a private key and apply the following: . At this point we will have 2 public keys for each alice and bob and they will send it to each other (until now eve got it also), now alice and bob create a shared secret key and eve will not get it by: ,  

16. Diffie- hellman key exchange Let’s expand those expressions in order to make it simple: Alice: Bob: Alice public key: , Bob public key: Now Alice and Bob will exchange the public keys Alice shared key: , Bob shared key: which will always be the same since it’s the same calculations, why?? That’s easy the what alice did was and bob Now eve only have: and she cannot get the shared key.  

17. RSA The previous way needed alice to generate a shared key for everyone she is contacting with, which can bee too hard and difficult, for this James Ellis, a British mathematician introduced and idea to create only 1 public key and send it to everyone then anyone wants to contact Alice will just use this key. After that, a British mathematician and cryptographer, Clifford Cocks, introduced a mathematical way to apply this concept.

18. RSA Bob will send a message using alice public key and a public exponent as follows: where is the encrypted message Now alice needs to have a private key to decrypt the message such that: Now eve only have let’s see if eve wants to get what she needs to do.  

19. Euler’s totient Euler’s phi function is a simple function to calculate the count of co-primes less than a number . If we noticed the co-primes of a prime number , they will be all the numbers below it since it’s already a prime, means  

20. Euler’s Formula Euler’s Formula states that: Rising to the power then multiplying by would give us Now back to the decryption formula: now we can see that , is co-prime to In order to choose our we need to know 2 important theorems.  

21. Chinese Remainder Theorem Chinese Remainder Theorem states that if we have some numbers: and they are all relatively prime to each other, then for , , , ,….., have exactly one solution .  

22. Example Ok as we can see we have the same in 3 different congruences and we need to solve for , using the Chinese remainder theorem we can create a table consist of Four columns: and their product. Where is our remainder, is for and Now our final is the sum of the last column   3 56 1 168 1 40 3 120 6 35 3 630 3 56 1 168 1 40 3 120 6 35 3 630

23. Fermat’s Little Theorem Fermat’s Little Theorem states that if is a prime number and doesn’t divide then .  

24. Choosing and   There is some constrains on to which are: have to be co-prime with The private key have to satisfy that which means .  

25. Wrap everything up Let’s give a simple example to show everything we mentioned Encryption: Decryption:  

26. Attacks on RSA Now let’s start to interduce how can attacker know our secrets, note that we are not showing that the RSA is breakable, we will show that bad choosing of numbers can lead to recover the private key. Factorizing : Choosing needs to be very careful, there is a lot of services online that works on factorize a huge collection of numbers like factordb , as shown in the previous example we could find just by getting the prime factorization of Let’s discuss some of the Factorization methods for .  

27. Prime Factorization Fermat’s Factorization: named after Pierre de fermat , which represent the odd integers as difference of two squares, Since we can already factor the difference of two squares: And we know that our where are primes, we can write it as Assuming that is odd so are also odd. Now the steps are simple, first we can rewrite as Then we need to find the smallest s.t Then we start to look at the following numbers Until we get a perfect square. Note that this will terminate always since  

28. Fermat Factorization Example Here is a small example to apply our steps, let First find since is the smallest k s.t Then we start to find the perfect square from the sequence we mentioned: (not perfect square) (not perfect square) …. … (perfect square!) Now we can write as Which is our prime factorization for .  

29. Pollard’s p-1 Factorization Another method of factorization that uses Fermat's little theorem that we introduced. The method is simple, since we know from Fermat’s Little theorem that where ,suppose that we have a number s.t it’s a factor for another number where . Then , since in rsa our , then . So will include the factor or will equal it.  

30. Pollard’s p-1 Factorization So, let’s wrap our steps: Choose integer s.t Calculate to find the nontrivial factor, note that we replaced the with Since it’s increase so fast and will give us a good chance to check if is prime. Now we will take the if it's nontrivial. Example: … So,  

31. RSA Security We still have many other factorizations methods like Quadratic sieve, ECM but does that mean that the RSA is not secure? The answer is until now no, the strength point in RSA that it’s depends on ignorance than knowledge, we don’t have an efficient way to calculate how hard is to factor a huge number, we just know it’s hard, and a small mitigation for the previous factorization methods is adding more digits to our which will make it harder to factorize. But there are some attacks on RSA based on bad key generation for our variables or even our encryption methodology.  

32. Bad Key generation Attacks Some of the attacks can be applied on RSA are: Common Modulus Blinding Small Private Exponent: wiener Small Public Exponent: Coppersmith, Hastad Time Attack We will try to explain some of them by examples in order to make it clearer.

33. Example1 Question from PICOCTF 2018: N: 374159235470172130988938196520880526947952521620932362050308663243595788308583992120881359365258949723819911758198013202644666489247987314025169670926273213367237020188587742716017314320191350666762541039238241984934473188656610615918474673963331992408750047451253205158436452814354564283003696666945950908549197175404580533132142111356931324330631843602412540295482841975783884766801266552337129105407869020730226041538750535628619717708838029286366761470986056335230171148734027536820544543251801093230809186222940806718221638845816521738601843083746103374974120575519418797642878012234163709518203946599836959811 e: 3, c: 2205316413931134031046440767620541984801091216351222789180582564557328762455422721368029531360076729972211412236072921577317264715424950823091382203435489460522094689149595951010342662368347987862878338851038892082799389023900415351164773

34. Example1 As you can see the is huge number, factorizing it won’t be an easy thing at all, but we notice that is so small, small such that , so So, to get we can just take the cubic root for , computer can do this easily. So, Decoding the long to string using the ASCII table will result this message: picoCTF {e_w4y_t00_sm411_81b6559f} , which is our solution.  

35. Example2 PICO CTF 2018: We are given the following inputs: c: 1778673018511075140350698252891639557906407090250539057221806340768776705763113815373271713598206734943304136885307657644746166557801527614555955063613958550715606102502660768573300084767410478866161295739179626743292839204862654148472896949835346074323716667404949929701903737872090588147698250826373180618 n: 77531969503748326589677418948315140870584015245386763633241518845356850979564402923266696704186567270006361208862086254527576010412135230279553684940635956656649728134893874567619948675304052482720430367748612708917105846534082863042823913166120865362252479206576942147071396319459112580853771742537940112457 e: 56172436577459725698934391359139104915041430213184221292301658571726414059411889155782982024019814564512291421932489731563519296372873415080546379424619308859152360214209740169135159761234894923144971372974038021945201954600238994209605035703317119192844975463915465725406543097929017637859019950590916533609 As you can see everything is huge, and after tries to factorize it didn’t work, in this case we can consider checking another attack called wiener attack  

36. Wiener’s Attack Michael J. Wiener was able to state a theorem based on continuous fractions that says if then we can recover without factoring . Explaining: we already mentioned before that , and since , and since are so large we can take a good approximation that . Now substituting this into our first equation:  

37. Wiener’s Attack So, let’s set our steps: We need to find a set of convergent that approximate (using continued fractions and we will demonstrate it), under some conditions: Since and is product of 2 primes so it will be even number, will be odd, so we can skip the convergent if our is not odd. Since must be a whole number, also must be a whole number, and if it’s not so we will move to the next convergent. Now let be a quadratic equation then: If we got the right value for then the roots of the equation will be our factors for .  

38. Wiener’s Attack Short Example: Solution: now using the Euclidean algorithm to find the convergent in the continued fraction (ignore) (ignore) (d is even, ignore) (passed first check)  

39. Wiener’s Attack Now since We can set our quadratic equation as: Solving it will give us which are whole numbers, so we got the right value of which is 3 .  

40. Example2 Now applying this to the example will be hard to do manually so with a use of simple script and run it on a computer we get the following message: picoCTF {w@tch_y0ur_Xp0n3nt$_c@r3fu11y_5495627}

41. Example3 Qiwi CTF 2016: We are given the following data: e = 3 n1 = 95118357989037539883272168746004652872958890562445814301889866663072352421703264985997800660075311645555799745426868343365321502734736006248007902409628540578635925559742217480797487130202747020211452620743021097565113059392504472785227154824117231077844444672393221838192941390309312484066647007469668558141 n2 = 98364165919251246243846667323542318022804234833677924161175733253689581393607346667895298253718184273532268982060905629399628154981918712070241451494491161470827737146176316011843738943427121602324208773653180782732999422869439588198318422451697920640563880777385577064913983202033744281727004289781821019463 n3 = 68827940939353189613090392226898155021742772897822438483545021944215812146809318686510375724064888705296373853398955093076663323001380047857809774866390083434272781362447147441422207967577323769812896038816586757242130224524828935043187315579523412439309138816335569845470021720847405857361000537204746060031 c1 = 64830446708169012766414587327568812421130434817526089146190136796461298592071238930384707543318390292451118980302805512151790248989622269362958718228298427212630272525186478627299999847489018400624400671876697708952447638990802345587381905407236935494271436960764899006430941507608152322588169896193268212007 c2 = 96907490717344346588432491603722312694208660334282964234487687654593984714144825656198180777872327279250667961465169799267405734431675111035362089729249995027326863099262522421206459400405230377631141132882997336829218810171728925087535674907455584557956801831447125486753515868079342148815961792481779375529 c3 = 43683874913011746530056103145445250281307732634045437486524605104639785469050499171640521477036470750903341523336599602288176611160637522568868391237689241446392699321910723235061180826945464649780373301028139049288881578234840739545000338202917678008269794179100732341269448362920924719338148857398181962112

42. Example3 As you can see yes, our public exponent is small, but taking the 3 rd root for won’t give us the solution, this means that Now there is an attack in this case we can apply called Hastad’s attack. Let’s discuss it in the next slide  

43. Hastad’s Attack Simply when we send the same message to different receivers, an attacker can retrieve the private key using Chinese remainder theorem that we discussed before. …… The Chinese Remainder Theorem allows us to solve those congruences and since , then *.. so we can solve them and get our .  

44. Hastad’s Attack Example: Solution: we need to write them as congruences: Using Chinese remainder algorithm:  

45. Hastad’s Attack Now Applying the same steps on Example3 will result the message: theoretical_computer_scientist_johan_torkel_hastad  

46. Example4 ( CodeBlue CTF 2017) Given: 791311309087374588934274354916349141233150778762086315374343850126808782284294921228110916322178898551691669133101997907127587121520288166574468605214516304122927763843434653215681360872523253290766297044510870617745122997739814947286892376888776319552516141136363673315815999597035068706744362048480852074989063152333880754375196551355543036200494314973628012006925154168913855587162465714207917714655810265293814697401062934881400969828166519415465439814160673468968009887672546243771190906300544375962002574334018175007498231632240021805593635057187842353840461973449205839419195826992169177108307004404365745462706797969436718212150888171299620800051183755681631250040936288149592343890616920153400691102933966724025765766418338452595218861582008026186067946508221264938736562082192890727980844444978081110599714993030990031363457184296168457089953510500474033234298252385232725393194957086065274263743550741242453140557383981358497807318476777558208795816650619401057283873302725816795298930817307745973266335447938091252055872816232968635169429875153933553733116356920185396530990560434510949092154539711124052490142742567527833751624924993906099869301505096094512729115132147653907827742334805918235749308541981388529841813147 813647 791311309087374588934274354916349141233150778762086315374343850126808782284294921228110916322178898551691669133101997907127587121520288166574468605214516304122927763843434653215681360872523253290766297044510870617745122997739814947286892376888776319552516141136363673315815999597035068706744362048480852074989063152333880754375196551355543036200494314973628012006925154168913855587162465714207917714655810265293814697401062934881400969828166519415465439814160673468968009887672546243771190906300544375962002574334018175007498231632240021805593635057187842353840461973449205839419195826992169177108307004404365745462706797969436718212150888171299620800051183755681631250040936288149592343890616920153400691102933966724025765766418338452595218861582008026186067946508221264938736562082192890727980844444978081110599714993030990031363457184296168457089953510500474033234298252385232725393194957086065274263743550741242453140557383981358497807318476777558208795816650619401057283873302725816795298930817307745973266335447938091252055872816232968635169429875153933553733116356920185396530990560434510949092154539711124052490142742567527833751624924993906099869301505096094512729115132147653907827742334805918235749308541981388529841813147 846359 767202255403494641285723819543278226263601155898823605265497361830705668240032418501494959141449028517100422081272691883369257107388411439611318808983979122090486252578041006071999581282663085495058515958745546211668701835250122032715473014598395050184702983368667972803718169481809394565706175141425650370279775233813674442957760484285820381853600163980060348710028919659329781877491724136976028815641232407109144869660767954119268355348405951052583739555066569345526640029961785158127382321111833599691079949415049786723663210542733655554868327542833053024595895523192888118675763242352407948643537985861448788568550308481655116845634952516676905251579084404308314639717162526798451410767058423619677212069270398132021729448047980766312818656065369023093123058422620085273728481545680423266197847937925342263870309939913221308330842487685037638837340238355192125668409039255551545407800543798158964963358868702135730305156935767426581823180696819366253148799571923731323928995477390559418822575259531941023518182807739949726026157027426545624061195471888653152768495272113769751755053321333829345939391638863918920798107792346015224509118930143010726156407828938941341788657835191853473698010478888928860138978235297618195944868175 393205642868817442649216793359718556278406137459770244761832906195960432918468617731069456704644789806507809829093842629745066759599286729538728368882491382997337611417441529220397067642218119525968897551289230558627870154984979444195757677411673096443476021362319325097662392808170632471553717355895219405644518503783235536597143112954291157798713583737689125917709618182162360535659223966858707155741267214975141963463832314566520144602105237041672437684177707624423211972004800873375670613148140256099552724408192217550331987310558991433383571470532995856778764797540637679226825577553396934734325550293550389623919904744913990305949697308222046594160302362669510242921299755255790640101006152269619965560742243168099219363626217512940995615730916134775134764069912120583282148219405178065222313607957426887495658080497917440100549199528894874905968298614233827155712422019324710018755792249855902168601927285980197334672067920857960628679370550895555840658121626134216719240409691397735762685349162277111815727100169755960553688569326705249270662470879197234836585418835845237231721910938341557726245940031873345666571751867755961294973426045629909899256967038811807893676700888551318830676356324765330202998096318754445585853694  

47. Example4 As u can see we cannot use any of the previous attacks since is not small enough and we couldn’t factorize but we noticed that they are the same, also it’s given that the message is the same. In this case we can use an attack called Common modulus Attack  

48. Common Modulus Attack Let’s translate our input as math: Now we know that RSA system is homomorphic to multiplication, so we can get a new cipher text which is the product of the other cipher texts raised to powers : Now we can use Bézout's identity which states: For  

49. Common Modulus Attack Now using Extended Euclidean algorithm to find the multiplicative inverse , we can recover our , let’s see example with small numbers. Let: Solution: In EEA: So And from this   q 2 17 7 3 1 -2 2 7 3 1 1 -2 5 3 3 1 -2 5 -17 1 5 -17 q 2 17 7 3 1 -2 2 7 3 1 1 -2 5 3 3 1 -2 5 -17 1 5 -17

50. Common Modulus Attack To validate our result, we know from Bézout's identity that: which is true Now to get our new Now we need to e EEA again for for short using computers it will give us 16 So And since so our  

51. Example4 Applying the same steps on the example we will get message: CBCTF{6ac2afd2fc108894db8ab21d1e30d3f3}

52. Last Words Number theory is very interesting and fun, applying it to cryptography will give you more fun, there is still a lot of topics we can discuss and other attacks like: LLL and time attacks, also there is a lot of interesting topics in cryptography like fast powering, elliptic curves, lattices, successive powers, quadratic residue and much more, I really want to stay with you and talk more but we can do it in another time, so always keep learning and excited and never give up to math, it might seems hard and most of simple thing seems weird to you but when you get it you will be so proud. In the next slide I will share a great resources that I use to practice and learn. Don’t learn to hack… hack to learn.

53. Resources Cryptohack one of the best websites that teaches you by challenges Math 3107 by prof. Jeff Suzuki Boston University MIT 6.875 MIT Cryptography Spring 2018 An Introduction to Mathematical Cryptography by J.H. Silverman, Jill Pipher , Jeffrey Hoffstein

54. References https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf https://cryptohack.org/challenges/maths/ https://www.youtube.com/playlist?list=PLKXdxQAT3tCssgaWOy5vKXAR4WTPpRVYK https://link.springer.com/book/10.1007/978-0-387-77993-5 https://www.amazon.com/Friendly-Introduction-Number-Theory-4th/dp/0321816196/ref=sr_1_2?ie=UTF8&qid=1326998078&sr=8-2 https://www.khanacademy.org/computing/computer-science/cryptography/