Elliptic Curve

For an elliptic curve E over the field GF(p) given by short Weierstrass equation

y² = x³ + Ax + B,

realized:

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

Modular Operations (Integer) in finite field (or Galois field)

1. x mod n means “the remainder of n dividing x”. In other words, if x = an + b, and a, b ∈ integer as well as 0 ≤ b ≤ n − 1, then x mod n = b.

2. Inverse: If ax = 1 mod n,then a is the inverse of x mod n. There are two popular methods to solve a:

   • Method 1: Try every value for a < n until xa mod n = 1.

   • Method 2: Euclidean method, which is usually used to solve the inverse of big integers, so it is recommended to use Method 1 to solve the inverse of small integers.

Elliptic Curve Points Operation

A point P(x₀, y₀) on elliptic curve E means: its coordinates x₀ and y₀ are elements in the field, and the coordinates x₀ and y₀ satisfy Equation.

1. Elliptic curve points addition: Let P, Q and R be three points on an elliptic curve. Points addition P + Q = R.
2. Elliptic curve points doubling: Let P, Q be two points on an elliptic curve. Points doubling P + P = 2P = Q
3. Scalar multiplication: Let P be a point on curve E defined in equation
   • Scalar 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 curve E.
   • The minimal positive integer a for aP = O is called the order of P .
   • Scalar multiplication is extensively required in elliptic curve cryptosystems.

Divisor

A divisor D on curve E is a convenient way to denote a multi-set of points on E, written as the formal sum

• The set of all divisors on E is denoted by Div_Fq(E) and forms a group, where addition of divisors is natural.
• The zero divisor: it is the divisor with all n_P = 0, the 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 the group of divisors.

The Divisor of a Function f on E

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

The Weil pairing

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

e_m(P₁ + P₂, Q) = e_m(P₁, Q) * e_m(P2, Q),

e_m(P, Q₁ + Q₂) = e_m(P, Q₁) * e_m(P, Q₂).

The Weil pairing of P and Q is the quantity

where S ∈ E is any point satisfying S ∉ {O, P, −Q, P − Q}. (This ensures that all of the quantities on the right-hand side of are defined and nonzero.) 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 algorithm to compute the Weil pairing

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 line to E at P if P = Q. (If the line is vertical, we let λ = ∞.) 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 expansion of m as

m = m₀ + m₁ * 2 + m₂ * 2² +···+ m_{n - 1} 2^{n - 1}

with m_i ∈ {0, 1} and m_{n - 1} ≠ 0. The following algorithm returns a function f_P whose divisor satisfies

div(f_P) = m[P] − [mP] − (m − 1)[O],

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

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

Requirements

• Python 3.5
• numpy

---

Commands:

git clone https://github.com/demining/CryptoDeepTools.git

cd CryptoDeepTools/04AlgorithmsForSecp256k/

pip3 install numpy

Code Organization

├── Curves.py             <- Dataset of elleptic curves
├── Divisor.py            <- Generarate divisor
├── EllipticCurve.py      <- Classes of elliptic curve and point on elliptic curve
├── EuclideanAlg.py       <- Extended Euclidean algorithm
├── Helper.py             <- Helping functions(Reverse bits, modulo power...) 
├── Pairing.py            <- Weil pairing and Miller’s Algorithm
├── Tests.py              <- Unit tests for functions
├── Tonelli_ShanksAlg.py  <- Tonelli–Shanks algorithm
├── main.py               <- main

Acknowledgements

We would like to thank @ElizaLo for her valuable work.

Useful Articles

• Efficient Computation of Miller's Algorithm in Pairing-Based Cryptography
• An Introduction to Mathematical Cryptography
• Tonelli–Shanks algorithm
• Quadratic residue
• Exponentiation by squaring
• Extended Euclidean algorithm

Useful Links

• Elliptic Curves
• How to find primitive point on an elliptic curve?
• Generating random (torsion) point on elliptic curve efficiently

---

	Donation Address
♥ BTC	1Lw2gTnMpxRUNBU85Hg4ruTwnpUPKdf3nV
♥ ETH	0xaBd66CF90898517573f19184b3297d651f7b90bf