> For the complete documentation index, see [llms.txt](https://thias-organization.gitbook.io/p256-documentation/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://thias-organization.gitbook.io/p256-documentation/elliptic-curve-digital-signature-algorithm-ecdsa.md). # Elliptic Curve Digital Signature Algorithm (ECDSA) The Elliptic Curve Digital Signature Algorithm (ECDSA) is a widely used cryptographic algorithm for creating digital signatures, leveraging the security and efficiency of elliptic curve cryptography (ECC). A very simple implementation of ECDSA verification can be found [here](https://github.com/tsumian/ecdsa). By default, it is specific to the NIST P-256 curve, but it could be customised for other elliptic curves as well. In the following sections, we will use the code to understand the process of ECDSA. ## Key Generation The very first step is key generation. The ECDSA key pair consist of a **private key** and a **public key**. The private key is a random integer in the range $$\[0 \dots n - 1]$$ where $$n$$ is the order of the elliptic curve ```rust fn generate_private_key(order: &BigInt) -> BigInt { let mut rng = rand::thread_rng(); let priv_key = rng.gen_bigint_range(&BigInt::from(1u8), order); priv_key } ``` The public key is a point on the elliptic curve, calculated by multiplying the generator point with the private key. > *Note that in this multiplication, we are using*$$\mod p$$ *because we are dealing with point arithmetic. In the code, every multiplication is called using* `scalar_mult` *for convenience but differs in the* `modulo` *parameter.* ```rust fn generate_public_key( priv_key: &BigInt, generator_point: &(BigInt, BigInt), modulo: &BigInt, a: &BigInt, ) -> (BigInt, BigInt) { scalar_mult(priv_key, generator_point, modulo, a) } ``` In the main function we can simply call `generate_private_key()` to get a random key. Then we multiply the generator point, defined as `(gx, gy)`, by the `priv_key` to get the corresponding `public_key` ```rust let n: BigInt = BigInt::from_str_radix(&N_STRING, 16).unwrap(); let p: BigInt = BigInt::from_str_radix(&P_STRING, 16).unwrap(); let gx: BigInt = BigInt::from_str_radix(&GX_STRING, 16).unwrap(); let gy: BigInt = BigInt::from_str_radix(&GY_STRING, 16).unwrap(); let a: BigInt = BigInt::from_str_radix(&A_STRING, 16).unwrap(); // Key generation let priv_key = generate_private_key(&n); let g = (gx.clone(), gy.clone()); let public_key = generate_public_key(&priv_key, &g, &p, &a); ``` ## Signing The ECDSA signing algorithm takes as input a message and a private key to return a signature as an output. The signature produced consists of a pair of integers `(r, s)` and the simplified steps are as follows ### 1) Calculate message hash Calculate the message **hash**, using a cryptographic hash function like SHA-256 in this case ```rust let mut sha256 = Sha256::new(); sha256.update(message); let hash_string: String = format!("{:X}", sha256.finalize()); let h: BigInt = BigInt::from_str_radix(&hash_string, 16).unwrap(); ``` ### 2) Generate another random number We need a random integer $$k$$ in the range $$\[0 \dots n - 1]$$ to generate a random point $$R$$ ```rust let k = match k { Some(key) => key.clone(), None => generate_random_key(order), }; ``` ### 3) Calculate random point Given $$k$$ we can find $$R = k \* G$$ and take the $$x$$-coordinate of $$R$$ as the value $$r$$ of the signature ```rust // r is the x-coordinate let (r, y) = scalar_mult(&k, generator_point, modulo, a); ``` ### 4) Calculate the signature proof To complete the signature, we will need the signature proof $$s = k^{-1} \* (h + r \*privKey) \mod n$$. For this we have a function `calculate_signature_proof` that calculates the [multiplicative modular inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) of $$k$$ and its product with the result of $$(h + r \* privKey)$$ ```rust fn calculate_signature_proof( k: &BigInt, h: &BigInt, r: &BigInt, priv_key: &BigInt, modulo: &BigInt, ) -> BigInt { let k_inv = inv_mod(k, modulo).expect("Multiplicative inverse does not exist!"); let mut temp = mul_mod(r, priv_key, modulo); temp = add_mod(h, &temp, modulo); let s = mul_mod(&k_inv, &temp, modulo); s } ``` In the unlikely event that $$s = 0$$ start again with a different random $$k$$. The signature pair `(r, s)` encodes the random point $$R$$ along with a proof $$s$$ to show that the signer knows the message $$h$$ and the private key. ## Signature Verification The ECDSA signature verification algorithm takes in the signed message, the signature (from the [signing algorithm](#signing)) and the public key as inputs, and returns a boolean value to indicate a successful or unsuccessful verification. The idea of signature verification is to recover the point $$R'$$ using the public key and check whether it is the same point $$R$$ [generated during the signing process](#id-3-calculate-random-point). The algorithm works as follows: ### 1) Calculate message hash The same way as we did [previously](#id-1-calculate-message-hash). ### 2) Calculate the modular inverse of signature proof We want to get the modular inverse $$s1 = s^{-1} \mod n$$. This can be done so by using `BigInt`'s `modinv` function ```rust fn inv_mod(x: &BigInt, p: &BigInt) -> Option { if *x == BigInt::ZERO || *p == BigInt::ZERO { panic!("Multiplicative inverse does not exist!"); // No inverse if x or p is zero } // Use BigInt's modinv function match x.modinv(p) { Some(inv) => Some(inv), None => None, // No inverse if modinv returns None } } let s1 = inv_mod(s, order).expect("Multiplicative inverse does not exist!"); ``` ### 3) Recover the random point used during signing To recover the random point, we need to calculate $$R' = (h \* s1) \* G + (r \* s1) \* pubKey$$. We can think of $$p$$$$(h \* s1) \* G$$ as the first point and added to $$(r \* s1) \* pubKey$$ which is the second point ```rust let c1 = h.clone() * s1.clone(); let point_1 = scalar_mult(&c1, generator_point, modulo, a); // (h * s1) * G let c2 = r.clone() * s1.clone(); let point_2 = scalar_mult(&c2, public_key, modulo, a); // (r * s1) * pubKey ``` Then we take the $$x$$-coordinate of $$R'$$ to be $$r'$$ ```rust let (r_prime_x, r_prime_y) = point_add(point_1, point_2, modulo.clone(), a.clone()); ``` ### 4) Signature Validation Compare $$r'$$ and $$r$$. If they are equal, then signature is valid, else it is invalid ```rust assert_eq!(r_prime_x, r.clone()); r_prime_x == *r ``` ## Why Does This Work? Firstly, the signing steps encodes a random point $$R$$ through elliptic curve arithmetic transformations using the private key and the hash into the signature proof $$s$$. This is the **proof that the signer knows the private key** * Moreover, because of the difficulty of ECDLP, the signature `(r, s)` cannot reveal the private key Next, the verification step decodes the original point $$R$$ using the signature proof $$s$$ **using the public key** and message hash, and compares the $$x$$-coordinate of the recovered point with the $$r$$ value from the signature, without the knowledge of the private key! ### Proof that it works Mathematically! The signing and verification works because it is mathematically sound. We can work backwards from the signature verification step. $$R'$$ is defined as $$ \begin{align\*} R' &= (h \* s1) \* G + (r \* s1) \* pubKey \\&= (h \* s1) \* G + (r \* s1) \* (privKey \* G) \ &= (h + r \* privKey) \* s1 \* G \end{align\*} $$ Since $$s = k^{-1} \* (h + r \* privKey) \mod n$$ and $$s1 = s^{-1} \mod n$$ $$ \begin{align\*} s1 &= s^{-1} \mod n\\ &= (k ^{-1} \* (h + r \* privKey))^{-1} \mod n\\ &= k \* (h + r \* privKey)^{-1} \mod n \end{align\*} $$ Substitute $$s1$$ into $$R'$$ to get $$ \begin{align\*} R' &= (h + r*privKey)*s1*G\\ &=(h +r*privKey)*k*(h + r \* privKey)^{-1} \* G\\ &= k \* G\\ &= R \end{align\*} $$ Hence this proves that the verification step recovers the original random point in the signing step.