# 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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://onyb.gitbook.io/roll-your-own-crypto/ecdsa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.