ElGamal Cryptosystem, DH Key Exchange, Digital Signatures PDF

1 1 The ElGamal Cryptosystem Let p be a prime such that the Discrete Log problem is intractable in the multiplicative group Z⇤p , and let ↵ be a generator (=primitive element) of Z⇤p. Then I set of plaintexts is Z⇤p 1,2 10 1 I set of ciphertexts is Z⇤p ⇥ Z⇤p I Parameters: p; a 2 Zp \ {0};...

1 1 The ElGamal Cryptosystem Let p be a prime such that the Discrete Log problem is intractable in the multiplicative group Z⇤p , and let ↵ be a generator (=primitive element) of Z⇤p. Then I set of plaintexts is Z⇤p 1,2 10 1 I set of ciphertexts is Z⇤p ⇥ Z⇤p I Parameters: p; a 2 Zp \ {0}; ↵, 2 Z⇤p with = ↵a %p. I Public key PK = (p, ↵, ); Secret Key = a I Encryption of a plaintext x: pick a secret random so k 2 Zp 1 \ {0}; then EPK (x) = (y1 , y2 ), where y1 = ↵k %p and y2 = x k %p. I Decryption of ciphertext: Da (y1 , y2 ) = y2 (y1a ) 1 %p x Celess u.ly f xfk ykaH xjak.aff1 sidier A cannot figureout k from αᵗ p I cannotfigure out 42 I cannot figure out a from f 2 Et 1 Secret Key Exchange: DH (original) Let p be a prime number such that the Discrete Log Problem (DLP) and the Diffie-Hellman Problem (DHP) are intractable in the multiplicative group Z⇤p. Let g be a generator (=primitive element) of Z⇤p. 2 $ 1,2 p 1 4g 90,91 gr 1a. A picks x Z⇤p and computes X gx. 2a. A sends X to B. Adversary sees knows $ 1b. B picks y Z⇤p and computes Y gy. p g 2b. B sends Y to A. X g Yegg g 997 3a. A computes the key K Yx // this is g xy But cannot 3b. B computes the key K Xy // this is g xy. out g 9p) gxy figure (all arithmetic above is done modulo gxy knows knows gx y gy gy gx gn gm gmx gny nonauthenticatedversion LEFT part: Eve pretends to be Bob, and establishes a shared key, gmx, with Alice. Alice thinks she now communicates with Bob via that key. - RIGHT part: Eve pretends to be Alice, and establishes a shared key, gny, with Bob. Bob thinks he now communicates with Alice via that key. DH Key Exchange (authenticated) We assume that If Thegroup is Ip 11,2 10 1 A has a secret key a and a public key g a. with generator B has a secret key b and a public key g b. g $ 1a. A picks x Z⇤p and computes X gx. 2a. A sends X to B. $ 1b. B picks y Z⇤p and computes Y gy. 2b. B sends Y to A. 1,9972 gbxgya G 3a. A computes the key K (g b )x · Y a // this is g bx+ay shared key 3b. B computes the key K (g a )y · X b // this is g bx+ay. 973 4a. A encrypts any M1 as C1 = EK (M1 ) and sends C1 to B 4b. B encrypts any M2 as C2 = EK (M2 ) and sends C2 to A 5a. A computes DK (C2 ) and sends it to B 5b. B computes DK (C1 ) and sends it to A 6a. A confirms to B that there is a match 6b. B confirms to A that there is a match Alec encrypts x y z yea yea Zea and sends the encryptions to Bob in randomorder Alice'scard yea andsends ittoAlice Bodo picks one as say Azel receives yea and decrypts it yea Bod encrypts Xa yea xea eB y ea eB XealB yeals and sends them to Alice Ali picks one say EACB as Bob's card and decrypts it as xeaeBdA xeadAeB xeBandsends it toBob dB Bolt receives xers and decrypts it as x eB X DIGITAL SIGNATURES 1 / 74 Signing electronically SIGFILE ! "# $ scan Alice s 101 · · · 1 signature ALICE Bank Internet Pay Bob $100 Problem: signature is easily copied Inference: signature must be a function of the message that only Alice can compute 3 / 74 What about a MAC? Let Bank and Alice share a key K Internet ALICE Pay Bob $100 MAC K Bank T o A digital signature will have additional attributes: Even the bank cannot forge Verifier does not need to share a key with signer or, indeed, have any secrets 4 / 74 RSA Signatures: non-secure version Recall, an RSA generator (with security parameter k) is a randomized algorithm KRSA (k) that returns a pair of keys (public, secret): # $ (N, e), (N, p, q, d) The keys can be used for signing and verifying: Sign. Signing a message M happens by “decrypting” M: σ = M d %N Verify. Verifying (M, σ) happens by “encrypting” σ: (M, σ) is correct iff M = σ e %N Teenage med AM Digital signatures A digital signature scheme DS = (K, S, V) is a triple of algorithms where pk K sk V σ′ A σ S M M′ 0/1 Correctness: V(pk, M, S(sk, M)) = 1 with probability one for all M. 5 / 74 Usage Step 1: key generation $ Alice lets (pk, sk) ← K and stores sk (securely). Step 2: pk dissemination Alice enables any potential verifier to get pk. Step 3: sign Alice can generate a signature σ of a document M using sk. Step 4: verify Anyone holding pk can verify that σ is Alice’s signature on M. 6 / 74 Dissemination of public keys The public key does not have to be kept secret but a verifier needs to know it is authentic, meaning really Alice’s public key and not someone else’s. Could put (Alice,pk) on a trusted, public server (cryptographic DNS.) Common method of dissemination is via certificates as discussed later. 7 / 74 Signatures versus MA schemes In a MA scheme: Verifier needs to share a secret with sender Verifier can “impersonate” sender! In a digital signature scheme: Verifier needs no secret Verifier cannot “impersonate” sender 8 / 74 Digital Signature: security In PSA M od N posolve Possible adversary goals: for d Find the secret ket SK Forge: produce a (new) pair (M, σ) that can be verified. Possible adversary abilities: knows PK known message attack chosen message attack Digital Signatures: security: chosen message attack Adversary possesses signed messages (M1 , σ1 ),... , (Mq , σq ) of Alice and produces a pair: (M, σ). Adversary wins if (M, σ) is a new signed message, that is, M ∕= Mi and V(PK, M, σ) = 1 Interpretation. Adversary cannot get a verifier V to accept σ as Alice’s signature of M, unless Alice has really previously signed M. This is even if adversary can obtain Alice’s signatures on messages of the adversary’s choice. RSA Signatures: non-secure version: K, S, V # $ Algorithm KRSA (k): returns (N, e), (N, p, q, d) Algorithm SN,d : Signing M happens by “decrypting” M: SN,d (M) = M d %N, so σ = SN,d (M) Algorithm VN,e : Verifying (M, σ) happens by “encrypting” σ: VN,e (M, σ) = 1 iff M = σ e %N To forge signature of message M, given N, e but not d, the adversary must compute M d %N, meaning invert RSA at M. But RSA is 1-way so this task should be hard and the scheme should be secure. Correct? Ng Attacks on non-secure RSA signatures Goal. Produce (M, σ) such that VN,e (M, σ) = 1, which is equivalent to σ = M d %N. Easy 1,1 1 1ᵈ N Given Ms 0s Ms 02 the adversary can make a new one M o GE Md Fft tm.dz and Not clear 0.02 M.d.MG MM2d So 0 002 MMM More formal verification M M2 501 1 iff Mime 0,0218 ou M.mil mmol e 0,02 oe.ae mid MI M M Attacks on non-secure RSA signatures Goal. Produce (M, σ) such that VN,e (M, σ) = 1, which is equivalent to σ = M d %N. Here is how. ◮ Note that 1 = 1d %N, so (M, σ) = (1, 1). ◮ Recall adversary knows PK = (N, e). Pick any σ; then: compute M = σ e %N; so the forge pair is (M, σ) :) Indeed, recall VN,e (M, σ) = 1 iff M = σ e %N ◮ The RSA function is homomorphic: SN,d (M1 · M2 %N) = SN,d (M1 ) · SM2 %N. Thus, if Alice has signed (M1 , σ1 ) and (M2 , σ2 ), adversary can produce (M1 M2 %N, σ1 σ2 %N). RSA Signatures: SECURE version with Hash function Fixing RSA signatures. Pick a hash function H and hash M before applying the RSA function. # $ Algorithm KRSA (k): returns (N, e), (N, p, q, d) (same) Algorithm SN,d : Signing M: SN,d (M) = H(M)d %N, so σ = SN,d (M) Algorithm VN,e : Verifying (M, σ): VN,e (M, σ) = 1 iff H(M) = σ e %N Jer Forgery. Suppose adversary knows (M1 , σ1 ),... , (Mq , σq ). Adversary computes collision: H(N MM i ) = H(Mi ) for some new M Ni ∈ MM Mi , σi ) is a forge signature. S t / {M1 ,... , Mq }. Then, (N Conclusion. The hash function H must be CR. HCM Hemi  a Fixing RSA signatures. Pick a hash function H and hash M before applying the RSA function. # $ Algorithm KRSA (k): returns (N, e), (N, p, q, d) (same) Algorithm SN,d : Signing M: SN,d (M) = H(M)d %N, so σ = SN,d (M) Algorithm VN,e : Verifying (M, σ): VN,e (M, σ) = 1 iff H(M) = σ e %N Previous attacks. ◮ Before 1 = 1d %N. Now 1 ∕= H(1)d %N ◮ Before (M1 M2 )d ≡ M1d · M2d mod N. Now H(M1 M2 )d ∕≡ H(M1 )d · H(M2 )d mod N. A good hash function H prevents those attacks. DSA Signatures: non-secure version Ip is one of the 1 factor ofp p 1 prime fog Parameters. The set-up for DSA signatures is as follows. ◮ Pick primes p, q such that q | (p − 1), that is, q divides p − 1 o ◮ Let g ∈ Z∗p such that o(g ) = q, that is, 〈g 〉 has q elements. $ ◮ Keys: SK = x ← Zq and PK = X = g x %p Signing and Verifying. Let m ∈ Zq. ! k " ◮ Signature of m: (r , s) = (g %p)%q, (m + xr )k %q −1 $ where o k ← Z∗q. (Try again in the unlikely case that s is 0) # $ ◮ Verification test: r = g ms −1 %q X rs −1 %q %p %q S mtxr k Ks Mtxt k St mtxr stmts.tt k f imts ixr 9 Hence gk gas xrs 1 89 1 p 9ms Ogers 1 11 9 yrs p gas 1 Hence 84517 9 yrs 9 p gk p r Some details About the generator g. Consider the two primes p, q as specified above. If h is a known generator of Z∗p then g = h(p−1)/q is a generator of Z∗q. Two primes. The double mod operator adds an extra level of “randomness” and, at the same time, the mod q operator produces a smaller signature than what mod p would produce. FIPS 186. The Digital Signature Standard (DSS) is described in detail in https://csrc.nist.gov/publications/fips DSA Signatures: Forgery of non-secure version ! " We want to choose m, (r , s) such that m, r , s ∈ Z∗q and ms −1 %q rs −1 %q r ≡ g X %p mod q Notice that the main restriction is that r appears on both sides of the above congruence, but m, s can be chosen ! freely. If "we choose −1 ms −1 %q any m and s = r %q, then r must be g X %p %q. DSA Signatures: secure version using a Hash function Parameters. The set-up for DSA signatures is as follows. ◮ Pick primes p, q such that q | (p − 1), that is, q divides p − 1 ◮ Let g ∈ Z∗p such that o(g ) = q, that is, 〈g 〉 has q elements. $ ◮ Keys: SK = x ← Zq and PK = X = g x %p ◮ H : {0, 1}∗ → Zq is a CR and OW hash function. Signing and Verifying. Let M ∈ {0, 1}∗ and m = H(M) ∈ Zq. ! k ◮ Signature of M: (r , s) = (g %p)%q, (m + xr )k %q $ −1 " 0 where k ← Z∗q. (Try again in the unlikely case that s is 0) # ◮ Verification test: r = g ms −1 %q X rs −1 %q $ %p %q James......RSA ATTACKS – INTEGER FACTORING end mod EA a Pi9 If we knew acN Can we compute (N), given N? thenthe secret Inverse This problem is at least as hard as factoring N; that is, if I can of compute (N), then I can also factor N = p ⇥ q. thepubl e mode can be found nor the GCD extended ANYTHING BELOW NOT DONE LEFT HERE FYI Finding Generators: Randomly Pick and Check Recall, we have a cyclic group G with some identity 1. Thus, G = hg i = {g 0 , g 1 ,... , g m 1 }. E.g, G = Z⇤p. repeat $ g G \ {1} until (TEST GENG (g ) = True) How many iterations does the algorithm take? How do we design TEST GENG ? If G = Z⇤p , where p is a prime, then this test is easy if the prime factorization of p 1 is known. Theorem. In Z⇤p , g is a generator (=primitive element), IFF for every prime factor q of p 1 we have that g (p 1)/q 6⌘ 1. Note: p > 2....Finding Generators: Randomly Pick and Check Of course, the problem with the above theorem is that factoring a large number like p 1 is hard. One method to find a prime p and a generator g of Z⇤p is to construct a composite p 1 with n + 1 factors as follows: 1. Select n random primes q1 ,... , qn. 2. Select n + 1 random exponents e0 , e1 ,... , en. 3. Define the number p = 1 + 2e0 q1e1 · · · qnen 4. Confirm that p is prime. If p is prime, then the prime factors of p 1 are known: 2, q1 ,... , qn. Finding Generators using SAFE primes Recall, we have a cyclic group G with some identity 1. Thus, G = hg i = {g 0 , g 1 ,... , g m 1 }. E.g, G = Z⇤p. repeat $ g G \ {1} until (TEST GENG (g ) = True) How many iterations does the algorithm take? How do we design TEST GENG ? We shall work with G = Z⇤p , where p is a safe prime: p is prime and p 1 = 2q for some prime q. Example: 7 is safe: 7 1 = 6 = 2 · 3, but 13 is not a safe prime. Generators mod 7 Let G = Z∗7 = {1, 2, 3, 4, 5, 6} i 1 2 3 4 5 6 1i 1 1 1 1 1 1 2i 2 4 1 2 4 1 3i 3 2 6 4 5 1 4i 4 2 1 4 2 1 5i 5 4 6 2 3 1 6i 6 1 6 1 6 1 The generators are 57 / 70 Generators mod 7 Let G = Z∗7 = {1, 2, 3, 4, 5, 6} i 2 3 1i 1 1 2i 4 1 3i 2 6 4i 2 1 5i 4 6 6i 1 6 We observe that g is a generator if and only if g 2 ̸= 1 and g 3 ̸= 1. 58 / 70 Testing whether a g is a generator RECALL: Theorem. In Z⇤p , g is a generator (=primitive element), IFF for every prime factor q of p 1 we have that g (p 1)/q 6⌘ 1. Note: If p is safe, then p 1 = 2q has two prime factors: 2, q. Corollary. Let p be safe. Any g 2 Z⇤p is a generator IFF g 2 6⌘ 1 and g q 6⌘ 1. Example. Let p = 7 safe. Then, p 1 = 2 · 3, so any g 2 Z⇤7 is a generator IFF g 2 6⌘ 1 and g 3 6⌘ 1. Fact. p 1 is never a generator of Z⇤p. Why? (p 1)2 = pp 2p + 1 ⌘ 0 0 + 1 = 1. RECALL: Finding Generators using SAFE primes For G = Z⇤p with p = 2q + 1 safe: repeat $ g G \ {1, p 1} // recall p 1 is never a generator until (g 2 6⌘ 1 and g q 6⌘ 1) How many iterations does the algorithm take? It depends on how many generators Z⇤p has. How many generators does Z⇤p have? If p is safe, then p 1 = 2q and Z⇤p has q 1 generators. Finding Generators using SAFE primes For G = Z⇤p with p = 2q + 1 safe: repeat $ g G \ {1, p 1} // recall p 1 is never a generator until (g 2 6⌘ 1 and g q 6⌘ 1) How many iterations does the algorithm take? It takes about 2 iterations ANYTHING BELOW NOT DONE LEFT HERE FYI ElGamal Signatures Let G = Z∗p = ⟨g ⟩ where p is prime. $ Signer keys: pk = X = g x ∈ Z∗p and sk = x ← Zp−1 Algorithm VX (m, (r , s)) Algorithm Sx (m) $ if (r ∈ / G or s ∈ / Zp−1 ) k ← Z∗p−1 then return 0 r ← g k mod p if (X r · r s ≡ g m mod p) s ← (m − xr ) · k −1 mod (p − 1) then return 1 return (r , s) else return 0 $ Correctness check: If (r , s) ← Sx (m) then xr +ks xr +k(m−xr )k −1 mod (p−1) r s X ·r = g g xr ks =g =g = g xr +m−xr = g m so VX (m, (r , s)) = 1. 65 / 74 ElGamal Signatures Let G = Z∗p = ⟨g ⟩ where p is prime. $ Signer keys: pk = X = g x ∈ Z∗p and sk = x ← Zp−1 Algorithm VX (m, (r , s)) Algorithm Sx (m) $ if (r ∈ / G or s ∈ / Zp−1 ) k ← Z∗p−1 then return 0 r ← g k mod p if (X r · r s ≡ g m mod p) s ← (m − xr ) · k −1 mod (p − 1) then return 1 return (r , s) else return 0 $ Correctness check: If (r , s) ← Sx (m) then xr +ks xr +k(m−xr )k −1 mod (p−1) r s X ·r = g g xr ks =g =g = g xr +m−xr = g m so VX (m, (r , s)) = 1. 65 / 74 Security of ElGamal Signatures $ Signer keys: pk = X = g x ∈ Z∗p and sk = x ← Zp−1 Algorithm Sx (m) Algorithm VX (m, (r , s)) $ k ← Z∗p−1 if (r ∈ / G or s ∈ / Zp−1 ) r ← g k mod p then return 0 s ← (m − xr ) · k −1 mod (p − 1) if (X r · r s ≡ g m mod p) return (r , s) then return 1 else return 0 Suppose given X = g x and m the adversary wants to compute r , s so that X r · r s ≡ g m mod p. It could: Pick r and try to solve for s = DLog Z∗ ,r (g m X −r ) p Pick s and try to solve for r...? 66 / 74 Forgery of ElGamal Signatures Can we find m, (r , s) such that X r ⇤ r s ⌘ g m mod p? The answer is YES: Let m = ( r )%(p 1), r = (gX )%p, s = m. Then, Xrrs ⌘ X r (gX )s ⌘ X rX sgs ⌘ X r +s g s ⌘ X (r +s) % (p 1) g s ⌘ X (r r ) % (p 1) g s ⌘ gs ⌘ g m mod p. So (r , s) is a valid forgery on m. ElGamal with hashing Let G = Z∗p = ⟨g ⟩ where p is a prime. $ Signer keys: pk = X = g x ∈ Z∗p and sk = x ← Zp−1 H : {0, 1}∗ → Zp−1 a hash function. Algorithm Sx (M) Algorithm VX (M, (r , s)) m ← H(M) m ← H(M) $ k ← Z∗p−1 if (r ∈ / G or s ∈ / Zp−1 ) r ← g k mod p then return 0 s ← (m − xr ) · k −1 mod (p − 1) if (X r · r s ≡ g m mod p) return (r , s) then return 1 else return 0 Requirements on H: Collision-resistant One-way to prevent previous attack 68 / 74