# ECDSA Algorithm

By [Symbiosis Finance](https://paragraph.com/@symbiosis-finance) · 2022-07-08

---

_We continue publishing articles on the principles of the threshold signature scheme._ [_In the previous article_](https://mirror.xyz/0xd49CbaFBA1ff5565Ec07e7d0C950436C06D7e65C/DeALvAfQTGV2mfOtWTWSVwOJXBQlhJeSuVrpan1ds9g)_, 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](https://storage.googleapis.com/papyrus_images/69d0b4d1a0210e9357d6fea0ded3235683c5cf77b75de4c81ae14c7d2043745f.png)

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](https://storage.googleapis.com/papyrus_images/8c302b35e88e7e089cf8be69d615957cb8fd593dfac865b058fb0ddd09044669.png)

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)”](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.8014&rep=rep1&type=pdf)
    
2.  [William Stein, “Elementary Number Theory: Primes, Congruences, and Secrets”](https://wstein.org/ent/ent.pdf)
    

Authors:

**Alexey Troshichev** Main Concept

**Artem Fomichev** Math Expert

**Inga Pashentseva** Editor

**Alexander Polovian** Fact Checking

Catch up with us on social media

[Twitter](https://twitter.com/symbiosis_fi) | [Telegram](https://t.me/symbiosis_finance) | [Discord](https://discord.gg/DckkhfWN) | [Facebook](https://web.facebook.com/symbiosis.finance/) | [Instagram](https://www.instagram.com/symbiosis.fi/) | [Linkedin](https://www.linkedin.com/company/symbiosis-finance?trk=pulse-article_main-author-card)

---

*Originally published on [Symbiosis Finance](https://paragraph.com/@symbiosis-finance/ecdsa-algorithm)*