DOC PREVIEW
UT CS 361s - Overview of Public-Key Cryptography

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 n1 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 aZn*, 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 ed  1 mod (n) Thus ed = 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 pq=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 m1m2 – (m1e)  (m2e) mod n  (m1m2)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 MG(r) ; rH(MG(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 0t8 • Select hZp* and compute g=h(p-1)/q mod p • Select random x such 1xq-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)+xr) 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)+xr) mod q Thus H(M)  -xr+ks mod q Multiply both sides by w=s-1 mod q H(M)w + xrw  k mod q Exponentiate g to both sides (gH(M)w + xrw  gk) mod p mod q In a valid signature, gk mod p mod q = r, gx mod p = y Verify gH(M)wyrw  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

UT CS 361s - Overview of Public-Key Cryptography

Download Overview of Public-Key Cryptography
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Overview of Public-Key Cryptography and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Overview of Public-Key Cryptography 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?