ECDSA (Elliptic Curve Digital Signature Algorithm)
[ECDSA Home][Home]
ECDSA has been around for over two decades and was first proposed in [1]. The ECDSA method significantly improved the performance of signing messages than the RSA-based DSA method. Its usage of elliptic curve methods speeded up the whole process and supported much smaller key sizes. Its crown and glory were being selected by Satoshi Nakamoto for his Bitcoin protocol, and then its adoption into Ethereum.
|
Theory
An outline of ECDSA is:
Creating key pair
With our curve, we have a generator point of \(G\) and an order \(n\). We start by generating a private key (\(d\)) and then generate the public key of:
\(Q=d.G\)
The public key is a point on the curve, and where it is derived from adding the point \(G\), \(d\) times.
Signing the message
With a message (\(m\)), we aim to apply the private key, and then create a signature (\(r,s\)). First we create a random nonce value (\(k\)) and then determine the point:
\(P=k.G\)
Next we compute the x-axis point of this point:
\(r=P_x \pmod n \)
This gives us the \(r\) value of the signature. Next, we take the hash value of the message:
\(e=H(m)\)
And then compute the \(s\) value as:
\(s=k^{-1}.(e + d.r) \pmod n
Verifying the signature
We can verify by taking the message (\(m\), the signature (\(r,s\)) and the public key (\(Q\)):
\(e=H(m)\)
Next we compute:
\(w =s^{-1} \pmod n\)
\(u_1 = e.w\)
\(u_2 = r.w\)
We then compute the point:
\(X = u_1.G + u_2.Q \)
And then take the x-co-ordinate of \(X\):
\(x = X_x \pmod n\)
If \(x\) is equal to \(r\), the signature has been verified.
Presentation
References
[1] Johnson, D., Menezes, A., & Vanstone, S. (2001). The elliptic curve digital signature algorithm (ECDSA). International journal of information security, 1(1), 36–63 [here].