DSA taking a expensive computation operation because it uses modular exponentiation and modular inverse. So in the small computer like microcontroller, we need the light weight algorithms. Elliptic Curve Digital Signature Algorithm (ECDSA) is one of them.
ECDSA is a variant of DSA which use Elliptic Curve Cryptography (ECC). If you have no idea about ECC please go through the ECC series.
ECDSA Operations
To go deeper into the operations we need look at some parameters:
\(\bullet \text{ Elliptic Curve, for example: } y^2 = x^3 + x + 3 \ mod \ 23 \) \(\\\)
\(\bullet \text{ Base point, G is a point on the Curve}\) \(\\\)
\(\bullet \text{ The order of G, denoted as n is the number of times G adds itself (can be call as group order n).}\) \(\\\)
\(\bullet \text{ Random select a private key:} \ d_{A}\) \(\\\)
\(\bullet \text{ Public key key:} \ d_{A}\times G \) \(\\\)
Signing process
\(\text{1. Calculate e = HASH(m)} \) \(\\\)
\(\text{2. Let z be the } L_{n} \ \text{leftmost bits of e, where} \ L_{n} \ \text{is the bit length of the group order n.}\) \(\\\)
\(\text{3. Select a cryptographically secure random integer k from } \left [ 1, n-1 \right ].\) \(\\\)
\(\text{4. Calculate the curve point:} \ \left ( x_1, y_1 \right ) = k\times G. \) \(\\\)
\(\text{5. Calculate} \ r = x_1 \ mod \ n. \ If \ r = 0, \text{go back to step 3.} \) \(\\\)
\(\text{6. Calculate} \ s = k^{-1}\times(z + r\times d_{A}) \ mod \ n. \text{If} \ s = 0, \text{go back to step 3.} \) \(\\\)
\(\text{7. The signature is (r, s).} \) \(\\\)
Verification process
\(\text{1. Verify} \ Q_{A} \ \text{is not} \ O \ \text{and, lies on the curve and} \ n*Q_{A}=O. \text{Where O is the unique point at infinity.}\) \(\\\)
\(\text{2. Check r and s are integer and in} \ \left [ 1, n-1 \right ]. \) \(\\\)
\(\text{3. Calculate e = HASH(m), where HASH is the same hash function with the sender}.\) \(\\\)
\(\text{4. Let z be the } L_{n} \ \text{leftmost bits of e}.\) \(\\\)
\(\text{5. Calculate } \ u_{1}=z\times s^{-1} \ mod \ n \ and \ u_{2}=r\times s^{-1} \ mod \ n. \) \(\\\)
\(\text{6. Calculate the curve point } \left ( x_{1}, y_{1} \right ) = u_{1}\times G + u_{2}\times Q_{A}, \left ( x_{1}, y_{1} \right ) = O \ \text{is invalid}.\) \(\\\)
\(\text{6. The signature is valid if} \ r=x_{1}.\) \(\\\)
Correctness of the algorithm
\(\text{Call: } \ C=u_{1}\times G + u_{2}\times Q_{A}, \text{From the public key is } \ Q_{A} = d_{A}\times G.\) \(\\\)
\(C= u_{1}\times G + u_{2}\times d_{A}\times G = (u_{1}+u_{2}\times d_{A})\times G\) \(\\\)
\(C = (z\times s^{-1} + r\times d_{A}\times s^{-1})\times G=(z+r\times d_{A})\times s^{-1}\times G\) \(\\\)
\(\text{From the signing process we have: } \ s = k^{-1}\times(z + r\times d_{A}) \ mod \ n\) \(\\\)
\(C= (z+r\times d_{A})\times (z+r\times d_{A})^{-1}\times (k^{-1})^{-1}\times G\) \(\\\)
\(C=k\times G.\text{ This is the point in step 4 of signing process.}\) \(\\\)
References
Elliptic Curve Digital Signature Algorithm – Wikipedia
Thanks for reading!