220
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 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 are any numbers satisfying the inequality 4•a?+27•b??0. For example, Bitcoin and Ethereum use the curve (Figure 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 is the first coordinate and is the second. So, the rule of multiplying a point by a number is just a formula for recalculating this point’s coordinates . As a result, the point moves in a determined way.
Let’s consider is a point on a curve, and is a positive integer; then for the new point there are three possible locations:
- , that is multiplying does nothing, and the point coincides with
For example, multiplying by one leaves any point in place: for any . 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.
- does not coincide with but still lies on the curve. As a result of multiplication by the point somehow slides along the curve.
Figure 2 illustrates how a particular point slides along the curve , when we multiply it by integers from 1 to 7.
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 does not exist, we say that it is equal to the identity point and denote it as
For example, if is the point where the curve intersects the x-axis, then always
The operation of multiplying a point by a number has one interesting property. Let’s consider a point on a curve, for which such exists that ?. And let 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 by numbers greater than , 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
Thus, point has only -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 possible options for the product: these are 2•G, …, (n-1)•G, or ?. In these circumstances, we say that is the order of point . An arbitrary point on a curve may or may not have an order.
For example, as we already know, ? if G lies on the -axis. At the same time ?. So, 2 is the smallest positive integer that makes move to the identity point ?. Therefore, for points where the curve intersects the -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 on a curve for which there is no such number =?. Then it is guaranteed that if we start multiplying 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 is infinity or that has an infinite order.
To conclude, we use the word to denote how many different results we can get after multiplying a point by all positive integers. The order of is finite if and only if there is such =?. And the order of is infinite if and only if there is no such
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 from the equation y?=x?+a•x+b, 4•a?+27•b??
The second parameter is some prime number . A prime number is a positive integer that is only divisible by 1 and itself.
The third parameter is such point on the curve that is the order of . This point is called the base point.
For example, Ethereum and Bitcoin use the following values:
n=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,
G=(x, y)
79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
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 algorithms in ECDSA.
Key generation with KeyGen algorithm
A secret key is chosen randomly between 1 and 1. And the corresponding public key is set to be the point
Here comes another crucial property of the multiplying operation. It appears that if we are given two points is unknown, then it is computationally intractable to find . This is called the elliptic curve discrete logarithm problem.
Thus, knowing the base point and the public key pk=sk•G, we won’t be able to find the corresponding secret key
Also, since is the order of , there are only -1 possible outcomes for the product , that is there are only -1 possible values for
So, the output of the algorithm is a pair (sk, pk) is a number and is a point, that is two coordinates.
Signature generation with Sig algorithm
The signature generation algorithm takes as input the secret key and the number , which is a hash of a message that is going to be signed.
The output signature is a pair of numbers (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 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 , then the value of could be successfully recovered based on just two already created signatures.
But because of the randomness of 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 . And so, the first part of the signature is used to reflect this information. So, first, we calculate using only the value of , and then we calculate using all three parameters
Signature verification with Ver algorithm
The verification algorithm takes as input the public key , the hash , and the signature (
The algorithm computes two different numbers based on the signature and the hash. Then it finds two points on the domain elliptic curve: is a point, so is also a point).
If the signature was initially calculated using the correct values of and m then the points will be connected to each other through a certain relation. The 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:
- Don Johnson, Alfred Menezes, “The Elliptic Curve Digital Signature Algorithm (ECDSA)”
- William Stein, “Elementary Number Theory: Primes, Congruences, and Secrets”
Alexey Troshichev Main Concept
Artem Fomichev Math Expert
Inga Pashentseva
Alexander Polovian Fact Checking
Catch up with us on social media
FacebookInstagramLinkedin
