Useful and efficient algorithms for secp256k1 elliptic curve

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

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

• Algorithm for generating a point on a 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 divider D over the curve E with carrier supp(D) given size d

• Miller’s algorithm for calculating the value of the Weil function f _{n, P} by divisor D such that supp(D) ∩ {P, O} = ∅

• Pairing Weil (Weyl pairing)

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 inverse of x mod n . There are two popular methods solutions :• Method 1 : Try each value for a bye xa mod n = 1 .• Method 2 : Euclidean method that is commonly used to solve the inverse problem of large integers, so it is recommended to use method 1 to solve the inverse problem of small integers.

Elliptic Curve Point Operation

Dot P(x ₀ ,y ₀ ) on an 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 will be three points on an elliptic curve. Adding points P + Q = R.

2. Doubling points on an elliptic curve : let P, Q are two points on an elliptic curve. Doubling Points P + P = 2P = Q

3. Scalar multiplication : let P will be a point on the curve E defined in the equation

   • Scalar multiplication nP defined as nP = P + P + P + … + P ( n times), where n is an integer; nP is also a point on the same curve E .

   • The minimum natural number a for aP = O called in order P .

   • Dot multiplication is widely required in elliptic curve cryptosystems.

Divider

Divisor (Divider) D on the curve E is a convenient way to indicate multiset of points on E written as a formal sum

• The set of all divisors E denoted Div _Fq (E) and forms a group in which the addition of divisors is natural.

• Zero Divisor: This is the divisor for all n _P = 0, zero divisor 0 ∈ Div _Fq (E) .

• If the field F _q is not specific, it can be omitted and simply written as Div(E) to denote a group of divisors.

Function f divided by E

Function Divisor f on the E used to denote intersection points (and their multiplicities) of functions f and E .

Pairing Weil

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

e _m (P _one + P ₂ Q) = e _m (P _one Q) * e _m (P2, B),

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

Pair Weil P and Q is the quantity

where S ∈ E is any point that satisfies the condition S ∉ {O, P, −Q, P − Q} . (This ensures that all quantities on the right side are defined and non-zero.) You can check that the value e _m (P,Q) does not depend on choice 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 ) are nonzero points on E .

Let λ will be the slope of the line connecting P and Q or the slope of the tangent to E in P if P= Q. (If the line is vertical, we assume λ = ∞.) Define the function g _{P, Q} on the E in the following way:

then

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

Miller’s algorithm

Let m ≥ and write the binary expansion m how

m = m ₀ + m _one *2+m ₂ *2 ² +···+m _{n – 1} 2 ^{n – 1}

at 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 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

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 footage: https://youtu.be/gFbiBCNPsFk

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

---