Elliptic Curve Key Exchange

Elliptic Curve Cryptography is used to create a Public Key system that allows two people (or computers) to exchange public data so that both sides know a secret that no one else can find in a reasonable time.  The simplest method uses a fixed public key for each person.  Once cracked, every message ever sent with that key is open.  More advanced key exchange systems have "perfect forward secrecy" which means that even if one message key is cracked, no other message will be.

To discuss crypto exchange systems we always have two sides.  Let's name side one Amelia and side two Brad.  For an elliptic curve key exchange everyone operates on the same curve with a fixed base point.  Call the base point $B$ and we'll assume it has order $p$ which is a very large prime number.  That means if we multiply $p B$ we get the "point at infinity".  

The simplest key exchange method is for both Amelia and Brad to create their own secrets $k_A$ and $k_B$.  They send the public version $P_A=k_A B$ and $P_B=k_B B$ to each other.  Then both sides have the same secret $S = k_A P_B = k_B P_A = k_A k_B B$. Note that this is not simple multiplication, it is multiple point addition over the elliptic curve.

The problem is that this secret $S$ is the same for every message.  Given enough messages and time, an attack can be mounted to crack one of the keys.  This would allow the attacker to crack every message ever sent.  To prevent this a couple of methods have been developed to inject a random number for each key exchange.  The first method I'll describe was developed by El Gamal, and this is an elliptic curve version of it.

Amelia initiates the communications by creating two random numbers $m$ and $r$.  She creates the points $P_m=m B$ and $P_r=r B$. The shared secret key is the $x$ component of $P_m$. She then combines the random number $r$ with Brad's public key and the point $P_m$ using $$P_h = P_m + r P_B$$ Amelia then sends the points $P_r$ and $P_h$ to Brad.

To recover the secret key, Brad first computes $$P_s=k_B P_r$$ He then finds $$P_m=P_h - P_s$$ Once this exchange has finished both sides have the $x$ component of $P_m$ as the secret key for message exchange.

To see how this works, notice that $r P_B=r k_B B = k_B P_r$.  When Brad computes $P_s$ he undoes the point hiding because $$P_h - P_s = P_m + r P_B - k_B P_r = P_m + r k_B B - k_B r B= P_m$$ The advantage of this protocol is that the secret key is a random value every time.  The only disadvantage is that it does not use Amelia's secret key at all, so there is no verification on Brad's side he is actually talking to Amelia.

If Amelia and Brad exchange their public keys offline they can eliminate "man in the middle" attacks where someone pretends to be a person and substitutes their own key for the real one.  A protocol which includes both sides public keys as well as random values was developed by Menezes, Qu and Vanstone and is called the MQV algorithm.  

This algorithm uses the order of the base point (call it p) to compute an integer value modulo p.  This combines integer math with elliptic curve math.  It works because adding points of prime order on an elliptic curve is the same thing as working with integers modulo that prime value.  

We start with the same public keys as before$$\begin{array}{c}P_A=k_A B=(x_A, y_A)\\ P_B=k_B B=(x_B, y_B)\end{array}$$  But this time both Amelia and Brad pick random numbers $r_A$ and $r_B$ and compute points $$\begin{array}{c}R_A=r_A B=(u_A, v_A)\\ R_B=r_B B=(u_B, v_B)\end{array}$$ which they exchange with each other. In both cases I've shown the $x$ and $y$ values of each point.  The protocol uses these values as integers by computing modulo p. In the elliptic curve math they are not necessarily integers, they can be polynomials over $GF(2^n)$. The translation is trivial, the same bit patterns are used to mean $GF(2^n)$ polynomials when representing points on an elliptic curve or integers when doing multiplication.

Amelia computes $$s_A=r_A+u_A x_A k_A \mod p$$ She then does the elliptic curve sum $$U_A=R_B + u_B x_B P_B$$ Finally she finds the point $$W = s_A U_A$$ and uses the $x$ component of this as the shared secret.

Brad computes a similar set of values with $$s_B=r_B + u_B x_B k_B \mod p$$ and $$U_B=R_A + u_A x_A P_A$$ He then finds the $x$ component of $$W=s_B U_B$$ and gets the same secret as Amelia.

To see why it is the same secret, expand $U_A$ into its base components. $$\begin{array}{c}U_A=R_B+u_B x_B P_B\\=r_B B + u_B x_B k_B B \\= (r_B + u_B x_B k_B)B\end{array}$$ Similarly when we expand $U_B$ into its base components we get $$\begin{array}{c}U_B=R_A + u_A x_A P_A\\ =r_A B + u_A x_A k_A B\\ = (r_A + u_A x_A k_A)B\end{array}$$ From here it is easy to see both sides have the same value since $$ W=s_A U_A = (r_A+u_A x_A k_A)(r_B+u_B x_B k_B)B=s_B U_B$$

Anyone who intercepts the communications can compute $U_A$ or $U_B$.  Since they do not know any of the secret values ($r_A$, $r_B$, $k_A$, or $k_B$) they can not compute $s_A$ nor $s_B$.  Even if they do find a solution to the elliptic curve log problem for one of the keys, at most they can crack one message.  They would have to do the same amount of work to crack any previous (or future) message because the random values change each time.

In an FPGA an engineer may not want to include space for a modular multiply if most of the area is used for doing the polynomial math and elliptic curve multiply functions.  The MQV algorithm can be computed using only elliptic curve math which eliminates the need for the modular math routines.  Instead of computing $s_A$ Amelia can compute $$\begin{array}{c}W=s_A U_A\\ = (r_A + u_A x_A k_A)U_A \\=r_A U_A  + u_A x_A k_A U_A\end{array}$$ Similarly Brad can compute $$\begin{array}{c}W=s_B U_B\\ = (r_B+u_B x_B k_B)U_B\\ =r_B U_B + u_B x_B k_B U_B\end{array}$$ Both sides still have the same secret. If one side is a card with limited gates and the other side is a full workstation then the card side can do the math solely on the curve and the workstation can do the modular multiply first and then do the elliptic curve multiply. The MQV algorithm is nicely flexable as well as secure.

Ideally the random numbers used to create the secret keys are never stored and immediately erased once the secret key is proven exchanged so that academic attacks are impossible. These Elliptic curve key exchange protocols allow both sides to verify they are talking to the correct person, and they can have a different secret key every transmission.  This not only improves security, it maintains security for a long time in the future.  

Sign in