# 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$$\
                  $$z$$ is the 256-bit message being signed\
                   
* Simplify the resulting equation to get the $$s$$ component of the signature:

      $$s = (z + re) / k$$ 

```python
from random import randint

@dataclass
class 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)
```

{% hint style="warning" %}
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 **`k`**in  the next section.
{% endhint %}

**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$$.

```python
@dataclass
class 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

```python
pub = Point(
    x=0x887387E452B8EACC4ACFDE10D9AAF7F6D9A0F975AABB10D006E4DA568744D06C,
    y=0x61DE6D95231CD89026E286DF3B6AE4A894A3378E393E93A0F45B666329A0AE34,
    curve=secp256k1
)

# Test case 1: verify authenticity
z = 0xEC208BAA0FC1C19F708A9CA96FDEFF3AC3F230BB4A7BA4AEDE4942AD003C0F60
r = 0xAC8D1C87E51D0D441BE8B3DD5B05C8795B48875DFFE00B7FFCFAC23010D3A395
s = 0x68342CEFF8935EDEDD102DD876FFD6BA72D6A427A3EDB13D26EB0781CB423C4

assert Signature(r, s).verify(z, pub)

# Test case 2: verify authenticity for different signature w/ same P
z = 0x7C076FF316692A3D7EB3C3BB0F8B1488CF72E1AFCD929E29307032997A838A3D
r = 0xEFF69EF2B1BD93A66ED5219ADD4FB51E11A840F404876325A1E8FFE0529A2C
s = 0xC7207FEE197D27C618AEA621406F6BF5EF6FCA38681D82B2F06FDDBDCE6FEAB6
assert Signature(r, s).verify(z, pub)

# Test case 3: sign and verify
e = PrivateKey(randint(0, N))  # generate a private key
pub = e.secret * G  # public point corresponding to e
z = randint(0, 2 ** 256)  # generate a random message for testing
signature: Signature = e.sign(z)
assert signature.verify(z, pub)
```

#### Resources

* [https://www.instructables.com/id/Understanding-how-ECDSA-protects-your-data](https://www.instructables.com/id/Understanding-how-ECDSA-protects-your-data/)