ECDSA — The art of cryptographic signatures
This article aims to give an introduction to the Elliptic Curve Digital Signing Algorithm using a little math.
Introduction
In one of my previous articles “Learn how to code elliptic curve cryptography” I tried to give a glimpse on the mechanisms behind cryptography based on the math of elliptic curves. Since taking a point on an elliptic curve and adding it with itself results in another point also being situated on the curve, one can define the private key as a large number d and the public key P as the scalar product of the number d with a chosen point on the curve G:
P = d ⋅ G
So there is a deep connection between the public and the private key — they belong together. This can be used to send messages together with a signature, which is just a prove that the sender of the message is indeed the one having created it. The signature itself can be verified by the recipient without the need to know the sender’s private key. Cryptographic systems, that work this way are often referred to as asymmetric. In this article I would like to go a little bit more into detail, describing how signatures can be created and verified.
Creating a signature
Creating digital signatures based on the math of elliptic curves is called the Elliptic Curve Digital Signing Algorithm, short ECDSA. Let’s take a look at the individual steps of this algorithm.
Assume there are two participants in a network and we are calling them Alice and Bob. Actually those two names seem to be used always in practical explanations of cryptographic systems. Alice’s public key shall be Pₐ, her private key dₐ. Bob’s public and private key will not be needed for the signing and verifying procedure. Now Alice wants to send a message M to Bob and also likes to provide this message with a signature. The first step before applying the Signing Algorithm will be to hash the message und truncate the hash’s bit length, such that it fits together with the properties of the chosen elliptic curve. Concerning creating hashes I would like to recommend you one of my previous articles on “Building a simple blockchain”. There I explained, how cryptographic hash functions work and what properties such hashes have. The hash of the message M will be just the following:
z = Hash(M)
Now that we have the hash z, we can take a look at the steps, that Alice’s signing algorithm will run through:
- Choose a large integer number k from the set of numbers 0,…,n-1. To understand the algorithm, it is not necessary to understand, under which conditions the number n is chosen. Together with the point G being used to get the public key, another point E on the curve is being calculated:
E= kG - The calculated point H has a x- and a y-coordinate, E= (xₑ ,yₑ). Using the x-coordinate of the point, the first part of the signature will be:
r = xₑ mod n
The abbreviation mod means, that modular arithmetics is applied. Don’t worry! It’s not complicated at all. It just means division with rest. If you take a number modulo another number, for example 7 mod 4, the result will be the rest from the division. Dividing 7 by 4 results in a rest of 3, so
7 mod 4 = 3. - Is the result for r equals zero, the algorithm goes back to step one and starts over with a new number k.
- Now the second part of the signature will be calculated. Therefore, ECDSA requires the Hash z of the message, Alice intends to send, her private key and the lately calculated first part of the signature r. The second part s of the signature has the following form:
s = k⁻¹ ⋅ (z+r ⋅ dₐ ) mod n - If s equals zero, the algorithm has to jump back to the first step and start all over again.
Going through these steps, will eventually give you a pair of numbers (r,s) -this is the desired signature. Now that we know how a signature is created, the next part of interest will be, how it can be verified by the recipient of the message, i.e. Bob.
Verifying the signature
Alice sent her message out and Bob received it together with the signature attached. Now he wants to know if the message, he received, is indeed coming from Alice. All the information he got is just the signature (r,s) itself, the message and Alice’s public key Pₐ. A way has to be found, that he can verify the signature using only those pieces of information. To do so, Bob’s Verifying Algorithm needs to calculate the point E and has to prove, that xₑ fulfills the following requirement:
xₑ mod n = r
Concerning the point E, this equation holds:
E = k ⋅ G
The one problem is, that Bob does not know what k is. But there is a way! Let’s take the equation from the fourth step of the signing algorithm:
s = k⁻¹ ⋅ (z+r ⋅ dₐ ) mod n
We can reformulate in way, such that we get an expression for the number k:
k = s⁻¹ ⋅ (z+r ⋅ dₐ ) mod n
Taking this expression for k, we can rewrite the equation for calculating the point E:
E = k ⋅ G = s⁻¹ ⋅ (z+r ⋅ dₐ ) ⋅G mod n
Now we are going to do a little maths. We multiply out the brackets first:
E = (s⁻¹ ⋅ z ⋅ G) mod n + (s⁻¹ ⋅ r ⋅ dₐ ⋅ G) mod n
Remembering the definition of the public key shown in the introduction to this article
Pₐ = dₐ ⋅ G
we can replace the multiplication of the private key by the point G with Alice’s public key. Thus, the point E can now be calculated using only the information of the Hash z of the message, Alice’s public key and the signature:
E = (s⁻¹ ⋅ z ⋅ G) mod n + (s⁻¹ ⋅ r ⋅ Pₐ) mod n
Now that we have derived a way to verify a signature, it’s time to summarize the single steps of the Verifying Algorithm:
- Take the signature (r,s) and calculate the multiplicative inverse s⁻¹. Using the truncated Hash z of the message, calculate the number
A₁ = s⁻¹⋅ z - Calculate the number A₂ = s⁻¹ ⋅ r .
- Evaluate the point E = A₁ ⋅ G + A₂ ⋅ Pₐ
- Take the x- coordinate xₑ of the point E and check whether the following condition holds:
xₑ mod n = r
If this condition holds, the signature is correct!
The End
Understanding how the Elliptic Curve Signing Algorithm works might require a little math, but I hope that you still could get a small glimpse on the underlying mechanisms. If you liked my article leave a few claps. :) Also feel free to comment. Thanks for reading!
