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
How is discrete log problem is used in public key ciphers?
Implementation of these depends on this property:
a^p-1≡1
for all nonzero elements in Z_p
Why does discrete log ciphers modulo p offer the same level of security as RSA?
Solving the discrete log problem over Z_p is comparable to the difficulty of factoring n, where n is the product of 2 primes, if the number of bits in n is the same as the number of bits in p.
What are elliptic curves?
Algebraic structures formed from cubic equations.
Elliptic fields can be defined over any field.
Example:
Set of all (x,y) which satisfy:
y²=x³+ax+b mod p
What is an elliptic curve group?
When we have elliptic curves, once an identity element is added, a binary operation can be defined on these points.
With the operation, the elliptic curve points form an elliptic curve group
How are elliptic curve computations denoted?
The operation can be denoted by any symbol, but by convention it is called elliptic curve addition:
P + Q = R
Shows group operation on curve points P and Q with the result R
What is the elliptic curve discrete log problem?
Find value m, given point P and generator G so that
P = mG = G + G +…+ G (m times)
The same as in Z_p^* but with addition as the group operation instead of multiplication
Name 3 ways of representing elliptic curves?
Short Weierstrass
Montgomery: Allows fixed time elliptic curve multiplication
Edwards: Allows faster group operations
How are elliptic curves chosen?
A new curve can be generated at any time, but usually standard curves are used.
The predefined set of curves exist because they are generated in a way to ensure no hidden special properties.
How are elliptic curves used in cryptography?
Widely deployed
Most cryptosystems based on discrete logarithms can be constructed with elliptic curves as well as in Z_p^*
For example, DH and Elgamal can be run on elliptic curves
How will public key cryptography be affected by post-quantum computers?
Broken due to Shor’s algorithm for factorisation.
This algorithm can also be used to find discrete logarithms.
How will symmetric key cryptography be affected by post-quantum computers?
Can still be used, but with double length keys due to Grover’s algorithm for searching
