ECDSA Algorithm

We continue publishing articles on the principles of the threshold signature scheme. In the previous article, we talked about the standard digital signature scheme. In this article, we will cover the ECDSA algorithm and elliptic curves.

Algorithm ECDSA

ECDSA (Elliptic Curve Digital Signature Algorithm) is a particular implementation of the standard digital signature scheme that we covered previously. We will leave a detailed analysis of this algorithm’s aspects and the corresponding mathematical theory for future articles. Now let’s focus on some core ideas underlying the KeyGen, Sig, and Ver implementations in ECDSA.

There are two things ECDSA is based on: elliptic curves and modular arithmetic. Modular arithmetic is a fascinating topic, but it requires some time to explain. So, for now, let’s talk only about the elliptic curves.

An elliptic curve is a smooth curve on a plane that is determined by the equation y²=x³+a∙x+b. Here a and b are any numbers satisfying the inequality 4∙a³+27∙b²≠0. For example, Bitcoin and Ethereum use the curve y²=x³+7(Figure 1).

Fig.1

The main feature of an elliptic curve is that its points can be multiplied by positive integers using a particular rule. Any point can be represented as a pair of numbers (x, y), where x is the first coordinate and y is the second. So, the rule of multiplying a point by a number is just a formula for recalculating this point’s coordinates x and y. As a result, the point moves in a determined way.

Let’s consider G is a point on a curve, and k is a positive integer; then for the new point k∙G there are three possible locations:

1. k∙G=G, that is multiplying G by k does nothing, and the point k∙G coincides with G.
   For example, multiplying by one leaves any point in place: 1∙G=G for any G. The analogy with regular numbers works here: multiplying by one doesn’t change the origin number. The same is with points: multiplying by one doesn’t change the point’s position.

2. k∙G does not coincide with G but still lies on the curve. As a result of multiplication by q the point somehow slides along the curve.
   Figure 2 illustrates how a particular point P slides along the curve y²=x³+7, when we multiply it by integers from 1 to 7.
   
   Fig.2

3. k∙G does not exist. In practice, this means that in the formulas of coordinates’ calculation for this point, a division of 0 happened. There is a special term for it: the identity point. If k∙G does not exist, we say that it is equal to the identity point and denote it as k∙G=〇.

For example, if G is the point where the curve intersects the x-axis, then always 2∙G=〇.

The operation of multiplying a point by a number has one interesting property. Let’s consider a point G on a curve, for which such n exists that n∙G=〇. And let n be the smallest such a positive integer. Then it is guaranteed that the points G, 2∙G, …, (n-1)∙G are all different; no two of them match. Furthermore, if we start multiplying G by numbers greater than n, the point begins to change its positions in a loop: (n+1)∙G=G, (n+2)∙G=2∙G, …, (n+k)∙G=k∙G for any k>0.

Thus, point G has only n-1 possible positions on the curve where it can move as a result of multiplication by a number. Taking the identity point 〇 into account, we obtain total n possible options for the product k∙G: these are G, 2∙G, …, (n-1)∙G, or 〇. In these circumstances, we say that n is the order of point G. An arbitrary point on a curve may or may not have an order.

For example, as we already know, 2∙G=〇 if G lies on the x-axis. At the same time 1∙G=G≠〇. So, 2 is the smallest positive integer that makes G move to the identity point 〇. Therefore, for points where the curve intersects the x-axis there are only two possible options: multiplied by an odd number, they stay in place; multiplied by an even number, they become the identity point. Hence, these points do have an order, and this order equals 2.

Now, let’s consider a point G on a curve for which there is no such number n that n∙G=〇. Then it is guaranteed that if we start multiplying G by all positive integers, we’ll get a new result every time. So the point has an infinite number of possible positions on the curve, and there are no loops as in the previous case. Here we say that the order of G is infinity or that G has an infinite order.

To conclude, we use the word order to denote how many different results we can get after multiplying a point by all positive integers. The order of G is finite if and only if there is such n that n∙G=〇. And the order of G is infinite if and only if there is no such n.

Now we are ready to discuss the ECDSA itself. Initially ECDSA assumes the generation of five domain parameters that will be the same for all users in the system. Two of these parameters are related to the modular arithmetic part of ECDSA, so now let’s talk only about the other three.

The first one is a particular elliptic curve. To determine a curve we just have to choose two numbers a and b from the equation y²=x³+a∙x+b, 4∙a³+27∙b²≠0.

The second parameter is some prime number n. A prime number is a positive integer that is only divisible by 1 and itself.

The third parameter is such point G on the curve that n is the order of G. This point G is called the base point.

For example, Ethereum and Bitcoin use the following values:

a=0, b=7,

n=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,

G=(x, y), where

x=79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,

y=483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8.

We will take a closer look at the process of generating these parameters in the future articles. Now let’s move to the KeyGen, Sig, and Ver algorithms in ECDSA.

Key generation with KeyGen algorithm

A secret key sk is chosen randomly between 1 and n-1. And the corresponding public key pk is set to be the point sk∙G.

Here comes another crucial property of the multiplying operation. It appears that if we are given two points G and d∙G, where d is unknown, then it is computationally intractable to find d. This is called the elliptic curve discrete logarithm problem.

Thus, knowing the base point G and the public key pk=sk∙G, we won’t be able to find the corresponding secret key sk.

Also, since n is the order of G, there are only n-1 possible outcomes for the product sk∙G, that is there are only n-1 possible values for pk.

So, the output of the algorithm is a pair (sk, pk), where sk is a number and pk is a point, that is two coordinates.

Signature generation with Sig algorithm

The signature generation algorithm Sig takes as input the secret key sk and the number m, which is a hash of a message that is going to be signed.

The output signature is a pair of numbers (r, s)=Sig(sk, m).

But why are there two numbers instead of just one? This is due to the fact that inside the algorithm, we randomly choose an additional number k which afterward affects the resulting signature. This additional parameter is needed to ensure the secrecy of the secret key. If a signature were completely determined only by the input parameters sk and m, then the value of sk could be successfully recovered based on just two already created signatures.

But because of the randomness of k the Sig algorithm can produce different results for the same input values. Therefore, in order to make it possible to verify the output signature, we need to share some information about k. And so, the first part of the signature r is used to reflect this information. So, first, we calculate r using only the value of k, and then we calculate s using all three parameters k, sk and m.

Signature verification with Ver algorithm

The verification algorithm Ver takes as input the public key pk, the hash m, and the signature (r, s).

The algorithm computes two different numbers u₁ and u₂ based on the signature and the hash. Then it finds two points on the domain elliptic curve: u₁∙G and u₂∙pk (pk is a point, so u₂∙pk is also a point).

If the signature s was initially calculated using the correct values of sk and m then the points u₁∙G and u₂∙pk will be connected to each other through a certain relation. The Ver algorithm checks whether this connection holds or not. If it does, then the signature is considered to pass the verification, and the algorithm returns 1 (TRUE). Otherwise, it returns 0 (FALSE).

In the following article, we will move on to a description of the threshold signature.

---

References:

1. Don Johnson, Alfred Menezes, “The Elliptic Curve Digital Signature Algorithm (ECDSA)”
2. William Stein, “Elementary Number Theory: Primes, Congruences, and Secrets”

---

Authors:

Alexey Troshichev Main Concept

Artem Fomichev Math Expert

Inga Pashentseva Editor

Alexander Polovian Fact Checking

---

Catch up with us on social media

Twitter | Telegram | Discord | Facebook | Instagram | Linkedin