Useful and efficient algorithms for secp256k1 elliptic curve

In this article, we will consider several useful and efficient algorithms for an elliptic curve  E  over a field  GF(p)  given by the short Weierstrass equation

у^2 = х^3 + Ах + В

•  Algorithm for generating a point on curve  E
•  Algorithm for adding points
•  Doubling Point Algorithm
•  Algorithm for finding an integer multiple point
•  Algorithm for finding an integer multiple point (scalar multiplication)
•  Algorithm for constructing a divisor  D  over a curve  E  with support  supp(D)  of a given size  d
•  Miller’s algorithm for calculating the value of the Weyl function  f  _{n, P}  from a divisor  D  such that  supp(D)  ∩ {P, O} = ∅
•  Pairing  Weil

Modular operations (integers) on a finite field (or Galois field)

1. x mod n  means «the remainder of n after dividing x». In other words, if  x = an + b  and a, b ∈ integer, and also 0 ≤ b ≤ n − 1, then  x mod n = b  .
2. Reverse  : if  ax = 1 mod n  , then  a  is the reciprocal of  x mod n  . There are two popular  solution methods  : •  Method 1  : Try each value for  a < n as  long as  xa mod n = 1  .•  Method 2  : Euclidean method which is usually used to solve the inverse problem of large integers, so it is recommended to use method 1 to solve inverse problem of small integers.

Elliptic Curve Point Operation

The point  P(x  ₀  , y  ₀  )  on the elliptic curve  E  means: its coordinates  x  ₀  and  y  ₀  are elements of the field, and the coordinates  x  ₀  and  y  ₀  satisfy the equation.

1. Adding points on an elliptic curve  : Let  P, Q  and  R  be three points on an elliptic curve. Adding points P + Q = R.
2. Doubling points on an elliptic curve  : Let  P, Q  be two points on an elliptic curve. Doubling Points P + P = 2P = Q
3. Dot multiplication  : let  P  be a point on the curve  E  , defined in the equation
   • Dot multiplication  nP  is defined as  nP = P + P + P + … + P  (  n  times), where  n  is an integer; nP  is also a point on the same  E curve  .
   • The minimal natural number a with  aP = O  is called  the order  of P  .
   • Dot multiplication is widely required in elliptic curve cryptosystems.

Divider

Divisor  (Divisor)  D  on a curve  E  is a convenient way to denote a  multiset of points on  E  , written as a formal sum

• The set of all divisors on  E  is denoted  by Div  _{F q}  (E)  and forms a group in which the addition of divisors is natural.
• Zero Divisor: This is the divisor for all n  _P  = 0, the zero divisor is  0 ∈ Div  _{F q}  (E)  .
• If the field  F  _q  is not specific, it can be omitted and simply written as  Div(E)  to denote the divisor group.

Function f divided by E

The divisor of a function  f  by  E  is used to denote the intersection points (and their multiplicities) of the functions  f  and  E  .

Pairing Weil

The Weil pairing, which is denoted  by e  m  , takes as input a pair of points  P, Q ∈ E[m] and  produces  as output a root _m of unity  e  m (  P , Q)  . The bilinearity of the Weyl pairing is expressed by the equations

e  _m  (P  ₁  + P  ₂  , Q) \u003d e  _m  (P  ₁  , Q) * e  _m  (P2, B),

e  _m  (P, Q  ₁  + Q  ₂  ) = e  _m  (P, Q  ₁  ) * e  _m  (P, Q  ₂  ).

The Weil  pair  P  and  Q  is the number

where  S ∈ E  is any point satisfying the condition  S ∉ {O, P, −Q, P − Q}  . (This ensures that all quantities on the right hand side are defined and non-zero.) One can check that the value of  e  _m  (P,Q)  does not depend on the choice of  f  _P  ,  f  _Q  and  S  .

An Efficient Weil Pairing Computation Algorithm

Let  E  be an elliptic curve and let P = (x  _P  ,y  _P  ) and Q = (x  _Q  , y  _Q  ) be nonzero points on  E  .

Let  λ  be the slope of the line connecting  P  and  Q  , or the slope of the tangent to  E  at P if  P =  Q. (If the line is vertical, we set  λ  = ∞.) Define a function g  _{P, Q}  on  E  as follows:

then

div(g  _{P, Q}  ) = [P] + [Q] — [P + Q] — [  O  ].

Miller’s algorithm

Let  m ≥  and write the binary extension of  m  as

m \u003d m  ₀  + m  ₁  * 2 + m  ₂  * 2  ²  + + m  _{n — 1}  2  ^{n — 1}

for  m  _i  ∈ {0, 1}  and  m  _{n — 1}  ≠ 0  . The following algorithm returns a function  f  _P  whose divisor satisfies the condition

div(  f  _P  ) =  m  [  P  ] — [  mP  ] — (  m — 1  ) [  O  ],

where the functions  g  _{T, T}  and  g  _{T, P}  used by the algorithm are defined in (a).

In particular, if  P ∈ E[m]  , then div(  f  _P  ) =  m  [  P  ] −  m  [  O  ].

Requirement

• Python 3.5
• numpy

git clone https://github.com/demining/CryptoDeepTools.git
cd CryptoDeepTools/04AlgorithmsForSecp256k/
pip3 install numpy

├── Curves.py             <- Набор данных эллиптических кривых
├── Divisor.py            <- Создать делитель
├── EllipticCurve.py      <- Классы эллиптической кривой и точки на эллиптической кривой
├── EuclideanAlg.py       <- Расширенный алгоритм Евклида
├── Helper.py             <- Вспомогательные функции (обратные биты, мощность по модулю) 
├── Pairing.py            <- Спаривания Вейля, а так же Алгоритм Миллера
├── Tests.py              <- Модульные тесты для функций
├── Tonelli_ShanksAlg.py  <- Алгоритм Тонелли – Шенкса
├── main.py               <- main

---

Source

Telegram:  https://t.me/cryptodeeptech

Video:  https://youtu.be/gFbiBCNPsFk

Source: https://cryptodeeptech.ru/algorithms-for-secp256k

---

	Donation Address
♥ BTC	1Lw2gTnMpxRUNBU85Hg4ruTwnpUPKdf3nV
♥ ETH	0xaBd66CF90898517573f19184b3297d651f7b90bf