The series consists of four parts; each part uses the concepts discovered in the previous parts:
- The Magic of Elliptic Curves
- The Magic of Elliptic Curves Combined with Finite Fields
- Using The Magic of Elliptic Curves to Sign and Verify Messages [you're here]
- ECDSA Implementation in Python Using Zero Dependencies
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.
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.
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:
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:
We have our PrivateKey and message. To sign a message, we should*:*
- Generate a random integer k. This should be a big number. [1, n-1]
- Calculate point R = G * k
That’s it. The signature is a pair of points (r, s).
Here is the visual representation of the algorithm:
We have the signer’s PublicKey, message, and signature(r, s).
Calculate point C = U * G + V * PublicKey
If C.x mod n = r, then the signature is valid. Invalid otherwise.
Not obvious at all!
Actually, this is just a mathematical trick.
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).
For the elliptic curve:
For point G:
- x coordinate =
- y coordinate =
- Order n =
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.
Feel free to contact me and ask questions: