Section 3.4 The Elgamal cryptosystem
In their 1978 paper, Diffie and Hellman proposed a scheme called public key encryption, though they didn't provide an implementation. Two successful schemes that followed immediately from their work are the RSA family of methods (which are based on modular square roots) and the Elgamal family of methods (which are based on modular exponentiation). While RSA came first historically, the Elgamal cryptosystem is directly related to Diffie-Hellman key exchange, and so we are motivated to discuss it first. The Elgamal system is also readily adapted to more complicated setups, like groups on elliptic curves, which will be discussed later in this chapter.
An asymmetric or public key system is a one-way encrpytion scheme. That is, Alice provides certain information - the particular algorithm to be used, information about the keyspace and message space, and a public key \(k_{pub}\text{.}\) Bob uses that information to encrypt a message \(m\) as a ciphertext \(c\) that he sends to Alice. Alice then uses a piece of secret information, the private key \(k_{priv}\text{,}\) to decrypt the ciphertext back into the message.
The Elgamal system works as follows: Alice chooses a large prime \(p\) and an element \(g\) of large prime order in \(\F_p\ad\text{.}\) She then selects her private key, \(a \in \F_p\ad\text{.}\) She uses her key to compute her public key \(A = g^a\) and publishes \(p, g, A\text{.}\)
Bob chooses a plaintext \(m \in \F_p\ad\text{.}\) He generates a one-use only random element \(k \in F_p\ad\) (to emphasize that this is to be used only once, we sometimes refer to it as an ephemeral key), and he computes \(c_1 = g^k\) and \(c_2 = mA^k\text{.}\) He then sends the pair \((c_1, c_2)\) to Alice.
To decrypt the message, Alice computes the quantity
Then \(m' = m\text{.}\)
Algorithm 3.4.1. Elgamal.
- Alice chooses a large prime \(p\text{,}\) \(g \in F_p\ad\) of large prime order and \(a \in F_p\ad\text{.}\)
- Alice computes \(A = g^a\text{.}\)
- Alice publishes \(p, g, A\text{.}\)
- Bob selects a plaintext \(m\text{.}\) He generates a random element \(k\text{.}\)
- Bob computes \(c_1 = g^k, c_2 = mA^k\text{.}\)
- Bob sends \((c_1, c_2)\) to Alice.
- Alice computes \(c_2 (c_1^a)\inv\text{.}\)
How do we decide if the Elgamal system is secure? One method of proof is to show that the problem is equivalent in difficulty to the DHP, which we know to be at least as hard as the DLP. To prove this, we will use the concept of an oracle, a thought-experiement black box that we can endow with any particular ability that we choose. For the purpose of the next argument, we will posit the existence of an Elgamal oracle - that is, a function that takes as input \(p, g, A, (c_1, c_2)\) and produces a plaintext \(m\text{.}\) (Notice that the magic of the oracle is in not requiring knowledge of the private key \(a\text{.}\))
Proposition 3.4.2.
\(p, g\text{.}\)Proof.
Suppose that Eve has an Elgamal oracle, and that she wishes to compute the value of \(g^{ab}\) given known values of \(g^a\) and \(g^b\text{.}\) She knows that if she feeds the oracle a ciphertext \((c_1, c_2)\) that the oracle will return the quantity \(c2 (c_1^a)\inv\text{.}\) If Eve feeds the oracle the ciphertext \((g^b, 1)\text{,}\) then the oracle will return the quantity \(1\cdot(g^{ab})\inv.\) The fast inverse computation methods will allow Eve to calculate \(g^{ab}\) with little difficulty.
On the other hand, if Eve can solve the DHP, then she can compute \(g^{ak}\) from \(c_1 = g^k\) and \(A = g^a\text{.}\) Then it is straightforward for her to compute \(c_2 \cdot (g^{ak})\inv = m\text{.}\)
Thus, breaking Elgamal has equivalent difficulty to solving the DHP.