Sirwin
Sirwin

Useful and efficient algorithms for secp256k1 elliptic curve

By CryptoDeep | CRYPTODEEP | 7 Sep 2022


CRYPTO DEEP TECH  

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  0  , y  0  )  on the elliptic curve  E  means: its coordinates  x  0  and  y  0  are elements of the field, and the coordinates  x  0  and  y  0  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

Useful and efficient algorithms for secp256k1 elliptic curve

  • 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  1  + P  2  , Q) \u003d e  m  (P  1  , Q) * e  m  (P2, B),

e  m  (P, Q  1  + Q  2  ) = e  m  (P, Q  1  ) * e  m  (P, Q  2  ).

The Weil  pair  P  and  Q  is the number

Useful and efficient algorithms for secp256k1 elliptic curve

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:

Useful and efficient algorithms for secp256k1 elliptic curve

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  0  + m  1  * 2 + m  2  * 2  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).

Useful and efficient algorithms for secp256k1 elliptic curve

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

 

How do you rate this article?

1


CryptoDeep
CryptoDeep

Financial security of data and secp256k1 elliptic curve cryptography against weak ECDSA signatures in BITCOIN cryptocurrency


CRYPTODEEP
CRYPTODEEP

Financial security of data and secp256k1 elliptic curve cryptography against weak ECDSA signatures in BITCOIN cryptocurrency [email protected] - Email for all questions. The creators of the software are not responsible for the use of materials Donation Address: ♥ BTC: 1Lw2gTnMpxRUNBU85Hg4ruTwnpUPKdf3nV ♥ETH: 0xaBd66CF90898517573f19184b3297d651f7b90bf ♥ YooMoney.ru/to/410011415370470

Send a $0.01 microtip in crypto to the author, and earn yourself as you read!

20% to author / 80% to me.
We pay the tips from our rewards pool.