Elliptic Curve Cryptography - Key Exchange and Signatures

Quick Links

• Part 1: New book on Elliptic Curve Cryptography
• Part 2: Elliptic Curve Cryptography - Basic Math
• Part 3: Elliptic Curve Cryptography - Security Considerations
• Part 4: Elliptic Curve Cryptography - Key Exchange and Signatures
• Part 5: Elliptic Curve Cryptography - Extension Fields
• Part 6: Elliptic Curve Cryptography - Multiple Signatures

To recap the basic math, an elliptic curve over a finite field has points $(x, y)$ which satisfy the equation $$y^2 = x^3 + a x + b \text{ mod } q.$$When points are added to themselves multiple times we write the multiplication as $$Y = k P$$where $k$ is an integer. Since the number of points is finite, after a while we get to a value of $k = n$ such that $$\mathscr O = n P. $$Where $\mathscr O$ is the point at infinity. We call $n$ the order of the point $P$. (See part 2 for more details.)

The best curves for cryptographic use have the order of the curve $\#E$ (that is, the total number of points on the curve) equal to the order of every point, and that number is a prime. The relationship between the field prime of the elliptic curve equation and the order of the curve is given by Hasse's theorem:$$\#E = q +1 - t$$and the value of $t$ is in the range $$2\sqrt q \ge t \ge -2\sqrt q$$ We can find curves for which $\#E = n$ is a prime. For details on how to do that, look at chapter 6 in Elliptic Curve Cryptography for Developers.

As shown in part 3, we can find a good cryptographic curve for which the ECDLP is too hard to solve. We can use that curve to create a secret key for message encryption. To do that we set up values which are private to each person and public for each person. The private values are never shown, and given the way elliptic curves work, they don't need to be stored either. The public values are either exchanged between parties, or published in some fashion. It's better to get a key from someone every time and compare it with previous times to help build trust that you are talking to the same person - but that is cyber security, not cryptographic security.

The best way to create a private key is to enter a phrase into a hash function and spit out a bunch of garbage bits. As long as the entered phrase is the same each time, the private key does not change. Remembering a phrase can be a problem - but again, that's not cryptographic security. Making cryptographic security user friendly is hard, but the more all the details can be hidden from users the more they will use real security without thinking about it.

Key Exchange

Let's assume we have a good cryptographic elliptic curve over a field $F_q$ with a prime number of points $n$. We pick a random point on the curve $G = (G_x, G_y)$ and publish the curve parameters $a$, $b$ and the point $G$. What this means is that the arithmetic for the curve is done modulo $q$, the values of $a$ and $b$ are modulo $q$, and the mathematics of the curve are modulo $n$. Every person who wants to use this curve selects a private key $r$ which is modulo $n$.

Let's suppose Albert and Barbara want to communicate using AES to encrypt and decrypt private messages. They need to create a secret key using public channels that anyone can eavesdrop on. The simplest way to create a secret is to use the elliptic curve version of the Diffie-Hellman protocol. 

Albert creates a private key $r_a$ using some method, and Barbara creates a private key $r_b$. They each then use point $G$ to create public keys with$$P_a = r_a G$$$$P_b = r_b G.$$Albert sends $P_a$ to Barbara and Barbara sends $P_b$ to Albert.

Using his private key, Albert computes $$S = r_a P_b$$and using her private key Barbara computes$$S = r_b P_a.$$ The value $S_x$ is then the shared secret key they can both use to encrypt messages using AES.

In part 3 I explained the elliptic curve discrete log problem (ECDLP). For good curves finding the values of $r_a$ or $r_b$ is not possible (yet - see using quantum computers to break ECC ) so the public transmission of the points $P_a$ and $P_b$ hide the private key values. 

The reason both Albert and Barbara get the same value $S_x$ is because $$S = r_a P_b = r_a r_b G$$and$$S = r_b P_a = r_b r_a G$$are the same points. Only the $x$ portion of the result is used for the AES key because $y$ is a simple function of $x$, and finding $x$ is the crux of the security.

Digital Signature

Another fundamental algorithm that relies on the intractability of solving the ECDLP is digital signature. The idea is to lock a specific document to a specific person. If the document changes or someone tries to spoof a signature, the verification process will fail.

The signing process uses a random number. For real security, this should be created using a hardware source. A different random number should be created for every signature, even if it is the same person and the same document on a different date. Let's call the random number $k$. We use the same curve and base point $G$ as in the key exchange to create the point$$Q = k G.$$The point $Q$ becomes a public key for the digital signature. The value of $k$ should be taken modulo $n$, and $Q$ should not be $\mathscr O$ - but the odds of a random value being $n$ is astronomically small.

Let's call the document to be signed $M$. The details of making sure everyone has the same $M$ on different platforms requires care. Some documents will have carriage return, line feed at the end of a line, some will have just carriage return, and others will have just line feed. It is absolutely essential that the signing operation and the verification operation use the exact same set of bits for $M$ or verification won't work.

A hash function is used to combine the point $Q$ with the document $M$. With the description $||$ meaning "concatenate" the value$$e = \text{ hash}(Q_x || Q_y || M)$$is computed. Let's now take Albert as the person signing the document. The digital signature Albert computes is$$s = k - e r_a \text{ mod }n.$$

The published value for the signature is $(s, Q)$. The value $e$ can be computed by anyone, and in fact that is required as part of the verification process. But nobody knows $r_a$ nor $k$, so using $s$ to find either one of those is more difficult than finding $k$ directly from $Q$. For even more security, the value of $k$ should be destroyed once $s$ is computed so no matter what happens, the signature can not be changed.

To verify that Albert signed the document $M$, you gather the document and the three values of the signature (the point $Q$ is two values $(Q_x, Q_y)$) along with Albert's public key $P_a$. You then compute$$e' = \text{ hash}(Q_x || Q_y || M)$$and check to see if$$Q' = s G + e' P_a \stackrel{?}{=} Q.$$If $Q' = Q$ the signature is verified, otherwise it fails.

The whole idea of a hash function is that if one bit changes on the input, half the bits change on the output. So the value of $M$ must be the exact same set of bits for $e$ and $e'$. Let's see how this works by expanding $s$:$$Q' = s G + e' P_a $$ $$= (k - e r_a) G  + e' P_a$$ $$ = k G - e r_a G + e' P_a $$ $$= Q + (e' - e)P_a.$$

As long as the value computed for $e'$ is exactly the same value computed in the original signature $e$, the last term is eliminated and result is a match. The value of $k$ is not known to anyone once the signature is finished, and is never required to be known again. Only the public key $Q$ is required to compute the hash of the document. 

There are other algorithms which are more sophisticated than these to prevent specific types of attacks from threatening security. They are similar in construction, so the basic ideas here should give you a good grounding in how the compute engine is working in the background when you use things like SSH or TLS with  elliptic curve cryptography.

Sign in