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