1David Evanshttp://www.cs.virginia.edu/~evansCS588: Security and PrivacyUniversity of VirginiaComputer ScienceLecture 8:Non-secret Key Cryptosystems (How Euclid, Fermat and Euler Created E-Commerce)Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers.G. H. Hardy, The Mathematician’s Apology, 1940.24 Sept 2001 University of Virginia CS 588 2Public-Key Applications: Privacy• Alice encrypts message to Bob using Bob’s Private Key• Only Bob knows Bob’s Private Key ⇒only Bob can decrypt messageEncrypt DecryptPlaintextCiphertextPlaintextAliceBobBob’s Public KeyBob’s Private Key24 Sept 2001 University of Virginia CS 588 3Signatures• Bob knows it was from Alice, since only Alice knows Alice’s Private Key• Non-repudiation: Alice can’t deny signing message (except by claiming her key was stolen!)• Integrity: Bob can’t change message (doesn’t know Alice’s Private Key)Encrypt DecryptPlaintextSignedMessagePlaintextAliceBobAlice’s Private KeyAlice’s Public Key24 Sept 2001 University of Virginia CS 588 4Public-Key Cryptography• Private procedure: E• Public procedure: D• Identity: E (D(m)) = D (E(m)) = m• Secure: cannot determine E from D• But didn’t know how to find suitable Eand D24 Sept 2001 University of Virginia CS 588 5Properties 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)) = M24 Sept 2001 University of Virginia CS 588 6RSAE(M) = Me mod nD(C) = Cddmod n (red = secret)n = pqpq pp, qq are primedd is relatively prime to (p – 1)(q – 1)edd ≡ 1 (mod (p – 1)(q – 1))224 Sept 2001 University of Virginia CS 588 7RSA in Perlprint pack"C*", split/\D+/, `echo "16iII*o\U@{$/=$z; [(pop,pop,unpack"H*",<>)]} \EsMsKsN0[lN*1lK[d2%Sa2/d0 <X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`(by Adam Back)Until 1997 – Illegal to show this slide to non-US citizens!Until Jan 2000: can export RSA, but only with 512 bit keysNow: can export RSA except to embargoed destinations24 Sept 2001 University of Virginia CS 588 8First AmendmentBecause computer source code is an expressive means for the exchange of information and ideas about computer programming, we hold that it is protected by the First Amendment.Sixth Circuit Court of Appeals, April 4, 2000Ruling that Peter Junger could post RSA source code on his web site24 Sept 2001 University of Virginia CS 588 9Properties 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)) = M24 Sept 2001 University of Virginia CS 588 10Property 1: D (E (M)) = ME(M) = Me mod nD(E(M)) = (Me mod n)dmod n= Med mod n (as in D-H proof)Can we choose e, d and n so:M ≡ Med mod n1 ≡ Med-1mod n24 Sept 2001 University of Virginia CS 588 11Euler’s totient (phi) function• ϕ (n) = number of positive integers < n which are relatively prime to n.• If n is prime, ϕ (n) = n – 1.–Proof by contradiction.24 Sept 2001 University of Virginia CS 588 12Totient ProductsFor primes, pand q: n = pqϕ (n) = ϕ (pq) ϕ (n) = numbers < n not relatively prime to pq= pq– 1 numbers less than pq– p, 2p, 3p, …, (q – 1)p ; q-1 of them– q, 2q, 3q, …, (p – 1)q ; p-1 of them= pq– 1 – (q – 1) – (p– 1) = pq– (p + q) + 1 = (p – 1) (q– 1) = ϕ (p) ϕ (q)324 Sept 2001 University of Virginia CS 588 13Euler’s Theorem• For a and n relatively prime:aϕ(n)≡ 1 mod n• Recall: we are looking for e, d and n such that:Med-1≡ 1mod n24 Sept 2001 University of Virginia CS 588 14Fermat’s Little TheoremIf n is prime and a is not divisible by nan-1≡ 1 mod nStronger version: (in MBC p. 200):If n is prime, for any a:an≡ a mod n24 Sept 2001 University of Virginia CS 588 15Fermat’s Little Theorem Proof{a mod n, 2a mod n, … , (n-1)a mod n} = {1, 2, …, (n – 1) }if ab mod n = ac mod n and a is relatively prime to nthen b = c mod n 24 Sept 2001 University of Virginia CS 588 16Fermat’s Little Theorem Proof{a mod n, 2a mod n, … , (n-1)a mod n} = {1, 2, …, (n – 1) }a × 2a × … × (n – 1) a ≡ (n – 1)! mod n(n – 1)!an-1 ≡(n – 1)! mod nan-1 ≡ 1 mod n24 Sept 2001 University of Virginia CS 588 17Euler’s TheoremFor a and n relatively prime:aϕ(n)≡ 1mod nProof:If n is prime, ϕ (n) = n – 1 and an - 1≡ 1mod nby Fermat’s Little Theorem.What if n is not prime? 24 Sept 2001 University of Virginia CS 588 18Euler’s Theorem, cont.For a and n relatively prime:aϕ(n)≡ 1 mod nϕ (n) = number of numbers < n notrelatively prime to nWe can write those numbers as:R = { x1, x2, … , xϕ(n)}424 Sept 2001 University of Virginia CS 588 19Proving Euler’s TheoremR = { x1, x2, … , xϕ(n)} multiply by a mod n:S = { ax1 mod n, ax2 mod n, …, axϕ (n) mod n}S is a permutation of R:– a is relatively prime to n and xiso axi is relatively prime to n hence all elements of Sare in R.– There are no duplicates in S. If aximod n = axjmod n then i = j. since a is relatively prime to n.24 Sept 2001 University of Virginia CS 588 20Proving Euler’s Theoremx1 × x2 … × xϕ (n) = ax1 mod n × ax2 mod n … × axϕ(n) mod n≡ (ax1 × ax2 … × axϕ(n)) mod n≡ aϕ(n)× x1 × x2 … × xϕ (n)mod n1 ≡ aϕ(n)mod n QED.24 Sept 2001 University of Virginia CS 588 21Recap• Euler’s Theorem: 1 ≡ aϕ(n)mod nfor a and n relatively prime• If n is prime, ϕ (n) = n – 1.• For p and q prime, ϕ (pq) = ϕ (p)ϕ (q)• We are looking for e, d and n such that:Med-1≡ 1mod ned – 1 = ϕ (n) = (p-1)(q-1)What if M is not relatively prime to n?24 Sept 2001 University of Virginia CS 588 22M and n• Suppose M and n not relatively prime:gcd (M, n) ≠ 1• Since n = pq and p and q are prime:gcd (M, p) ≠ 1 OR gcd (M, q) ≠ 1Case 1: M = cpgcd (M, q) = 1 (otherwise M is multiple of both p and q, but M < pq).So, Mϕ(q)≡1 mod q(by Euler’s theorem, since Mand q are relatively prime)24 Sept 2001 University of Virginia CS 588 23M and n, contCase 1: M = cpgcd (M, q) = 1 (otherwise M is multiple of both pand q, but M < pq ).So, M ϕ (q)≡ 1 mod q(by Euler’s theorem, since M and qare relatively prime)Mϕ (q)≡ 1 mod q(Mϕ (q))ϕ (p)≡ 1 mod qMϕ (q)ϕ (p)≡ 1 mod qMϕ (n)≡ 1 mod q24 Sept 2001 University of Virginia CS 588 24M and nMϕ (n)≡ 1 mod qMϕ (n)= 1 + kq for some kM