Elliptic Curve Digital Signatures

• Basics
• Networking

A digital signature is used to prove a message is connected to a specific sender.  The sender can not deny they sent that message once signed, and no one can modify the message and maintain the signature. The message itself is not necessarily secret. Certificates of authenticity, digital cash, and software distribution use digital signatures so recipients can verify they are getting what they paid for.

Since messages can be of any length and mathematical algorithms always use fixed length arguments the method used to compress a message to a fixed length is called "hashing".  A good hashing algorithm will change half its bits if any one bit of a message changes.  This makes it very very difficult to change a message and find the same hash value - which is possible simply because the result is much smaller than the message.

As of August 2015 the latest Secure Hash Algorithm recommended by the United States National Institute of Science and Technology is SHA-3. This is actually a family of algorithms based on a routine called Keccak developed by a group at STMicroelectronics.  A detailed description of the core of this hash function can be found in this pdf.  The algorithm has been designed to work well in both FPGA  and embedded environments.  Because dealing with hash functions is a few blogs in itself, I will just assume a hash function exists which will compress or convert any length message to the suitable length for the digital signature algorithm. 

Like all elliptic curve algorithms, the digital signature algorithm starts with a base point $B$ with large prime order on an elliptic curve.  We'll call the order of the point $p$.  The signer's secret key is $s$ and their public key is $S = s B$. To sign a message the first step is to compute the hash of the message $$e = Hash(\text{message}) \mod p$$ The second step is to pick a random value $r$ and compute the point $R = r B = (x, y)$. The two values of the signature are $$\begin{array}{c}c = x \mod p \\d = r^{-1}(e + s c)\end{array}$$ The values (c, d) are then the public signature of the message.

To verify a signature, the first step is to find the hash of the message $$e' = Hash(\text{message'})$$ followed by three more values $$\begin{array}{c}g = d^{-1} \mod p\\ g_1=e' g \mod p\\g_2= c g \mod p\end{array}$$ The main computation is $$R' = g_1 B + g_2 S=(x',y')$$ The final check is to see if $$c = x' \mod p$$ If it does, the signature is verified.

So why does it work? Let's expand the $g$, $g_1$ and $g_2$ terms.  First we have $$g = d^{-1}=r(e+sc)^{-1}$$ Then using this in $g_1$ and $g_2$ we have $$\begin{array}{c}g_1=e' r(e+s c)^{-1}\\g_2=c r(e+s c)^{-1}\end{array}$$ Putting these terms into the $R'$ equation we get $$\begin{array}{c}R'=g_1 B + g_2 S\\=e' r(e+s c)^{-1} B + c r(e+s c)^{-1}S\\=e' r(e+s c)^{-1}B + s c r(e+s c)^{-1} B\\=r(e'+s c)(e+sc)^{-1}B\end{array}$$

From this last equation we can see that if $e' = e$ the terms in parentheses will cancel and we get $R' =r B= R$.  This gives us the correct $x$ component which in turn gives the matching $c$ value.

Retyping a message usually will introduce errors.  White space characters are hard to replicate exactly, and even a one bit change in a message will destroy a hash result that matches the original.  That is the whole point of a digital signature. The signature will not verify (to extreme levels of probability) unless the message being checked is exactly the same as the message that was signed.

The main problem with digital signatures is the level of complexity. Not only does one need to compute elliptic curve math, one needs modular integer math and division (or inversion) as well as the hash algorithm. If the elliptic curve is over $GF(q)$ where $q$ is a large prime then the modular math functions are all ready available.  For FPGA or embedded systems this may not be an optimal choice.

An alternative digital signature which does not require modular inversion is called the Nyberg-Rueppel signature scheme. We similarly start with the signer's public key $S=s B$ and a random point $R=r B =(x, y)$ . The hash of the message is again $e = Hash(\text{message})$ but now we take $$c=x+e \mod p$$ and $$d=r-s c \mod p$$ The signature is again the pair $(c, d)$. The check only needs to compute $$R'=d B + c S$$ Then using the $x$ component of $R'$ the value $e'=c-x' \mod p$ is computed.  If the hash of the message sent $$e'=Hash(\text{message'})$$ matches this computed value then the signature is verified. 

The method works because $d B = (r-s c)B = r B - s c B$ and $c S = c s B$.  Adding these two gives $r B - s c B + c s B = r B = R$. This is the original $(x, y)$ value used in the signature, so $c-x = e$ is the value of the original hash.  If the new value $e' \ne e$ then the verification fails.

If an application really needs to avoid the modular integer math for speed and area concerns in embedded or FPGA environments, the point $D = d B = R - c S$ can be sent along with the value $c$ as the digital signature.  The verification is then done on the curve with $$R' = D + cS$$ and the check that $\text{Hash}(message')=e' = c - x'$.  This implements the full signature scheme without using integer modular arithmetic.

Sign in