PowerPoint PresentationMenuProperties of E and DProperty 2: Easy to ComputeHow many prime numbers?Density of PrimesApproximating (x)Need a faster prime testFermat TestSlide 10Property 4: E (D (M)) = MSlide 12RSARevealing E doesn’t reveal DGardner’s Column: Original RSA challenge ($100)40000000000000000  17Trial and Error FactoringPollard’s Rho MethodHow so FastFermat FactoringSlide 21Kraitchik’s EnhancementKraitchik, cont.Finding the x’sFinding the FactorsFactoring PragmaticsBreaking RSA-129Slide 28Recent Factoring AlgorithmsRSA Security (n) without factoringp – q = sqrt ((p + q)2 – 4n)Determine d without  (n)Determining d  factoringProperties of RSA’s E and DApplications of RSATwo “Questionable” Statements in RSA PaperSlide 38Who really invented RSA?ChargeBecause both the system’s privacy and the security of digital money depend on encryption, a breakthrough in mathematics or computer science that defeats the cryptographic system could be a disaster. The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers. Any person or organization possessing this power could counterfeit money, penetrate any personal, corporate, or government file, and possibly even undermine the security of nations. Bill Gates, The Road AheadDavid Evanshttp://www.cs.virginia.edu/~evansCS588: Security and PrivacyUniversity of VirginiaComputer ScienceLecture 9: Security of RSA THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE.26 Sept 2001 University of Virginia CS 588 2Menu•Finding Big Pseudo Primes•Security of RSA–Factoring26 Sept 2001 University of Virginia CS 588 3Properties of E and DTrap-door one way function:1. D (E (M)) = M 2. E and D are easy to compute.3. Revealing E doesn’t reveal an easy way to compute DTrap-door one way permutation: also4. E (D (M)) = M26 Sept 2001 University of Virginia CS 588 4Property 2: Easy to Compute•We need large “random” primes p and q•Are there enough primes?•How can we find them?26 Sept 2001 University of Virginia CS 588 5How many prime numbers?•Infinite (proved by Euclid, 300BC)•Proof by contradiction:Suppose that there exist only finitely many primes p1 < p2 < ... < pr. Let N = (p1)(p2)...(pr) + 1N > pr so it is composite, N = p * MIf p = pi for some 1…r, then, N = pi * M = pi * (p1)(p2)...(pi-1) (pi+1)...(pr) + 1 pi (M - (p1)(p2)...(pi-1) (pi+1)...(pr)) = 1Contradiction: pi > 1 Hence, there must be infinitely many primes.26 Sept 2001 University of Virginia CS 588 6Density of PrimesFrom http://www.utm.edu/research/primes/howmany.shtml(x) is the number of primes  x26 Sept 2001 University of Virginia CS 588 7Approximating (x) •The Prime Number Theorem: (x) ~ x/ln x –Difficult to prove (first conjectured by Legendre in 1798 by looking at table of values) •How many guesses to find a prime bigger than x?–About ln x/2 guesses•(Naïvely) Each guess requires sqrt(x) work•For 200 digits: 230 guesses * 10100–More work than breaking 3DES!26 Sept 2001 University of Virginia CS 588 8Need a faster prime test•There are several fast probabilistic prime tests•Can quickly test a prime with high probability, with a small amount of work•If we pick a non-prime, its not a disaster (exercise for reader, will be on PS3)26 Sept 2001 University of Virginia CS 588 9Fermat Test•Recall Fermat’s Little Theorem: If n is prime and a is not divisible by n then an-1  1 mod n•Prove n is composite by finding an-1  1 mod n•Showing an-1  1 mod n does not prove it is prime•But if it holds for many a’s it is likely than n is prime –Holds for all a’s for some non-primes known as Carmichael Numbers: 561, 645, 1105, …)•Better prime test: Miller-Rabin –Probability n is prime  1 – ¼k26 Sept 2001 University of Virginia CS 588 10Properties of E and DTrap-door one way function:1. D (E (M)) = M 2. E and D are easy to compute.3. Revealing E doesn’t reveal an easy way to compute DTrap-door one way permutation: also4. E (D (M)) = M26 Sept 2001 University of Virginia CS 588 11Property 4: E (D (M)) = MD(M) = Md mod nE(D(M)) = (Md mod n)e mod n = Mde mod n = Med mod n = M(from the property 1 proof)26 Sept 2001 University of Virginia CS 588 12Properties of E and DTrap-door one way function:1. D (E (M)) = M 2. E and D are easy to compute.3. Revealing E doesn’t reveal an easy way to compute DTrap-door one way permutation: also4. E (D (M)) = MAre there other functions that have properties 1, 2 and 4?26 Sept 2001 University of Virginia CS 588 13RSAE(M) = Me mod nD(C) = Cd mod n n = pq p, q are primed is relatively prime to (p – 1)(q – 1)ed  1 (mod (p – 1)(q – 1))26 Sept 2001 University of Virginia CS 588 14Revealing E doesn’t reveal D•Revealing E: e, n.•Can attacker find D?•If attacker factors n = p * qed  1 mod (p – 1)(q – 1) Easy to find d  e-1 mod (p – 1)(q – 1)•Use experience to argue factoring is hard.•Argue all other attacks are at least as hard as factoring n.26 Sept 2001 University of Virginia CS 588 15Gardner’s Column: Original RSA challenge ($100)n (RSA-129) = 1 1438 1625 7578 8886 7669 2357 7997 6146 6120 1021 8296 7212 4236 2562 5618 4293 5706 9352 4573 3897 8305 9712 3563 9587 0505 8989 0751 4759 9290 0268 7954 3541e = 9007C = 9686 9613 7546 2206 1477 1409 2225 4355 8829 0575 9991 1245 7431 9874 6951 2093 0816 2982 2514 5708 3569 3147 6622 8839 8962 8013 3919 9055 1829 9451 5781 5154Scientific American, August 197726 Sept 2001 University of Virginia CS 588 1640000000000000000  17Ron Rivest (1977): factoring n (129 digits) would require at least 40 quadrillion years if you could do a * b mod c in one nanosecond.Derek Atkins (April 1994): We are happy to announce that RSA-129 = 3490 5295 1084 7650 9491 4784 9619 9038 9813 3417 7646 3849 3387 8439 9082 0577 * 3 2769 1329 9326 6709 5499 6198 8190 8344 6141 3177 6429 6799 2942 5397 9828 853326 Sept 2001 University of Virginia CS 588 17Trial and Error Factoring•Guess x, if 1 < gcd (x, n) < n then x is an interesting factor•If p and q are similar size, lowest factor is around n.–Requires O(n) divisions.–For RSA-129 = 1.1 * 1064 divisions, 1 per nanosecond = 3.4 * 1047 years26 Sept 2001 University of Virginia CS 588 18Pollard’s Rho Method•Fastest known in 1977 [Pollard75]•To find factor p, requires 4p modular multiplies•Worst case: lowest p is n, we need 4n multiplies•For RSA-129 =