# Implementations

This document contains information about possible implementation choices and algorithms when implementing elliptic curve cryptography. It is mainly concerned with curve models, coordinate systems, addition formulas and scalar multiplication algorithms. Also, only curves over ( \mathbb{F}_p ) are analyzed.

## Curve models

### Weierstrass (full)

#### Affine

$y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$

#### Projective

$Y^2Z + a_1XYZ + a_3YZ^2 = X^3 + a_2X^2Z + a_4XZ^2 + a_6Z^3$

### Weierstrass (short)

EFD entry

toweierstrass weierx = x
toweierstrass weiery = y
a0 = 1
a1 = 0
a2 = 0
a3 = 0
a4 = a
a6 = b
fromweierstrass x = weierx
fromweierstrass y = weiery


#### Affine

$y^2 = x^3 + a x + b$

#### Projective

$Y^2Z = X^3 + aXZ^2 + bZ^3$

#### Jacobian

$Y^2 = X^3 + aXZ^4 + bZ^6$

### Montgomery

EFD entry

toweierstrass weierx = x
toweierstrass weiery = y
a0 = b
a1 = 0
a2 = a
a3 = 0
a4 = 1
a6 = 0
fromweierstrass x = weierx
fromweierstrass y = weiery


#### Affine

$By^2 = x^3 + Ax^2 + x$

### Edwards

EFD entry

toweierstrass u = (c+y)/(c-y)
toweierstrass v = 2 c (c+y)/(x(c-y))
a0 = 1/(1-d c^4)
a1 = 0
a2 = 4/(1-d c^4)-2
a3 = 0
a4 = 1
a6 = 0
fromweierstrass x = 2 c u/v
fromweierstrass y = c(u-1)/(u+1)


#### Affine

$x^2 + y^2 = c^2 (1 + dx^2y^2)$

### Twisted Edwards

EFD entry

toweierstrass u = (1+y)/(1-y)
toweierstrass v = 2 (1+y)/(x(1-y))
a0 = 1/(a-d)
a1 = 0
a2 = 4 a/(a-d)-2
a3 = 0
a4 = 1
a6 = 0
fromweierstrass x = 2 u/v
fromweierstrass y = (u-1)/(u+1)


#### Affine

$ax^2 + y^2=1 + dx^2y^2$

### Hessian

EFD entry

toweierstrass u = 12(d^3-1)/(d+x+y)-9 d^2
toweierstrass v = 36(y-x)(d^3-1)/(d+x+y)
a0 = 1
a1 = 0
a2 = 0
a3 = 0
a4 = -27 d(d^3+8)
a6 = 54(d^6-20 d^3-8)
fromweierstrass x = (36(d^3-1)-v)/(6(u+9 d^2))-d/2
fromweierstrass y = (v+36(d^3-1))/(6(u+9 d^2))-d/2


#### Affine

$x^3+y^3+1=3dxy$

#### Projective

$X^3 + Y^3 + Z^3 = 3dXYZ$

## Coordinates

### Affine

(Weierstrass) infinity is special cased, sometimes represented as ( [0] ).

(Weierstrass) negation: (-[x, y] = [x, -y] )

• To Projective: ( [x, y] \rightarrow (x : y : 1) )
• To Jacobian: ( [x, y] \rightarrow (x : y : 1) )
• To Chudnovsky: ( [x, y] \rightarrow (x : y : 1 : 1 : 1) )

### Projective

\begin{align} [X, Y, Z] &\in \mathbb{K}^3
[X_1, Y_1, Z_1] &\sim [X_2, Y_2, Z_2]
\text{if}\ X_1 &= λ X_2,
Y_1 &= λ Y_2,
Z_1 &= λ Z_2
\text{for some}\ λ &\in \mathbb{K}^

(X : Y : Z) &= {(λ X, λ Y, λ Z) | λ \in \mathbb{K}^* } \end{align*}

(Weierstrass) infinity is ((0 : 1 : 0)).

(Weierstrass) negation: ( -(X : Y : Z) = (X : -Y : Z) )

• To Affine: ( (X : Y : Z) \rightarrow [X/Z, Y/Z] )
• To Jacobian: ( (X : Y : Z) \rightarrow (X/Z : Y/Z : 1) ) ?
• To Chudnovsky: ( (X : Y : Z) \rightarrow (X/Z : Y/Z : 1 : 1 : 1) ) ?

### Jacobian

\begin{align} [X, Y, Z] &\in \mathbb{K}^3
[X_1, Y_1, Z_1] &\sim [X_2, Y_2, Z_2]
\text{if}\ X_1 &= λ^2 X_2,
Y_1 &= λ^3 Y_2,
Z_1 &= λ Z_2
\text{for some}\ λ &\in \mathbb{K}^

(X : Y : Z) &= {(λ^2 X, λ^3 Y, λ Z) | λ \in \mathbb{K}^* } \end{align*}

(Weierstrass) infinity is ( (1 : 1 : 0) ).

(Weierstrass) negation: ( -(X : Y : Z) = (X : -Y : Z) )

• To Affine: ( (X : Y : Z) \rightarrow [X/Z^2, Y/Z^3] )
• To Projective: ( (X : Y : Z) \rightarrow (X/Z^2 : Y/Z^3 : 1) ) ?
• To Chudnovsky: ( (X : Y : Z) \rightarrow (X : Y : Z : Z^2 : Z^3) )

### Chudnovsky

\begin{align} [X, Y, Z, Z^2, Z^3] &\in \mathbb{K}^5
(X : Y : Z : Z^2 : Z^3 ) &= {(λ^2 X, λ^3 Y, λ Z, λ^2 Z^2, λ^3 Z^3) | λ \in \mathbb{K}^
} \end{align*}

(Weierstrass) infinity is ( (1 : 1 : 0 : 0 : 0) ). ?

(Weierstrass) negation: ( -(X : Y : Z : Z^2 : Z^3) = (X : -Y : Z : Z^2 : Z^3) )

• To Affine: ( (X : Y : Z : Z^2 : Z^3) \rightarrow [X/Z^2, Y/Z^3] )
• To Projective: ( (X : Y : Z : Z^2 : Z^3) \rightarrow (X/Z^2 : Y/Z^3 : 1) ) ?
• To Jacobian: ( (X : Y : Z : Z^2 : Z^3) \rightarrow (X : Y : Z) )

• Doubling
• Tripling
• Scaling

See EFD[^3].

## Scalar multiplication

See TAOCP volume 2, section 4.6.3 for introduction to multiplication/exponentiation and addition/multiplication chains.[^5]

Scalar multiplication on elliptic curves is very similar to usual multiplication/exponentiation in general additive/multiplicative groups, respectively, with some additional structure:

• (A + B) when (A \ne B) might be a different operation from (A + A = [2]A), and also sometimes takes different time.
• negation (-A) is easy/fast.
• (0) sometimes has a special representation and thus requires special casing.
• sometimes, there exists a fast operation of (\phi: E(\mathbb{F}_p) \rightarrow E(\mathbb{F}_p) ) with ( \phi(P) = [k]P ) for some (k \in \mathbb{K}) computable using some endomorphism on the curve.

We define:

• ( \lambda(k) = \lfloor \log_2 k \rfloor ) , the size of k
• ( k_i ) , the i-th bit of k
• ( \nu(k) = \vert { i \vert 0 \le i \le \lambda(k), k_i = 1} \vert ) , the number of nonzero bits in k
• ( l(k) ) , the length of NAF of k
• ( \sigma(k) = \vert { i \vert 0 \le i \le l(k), NAF(k)_i \ne 0 } \vert ) , the number of nonzero values in the NAF of k
• ( C_2 ) , the cost of doubling a point
• ( C_+ ) , the cost of point addition
• ( C_{algo}(k) ) , the cost of scalar multiplication by k of the algorithm algo
• Addition chain of n, is a sequence of integers: ( 1 = a_0, a_1, \ldots, a_r = n), where (a_i = a_j + a_k) for some ( k \le j < i, \forall i \in { 1, 2, \ldots, r } )
• Addition-subtraction chain of n, is a sequence of integers: ( 1 = a_0, a_1, \ldots, a_r = n), where (a_i = \pm a_j \pm a_k) for some ( k \le j < i, \forall i \in { 1, 2, \ldots, r } )
• Addition sequence for ( r_1, r_2, \ldots, r_t ) is an addition chain: ( 1 = a_1, a_2, \ldots, a_l ) which contains ( r_1, r_2, \ldots, r_t ). Useful when operating with one element and many powers ( g^{r_1}, g^{r_2}, \ldots )
• Vector addition chain for (r \in \mathbb{N}^t ) is a sequence of elements ( v_i ) of ( \mathbb{N}^t ) such that ( v_i = e_i ) for ( 1 \le i \le t ) and ( v_i = v_j + v_k ) for (j \le k < i ). Useful when powering many elements to many powers ( g_1^{r_1}, g_2^{r_2}, \ldots )

### Double and Add (binary exponentiation)

Algorithm 3.26 (right-to-left) in GECC1

INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q).
OUTPUT: [k]P.
1. Q ← ∞.
2. For i from t - 1 downto 0 do
2.1 If k_i = 1 then Q ← Q + P.
2.2 P ← 2P.
3. Return(Q).


Algorithm 3.27 (left-to-right) in GECC1

INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q).
OUTPUT: [k]P.
1. Q ← ∞.
2. For i from t - 1 downto 0 do
2.1 Q ← 2Q.
2.2 If k_i = 1 then Q ← Q + P.
3. Return(Q).


Cost: ( C_{binexp}(k) = \lambda(k)C_2 + (\nu(k) - k_0)C_+)[^7]

### Double and Add Always (binary exponentiation - constant time)

(right-to-left)

INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q).
OUTPUT: [k]P.
1. Q ← ∞.
2. For i from t - 1 downto 0 do
2.1 If k_i = 1 then Q ← Q + P else Dummy ← Q + P.
2.2 P ← 2P.
3. Return(Q).


(left-to-right)

INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q).
OUTPUT: [k]P.
1. Q ← ∞.
2. For i from t - 1 downto 0 do
2.1 Q ← 2Q.
2.2 If k_i = 1 then Q ← Q + P else Dummy ← Q + P.
3. Return(Q).


Cost: ( C_{const_binexp}(k) = \lambda(k) (C_2 + C_+) ) ?

### Binary NAF multiplication (signed binary exponentiation)

Definition 3.281 A non-adjacent form (NAF) of a positive integer k is an expression ( k = \Sigma_{i=0}^{l - 1} k_i 2^i ) where (k_i \in {0, ±1}, k_{l−1} \ne 0), and no two consecutive digits ( k_i ) are nonzero. The length of the NAF is l.

Algorithm 3.30 Computing the NAF of a positive integer1

INPUT: A positive integer k.
OUTPUT: NAF(k).
1. i ← 0.
2. While k ≥ 1 do
2.1 If k is odd then:
k_i ← 2 − (k mod 4), k ← k − k_i ;
2.2 Else:
k_i ← 0.
2.3 k ← k/2, i ← i + 1.
3. Return(k_{i−1}, k_{i−2}, ..., k_1, k_0).


Algorithm 3.31 Binary NAF multiplication (left-to-right)1

INPUT: Positive integer k, P ∈ E(F_q).
OUTPUT: [k]P.
1. Use Algorithm 3.30 to compute NAF(k).
2. Q ← ∞.
3. For i from l - 1 downto 0 do
3.1 Q ← 2Q.
3.2 If k_i = 1 then Q ← Q + P.
3.3 If k_i = -1 then Q ← Q - P.
4. Return(Q).


Cost: ( C_{bin_NAF} = l(k)C_2 + \sigma(k)C_+ + \text{NAF computation cost}) ?

### (m)-ary method

Like binary double-and-add but uses a different base m.[^6]

INPUT: k = (k_{t-1}, ..., k_1, k_0)_m, P ∈ E(F_q).
OUTPUT: [k]P
1. Compute P_i = [i]P for i ∈ {1, 2, ..., m - 1}.
2. Q ← ∞.
3. For i from l downto 0 do
3.1 Q ← [m]Q.
3.2 Q ← Q + P_{k_i}.
4. Return(Q).


### ( 2^r ) method

Like (m)-ary method, with ( m = 2^r ), means that [m]Q is doable with only doubling.[^6]

### Sliding window

Algorithm 13.6 Sliding window in HEHCC2

INPUT: Window width w, k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q).
OUTPUT: [k]P
1. Compute P_i = [i]P for i ∈ {3, 5, ..., 2^w - 1}. //precomputation for fixed P
2. Q ← ∞, i ← t - 1.
3. While i ≥ 0 do
3.1 If k_i = 0 then:
Q ← [2]Q, i ← i - 1.
3.2 Else:
3.2.1   s ← max(i - k + 1, 0).
3.2.2   While k_s = 0 do
s ← s + 1.
3.2.3   For h from 1 to i - s + 1 do
Q ← [2]Q.
3.2.4   u ← (k_i, ..., k_s)_2.
3.2.5   Q ← P_u.                // u is odd.
3.2.6   i ← s - 1.
4. Return(Q).


Algorithm 3.38 Sliding window with NAF(signed sliding window) in GECC1

INPUT: Window width w, positive integer k, P ∈ E(F_q).
OUTPUT: [k]P.
1. Use Algorithm 3.30 to compute NAF(k).
2. Compute P_i = [i]P for i ∈ {1, 3, ..., 2(2^w - (-1)^w)/3 - 1}. //precomputation for fixed P
3. Q ← ∞, i ← l - 1.
4. While i ≥ 0 do
4.1 If k_i = 0 then:
t ← 1, u ← 0.
4.2 Else:
find the largest t ≤ w such that u ← (k_i , ..., k_{i-t+1}) is odd.
4.3 Q ← [2^t]Q.
4.4 If u > 0 then:
Q ← Q + P_u.
4.5 Else:
if u < 0 then Q ← Q - P_{-u}.
4.6 i ← i - t.
5. Return(Q).


### Window NAF multiplication

Definition 3.321 Let ( w \ge 2 ) be a positive integer. A width-w NAF of a positive integer k is an expression ( k = \Sigma_{i=0}^{l - 1} k_i 2^i ) where each nonzero coefficient ( k_i ) is odd, ( \vert k_i \vert < 2^{w - 1}, k_{l-1} \ne 0 ), and at most one of any w consecutive digits is nonzero. The length of the width-w NAF is l.

Algorithm 3.35 Computing the width-w NAF of a positive integer1

INPUT : Window width w, positive integer k.
OUTPUT : NAF-w(k).
1. i ← 0.
2. While k ≥ 1 do
2.1 If k is odd then:
k_i ← k mods 2^w , k ← k − k_i; // k mods 2^w is an integer u, -2^{w-1} ≤ u < 2^{w-1}, u ≡ k mod 2^w
2.2 Else:
k_i ← 0.
2.3 k ← k/2, i ← i + 1.
3. Return(k_{i−1}, k_{i−2}, ..., k_1, k_0).


Algorithm 3.36 in GECC1

INPUT: Window width w, positive integer k, P ∈ E(F_q).
OUTPUT: [k]P.
1. Use Algorithm 3.35 to compute NAF-w(k).
2. Compute P_i = [i]P for i ∈ {1, 3, 5, ..., 2^{w-1} - 1}. //precomputation for fixed P
3. Q ← ∞.
4. For i from l - 1 downto 0 do
4.1 Q ← 2Q.
4.2 If k_i != 0 then:
If k_i > 0 then:
Q ← Q + P_{k_i} ;
Else:
Q ← Q - P_{-k_i} .
5. Return(Q).


### Fractional window

[^10] and [^11]

The same name, Montgomery ladder, is used both for the general ladder idea of exponentiation/scalar-multiplication and the concrete x-coordinate only addition formulas and scalar multiplication algorithm on Montgomery curves.

Algorithm 13.35 in 2 (general Montgomery ladder)

INPUT: k = (k_{t-1}, ..., k_1, k_0)_2, P ∈ E(F_q).
OUTPUT: [k]P .
1. P_1 ← P and P_2 ← [2]P
2. For i = t − 2 downto 0 do
2.1 If k_i = 0 then
P_1 ← [2]P_1; P_2 ← P_1 + P_2.
Else
P_1 ← P_1 + P_2; P_2 ← [2]P_2.
3. Return(P_1).


Algorithm 3. in [^8] (general Montgomery ladder)

INPUT: G ∈ E(F_q), k = (1, k_{t−2}, ..., k_0)2
OUTPUT: Y = kG
R0 ← G; R1 ← [2]G
for j = t − 2 downto 0 do
if (k_j = 0) then
R1 ← R0 + R1; R0 ← [2]R0
else [if (kj = 1)]
R0 ← R0 + R1; R1 ← [2]R1
return R0


Montgomery addition formulas (Projective coordinates/XZ coordinates):2

• Addition (( n \ne m )): \begin{align} X_{m+n} &= Z_{m-n}((X_m - Z_m)(X_n + Z_n) + (X_m + Z_m)(X_n - Z_n))^2
Z_{m+n} &= X_{m-n}((X_m - Z_m)(X_n + Z_n) - (X_m + Z_m)(X_n - Z_n))^2 \end{align
}

• Doubling: \begin{align} 4X_nZ_n &= (X_n + Z_n)^2 - (X_n - Z_n)^2
X_{2n} &= (X_n + Z_n)^2 (X_n - Z_n)^2
Z_{2n} &= 4X_nZ_n((X_n - Z_n)^2 + ((A + 2)/4)(4X_nZ_n)) \end{align
}

• ( Y ) recovery: \begin{align} x_n &= X_n / Z_n; \qquad x_{n+1} = X_{n+1} / Z_{n+1}
y_n &= \frac{(x_1x_n + 1) (x_1 + x_n + 2A) - 2A - (x_1 - x_n)^2x_{n+1}}{2By_1} \end{align
}

Not really a scalar-multiplication algorithm. Generalization of the stricter Montgomery ladder(the x-coordinate only scalar-mult algo and addition formulas on Montgomery curves) to short Weierstrass elliptic curves over fields of ( \text{char}\ \mathbb{K} \ne 2, 3 ) by Brier & Joye. Furthermore the x-coordinate only addition formulas were generalized to curves over ( \mathbb{F}_{2^m} ) by Lopez & Dahab.

Brier-Joye addition formulas (Projective coordinates/XZ coordinates):2

• Addition (( n \ne m )): \begin{align} X_{m+n} &= Z_{m-n}(-4a_6Z_mZ_n(X_mZ_n + X_nZ_m) + (X_mX_n - a_4 Z_mZ_n)^2)
Z_{m+n} &= X_{m-n}(X_mZ_n - X_nZ_m)^2 \end{align
}

• Doubling: \begin{align} X_{2n} &= (X_n^2 - a_4Z_n^2)^2 - 8 a_6X_nZ_n^3
Z_{2n} &= 4Z_n(X_n(X_n^2 + a_4 Z_n^2) + a_6Z_n^3) \end{align
}

• ( Y ) recovery: \begin{align} x_n &= X_n / Z_n; \qquad x_{n+1} = X_{n+1} / Z_{n+1}
y_n &= \frac{2a_6 +(x_1x_n + a_4) (x_1 + x_n) - (x_1 - x_n)^2x_{n+1}}{2y_1} \end{align
}

Lopez-Dahab addition formulas on ( E(\mathbb{F}_{2^m}) )(Projective coordinates/XZ coordinates):2

• Addition (( n \ne m )): \begin{align} Z_{m+n} &= (X_mZ_n)^2 + (X_nZ_m)^2
X_{m+n} &= Z_{m+n}X_{m-n} + X_mZ_nX_nZ_m \end{align
}

• Doubling: \begin{align} X_{2n} &= X_n^4 + a_6Z_n^4 = (X_n^2 + \sqrt{a_6}Z_n^2)^2
Z_{2n} &= X_n^2Z_n^2 \end{align
}

• ( Y ) recovery: \begin{align} x_n &= X_n / Z_n; \qquad x_{n+1} = X_{n+1} / Z_{n+1}
y_n &= \frac{(x_n + x_1)((x_n + x_1)(x_{n+1} + x_1) + x_1^2 + y_1)}{x_1} + y_1 \end{align
}

[^13]

### Fixed-base windowing (BGMW)

Algorithm 3.41 and Algorithm 3.42 in GECC1

### Fixed-base comb

Algorithm 3.44 and Algorithm 3.45 in GECC1

### Möller-1

The method may fail in some cases in that an addition step may turn out to be a point doubling or may involve the point at infinity (which both requires special treatment and is potentially clearly visible through side channels). However, we will show that the probability of this happening is negligible if multipliers are appropriately selected: Randomly chosen e is safe.[^9]

## References

Tanja; NGUYEN, Kim; VERCAUTEREN, Frederik. Handbook of Elliptic and Hyper- elliptic Curve Cryptography. CRC Press, 2005-07-19. Discrete Mathematics and It’s Applications, no. 34. ISBN 9781584885184. [^3]: BERNSTEIN, Daniel J.; LANGE, Tanja. Explicit Formulas Database, https://www.hyperelliptic.org/EFD/ [^4]: http://point-at-infinity.org/ecc/ [^5]: KNUTH, Donald: The Art of Computer Programming, Volume 2: Seminumerical algorithms [^6]: GORDON, Daniel M.: A survey of fast exponentiation methods. [^7]: MORAIN, Francois; OLIVOS, Jorge: Speeding up the computations on an elliptic curve using addition-subtraction chains. [^8]: JOYE, Marc; YEN, Sung-Ming: The Montgomery Powering Ladder. [^9]: MOLLER, Bodo: Securing Elliptic Curve Point Multiplication against Side-Channel Attacks. [^10]: MOLLER, Bodo: Improved Techniques for Fast Exponentiation. [^11]: MOLLER, Bodo: Fractional Windows Revisited: Improved Signed-Digit Representations for Efficient Exponentiation. [^12]: KOYAMA, Kenji; TSURUOKA, Yukio: Speeding up Elliptic Cryptosystems by Using a Signed Binary Window Method. [^13]: GALLANT, Robert P.; LAMBERT, Robert J.; VANSTONE, Scott A.: Faster point multiplication on elliptic curves with efficient endomorphisms.

1. HANKERSON, Darrel; MENEZES, Alfred J.; VANSTONE, Scott. Guide to Elliptic Curve Cryptography. New York, USA: Springer, 2004. ISBN 9780387218465. Available from DOI: 10.1007/b97644 2 3 4 5 6 7 8 9 10 11

2. COHEN, Henri; FREY, Gerhard; AVANZI, Roberto M.; DOCHE, Christophe; LANGE,  2 3 4 5