Flashcards
ElGamal
Cards in this deck (18)
- 1Chocolate CRT?Given n1, ... , nk that are coprime and a1, ... , ak there's a unique x so x === a1 (mod n1) ... x === ak (mod nk)
- 2Setup for RSA Signatures?Signer generates an RSA key pair sk, pk = (d,n) (e,n) and publish identity (e,n)
Verifier generates a message m (mod n) - 3Sign for RSA Signatures?Compute sig === mod^d (mod n)
Send (sig, (e,n)) to verifier - 4Verify for RSA signatures?Check m === sig^e(mod m)
- 5Diffie-Hellman Key Exchange?
- 6What is the cyclic group Z/nZ - {0} and what should g be?{g (mod p), ... , g^(p - 1) (mod p)}
Large so it can take a lot of values - 7Setup for Elgamal Encryption?Diffie chooses prime p and generator g
Diffie chooses random secret d {1, .. , p-1} to get pkd = g^d (mod p)
Sends (p, g, pkd) to Hellman - 8Elgamal Encryption stage?Hellman chooses random secret h {1, .. , p-1} to get pkh = g^h (mod p)
Computes ss = pkd^h (mod p)
Compute encrypted message encm = m * ss
Send cipher (pkh, encm) - 9Elgamal Decryption stage?Diffie computes shared secret ss = pkh^d (mod p)
Computes cipher m = encm. pkh^(p -1 - d) - 10Setup for Elgamal signatures?Choose prime p and generator g in Z/pZ - {0}
Signer gets Diffie-Hellman (pk,sk)= (a, g^a (mod p)) where a is in [0, p - 1] and publishes pk as identity
Verifier generates message m (mod p - 1) - 11Sign for Elgamal?Pick nonce k in [0, p - 1]
Compute r === g^k (mod p)
Compute sig === k^-1(m - ar)(mod p - 1)
Publish signed message (r, sig) - 12Verify for Elgamal?Check g^m === pk^r * r^sig (mod p)
- 13How can an attacker get k and what's the equation?If two messages were used with the same nonce then k = (m1 - m2)/(sig1 - sig2) (mod p - 1)
- 14Use Euclid's algorithm to find the inverse of 3 (mod 7)?Worksheet
- 15What does applying Fermat's Little Theorem to 2^a === 17 (mod 37) result in?Computing a mod (36)
- 16Compute a (mod 36)Worksheet
- 17What is Hellman's secret?h(mod p - 1)
- 18If you had two pairs (r, sig1) (r, sig2) what can you tell about the message?The nonce has been reused as r is the same so sk = (m1 - ksig1)/r1
Information
- Description
- Cryptography Flashcards on ElGamal, created by Philip Masters on 13/01/2020.
- Created by
- Philip Masters
- Views
- 0
- Rating