Bitcoin Signatures From Scratch (3/4): Using The Magic of Elliptic Curves to Sign and Verify Messages
Tags: programming, computerscience, blockchain, algorithms
Published: 2022-10-17 20:08:12


The series consists of four parts; each part uses the concepts discovered in the previous parts:

1. [The Magic of Elliptic Curves](https://dev.to/exemak/bitcoin-signatures-from-scratch-14-the-magic-of-elliptic-curves-2n7h)
2. [The Magic of Elliptic Curves Combined with Finite Fields](https://dev.to/exemak/bitcoin-signatures-from-scratch-24-the-magic-of-elliptic-curves-combined-with-finite-fields-249o)
3. **Using The Magic of Elliptic Curves to Sign and Verify Messages** [you're here]
4. [ECDSA Implementation in Python Using Zero Dependencies](https://dev.to/exemak/bitcoin-signatures-from-scratch-44-ecdsa-implementation-in-python-using-zero-dependencies-410c)

---

## Let's start here!
The [Elliptic Curves Digital Signature Algorithm](https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm) works exactly over the algebra that we’ve just discovered in the [previous part](https://dev.to/exemak/bitcoin-signatures-from-scratch-24-the-magic-of-elliptic-curves-combined-with-finite-fields-249o).

This algorithm allows a person to **sign** a **message** using his or her **PrivateKey**, so that anyone else can **verify** that the **signature** actually **belongs** to that person, knowing their **PublicKey**. 

### This is what actually happens when you **sign** a **message** in blockchains:
You have a pair of keys: **PrivateKey** — **PublicKey**. Everyone knows your **PublicKey**, but no one except you knows your **PrivateKey**.

You just generate some **message** like “**I want to send X amount of crypto to address Y**”, and then you **sign** that message (using exactly the algorithm discovered in this article).  Other parties can **verify** that the **message** was actually **signed** by you.

### How it works

Everything spins around one certain **predefined** **point** **G**, lying on a **predefined** **elliptic curve**.

We can generate any **random integer** and call it our **PrivateKey.** 

**If we multiply this PrivateKey to point G, we will get the PublicKey. 
So PublicKey = PrivateKey * G:**

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ytqlau21yavqgbgu4x8c.png)

Yes, **PublicKey** is just a point on a curve.

As we already know, we can't divide point by point or point by a scalar value. All possible operations are listed at the end of [Part 1](https://dev.to/exemak/bitcoin-signatures-from-scratch-14-the-magic-of-elliptic-curves-2n7h).

So there is **no efficient way** to get the **PrivateKey** back because we can't divide **PublicKey** by **G**. This operation doesn't exist. Brute-forcing potentially works, but when there is really giant number of possible points, for example, that giant:

115792089237316195423570985008687907852837564279074904382605163141518161494337

### Even if someone uses all the existing computing power in the world, this would take billions of billions of billions… of years to find the **PrivateKey**.

In ECDSA we have this set of “global” public variables. **They are specified by standards**:

- Elliptic curve with some config (**a**, **b**, **p**)
- Point **G**, which lies on the curve (its **x** and **y** coordinates). This is called the **Generator Point**. This point is standardized.
- Order **n** of point **G**. As we know, order **n** is the property for point **G,** so as G*(n+1) = G, G*(n+2) = 2G, and so on.

Here are the variables that belong to a certain owner:

- **PrivateKey** - kept secret by the owner
- **PublicKey** - shared with the public

And, variables that are specific to one **signing** operation:

- The **message** itself: any integer that is not larger than order n. **Usually**, a **hash** of string is used. But for simplicity reasons, we will use pure integers.
- **K** - random integer, that is generated when signing a message, exactly for that signature. This is kept secret and there is no way to find it by a third party.

Here is the complete picture. Green stickers indicate that the variable is shared with the public, and the red ones indicate the variables that are kept secret.

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m8tpcz0pfek1jvmywqml.png)

Way too many variables!
Here are the algorithms for **signing** and **verifying** a message:

### The algorithm for signing a message:

We have our **PrivateKey** and **message**. To sign a message, we should**:**

1. Generate a random integer **k**. This should be a big number. [1, **n**-1]
2. Calculate point **R = G * k**
3. Calculate **r**:
![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5yjxoe4rodstruvodsga.png)

4. Calculate **s:**

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8jfbz876umyx5gt5e8v5.png)

That’s it. **The signature is a pair of points (r, s).** 

Here is the visual representation of the algorithm:

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8fb0x3n6jya57wtlmzcg.png)

### The algorithm for verifying a signature

We have the signer’s **PublicKey**, **message**, and **signature(r, s).**

1. Calculate **U**: 
![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g2wx160ppl8w0nd0ukk1.png)


2. Calculate **V**:
![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wpth9gx00hnnrpb45q2q.png)

3. Calculate point **C** = **U** * **G** + **V** * **PublicKey**

4. If **C**.x mod **n** = **r**, then the signature is valid. Invalid otherwise.

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s7z1d5njog4ll5eb60cg.png)

Not obvious at all!

Actually, this is just a mathematical trick.

### Let’s play with our formulas and prove that it works!

In step 3 of our **verification** algorithm we have a point **C = U * G + V * PublicKey:** 

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ufphupqj4u6l6imtnlbu.png)

 Let’s substitute the variables **U, V, and PublicKey** with their definitions:

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hb6hn2ub04av938c6xs4.png)

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iq2u24or0416hslglfq8.png)

Notice that G * s^-1 is duplicated. Let’s simplify the formula:

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8fo33kpikci3eb8m2ts1.png)

Let’s see the definition of s in step **4** of the **signing** algorithm:

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pvlt9mau9c2yiv5hujrg.png)

Let’s substitute s^-1 in our formula:

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9dztc0lt8xdj398uz6lx.png)

Let’s simplify this part:

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yuzmyb4kc7846crhagzo.png)

![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zqmtg3c63a3uhsthyum5.png)

Thus, if the signature is correct, the **x** coordinate of **C mod n** is equal to **r** (which is, by its definition, the same **x** coordinate of **G * k**). 

### Secp256k1 standardized variables:

For the elliptic curve:

- a=0
- b=7
- p=`115792089237316195423570985008687907853269984665640564039457584007908834671663`

For point G:

- x coordinate = `55066263022277343669578718895168534326250603453777594175500187360389116729240`
- y coordinate = `32670510020758816978083085130507043184471273380659243275938904335757337482424`
- Order n = `115792089237316195423570985008687907852837564279074904382605163141518161494337`

### Done! Now we know absolutely EVERYTHING essential!

The next part is going to be the easiest part for programmers. For everyone else, it’s not necessary to follow. Just proceed to the **Live Demo** at the end of the next part.

## Next part: [ECDSA Implementation in Python Using Zero Dependencies](https://dev.to/exemak/bitcoin-signatures-from-scratch-44-ecdsa-implementation-in-python-using-zero-dependencies-410c)

---
Feel free to contact me and ask questions: 

exemak@gmail.com
t.me/exemak
Mikhail Karavaev