Public key cryptosystems based on Discrete logarithms Flashcards
How does the Diffie-Hellman key exchange work?
Secret sharing over insecure communication channels
Public:
- Generator g of a multiplicative group G of order t
A: select a, 0 < a
B: select b, b < t
A -> B: g^a
B -> A: g^b
Both compute key Z = g^ab
Secret value Z can be used to compute a key
Example in Z_p^*
Public:
p = 181
g: 2
A: a = 50
B: b = 33
A -> B: g^50 mod 181 = 116
B -> A: g^33 mod 181 = 30
A: Z = 30^50 mod 181
B: Z = 116^33 mod 181
Z = 49
Define the security of Diffie-Hellman
The protocol can be broken if an attacker finds discrete logarithms in group G
- intercepts g^a and take the discrete log to obtain a
- compute g^ab
What is the Diffie-Hellman problem?
The problem of finding Z=g^ab from knowledge of g^a and g^b
How can a man-in-the-middle attack be used on Diffie-Hellman?
DH are not authenticated.
Neither A or B knows who the secret Z is shared with.
Because of this, an adversary can set up 2 keys, one with A and one with B, and relay messages between the two
What are ephemeral keys?
Keys that are used once and then discarded
How does static Diffie-Hellman work?
A chooses a long-term private key Xa with corresponding public key Ya = g^Xa
B chooses a long-term private key Xb with corresponding public key Yb = g^Xb
Shared secret can be found by looking up each others public key:
S = g^XaXb
What does it mean that a secret is static in the Static DH?
The key stays the same long-term, until the public keys are changed
What is the Elgamal cryptosystem?
Turns the DH protocol into a cryptosystem
A combines their ephemeral private key with B’s long-term public key
Describe Elgamal key generation
Select prime p and generator g of Z_p^*
Select long-term private key x where 0 < x < p-1
y = g^x mod p
Public key: (p, g, y)
Describe encryption in Elgamal
Public key: Ke = (p, g y)
- For any value M where 0 < M < p
- Choose k at random and compute g^k mod p
- C = E(M, Ke) =
(g^k mod p, M*y^k mod p)
y^k mod p is a mask for the message M
Describe decryption in Elgamal
Private key: Kd = x, with y = g^x mod p
1: C = (C1, C2)
2. Compute C_1^x mod p
3. D(C, Kd) = C_2 * (C_1^x)⁻1 mod p = M
What is the security of Elgamal?
The system can be broken if the discrete log problem is solved by determining the private key x from g^x mod p
Possible for many users to share the same p and g values
Has a proof of security in a suitable model subject to the difficulty of the decision DH problem
Describe the discrete log problem over Z_p
p: large prime
g: generator of multiplicative group Z_p
For any non-zero element in Z_p, we can find a unique i between 1 and p-1 such that a = g^i mod p
log_g(a) = i mod p
What is the definition of the discrete log problem?
given a,
find log_g(a) (mod p)
For a sufficiently large p, this is an intricate problem
