Public Key Cryptography
Symmetric Crypto: Alice and Bob decide on a key to encrypt a message when one wants to send a message to the other- what happens when Alice wants to send messages to many different people?
- Impossible to store enough secret keys to encrypt messages between every pair of entities in the world
Public Key Crypto: Facilitates broad communication needs as opposed to symmetric (pair) cryptography
MAC vs. Digital Signature
MAC: Signed so only Bob can verify; CCA2 Security: Pr[VerK(m, t) = 1] = 1/2L where L is the length of m
Ak --- m, t ---> Bk
m accept if:
t = MACk(m) Verk(m,t) =1
Digital Signature: PKA, SKA Signed so anyone can verify; CCA2 Security: Pr[VerK(m, σ) = 1] = 1/2L where L is the length of m
ASKA --- m, σ---> B
m accept if:
σ= SigSKA(m) VerPKA(m, σ) =1
Correctness: VerPK(m, SigSK(m))=1 Example: A DNS server signs IP address returns with its unique server signature to prove authenticity and that the user is actually directed to the site they intended to go to; however, public key distribution is a widespread problem. A signature can be valid, but come from an impersonator.
Public Key Encryption Scheme: Not a MAC/signature- provides confidentiality, but not authenticity. Combine with Digital Signature above to provide authenticity.
A PKB --- c ---> BSKB
c= EncPKB(m) DecSKB(c) =m
Encrypted with public key of recipient, and decrypted with secret key of recipient.
- Scheme guarantees that only the recipient can decrypt with secret key- no secrecy if a message can be decrypted with a public key!
- Note that above scheme provides no measure of authenticity on its own, because Alice uses Bob’s public key to encrypt Building a Public Key Crypto System: RSA RSA is comprised of:
- 2 very large 2048-bit primes p and q
- p and q are secret to everyone in the RSA “black box”; p*q=N
- N: RSA Modulus
- e: encryption exponent (often 3)
Easy: find me mod N when given (e, N, m)
Hard: find m such that y = me mod N; the “eth” root of y
Easy: known decryption exponent: d = e-1 mod ϕ(N) where ϕ(N) = (p-1)(q-1)
yd mod N = m, where m such that y = me mod N
Construction:
A PKB --- y ---> BSKB y= EncPKB(m) Dec(y) =yd mod N
Textbook RSA: EncPKB(m) = me mod N Actual RSA: EncPKB(m) = [Pad(m)]e mod N, where Pad is random
- Each time RSA is run, p and q must be fresh—a new modulus each time
- Random: p, q
- Fixed: e
- Public Key: N, e
- Private Key: N, d
- If assume RSA is secure, we are assuming that factorization of large primes is hard
Key Generation: RSAGen() = p,q,e d = e-1 mod (p-1)(q-1) Keep Secret: d, p, q Make Public: e, N