Applications of Number TheoryAbout this lecture setPrivate key cryptographyPublic key cryptographyPublic key cryptography goalsIs that number prime?Slide 7Slide 8More on the Fermat primality testGoogle’s recruitment campaignRSAKey generation stepsKey generation, step 1Slide 14Slide 15Slide 16Slide 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” PGPMan-in-the-middle attack: “Normal” RSA communicationSlide 40Other public key encryption methodsQuantum computersSources1Applications of Number TheoryCS 202Epp section 10.4Aaron Bloomfield2About this lecture set•I want to introduce RSA–The most commonly used cryptographic algorithm today•Much of the underlying theory we will not be able to get to–It’s beyond the scope of this course•Much of why this all works won’t be taught–It’s just an introduction to how it works3Private key cryptography•The function and/or key to encrypt/decrypt is a secret–(Hopefully) only known to the sender and recipient•The same key encrypts and decrypts•How do you get the key to the recipient?4Public key cryptography•Everybody has a key that encrypts and a separate key that decrypts–They are not interchangable!•The encryption key is made public•The decryption key is kept private5Public key cryptography goals•Key generation should be relatively easy•Encryption should be easy•Decryption should be easy–With the right key!•Cracking should be very hard6Is that number prime?•Use the Fermat primality test•Given:–n: the number to test for primality–k: the number of times to test (the certainty)•The algorithm is:repeat k times: pick a randomly in the range [1, n−1]if an−1 mod n ≠ 1 then return compositereturn probably prime7Is that number prime?•The algorithm is:repeat k times: pick a randomly in the range [1, n−1]if an−1 mod n ≠ 1 then return compositereturn probably prime•Let n = 105–Iteration 1: a = 92: 92104 mod 105 = 1–Iteration 2: a = 84: 84104 mod 105 = 21–Therefore, 105 is composite8Is that number prime?•The algorithm is:repeat k times: pick a randomly in the range [1, n−1]if an−1 mod n ≠ 1 then return compositereturn probably prime•Let n = 101–Iteration 1: a = 55: 55100 mod 101 = 1–Iteration 2: a = 60: 60100 mod 101 = 1–Iteration 3: a = 14: 14100 mod 101 = 1–Iteration 4: a = 73: 73100 mod 101 = 1–At this point, 101 has a (½)4 = 1/16 chance of still being composite9More on the Fermat primality test•Each iteration halves the probability that the number is a composite–Probability = (½)k–If k = 100, probability it’s a composite is (½)100 = 1 in 1.2  1030 that the number is composite•Greater chance of having a hardware error!–Thus, k = 100 is a good value•However, this is not certain!–There are known numbers that are composite but will always report prime by this test•Source: http://en.wikipedia.org/wiki/Fermat_primality_test1010Google’s recruitment campaignGoogle’s recruitment campaign11RSA•Stands for the inventors: Ron Rivest, Adi Shamir and Len Adleman•Three parts:–Key generation–Encrypting a message–Decrypting a message12Key generation steps1. Choose two random large prime numbers p ≠ q, and n = p*q2. Choose an integer 1 < e < n which is relatively prime to (p-1)(q-1)3. Compute d such that d * e ≡ 1 (mod (p-1)(q-1))–Rephrased: d*e mod (p-1)(q-1) = 14. Destroy all records of p and q13Key generation, step 1•Choose two random large prime numbers p ≠ q–In reality, 2048 bit numbers are recommended•That’s  617 digits–From last lecture: chance of a random odd 2048 bit number being prime is about 1/710•We can compute if a number is prime relatively quickly via the Fermat primality test•We choose p = 107 and q = 97•Compute n = p*q–n = 1037914Key generation, step 1•Java code to find a big prime number:BigInteger prime = new BigInteger (numBits, certainty, random);The number of bits of the primeCertainty that the number is a primeThe random numbergenerator15Key generation, step 1•Java code to find a big prime number:import java.math.*;import java.util.*;class BigPrime {static int numDigits = 617;static int certainty = 100;static final double LOG_2 = Math.log(10)/Math.log(2);static int numBits = (int) (numDigits * LOG_2);public static void main (String args[]) {Random random = new Random();BigInteger prime = new BigInteger (numBits, certainty, random);System.out.println (prime);}}16Key generation, step 1•How long does this take?–Keep in mind this is Java!–These tests done on a 850 Mhz Pentium machine–Average of 100 trials (certainty = 100)–200 digits (664 bits): about 1.5 seconds–617 digits (2048 bits): about 75 seconds18Key generation, step 1•Practical considerations–p and q should not be too close together–(p-1) and (q-1) should not have small prime factors–Use a good random number generator19Key generation, step 2•Choose an integer 1 < e < n which is relatively prime to (p-1)(q-1)•There are algorithms to do this efficiently–We aren’t going over them in this course•Easy way to do this: make e be a prime number–It only has to be relatively prime to (p-1)(q-1), but can be fully prime20Key generation, step 2•Recall that p = 107 and q = 97–(p-1)(q-1) = 106*96 = 10176 = 26*3*53•We choose e = 85–85 = 5*17–gcd (85, 10176) = 1–Thus, 85 and 10176 are relatively prime21Key generation, step 3•Compute d such that:d * e ≡ 1 (mod (p-1)(q-1))–Rephrased: d*e mod (p-1)(q-1) = 1•There are algorithms to do this efficiently–We aren’t going over them in this course•We choose d = 4669–4669*85 mod 10176 = 1•Use the script at http://www.cs.virginia.edu/cgi-bin/cgiwrap/asb/modpow22Key generation, step 3•Java code to find d:import java.math.*;class FindD {public static void main (String args[]) {BigInteger pq = new BigInteger("10176");BigInteger e = new BigInteger ("85");System.out.println (e.modInverse(pq)); }}•Result: 466923Key generation, step 4•Destroy all records of p and q•If we know p and q, then we can compute the private encryption key from the public