Mathematical Foundations of Schnorr Signatures

Tawan Suwannaphum

Schnorr signatures represent an elegant cryptographic primitive that leverages the properties of cyclic groups and elliptic curves. Let's dive into its mathematical foundations and implementation details.

The Group Theory Kitchen

Imagine you're in a very special kitchen (our elliptic curve) where you can only move in certain ways. In this kitchen:

• You can combine any two points to get another point (closure)

• The order of combining points doesn't matter (commutativity)

• You can combine points in any grouping (associativity)

• There's a special "nothing" point that doesn't change anything when combined (identity)

• Every point has its "opposite" point (inverse)

The Setup: Parameters and Key Generation

Imagine you're setting up a very special kitchen where every recipe must follow specific mathematical rules. Your kitchen isn't just any space - it's an elliptic curve defined by the equation:

E: y² = x³ + ax + b (over field Fp)

This curve is your workspace, and it comes with some special properties:

1. The Master Ingredient (Base Point G)

   • Think of G as your starter culture, like a sourdough mother

   • It's a special point on the curve that everyone agrees to use

   • Everyone in the world using this system uses the same G

2. The Recipe Cycle (Order n)

   • n is a prime number that tells you how many unique "turns" you can make

   • After n applications of G, you get back to the starting point (O)

   • Mathematically: n·G = O (where O is the point at infinity)

3. Creating Your Secret Recipe (Key Generation)

   • Pick a random number d between 1 and n-1 (this is your private key)

   • Multiple G by d to get your public key P: P = d·G

   • It's like saying "turn the starter culture d times"

   • Everyone can see the result (P), but only you know the number of turns (d)

For the commonly used curve secp256k1 (Bitcoin's choice):

p = 2²⁵⁶ - 2³² - 977
n ≈ 2²⁵⁶

The security of this system relies on a fascinating mathematical property: while it's easy to compute P = d·G (like following a recipe), it's computationally infeasible to figure out d given P and G (like trying to figure out the exact number of times a chef turned their dough just by looking at the final bread).

This property, known as the Discrete Logarithm Problem (DLP), is what makes our digital signatures secure. It's a one-way function, like baking bread - easy to go from dough to bread, but impossible to turn bread back into its original unbaked dough.

Key Points to Remember:

1. The curve and base point G are public knowledge

2. Your private key d must remain secret

3. Your public key P can be freely shared

4. The relationship P = d·G is what binds your keys together

5. The size of n ensures that randomly guessing d is practically impossible

Think of this whole setup as your mathematical mise en place - everything properly measured and arranged before we start creating signatures. In our next section, we'll look at how we use these ingredients to create and verify signatures.

Would you like me to elaborate on any of these concepts? Perhaps the mathematical properties of the curve or the specific details of the discrete logarithm problem?

Signature Generation: Cooking Up The Proof

Here's where we cook up our signature. We need:

1. A random number k (think of it as your daily special ingredient)

2. Your private key d (your secret recipe)

3. The message m (what you're trying to prove)

The mathematical process:

R = k·G                         // Your daily special point
e = H(R∥P∥m)                   // Mix everything together
s = k + e·d mod n              // The final touch

Verification: The Taste Test

Anyone can verify your signature by checking if:

Copys·G = R + e·P

Let's see why this works:

CopyLeft side:  s·G = (k + e·d)·G
Right side: R + e·P = k·G + e·d·G

They're the same! It's like having a recipe that can only be replicated if you knew the secret ingredient (d).

Why This Is Secure

The security relies on what we call the Discrete Logarithm Problem. It's like trying to figure out how many times someone turned the spice rack just by looking at where it stopped. When the rack has billions of positions (like our curve), this becomes practically impossible.

This is why Schnorr signatures are like a mathematical magic trick:

• Everyone can verify it works (like tasting the dish)

• Nobody can forge it without the secret (like recreating the exact dish without the recipe)

• The math proves it's unforgeable (like having a perfect cooking technique)

Let's examine the algebraic proof of signature verification:

s·G = (k + e·d)·G = k·G + e·d·G = R + e·P

This equality holds due to the distributive property of scalar multiplication over point addition in our elliptic curve group.

Multi-Signature: Cooking Together

The really cool part about Schnorr signatures is that multiple people can combine their signatures:

Combined signature = (R₁ + R₂, s₁ + s₂)

The linearity property of the underlying group operations enables signature aggregation. For n signers:

1. Each signer i generates their own ki and computes Ri = ki·G

2. The aggregate R = ∑Ri

3. Each signer computes si = ki + e·di

4. The aggregate signature is (R, ∑si)

This aggregation property directly follows from the Abelian group structure and linearity of scalar multiplication.

Security Considerations

1. Nonce Generation: The nonce k must be generated using a cryptographically secure random number generator

2. Nonce Reuse: Never reuse a nonce k across different signatures

3. Side-Channel Attacks: Implementations must be resistant to timing and power analysis attacks

4. Hash Function: Must be collision-resistant and second-preimage resistant

The security proof for Schnorr signatures can be constructed in the random oracle model, reducing the security to the discrete logarithm assumption in the underlying group.