Applications of Number TheoryAbout this lecture setPrivate key cryptographyPublic key cryptographyPublic key cryptography goalsIs that number prime?Slide 8Slide 9More on the Fermat primality testGoogle’s latest recruitment campaignRSAKey generation stepsKey generation, step 1Slide 15Slide 16Slide 17Slide 18Key generation, step 2Slide 20Key generation, step 3Slide 22Key generation, step 4The keysEncrypting messagesEncrypting messages exampleEncrypting RSA messagesDecrypting messagesDecrypting messages examplemodPow computationWhy this worksCracking a messageCracking a message exampleSigning a messageSlide 35PGP and GnuPGThe US gov’t and war munitionsHow to “crack” PGPOther public key encryption methodsQuantum computersSourcesQuick surveySlide 43Slide 4411Applications of Number Applications of Number TheoryTheoryCS/APMA 202CS/APMA 202Rosen section 2.6Rosen section 2.6Aaron BloomfieldAaron Bloomfield22 About this lecture setAbout this lecture setWe are only going to go over parts of section 2.6We are only going to go over parts of section 2.6Just the ones that deal directly with 2.6Just the ones that deal directly with 2.6Much of the underlying theory we will not be able Much of the underlying theory we will not be able to get toto get toIt’s beyond the scope of this courseIt’s beyond the scope of this courseMuch of why this all works won’t be taughtMuch of why this all works won’t be taughtIt’s just an introduction to how it worksIt’s just an introduction to how it works33 Private key cryptographyPrivate key cryptographyThe function and/or key to encrypt/decrypt The function and/or key to encrypt/decrypt is a secretis a secret(Hopefully) only known to the sender and (Hopefully) only known to the sender and recipientrecipientThe same key encrypts and decryptsThe same key encrypts and decryptsHow do you get the key to the recipient?How do you get the key to the recipient?44 Public key cryptographyPublic key cryptographyEverybody has a key that encrypts and a Everybody has a key that encrypts and a separate separate key that decryptskey that decryptsThey are not interchangable!They are not interchangable!The encryption key is made publicThe encryption key is made publicThe decryption key is kept privateThe decryption key is kept private55 Public key cryptography goalsPublic key cryptography goalsKey generation should be relatively easyKey generation should be relatively easyEncryption should be easyEncryption should be easyDecryption should be easyDecryption should be easyWith the right key!With the right key!Cracking should be Cracking should be veryvery hard hard66 Is that number prime?Is that number prime?Use the Fermat primality testUse the Fermat primality testGiven:Given:nn: the number to test for primality: the number to test for primalitykk: the number of times to test (the certainty): the number of times to test (the certainty)The algorithm is:The algorithm is:repeat repeat kk times: times: pick pick aa randomly in the range [1, randomly in the range [1, nn−1]−1]if if aann−1−1 mod mod nn ≠ 1 then return ≠ 1 then return compositecompositereturn return probably primeprobably prime88 Is that number prime?Is that number prime?The algorithm is:The algorithm is:repeat repeat kk times: times: pick pick aa randomly in the range [1, randomly in the range [1, nn−1]−1]if if aann−1−1 mod mod nn ≠ 1 then return ≠ 1 then return compositecompositereturn return probably primeprobably primeLet Let nn = 105 = 105Iteration 1: Iteration 1: aa = 92: 92 = 92: 92104104 mod 105 = 1 mod 105 = 1Iteration 2: Iteration 2: aa = 84: 84 = 84: 84104104 mod 105 = 21 mod 105 = 21Therefore, 105 is compositeTherefore, 105 is composite99 Is that number prime?Is that number prime?The algorithm is:The algorithm is:repeat repeat kk times: times: pick pick aa randomly in the range [1, randomly in the range [1, nn−1]−1]if if aann−1−1 mod mod nn ≠ 1 then return ≠ 1 then return compositecompositereturn return probably primeprobably primeLet Let nn = 101 = 101Iteration 1: Iteration 1: aa = 55: 55 = 55: 55100100 mod 100 = 1 mod 100 = 1Iteration 2: Iteration 2: aa = 60: 60 = 60: 60100100 mod 100 = 1 mod 100 = 1Iteration 3: Iteration 3: aa = 14: 14 = 14: 14100100 mod 100 = 1 mod 100 = 1Iteration 4: Iteration 4: aa = 73: 73 = 73: 73100100 mod 100 = 1 mod 100 = 1At this point, 101 has a (½)At this point, 101 has a (½)44 = 1/16 chance of still = 1/16 chance of still being compositebeing composite1010 More on the Fermat primality testMore on the Fermat primality testEach iteration halves the probability that the number is a Each iteration halves the probability that the number is a compositecompositeProbability = (½)Probability = (½)kkIf If kk = 100, probability it’s a composite is (½) = 100, probability it’s a composite is (½)100100 = 1 in 1.2 = 1 in 1.2  10 103030 that the number is compositethat the number is compositeGreater chance of having a hardware error!Greater chance of having a hardware error!Thus, Thus, kk = 100 is a good value = 100 is a good valueHowever, this is not certain!However, this is not certain!There are known numbers that are composite but will always There are known numbers that are composite but will always report prime by this testreport prime by this testSource: http://en.wikipedia.org/wiki/Fermat_primality_testSource: http://en.wikipedia.org/wiki/Fermat_primality_test1111Google’s latest recruitment Google’s latest recruitment campaigncampaign1212 RSARSAStands for the inventors: Ron Rivest, Adi Stands for the inventors: Ron Rivest, Adi Shamir and Len AdlemanShamir and Len AdlemanThree parts:Three parts:Key generationKey generationEncrypting a messageEncrypting a messageDecrypting a messageDecrypting a message1313 Key generation stepsKey generation steps1.1.Choose two Choose two randomrandom large prime numbers large prime numbers pp ≠ ≠ qq, and , and nn = = pp**qq2.2.Choose an integer 1 < Choose an integer 1 < ee < < nn which is relatively prime to which is relatively prime to ((pp-1)(-1)(qq-1)-1)3.3.Compute Compute dd such that such that d * ed * e ≡ 1 (mod ( ≡ 1 (mod (pp-1)(-1)(qq-1))-1))Rephrased: d*e mod (Rephrased: d*e mod (pp-1)(-1)(qq-1) = 1-1) = 14.4.Destroy all records of Destroy all records of pp and and qq1414