When adding a point to itself, the slope formula changes slightly because we can't divide by zero. The logic is similar to taking a derivative in calculus.

The slope s for doubling P1(x1, y1) is: s = (3 * x12 + a) * (2 * y1)-1 mod p. (Since a=0 for us, it's just 3 * x12 in the numerator).

The formulas for the new coordinates (x3, y3) remain the same as in point addition.

Scalar Multiplication

This is the most important operation. Scalar multiplication is how we get from a private key to a public key. It's defined as adding a point P to itself k times: k * P = P + P + ... + P (k times).

Doing this naively is too slow. Instead, we use the efficient "double-and-add" algorithm. It works by looking at the binary representation of k. For each bit, we double our current point. If the bit is a '1', we also add the original point P.

def scalar_mult(k, P):
    if k % N == 0 or P is None: # N is the order of the curve
        return None # Point at infinity
    if k < 0:
        # k * P = -k * -P
        return scalar_mult(-k, point_neg(P))
    
    result = None # Point at infinity
    addend = P

    while k:
        if k & 1:
            # Add
            result = point_add(result, addend)
        # Double
        addend = point_double(addend)
        k >>= 1

    return result

This simple function is the heart of our elliptic curve implementation. A private key d is just a large number, and the public key Q is simply d * G, where G is the generator point.

ECDSA: Signing and Verifying Messages

Now that we have our curve math, we can implement the signature algorithm itself.

Key Generation

This is the easiest part. A private key is just a securely generated random integer d where 1 <= d < n. The corresponding public key Q is calculated via scalar multiplication: Q = d * G.

Signing a Message

To sign a message m with a private key d, we follow these steps:

1. Hash the message: First, hash the message m using an algorithm like SHA-256. This gives you a number z.
2. Generate a nonce: Choose a cryptographically secure random number k, known as a nonce, where 1 <= k < n. This must be unique for every signature.
3. Calculate the point R: Use scalar multiplication to find the point R = k * G.
4. Get the r value: The first part of our signature, r, is the x-coordinate of R. So, r = R.x mod n. If r is 0, go back to step 2 with a new k.
5. Calculate the s value: The second part of the signature, s, is calculated with the formula:
   s = k-1 * (z + r * d) mod n.
   This involves another modular inverse. If s is 0, go back to step 2.

The final signature is the pair (r, s).

Verifying a Signature

To verify a signature (r, s) for a message m using the public key Q, anyone can perform these steps:

1. Hash the message: Calculate z from the message m using the same hash function.
2. Calculate w: Find the modular inverse of s: w = s-1 mod n.
3. Calculate u1 and u2: Compute two values:
   u1 = z * w mod n
u2 = r * w mod n
4. Calculate the verification point: Use scalar multiplication with both the generator point G and the public key Q:
   P = (u1 * G) + (u2 * Q).
5. Check for validity: The signature is valid if the x-coordinate of the calculated point P matches r. That is, if P.x mod n == r.

It seems like magic, but the math works out perfectly because Q = d * G. If you substitute the equations, you'll find that P simplifies to k * G, so P.x should indeed be r.

Putting It All Together: A Runnable Example

Here's a simplified script showing the flow. Note that the full code with curve parameters and helper functions would be needed to run this. (You can find a complete gist here).

import hashlib
import random

# --- Assume all secp256k1 parameters (P, N, G) and functions 
# --- (scalar_mult, point_add, inverse_mod) are defined above ---

# 1. Key Generation
private_key = random.randrange(1, N)
public_key = scalar_mult(private_key, G)

print(f"Private Key: {private_key}\n")
print(f"Public Key: ({public_key[0]}, {public_key[1]})\n")

# 2. Signing
message = b"Cryptography is fun!"
msg_hash = int.from_bytes(hashlib.sha256(message).digest(), 'big')

# A secure k is critical! For demo purposes only.
k = random.randrange(1, N) 

R = scalar_mult(k, G)
r = R[0] % N

# s = k^-1 * (z + r*d) mod n
k_inv = inverse_mod(k, N)
s = (k_inv * (msg_hash + r * private_key)) % N

signature = (r, s)
print(f"Message: {message.decode('utf-8')}")
print(f"Signature: (r={r}, s={s})\n")

# 3. Verification
# w = s^-1 mod n
w = inverse_mod(signature[1], N)

# u1 = z*w mod n, u2 = r*w mod n
u1 = (msg_hash * w) % N
u2 = (signature[0] * w) % N

# P = u1*G + u2*Q
point1 = scalar_mult(u1, G)
point2 = scalar_mult(u2, public_key)
P = point_add(point1, point2)

# Check if P.x mod n == r
if (P[0] % N) == signature[0]:
    print("Signature is VALID.")
else:
    print("Signature is INVALID.")
  

A Critical Warning: Do Not Use This in Production

This implementation is for educational purposes only. It is completely insecure for real-world applications for several critical reasons:

• Side-Channel Attacks: Our simple implementation is not "constant time." An attacker could analyze the time it takes to perform operations to leak information about the private key.
• Insecure Nonce (k) Generation: The biggest foot-gun in ECDSA is nonce reuse. If you ever use the same k to sign two different messages with the same private key, an attacker can trivially calculate your private key. Production libraries use deterministic methods (like RFC 6979) to generate k safely from the message and private key.
• Lack of Hardening: It's missing input validation, protection against edge cases, and many other security considerations that go into libraries like cryptography or ecdsa.

Conclusion

We did it! We started with a simple equation and built our way up to a functional ECDSA implementation. By building it from scratch, we've hopefully replaced a black box with a clear, understandable process. You now know what a private key is (a number), what a public key is (a point on a curve), and how they work together to create and verify a digital signature.

The world of cryptography is deep and fascinating. While our journey today ends here, I encourage you to keep exploring. Dig into how RFC 6979 creates deterministic nonces, look up side-channel attacks, or even try implementing another signature scheme. The magic is just math, and you now have the keys to understand it.