Bitcoin Signatures From Scratch (3/4): Using The Magic of Elliptic Curves to Sign and Verify Messages

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

1. The Magic of Elliptic Curves
2. The Magic of Elliptic Curves Combined with Finite Fields
3. Using The Magic of Elliptic Curves to Sign and Verify Messages [you're here]
4. ECDSA Implementation in Python Using Zero Dependencies

---

Let's start here!

The Elliptic Curves Digital Signature Algorithm works exactly over the algebra that we’ve just discovered in the previous part.

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:

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.

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.

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:
   

4. Calculate s:

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

Here is the visual representation of the algorithm:

The algorithm for verifying a signature

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

1. Calculate U:
   

2. Calculate V:
   

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

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

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:

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

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

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

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

Let’s simplify this part:

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

---

Feel free to contact me and ask questions:

[e-mail]
t.me/exemak
Mikhail Karavaev