slide 1 Vitaly Shmatikov CS 361S Overview of Public-Key Cryptographyslide 2 Reading Assignment Kaufman 6.1-6slide 3 Public-Key Cryptography ? Given: Everybody knows Bob’s public key - How is this achieved in practice? Only Bob knows the corresponding private key private key Goals: 1. Alice wants to send a message that only Bob can read 2. Bob wants to send a message that only Bob could have written public key public key Alice Bobslide 4 Applications of Public-Key Crypto Encryption for confidentiality • Anyone can encrypt a message – With symmetric crypto, must know the secret key to encrypt • Only someone who knows the private key can decrypt • Secret keys are only stored in one place Digital signatures for authentication • Only someone who knows the private key can sign Session key establishment • Exchange messages to create a secret session key • Then switch to symmetric cryptography (why?)slide 5 Public-Key Encryption Key generation: computationally easy to generate a pair (public key PK, private key SK) Encryption: given plaintext M and public key PK, easy to compute ciphertext C=EPK(M) Decryption: given ciphertext C=EPK(M) and private key SK, easy to compute plaintext M • Infeasible to learn anything about M from C without SK • Trapdoor function: Decrypt(SK,Encrypt(PK,M))=Mslide 6 Some Number Theory Facts Euler totient function (n) where n1 is the number of integers in the [1,n] interval that are relatively prime to n • Two numbers are relatively prime if their greatest common divisor (gcd) is 1 Euler’s theorem: if aZn*, then a(n) 1 mod n Special case: Fermat’s Little Theorem if p is prime and gcd(a,p)=1, then ap-1 1 mod pslide 7 RSA Cryptosystem Key generation: • Generate large primes p, q – At least 2048 bits each… need primality testing! • Compute n=pq – Note that (n)=(p-1)(q-1) • Choose small e, relatively prime to (n) – Typically, e=3 (may be vulnerable) or e=216+1=65537 (why?) • Compute unique d such that ed 1 mod (n) • Public key = (e,n); private key = d Encryption of m: c = me mod n Decryption of c: cd mod n = (me)d mod n = m [Rivest, Shamir, Adleman 1977]slide 8 Why RSA Decryption Works ed 1 mod (n) Thus ed = 1+k(n) = 1+k(p-1)(q-1) for some k If gcd(m,p)=1, then by Fermat’s Little Theorem, mp-1 1 mod p Raise both sides to the power k(q-1) and multiply by m, obtaining m1+k(p-1)(q-1) m mod p Thus med m mod p By the same argument, med m mod q Since p and q are distinct primes and pq=n, med m mod nslide 9 Why Is RSA Secure? RSA problem: given c, n=pq, and e such that gcd(e,(p-1)(q-1))=1, find m such that me=c mod n • In other words, recover m from ciphertext c and public key (n,e) by taking eth root of c modulo n • There is no known efficient algorithm for doing this Factoring problem: given positive integer n, find primes p1, …, pk such that n=p1e1p2e2…pkek If factoring is easy, then RSA problem is easy, but may be possible to break RSA without factoring n“Textbook” RSA Is Bad Encryption Deterministic • Attacker can guess plaintext, compute ciphertext, and compare for equality • If messages are from a small set (for example, yes/no), can build a table of corresponding ciphertexts Can tamper with encrypted messages • Take an encrypted auction bid c and submit c(101/100)e mod n instead Does not provide semantic security (security against chosen-plaintext attacks) slide 10slide 11 Integrity in RSA Encryption “Textbook” RSA does not provide integrity • Given encryptions of m1 and m2, attacker can create encryption of m1m2 – (m1e) (m2e) mod n (m1m2)e mod n • Attacker can convert m into mk without decrypting – (me)k mod n (mk)e mod n In practice, OAEP is used: instead of encrypting M, encrypt MG(r) ; rH(MG(r)) • r is random and fresh, G and H are hash functions • Resulting encryption is plaintext-aware: infeasible to compute a valid encryption without knowing plaintext – … if hash functions are “good” and RSA problem is hardslide 12 Digital Signatures: Basic Idea ? Given: Everybody knows Bob’s public key Only Bob knows the corresponding private key private key Goal: Bob sends a “digitally signed” message 1. To compute a signature, must know the private key 2. To verify a signature, only the public key is needed public key public key Alice Bobslide 13 RSA Signatures Public key is (n,e), private key is d To sign message m: s = hash(m)d mod n • Signing and decryption are the same mathematical operation in RSA To verify signature s on message m: se mod n = (hash(m)d)e mod n = hash(m) • Verification and encryption are the same mathematical operation in RSA Message must be hashed and padded (why?)slide 14 Digital Signature Algorithm (DSA) U.S. government standard (1991-94) • Modification of the ElGamal signature scheme (1985) Key generation: • Generate large primes p, q such that q divides p-1 – 2159 < q < 2160, 2511+64t < p < 2512+64t where 0t8 • Select hZp* and compute g=h(p-1)/q mod p • Select random x such 1xq-1, compute y=gx mod p Public key: (p, q, g, gx mod p), private key: x Security of DSA requires hardness of discrete log • If one can take discrete logarithms, then can extract x (private key) from gx mod p (public key)slide 15 DSA: Signing a Message Message Hash function (SHA-1) Random secret between 0 and q r = (gk mod p) mod q Private key s = k-1(H(M)+xr) mod q (r,s) is the signature on Mslide 16 DSA: Verifying a Signature Message Signature w = s’-1 mod q Compute (gH(M’)w yr’w mod q mod p) mod q Public key If they match, signature is validslide 17 Why DSA Verification Works If (r,s) is a valid signature, then r (gk mod p) mod q ; s k-1(H(M)+xr) mod q Thus H(M) -xr+ks mod q Multiply both sides by w=s-1 mod q H(M)w + xrw k mod q Exponentiate g to both sides (gH(M)w + xrw gk) mod p mod q In a valid signature, gk mod p mod q = r, gx mod p = y Verify gH(M)wyrw r mod p mod qslide 18 Security of DSA Can’t create a valid signature without private key Can’t change or tamper with signed message If
View Full Document