# Elliptic Curve Addition Presentation
---
## Metadata
**Status**:: #x
**Kind**:: #presentation
**Zettel**:: #zettel/literature
**Created**:: [[2024-03-27]]
**Due**:: [[2024-05-15]]
---
## Elliptic Curve Addition for Programmers
---
## Motivation
> [!note]
> According to the [[Feynman Technique]], the best way to learn is by teaching. With a desire to delve deeper into the topic of elliptic curves, I have decided to share my knowledge on the subject.
>
> I want to learn about elliptic curves because I am currently studying Zero Knowledge (ZK). For programmers interested in learning ZK, I highly recommend the series of tutorials on elliptic curves from Rareskills, called the [[RareSkills ZK Book]].
---
![[ecc-addition.svg|Elliptic Curve Addition]]
> [!note]
> I have some basic understanding of elliptic curves. They are curves on 2D space. The addition is defined as connecting the two points and finding the third intersection then flipping the y axis.
---
```python
from py_ecc import optimized_bn128 as bn128
print(bn128.G1)
# => (1, 2, 1)
print(bn128.G2)
# => ((108570...2781, 115597...5634)
# => ,(849565...1930, 408236...3531)
# => ,(1, 0))
```
> [!note]
> While familiarizing myself with the ZK (Zero Knowledge) protocol, I referenced the python library [py\_ecc](https://github.com/ethereum/py_ecc). However, when I experimented with bn128 curves, I encountered difficulties. In the `optimized_bn128` package, the points in the G1 curve are expressed as a tuple of 3 numbers, while in the G2 curve, a point is represented by 2x3 numbers. How this is related to the Cartesian coordinates which represents a point as $(x, y)$? I decided to delve into it.
---
## Objectives
- Intuitions on Abstract Algebra and Elliptic Curves
- Learn terminology
- Implement bn128 curves addition
- Use sympy to solve math problems
---
## Recommended Books
![[cover-calibre-557.jpg|256]] ![[cover-calibre-558.jpg|256]]
> [!note]
> The first book is for programmers. The second is more academic.
---
## Abstract Algebra
- [[Group]] / 群
- [[Ring]] / 环
- [[Field]] / 域
> [!note]
> Have you got a headache already? Don't be put off by the terminology. For programmers they are just interfaces. If something is a field, it is a set corresponding to a type in a program. You can do additions and multiplications on that type, while the additions and multiplications satisfy some properties.
---
### Isomorphism
> [!note]
> Isomorphism is a fundamental concept in abstract algebra that captures theidea of two algebraic structures being "essentially the same" despite possibly having different representations
> It's important in abstract algebra because if two structures are isomorphic, equations in one structure also hold in another structure.
---
### Isomorphism Example
Elliptic Curve group $sG$ is isomorphic to integers modulus prime number group.
$
aG + bG = cG \iff a + b = c
$
> [!note]
> ![[Elliptic Curve Scalar Multiplication#ECDLP]]
---
### Abelian Group
[[Abelian Group]] is a [[Group]] and the binary operator is commutative.
- Abelian group is a set U under the binary operator ⨁.
- ([[Magma]]) The binary operator is closed: $\forall a, b \in U: a \oplus b \in U$
- ([[Semigroup]]) The binary operator is associative: $(a \oplus b) \oplus c = a \oplus (b \oplus c)$
---
### Abelian Group (Cont.)
- ([[Monoid (Math)|Monoid]]) There exists an identity element: $\exists 0 \in U: a \oplus 0 = 0 \oplus a = a$
- ([[Group]]) Every element has an inverse: $\forall a \in U: \exists b \in U: a \oplus b = 0$
- (Abelian Group) The operator is commutative: $\forall a, b \in U: a \oplus b = b \oplus a$
---
### Group Interface
```rust
pub trait Group {
// monoid
const EMPTY: Self;
// magma
fn combine(self, rhs: Self) -> Self;
// group
fn inverse(self) -> Self;
}
```
---
### Group Constraints
```rust
pub fn constraints<T: Group + Copy + Eq + std::fmt::Debug>(a: T, b: T, c: T) {
// semigroup
assert_eq!(a.combine(b).combine(c), a.combine(b.combine(c)));
// monoid
assert_eq!(a.combine(T::EMPTY), a);
assert_eq!(T::EMPTY.combine(a), a);
// group
assert_eq!(a.combine(a.inverse()), T::EMPTY);
}
```
---
### Interface & Abstraction
> [!note]
> If two structures have the same interface, they are exchangeable if we only depend on their interfaces.
---
### Polynomials as Integers
> [!note]
> If we can define addition and multiplication on polynomials, and they hold the same properties under addition and multiplication as integers, we can use polynomials in places where integers are used.
---
### Field
A field is a set with two binary operators ⨁ and ⨂。
- The set under the operation ⨁ form an [[Abelian Group]].
- The set excluding the identity in the ⨁ abelian group under the operation ⨂ form an [[Abelian Group]].
---
### Field Examples
- Real numbers under + and x
- Integers modulus p under + and x when p is prime
- Polynomials with degree strictly less than n
---
## Elliptic Curve
The most popular elliptic curve is the Weierstrass curve which is defined as
$
y^2 = x^3 + ax + b
$
---
## Curve Addition
![[ecc-addition.svg|Elliptic Curve Addition]]
$\tag{1} P=(x_1, y_1), Q=(x_2, y_2), R=(x_3, -y_3)$
---
### Special Cases
- $P + 0 = 0 + P = 0$
- Case 3: $P + Q = 0$ where $P \neq Q$ and $P.x = Q.x$
- Case 4: $P + P = 0$ where $P.y = 0$
---
### Adding Distinct Points
---
#### Geometry Problem
$
\begin{align}
y^2 &= x^3 + ax + b \\
y - y_1 &= \lambda (x - x_1)\\
\end{align}
$
> [!note]
> P, Q, and -R are three points that lie on both a curve and a line. Let P be represented as $(x_1, y_1)$, and we have two formulas: one for the curve and one for the line. The line formula uses the slope $\lambda$ which is determined by any two points in the line.
---
#### Slope
$
\lambda = \frac{y_2 - y_1}{x_2 - x_1}
$
---
#### Y
$
\begin{align}
\tag{1} y - y_1 &= \lambda (x - x_1) \\
\lambda &= \frac{y_2 - y_1}{x_2 - x_1} \\
\tag{2} -y_3 - y_1 &= \lambda(x_3 - x_1) \\
y_3 &= \lambda(x_1 - x_3) - y_1
\end{align}
$
> [!note]
> To compute the value of $y_3$, substitute $R = (x_3, -y_3)$ into line formula (1), resulting in expression (2).
---
#### X
$
\begin{align}
\tag{1} y^2 &= x^3 + ax + b \\
\tag{2} y - y_1 &= \lambda (x - x_1)\\
y &= \lambda x + y_1 - \lambda x_1 \\
\tag{3} (\lambda x + y_1 - \lambda x_1)^2 &= x^3 + ax + b \\
\end{align}
$
> [!note]
> The three points satisfy both equations, allowing us to substitute $y$ in the curve formula (1) with the line formula (2). These three points serve as roots for the equation (3) on the x-axis.
---
#### X (Cont.)
$
x^3 - \lambda^2x^2 + a'x + c' = 0
$
> [!note]
> To simplify the equation, we can order it by the degree of the variable $x$, resulting in this formula.
---
#### Vieta's Formula
> [!important] Definition
> For a cubic polynomial $ax^3 + bx^2 + cx + d = 0$, the sum of its three roots is $-\frac{b}{a}$
> [!note]
> Computing the roots is challenging, and I'm unsure how the final formula is derived from the Elliptic Curve addition tutorials. So, I turned to AI, and it [provided me with the answer](https://www.perplexity.ai/search/What-is-the-4_Zpelt4T5q2SC66Cnl72w): Vieta's Formula.
---
#### X (Final)
$
\begin{align}
ax^3 + bx^2 + cx + d = 0 & \quad x_1+x_2+x_3=-\frac{b}{a} \\
x^3 - \lambda^2x^2 + a'x + c' = 0 & \quad x_1+x_2+x_3=\lambda^2 \\
x^3 = \lambda^2 - x_1 - x_2
\end{align}
$
---
#### Summary
$
\begin{align}
\lambda &= \frac{y_2 - y_1}{x_2 - x_1} \\
x_3 &= \lambda^2-x_1-x_2 \\
y_3 &= \lambda(x_1-x_3) - y_1 \\
\end{align}
$
---
### Doubling
![[ecc-addition.svg|Elliptic Curve Addition]]
$\tag{2} Q=(x_1, y_1), P=(x_3, -y_3)$
---
#### Slope of the Tangent Line
> [!important] Theorem
> Slope of the tangent line is the value of the derivative at the point.
---
#### Derivative What?
$
\lambda = y'(x_1)
$
---
#### Mathematician Way
$
\begin{align}
\frac{dy^2}{dx} &= \frac{d(x3 + ax + b)}{dx} \\
2y\frac{dy}{dx} &= 3x^2+a \\
\frac{dy}{dx} &= \frac{3x^2 + a}{2y}
\end{align}
$
---
#### Programmer Way
```python
from sympy import symbols, diff, solve, simplify
x, y, a, b = symbols('x y a b')
roots = solve(y**2 - x**3 - a*x - b, y)
for root in roots:
print(f"y = {root}")
dy = simplify(diff(root, x).subs(root, y))
print(f"dy = {dy}")
```
> [!note]
> [SymPy](https://www.sympy.org/en/index.html) is an open-source Python library for symbolic computation. It can compute the derivative for us. It supports printing expressions in different languages, such as Python, JavaScript, Rust, and etc.
---
#### Vieta's Formula For Doubling
The equation have two identical roots at the tangent point.
$x_1 + x_1 + x_3 = \lambda^2 $
---
#### Summary
$
\begin{align}
\lambda &= \frac{3x_1^2+a}{2y_1} \\
x_3 &= \lambda^2-2x_1 \\
y_3 &= \lambda(x_1-x_3) - y_1 \\
\end{align}
$
---
#### Security Alert
> [!important]
Using different equations to compute $\lambda$ is [[Mike Rosing - Defense Against Power Analysis Attacks Avoiding Elliptic Curve Side Channel Attacks (Highlights)|vulnerable to the side channel attacks]].
---
## Elliptic Curve Over Finite Field
> [!note]
> Elliptic Curve Addition also works for finite field.
---
### Finite Field
Field + Finite Number of Members
> [!note]
> Finite Field is computer friendly since we cannot represent real numbers precisely in computers.
---
### Example Finite Field
Integers modulus p where p is a prime, denoted as $\mathbb{Z}/p\mathbb{Z}$ or $\mathrm{GF}(p)$
> [!note]
> (**Reference**:: [[Modular Arithmetic]])
---
### Additive Inverse
$
\begin{align}
a + (-a) &\equiv 0 \pmod{p} \\
2 + 5 &\equiv 0 \pmod{7} \\
\end{align}
$
> [!note]
> Example: $2 + 5 \equiv 0 \pmod{7}$
---
### Multiplicative Inverse
$
\begin{align}
a \times \frac{1}{a} &\equiv 1 \pmod{p} \\
2 \times 4 &\equiv 1 \pmod{7} \\
\end{align}
$
> [!note]
> Example: $2 \times 4 \equiv 1 \pmod{7}$
---
### Non-Prime Modulus
$
\begin{align}
2 \times ? &\equiv 1 \pmod{4} \\
\end{align}
$
---
### Extended Euclidean Algorithm
> [!important] Bézout's identity
> Let _a_ and _b_ be integers with greatest common divisor _d_. Then there exist integers _x_ and _y_ such that $ax + by = d$. Moreover, the integers of the form $az + bt$ are exactly the multiples of _d_.
---
$
\begin{align}
ax + by &= d \\
a(\frac{1}{a}) + py &= 1 \\
a(\frac{1}{a}) &\equiv 1 \pmod{p} \\
\end{align}
$
---
> [!example] Python Example Code
> ```python
> import sys
> from typing import Tuple
> sys.setrecursionlimit(1000000) # long type, 32bit OS 4B, 64bit OS 8B (1bit for sign)
>
> def egcd(a: int, b: int) -> Tuple[int, int, int]:
> """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
> if a == 0:
> return (b, 0, 1)
> else:
> b_div_a, b_mod_a = divmod(b, a)
> g, x, y = egcd(b_mod_a, a)
> return (g, y - b_div_a * x, x)
> ```
---
### Modular Arithmetic Summary
$
\begin{align}
\overline{a}_p + \overline{b}_p &= \overline{(a + b)}_p \\
\overline{a}_p - \overline{b}_p &= \overline{a}_p + (-\overline{b}_p) \\
\overline{a}_p \times \overline{b}_p &= \overline{(a \times b)}_p \\
\overline{a}_p \div \overline{b}_p &= \overline{a}_p \times {\frac{1}{\overline{b}_p}} \\
\end{align}
$
---
### Elliptic Curve Addition Over Finite Field
$
y^2 = x^3 + ax + b \pmod{p}
$
, where $x, y, a, b \in \mathbb{Z}/p\mathbb{Z}$
> [!note]
> Field acts as the interface here. Real number and integers modulus prime are two types that implement field, so they can be used in elliptic curve addition algorithm.
---
### Secp256k1 Demo
- [Integers modulus p](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/field.py)
- [Addition implementation and curve definitions](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/ecc/ecc.py)
- [Tests](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/ecc/test_secp256k1.py)
---
## Homogeneous Coordinate
```python
print(bn128.G1)
# => (1, 2, 1)
```
---
### Division is Slow
$
\lambda = \frac{y_2 - y_1}{x_2 - x_1}
$
---
### Definition
$
(x, y, z) \Rightarrow (\frac{x}{z}, \frac{y}{z})
$
> [!note]
> ![[Homogeneous Coordinate#Introduction]]
>
> The division can be eliminated by move the common denominator.
---
### Adding Distinct Points
---
#### Recap
$
\begin{align}
\lambda &= \frac{y_2 - y_1}{x_2 - x_1} \\
x_3 &= \lambda^2-x_1-x_2 \\
y_3 &= \lambda(x_1-x_3) - y_1 \\
\end{align}
$
---
#### Over Homogeneous
$
\begin{align}
\lambda &= \frac{\displaystyle\frac{y_2}{z_2} - \frac{y_1}{z_1}}{\displaystyle\frac{x_2}{z_2} - \frac{x_1}{z_1}} \\
\frac{x_3}{z_3} &= \lambda^2-\frac{x_1}{z_1}-\frac{x_2}{z_2} \\
\frac{y_3}{z_3} &= \lambda(\frac{x_1}{z_1}-\frac{x_3}{z_3}) - \frac{y_1}{z_1} \\
\end{align}
$
> [!note]
> [[Elliptic Curve in the Homogeneous Coordinate#Adding Distinct Points]]
---
#### Substituting
$
\begin{align}
u &= - y_{1} z_{2} + y_{2} z_{1} \\
v &= - x_{1} z_{2} + x_{2} z_{1} \\
x_3 &= \frac{u^{2} z_{1} z_{2} z_{3} - v^{2} x_{1} z_{2} z_{3} - v^{2} x_{2} z_{1} z_{3}}{v^{2} z_{1} z_{2}} \\
y_3 &= - \frac{z_{3} \left(- u \left(- u^{2} z_{1} z_{2} + 2 v^{2} x_{1} z_{2} + v^{2} x_{2} z_{1}\right) + v^{3} y_{1} z_{2}\right)}{v^{3} z_{1} z_{2}} \\
\end{align}
$
---
#### Extract Denominator
$
\begin{align}
u &= - y_{1} z_{2} + y_{2} z_{1} \\
v &= - x_{1} z_{2} + x_{2} z_{1} \\
x_3 &= u^{2} v z_{1} z_{2} - v^{3} x_{1} z_{2} - v^{3} x_{2} z_{1} \\
y_3 &= u \left(- u^{2} z_{1} z_{2} + 2 v^{2} x_{1} z_{2} + v^{2} x_{2} z_{1}\right) - v^{3} y_{1} z_{2} \\
z_3 &= v^{3} z_{1} z_{2} \\
\end{align}
$
---
#### Sympy
[Example code](https://github.com/doitian/sympy-playground/blob/main/recipes/elliptic-curve-addition/homogeneous-coordinate-adding-distinct-points.py)
---
### Doubling
$
\begin{align}
w &= a z_{1}^{2} + 3 x_{1}^{2} \\
x_3 &= 2 w^{2} y_{1} z_{1} - 16 x_{1} y_{1}^{3} z_{1}^{2} \\
y_3 &= w \left(- w^{2} + 12 x_{1} y_{1}^{2} z_{1}\right) - 8 y_{1}^{4} z_{1}^{2} \\
z_3 &= 8 y_{1}^{3} z_{1}^{3} \\
\end{align}
$
---
### Bn128.G1
```python
print(bn128.G1)
# (x, y, z)
# => (1, 2, 1)
```
---
### Bn128.G1 Demo
- [Homogeneous Addition and Curve Definitions](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/ecc/homogeneous.py)
- [Tests](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/ecc/test_homogeneous_bn128_g1_curve.py)
---
## Extension Field
```python
print(bn128.G2)
# => ((108570...2781, 115597...5634)
# => ,(849565...1930, 408236...3531)
# => ,(1, 0))
```
---
### Motivation
**Extension Field** and **Twist** simplify **Paring**
> [!note]
> See **Twist** in the next chapter.
---
### Definition
> [!important] Definition
> Extension Field is a Finite Field with $p^n$ items, where $p$ is a prime and $n > 1$, denoted as $\mathrm{GF}(p^n)$.
> [!note]
> Also named Galois Extension.
---
### Field Members
$\overline{a_0}_p + \overline{a_1}_{p}x + \ldots + \overline{a_{n-1}}_{p}x^{n-1}$
> [!note]
> The members are polynomial which degree is less than $n$ and coefficients are from $\mathbb{Z}/p\mathbb{Z}$. There are n coefficients, and each has $p$ candidate value, so there are $p^n$ different polynomials.
>
> (**Reference**:: [[Extension Field Arithmetic]])
---
### Addition
$
\begin{align}
&\overline{a_0}_p + \overline{a_1}_{p}x + \ldots + \overline{a_{n-1}}_{p}x^{n-1} \\
+\quad & \overline{b_0}_p + \overline{b_1}_{p}x + \ldots + \overline{b_{n-1}}_{p}x^{n-1} \\
\hline \\
=\quad & (\overline{a_0}_p + \overline{b_0}_p) + (\overline{a_1}_{p} + \overline{b_1}_{p})x + \ldots + (\overline{b_{n-1}}_{p} + \overline{b_{n-1}}_{p})x^{n-1} \\
\end{align}
$
> [!note]
> Addition is defined by adding coefficients at the same degree using [[Modular Arithmetic]].
---
#### Addition Identity
The addition identity is the constant polynomial $\overline{0}_p$.
---
#### Addition Inverse
$
\begin{align}
&-(\overline{a_0}_p + \overline{a_1}_{p}x + \ldots + \overline{a_{n-1}}_{p}x^{n-1}) \\
=\quad &-\overline{a_0}_p + (-\overline{a_1}_{p})x + \ldots + (-\overline{a_{n-1}}_{p})x^{n-1} \\
\end{align}
$
> [!note]
> The addition inverse is the polynomial with modular additive inverse coefficients at each degree.
---
### Multiplication Problem
$x^2 \times x^2 = \mathord{?}$ in $\mathrm{GF(7^3)}$
---
#### Polynomial Product
$
\begin{align}
A &= \overline{a_0}_p + \overline{a_1}_{p}x + \ldots + \overline{a_{n-1}}_{p}x^{n-1} \\
B &= \overline{b_0}_p + \overline{b_1}_{p}x + \ldots + \overline{b_{n-1}}_{p}x^{n-1} \\
A \times B &= \overline{c_0}_p + \overline{c_1}_{p}x + \ldots + \overline{c_{(n-1)(n-1)}}_{p}x^{(n-1)(n-1)} \\
\overline{c_i}_p &= \prod_{\substack{\forall j,k \\ j+k=i}}(\overline{a_j}_p \times \overline{b_k}_p) \\
\end{align}
$
> [!note]
> The trouble for multiplication is that the degree of the polynomial product is larger than or equal to $n$.
---
#### Irreducible Polynomial
> [!important] Definition
> In mathematics, an **irreducible polynomial** is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials (with non-zero degree).
> [!note]
> (**Reference**:: [[Irreducible Polynomial]])
---
#### Irreducible Polynomial for $\mathrm{GF}(p^n)$
Irreducible Polynomial at degree $n$ which coefficients are from $\mathbb{Z}/p\mathbb{Z}$.
---
#### Finding Irreducible Polynomial
- Factor $X^{p^d}-X$
- Search and Test
---
#### Factor $X^{p^d}-X$
```python
from sympy import poly, GF, factor_list
from sympy.abc import x
Z = GF(2, symmetric=False)
y = poly(x**(2**3) - x, domain=Z)
for p in factor_list(y)[1]:
print(p[0].as_expr())
# => x
# => x + 1
# => x**3 + x + 1
# => x**3 + x**2 + 1
```
> [!note]
> Factor and choose any one at the degree n. However, it's too heavy. We only want one irreducible at degree $n$, it returns all irreducible polynomials with degree not larger than $n$.
>
> (**Reference**:: [[Irreducible Polynomial#Factor X p d -X]])
---
#### Search And Field
- Iterate the $p^{n}$ polynomials which degree is $n$ and the largest degree coefficient is $\overline{1}_p$.
- Try to factor it. Return if it is irreducible.
> [!note]
> It is fast in practice.
---
#### Search And Field (Code)
```python
import galois
print(galois.GF(2**3).properties)
# => Galois Field:
# => name: GF(2^3)
# => characteristic: 2
# => degree: 3
# => order: 8
# => irreducible_poly: x^3 + x + 1
# => is_primitive_poly: True
# => primitive_element: x
```
---
### Multiplication
$ A \times B \bmod{P} $
> [!note]
> The extension field multiplication is the reminder of the polynomial product of A and B divided by the irreducible polynomial P.
---
#### Polynomial Quotient and Reminder
$
\begin{array}
{}&3x^5 &+& 4x^3 &+& 6x &+& 5 \\
\div&2x^2 &+& 1 \\
\hline \\
&5x^3
\end{array}
$
---
$
\begin{array}
{}& 3x^5 &+& 4x^3 &+& 6x &+& 5 \\
\div& 2x^2 &+& 1 \\
\hline \\
& 5x^3 \\
\times & 2x^2 &+& 1 \\
\hline \\
& 3x^5 &+& 5x^3 \\
\end{array}
$
---
$
\begin{array}
{}& 3x^5 &+& 4x^3 &+& 6x &+& 5 \\
- & 3x^5 &+& 5x^3 \\
\hline \\
&&&6x^3&+& 6x &+& 5 \\
\end{array}
$
> [!note]
> (**Reference**:: [[Extension Field Arithmetic#Remainder Divided by P]])
---
#### Multiplication Identity
The multiplicative identity is the constant polynomial $\overline{1}_p$.
---
#### Multiplication Inverse
Same as [[#Extended Euclidean Algorithm]] for Integers Modulus Prime
---
> [!important] Extended Euclidean Algorithm for Polynomials
> Notice that the gcd of polynomials is required to be a monic polynomial. Divide result by the leading coefficient of the remainder. See more in the [example code](https://github.com/doitian/ecc-demo/blob/41cb148d5aef5f79059f54cc532e536ef8d3ebe4/ecc_demo/egcd.py#L19).
> [!note]
> (**Reference**:: [[Wikipedia Authors - Extended Euclidean Algorithm (Highlights)#^700420596]])
---
### Elliptic Curve Over Extension Field
![[Elliptic Curve Addition Presentation - Over Extension Field.excalidraw.svg]]
%%[[Elliptic Curve Addition Presentation - Over Extension Field.excalidraw|🖋 Edit in Excalidraw]]%%
> [!note]
> Extension Field is a finite field, so the elliptic curve addition is also defined for extension field. The homogeneous coordinates also work for extension field.
>
> (**Reference**:: [[Elliptic Curve Over Extension Field]])
---
### Bn128.G2
```python
print(bn128.G2)
# => ((108570...2781, 115597...5634)
# => ,(849565...1930, 408236...3531)
# => ,(1, 0))
# x = 108570...2781 + 115597...5634 X
# y = 849565...1930 + 408236...3531 X
# z = 1
```
---
## Twist
Roughly speaking, twist curve is an isomorphic curve.
$
\begin{align}
\forall{P_1, P_2 \in E}& : \phi(P_1) + \phi(P_2) = \phi(P_1 + P_2) \\
\forall{P_1, P_2 \in E'}& : \phi^{-1}(P_1) + \phi^{-1}(P_2) = \phi^{-1}(P_1 + P_2) \\
\end{align}
$
> [!note]
> The two curves have a bi-directional mapping $\phi$, that the addition equation holds after mapping to another curve.
>
> (**Reference**:: [[Elliptic Curve Twist]])
---
### Bn128.G2 Twist
> [!info] Definition
> BN curves always have order 6 twists. If m is an element that is neither a square nor a cube in an extension field $F_{p^2}$, the twist E' of E is defined over an extension field $F_{p^2}$ by the equation $E': y^2 = x^3 + b'$ with b' = b / m or b' = b * m.
---
### TL;DR
- Bn128.G2 Twist does not change curve addition algorithm.
- It affects the algorithm to check whether a point is on the curve.
---
### Bn128.G2 Demo
- [Polynomial Arithmetic](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/poly.py)
- [Extension Field Support](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/field.py)
- [G2 Definition](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/ecc/homogeneous.py)
- [Tests](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/ecc/test_homogeneous_bn128_g2_curve.py)
---
## Elliptic Curve Scalar Multiplication
$sG = \underbrace{G + G + \ldots + G}_{s}$
> [!note]
> When s is an integer, and $G$ is a point in the [[Elliptic Curve]], the scalar multiplication $sG$ is defined as [[Elliptic Curve Addition|adding]] G to itself s times.
>
> (**Reference**:: [[Elliptic Curve Scalar Multiplication]])
---
### Double and Add
$1000G = 512G \oplus 256G \oplus 128G \oplus 64G \oplus 32G \oplus 8G$
> [!note]
> (**Reference**:: [[RareSkills Authors - Elliptic Curve Point Addition (Highlights)]])
---
```python
def scalar_mul(s, g):
if s % 2 == 0:
half = scalar_mul(s / 2, g)
return half + half
elif s == 1:
return g
else:
return g + scalar_mul(s-1, g)
```
---
### That's Why This is Vulnerable
> [!important]
Using different equations to compute $\lambda$ is [[Mike Rosing - Defense Against Power Analysis Attacks Avoiding Elliptic Curve Side Channel Attacks (Highlights)|vulnerable to the side channel attacks]].
---
## Thanks
Q&A