Encryption Based on Discrete Logarithm
1/9
Discrete logarithm
Let G be a finite group, b ∈ G, and k ∈ {0, . . . , ord(b) − 1}. For y = bk
, the number k is
called the discrete logarithm of y w.r.t. base b. For proper choices of G and b, it is believed to
be difficult to compute the value k given the knowledge of G, b and bk
.
2/9
Subgroup generated by b.
When focusing on discrete logarithms of base b ∈ G, we will be dealing with the values
⟨b⟩ = {1, b, b2
, . . . , bord(b)−1
},
(where ord(b) is the order of b in G).
The tuple (⟨b⟩, ·) is itself a group: a subgroup of Z×
N . We call it a subgroup generated by b.
The difficulty of discrete logarithm of base b in G is determined by the size and the algebraic
structure of (⟨b⟩, ·).
3/9
Cyclic groups
Definition 1: Cyclic group
A group (G, ·) is cyclic if there exists an element b ∈ G s.t.
G = {bn
| n ∈ N}.
The element b is called a generator of the group (G, ·).
4/9
Cyclic groups
Definition 1: Cyclic group
A group (G, ·) is cyclic if there exists an element b ∈ G s.t.
G = {bn
| n ∈ N}.
The element b is called a generator of the group (G, ·).
Fact 1
If the group we want to work with is not cyclic (e.g. Z×
N for most non-prime choices of N, or
certain elliptic curve groups), we use some cyclic sub-group of it that is given via it’s generator.
In the following, we assume that G is directly the cyclic group we work it.
4/9
Computing generators of cyclic groups
Fact 2
Let G = {1, b, b2
, bm−1
} be a cyclic group of order m. Then G has ϕ(m) generators.
I.e., the fraction of group elements that are its generators is ϕ(n)
n .
5/9
Computing generators of cyclic groups
Fact 2
Let G = {1, b, b2
, bm−1
} be a cyclic group of order m. Then G has ϕ(m) generators.
I.e., the fraction of group elements that are its generators is ϕ(n)
n .
Fact 3
Let G be a cyclic group of order m. Given a prime factorization of m, one can efficiently
compute a generator of G. (See Handbook of Applied Cryptography, algorithm 4.80)
5/9
Discrete logarithm in general cyclic groups
Definition 2: General discrete logarithm
Let (G, ·) be a finite cyclic group, b ∈ G some generator of the group, and k ∈
{0, . . . , ord(b) − 1}. For y = bk
the value k is called the discrete logarithm of y w.r.t.
base b in G, written k = dlogG
b (y). For a proper choice of G and b it is believed to be
difficult to compute, the value dlogG
b (y) given the knowledge of G, |G|, b, and y = bk
.
6/9
Discrete logarithm in general cyclic groups
Definition 2: General discrete logarithm
Let (G, ·) be a finite cyclic group, b ∈ G some generator of the group, and k ∈
{0, . . . , ord(b) − 1}. For y = bk
the value k is called the discrete logarithm of y w.r.t.
base b in G, written k = dlogG
b (y). For a proper choice of G and b it is believed to be
difficult to compute, the value dlogG
b (y) given the knowledge of G, |G|, b, and y = bk
.
The “proper choice” criteria include:
• |G| should be sufficiently large, to prevent DL computation by bruteforcing or, e.g., the
baby-step giant-step algorithm
• the operation of G should be efficiently computable
• |G| should not be smooth, this is to defend against DL algorithms whose runtime is
dominated by the term exponential in the bitsize of the largest prime factor of |G|
(Pohlig-Hellman algorithm, Pollard’s ρ algorithm for discrete logarithm)
6/9
Discrete logarithm in general cyclic groups
Definition 2: General discrete logarithm
Let (G, ·) be a finite cyclic group, b ∈ G some generator of the group, and k ∈
{0, . . . , ord(b) − 1}. For y = bk
the value k is called the discrete logarithm of y w.r.t.
base b in G, written k = dlogG
b (y). For a proper choice of G and b it is believed to be
difficult to compute, the value dlogG
b (y) given the knowledge of G, |G|, b, and y = bk
.
The “proper choice” criteria include:
• |G| should be sufficiently large, to prevent DL computation by bruteforcing or, e.g., the
baby-step giant-step algorithm
• the operation of G should be efficiently computable
• |G| should not be smooth, this is to defend against DL algorithms whose runtime is
dominated by the term exponential in the bitsize of the largest prime factor of |G|
(Pohlig-Hellman algorithm, Pollard’s ρ algorithm for discrete logarithm)
How to pick the right group?: The typical choices for G are Z×
p for a large prime p s.t. p − 1 is
not smooth, or groups generated by elliptic curves (next lecture).
6/9
Diffie-Hellman key exchange
Suppose that Alice and Bob want to securely establish a shared symmetric key. The oldest
public-key method for achieving this is the Diffie-Hellman key exchange scheme.
7/9
Diffie-Hellman key exchange
Suppose that Alice and Bob want to securely establish a shared symmetric key. The oldest
public-key method for achieving this is the Diffie-Hellman key exchange scheme.
Setup: Alice and Bob agree in advance on a cyclic group G of order |G|, and on its generator
b. Also, they fix a method for translating the elements of G into symmetric keys. This can be
negotiated over an insecure channel.
Exchange:
• Alice randomly samples a number α ∈ {1, . . . , |G| − 1} and sends mAlice = bα
to Bob
(keeping α secret).
• Bob randomly samples a number β ∈ {1, . . . , |G| − 1} and sends mBob = bβ
to Alice
(keeping β secret).
Key derivation:
• Alice uses her knowledge of α to compute kAlice = mα
Bob.
• Bob uses his knowledge of β to compute kBob = mβ
Alice. 7/9
Diffie-Hellman key exchange
Suppose that Alice and Bob want to securely establish a shared symmetric key. The oldest
public-key method for achieving this is the Diffie-Hellman key exchange scheme.
Setup: Alice and Bob agree in advance on a cyclic group G of order |G|, and on its generator
b. Also, they fix a method for translating the elements of G into symmetric keys. This can be
negotiated over an insecure channel.
Exchange:
• Alice randomly samples a number α ∈ {1, . . . , |G| − 1} and sends mAlice = bα
to Bob
(keeping α secret).
• Bob randomly samples a number β ∈ {1, . . . , |G| − 1} and sends mBob = bβ
to Alice
(keeping β secret).
Key derivation:
• Alice uses her knowledge of α to compute kAlice = mα
Bob.
• Bob uses his knowledge of β to compute kBob = mβ
Alice.
Then kAlice = (bα
)β
= (bβ
)α
= kBob!
7/9
Man-in-the-middle attack against Diffie-Hellman
DH key exchange is considered to be secure against passive adversaries. However, since it lacks
any authentication mechanism, it is susceptible to active (“chosen ciphertext”) attacks.
In practice, DH is extended with authentication mechanisms based on digital signatures to
achieve a secure key establishment. (E.g. the STS - station-to-station - protocol).
8/9
Further remarks on discrete logarithm
• DL-based techniques are also heavily used to design digital signature methods (e.g. DSA,
ECDSA – coming in a couple of weeks).
9/9
Further remarks on discrete logarithm
• DL-based techniques are also heavily used to design digital signature methods (e.g. DSA,
ECDSA – coming in a couple of weeks).
• In practice, Diffie-Hellman and other DL techniques are used either with a Z×
p group for a
suitable prime p or with a group generated by an elliptic curve. To achieve roughly the
same level of security, much larger key sizes are required for the Z×
p -based methods
compared to the elliptic curve methods. Hence, there is a general trend in public-key
crypto to switch to the elliptic curve techniques.
9/9
Further remarks on discrete logarithm
• DL-based techniques are also heavily used to design digital signature methods (e.g. DSA,
ECDSA – coming in a couple of weeks).
• In practice, Diffie-Hellman and other DL techniques are used either with a Z×
p group for a
suitable prime p or with a group generated by an elliptic curve. To achieve roughly the
same level of security, much larger key sizes are required for the Z×
p -based methods
compared to the elliptic curve methods. Hence, there is a general trend in public-key
crypto to switch to the elliptic curve techniques.
• A nice theoretical property of the discrete logarithm problem is its random self-reducibility:
Suppose, that for a given group G and its generator b there exists an algorithm which
efficiently computes dlogG
b (x) for a non-negligible fraction of possible inputs x. Then there
exists an efficient algorithm for computing dlogG
b (x) for all x ∈ G. That is, an average
instance of the DL problem has ± the same difficulty as the worst-case instance.
Similar properties are unlikely to hold for, e.g. NP-complete problems.
9/9