# ECDSA

Signature algorithm

• Use the secret scalar $e$ to compute the public point$P$, by doing a scalar multiplication with $G$: $eG = P$.

• Pick a random (secret) scalar $k$, and perform a scalar multiplication with $G$ to get a random point$R$. $kG = R$

• Use the above variables in the general equation of ECDSA is: $uG + vP = R$, where, $u = z/s$, $v=r/s$

• Simplify the resulting equation to get the $s$ component of the signature:

$s = (z + re) / k$

from random import randint​​@dataclassclass PrivateKey:    secret: int        def sign(self, z: int) -> Signature:        e = self.secret        k = randint(0, N)        R = k * G        r = R.x.value        k_inv = pow(k, -1, N)  # Python 3.8+        s = ((z + r*e) * k_inv) % N                return Signature(r, s)

Apart from the fact that e is a secret number, the security of ECDSA also relies on the condition that k is also very random and secret.

We'll learn about the consequences of not having a random kin the next section.

Verification algorithm

• Given: (r, s) is the signature, z is the 256 bit message being signed, and P is the public key of the signer.

• Calculate: $u = z/s$, $v=r/s$.

• Calculate $uG + vP = R$.

• Signature is valid is $Rx$ is equal to $r$.

@dataclassclass Signature:    r: int    s: int        def verify(self, z: int, pub_key: Point) -> bool:        s_inv = pow(self.s, -1, N)  # Python 3.8+        u = (z * s_inv) % N        v = (self.r * s_inv) % N                return (u*G + v*pub_key).x.value == self.r

### Testing our ECDSA implementation

pub = Point(    x=0x887387E452B8EACC4ACFDE10D9AAF7F6D9A0F975AABB10D006E4DA568744D06C,    y=0x61DE6D95231CD89026E286DF3B6AE4A894A3378E393E93A0F45B666329A0AE34,    curve=secp256k1)​# Test case 1: verify authenticityz = 0xEC208BAA0FC1C19F708A9CA96FDEFF3AC3F230BB4A7BA4AEDE4942AD003C0F60r = 0xAC8D1C87E51D0D441BE8B3DD5B05C8795B48875DFFE00B7FFCFAC23010D3A395s = 0x68342CEFF8935EDEDD102DD876FFD6BA72D6A427A3EDB13D26EB0781CB423C4​assert Signature(r, s).verify(z, pub)​# Test case 2: verify authenticity for different signature w/ same Pz = 0x7C076FF316692A3D7EB3C3BB0F8B1488CF72E1AFCD929E29307032997A838A3Dr = 0xEFF69EF2B1BD93A66ED5219ADD4FB51E11A840F404876325A1E8FFE0529A2Cs = 0xC7207FEE197D27C618AEA621406F6BF5EF6FCA38681D82B2F06FDDBDCE6FEAB6assert Signature(r, s).verify(z, pub)​# Test case 3: sign and verifye = PrivateKey(randint(0, N))  # generate a private keypub = e.secret * G  # public point corresponding to ez = randint(0, 2 ** 256)  # generate a random message for testingsignature: Signature = e.sign(z)assert signature.verify(z, pub)