Section 4.5 Elliptic curve Diffie-Hellman key exchange and El Gamal
We are now prepared to give the elliptic curve versions of Diffie-Helman key exchange and the related Elgamal-type cryptosystem. These can be thought of as “positive” applications of elliptic curves in cryptography. It should be noted that the early use of elliptic curves in this setting was “negative” in the sense that several powerful factoring algorithms to attack problems in \(\F_p\) use elliptic curve methods.
Diffie-Hellman key exchance over \(E(\F_p)\) looks very similar to the algorithm presented in Algorithm 3.3.2, but with the operations shifted into the additive notation.
Algorithm 4.5.1. EC Diffie-Hellman.
- (public) Alice and Bob choose an elliptic curve over a finite field \(E(\F_p)\) and an element \(P\) of large prime order \(k\) in \(E(\F_p)>\text{.}\)
- (private) Alice and Bob choose secret integers \(1 \leq n_A, n_B \leq k\text{.}\)
- (private) Alice computes \(A = n_a P\) and Bob computes \(B = n_b P\text{.}\)
- (public) Alice and Bob exchange the points \(A\) and \(B\text{.}\)
- (private) Alice computes \(Q = a B = a b P\text{.}\) Bob computes \(Q = b A = b a P\text{.}\)
- (private) Alice and Bob now possess a shared secret key \(Q \in E(\F_p)\text{.}\)
As in the case over \(\F_p\text{,}\) an attacker Eve can break the system if the can solve the ECDLP. But this isn't the problem that she actually needs to solve.
Definition 4.5.2.
The elliptic curve Diffie-Hellman problem (ECDHP) is to find, given \(E(\F_p)\) and \(P \in E(\F_p)\text{,}\) the value of \(n_a n_b P\) from known values of \(n_a P\) and \(n_b P\text{.}\)We've at least hinted at the appeal of elliptic curves: storage required for security is growing as computers continue to increase in speed. With that in mind, we point out another place where elliptic curves can be made more efficient. The point \(A\) that Alice sends Bob has two coordinates, but she really only needs to send Bob the \(x\)-coordinate, since Bob can compute the value of \(y^2\) from the knowledge of the elliptic curve \(E\text{.}\) A complication arises where Bob might compute the wrong square root of \(y^2\text{,}\) but in that case he can flip the sign on the \(y\)-coordinate to get the inverse. Of course, this leaves open the important question of how Bob can compute square roots in \(E(\F_p)\text{,}\) a question that we leave open for now.
Question 4.5.3.
The trade-off is computation for storage, which is going to end up a running theme in the second half of the course. The issues start to arise because of the way that key sizes have scaled with CPU power and mathematical advances. Currently, the high security standard for the symmetric AES cryptosystem is 256-bit keys (\(n \sim 2^{256}\)). To get equivalent security in elliptic curves, key sizes are on the order of 521-bit (\(n \sim 2^{521}\)) and RSA/Elgamal keys are on the order of 15360-bit (\(n \sim 2^{15360})\) due to the existence of a method called the index calculus.
Now we introduce a direct generalization of the Elgamal system from Algorithm 3.4.1. There is a major flaw in the utility of this implementation which we'll point out after presentation. See if you can find it.
Algorithm 4.5.4. EC Elgamal.
- Alice chooses a large prime \(p\text{,}\) an elliptic curve \(E\text{,}\) a point \(P \in E(\F_p)\) of large prime order \(q\) and a secret key \(1 \leq n_a \lt q \text{.}\)
- Alice computes \(A = n_a P\text{.}\)
- Alice publishes \(E, p, P, A\text{.}\)
- Bob selects a point \(M \in E(\F_p)\text{.}\) He generates a one-time use random element \(1 \leq k \lt q\text{.}\)
- Bob computes \(c_1 = k P, c_2 = k A + M \text{.}\)
- Bob sends \((c_1, c_2)\) to Alice.
- Alice computes \(c_2 - n_a c_1 = \hat{M}\text{.}\)
Did you spot the problem? In Elgamal in \(\F_p\text{,}\) Bob can choose an arbitrary integer \(m\) to form his plaintext, which allows him to use encoding to change any text into a corresponding integer to encrypt. However, in the EC Elgamal version, Bob has to choose a point in \(E(\F_p)\text{,}\) and there isn't an obvious way to correspond those to messages. (The issue, of course, is that not every value of \(x \in \F_p\) corresponds to a point \((x, y) \in E(\F_p)\text{.}\))
A scheme by founders of the Certicom corporation (now owned by RIM) for working around this involves choosing two plaintext integers \(m_1, m_2\) and then “twisting” them into an elliptic curve point.
Algorithm 4.5.5. MV-Elgamal.
- (public parameters) Alice chooses \(E(\F_p)\) and \(P \in E(\F_p)\text{.}\)
- (private) Alice choose a secret key \(n_a\) and computes her public key \(A = n_A P\text{.}\)
- (public) Alice publishes \(E(\F_p), P, A\text{.}\)
- (private) Bob chooses two plaintext integers \(m_1, m_2 \in \F_p\text{.}\)
- (private) Bob generates a one time use random \(k\) and computes \(R = kP\) and \(S = k A\text{.}\)
- (private) Bob sets \(c_1 = x_S m_1 \bmod p\) and \(c_2 = y_S m_2 \mod p\text{.}\)
- (public) Bob sends Alice the encrpyted message \((R, c_1, c_2)\text{.}\)
- (private) Alice computes \(T = n_a R = (x_T, y_T)\text{.}\)
- (private) Alice finishes by computing\begin{align*} m_1' \amp= x_T\inv c_1 \bmod p\\ m_2' \amp= y_T\inv c_2 \bmod p \end{align*}and recovers \(m_1 = m_1', m_2 = m_2'\text{.}\) (The proof is left as an exercise.)