Isogenies

Isognies

(Warning: This is just a brief note, so it may have some errors. )

Introduction to Isogenies

Let $E_1,E_2$ be the elliptic curves over a finite field ${\mathbb{F}}_q$. Here $q$ is some prime power. As far as we known, $(E_1,+)$ form a group under the addition of points and as $F_q$ is finite, so are these groups.
So now we want to consider a map between these two elliptic curves:

$$\varphi :E_1\to E_2$$

What do we actually mean by this? To define such a map, we need to understand or provide an explicit formula describing the structure of these two curves.
We also wonder what properties should this map have for it to “behave well” in both the geometric and algebraic sense?

• $\varphi$ acts on points on the EC, which have an $x$ and a $y$ coordinate. So we can write $\varphi =({\varphi }_1,{\varphi }_2)$, which acts on a point $P=(x,y)$ on $E_1$ in the following way:

$$\varphi (P)=\varphi ((x,y))=({\varphi }_1(x),{\varphi }_2(y))$$

• We want this map to be rational. By this we mean that if $\varphi =({\varphi }_1,{\varphi }_2)$ then ${\varphi }_1$ and ${\varphi }_2$ are just algebraic fractions where the denominator and numerator are polynomials. For example

$$\frac{x^3+4x+1}{2x+5}$$

• We want $\varphi$ to have this property, because it is a well known fact in maths that a rational map is either surjective or constant. Though this may not seem important, once we define a few more properties and start looking at isogenies, this becomes really useful.
• As both $E_1$ and $E_2$ form groups, ideally we would like $\varphi$ to be a group homomorphism. Intuitively, this means that $\varphi$ will preserver the group structure. Mathematically, if $+$ is the group operation on $E$, and $P,Q$ are two points on $E_1$ then:

$$\varphi (P+Q)=\varphi (P)+\varphi (Q)$$

Review:
Rational map A rational map from a variety $X$ to a variety $Y$ (over a field $K$) is a map that can be expressed using ratios of polynomials in the coordinates of $X$.
Formally:

$$\varphi :X\to Y$$

is a rational map if, for each coordinate function of $Y$, there exist a polynomial numerator and denominator in the coordinates of $X$ such that

$${\varphi }_i(x_1,x_2,...,x_n)=\frac{f_i(x_1,x_2,...,x_n)}{g_i(x_1,x_2,...,x_n)}$$

for $i=1,...,\dim Y$ and $f_i,g_i\in K[x_1,x_2,...,x_n]$

You can read more from here: https://en.wikipedia.org/wiki/Rational_mapping
For example: A rational map $\varphi :E_1\to E_2$ could be

$$\varphi (x,y)=({\varphi }_1(x),{\varphi }_2(y))=(\frac{x^2+1}{x-2},\frac{y(x+3)}{x^2-1})$$

Definition 1. A rational map $\varphi :E_1\to E_2$ is called an isogeny if $\varphi ({\mathcal{O}}_1)={\mathcal{O}}_2$ where ${\mathcal{O}}_i$ is the identity of the group $E_i$.
A famous example of an isogeny when we’re working over a finite field ${\mathbb{F}}_q$ is the Frobenius Map. If $P=(x,y)$, this map is given by

$$\varphi (P)=(x^q,y^q)$$

Rational functions

Let $E(K)$ be an elliptic curve with equation $f(X,Y)=0$. Take a polynomial $g(X,Y)$ and consider its behavior on the points of $E(K)$ only, ignoring its behaviour on all other values of $X$ and $Y$.
If $g=f$ then from our point of view, $g$ is the same as the zero function because $g(P)=0$ for any point $P$ on the curve. Then by Hilbert’s Nullstellensatz theorem, a polynomial $g$ is the zero function if and only if it is a multiple of $f$.
This leads us to define the ring of regular functions of $E$ to be

$$\begin{array}{c}K[E]=K[X,Y]/⟨f⟩\end{array}$$

Its field of fractions $K[E]$ is called the field of rational functions of $E$.

Note: There are two version of Hilbert’s Nullstellensatz theorem, you can look it up on any algebraic geometry textbook

Let $F$ be a algebraically closed field, $x^d=(x_1,...,x_d)\in F^d$ and $P_1,...,P_m\in F[x]$ are polynomials in $d$ variables.

Weak nullstellensatz. Let $P_1,...,P_m\in F[x]$ be polynomials, here $F$ is a algebraically closed field. Then exactly one of the following statements hold:

1. The system of equations $P_1(x)=...=P_m(x)=0$ has a solution $x\in F^d$
2. There exist polynomials $Q_1,...,Q_m\in F[x]$ such that $Q_1{P}_1+...+Q_m{P}_m=1$.

Strong nullstellensatz. Same stament as above, but here we consider another polynomial $R\in F[x]$. Then exactly one of the following statements hold:

1. The system of equations $P_1(x)=...=P_m(x)=0,R(x)\ne 0$ has a solution $x\in F^d$
2. There exist polynomials $Q_1,...,Q_m\in F[x]$ and a non negative integer $r$ such that $P_1{Q}_1+...+P_m{Q}_m=R^r$.

Endomorphisms

Definition: If $E_1=E_2$ then $\varphi$ is called an endomorphism.
An endomorphism is an isomorphism if it is bijective. Review that $\varphi$ is either the identity or surjective, so we only need to check if $\varphi$ is injective.
An injective function is a function $f$ that map distinct elements of its domain to distinct elements of its codomain; that is, for $x1\ne x2$ implies $f(x_1)\ne f(x_2)$.
The set of endomorphisms of an elliptic curve $E$ together with the zero map (the map that sends everything to zero) actually forms a ring under the operations of pointwise addition and multiplication given by composing the endomorphisms $(f\times g)=f(g(x)))$ .
A ring means that the addition and multiplication behave nicely and interact well with each other. I will write this down again for archival purpose:
Ring. A ring is an algebraic structure consisting of a set with two binary operations called addition and multiplication. Also:

• it is a group under the addition
• the multiplication is associative and has an identity
• multiplication is distributive with respect to addition
  We denote this ring by $End(E)$.
  The zero map act as an additive identity and the identity map $id:P\to P$ is the multiplicative identity.
  For example we can consider the endomorphisms $f(P)=2P$ and $g(P)=3P$ for $P\in E$. Then we have their pointwise addition as follow:

$$(f+g)(P)=f(P)+g(P)=(2P)+(3P)=5P$$

Frobenius endomorphism

j - invariant

Usually we write the Weierstrass equation for our elliptic curve using non-homogeneous coordinates $x=X/Z$, and $y=Y/Z$

$$E:y^2+a_{1}xy+a_{3}y=x^3+a_2{x}^2+a_{4}x+a_6,$$

and point $O=[0,1,0]$ out at infinity. If $a_1,...,a_6\in K$ then $E$ is said to be defined over $K$.
If $char(\overline{K})\ne 2$, then we can simplify the equation by completing the square. Thus the substitution

$$y\mapsto \frac{1}{2}(y-a_{1}x-a_3)$$

gives an equation of the form

$$E:y^2=4x^3+b_2{x}^2+2b_{4}x+b_6$$

where

$$b_2=a_1^2+4a_4,b_4=2a_4+a_1{a}_3,b_6=a_3^2+4a_6$$

We also define quantities

$$\begin{array}{l}{b}_8=a_1^2{a}_6+4a_2{a}_6-a_1{a}_3{a}_4+a_2{a}_3^2-a_4^2,\\ c_4=b_2^2-24b_4,\\ c_6=-b_2^3+36b_2{b}_4-216b_6,\\ \Delta =-b_2^2{b}_8-8b_4^3-27b_6^2+9b_2{b}_4{b}_6\\ j=c_4^3/\Delta \end{array}$$

The quantity $\Delta$ is the discriminant of the Weierstrass equation, the quantity $j$ is the $j$ - invariant of the elliptic curve.
The $j$ - invariant help us to keep track the isomorphic class of an given elliptic curve. Two elliptic curves might have very different Weierstrass equation but if their $j$ - invariant are the same, they are isomorphic ( over the algebraic closure of $K$; that is, $\overline{K}$).
For Weierstrass equation $y^2=x^3+ax+b$ with char $\ne$ 2,3, the $j$ - invariant is equal to

$$j(E)=1728\times \frac{4a^3}{4a^3+27b^2}$$

More precisely, we consider the equivalence classes of elliptic curves, where $E_1$ and $E_2$ are equivalent if and only if they are isomorphic.
Theorem Let $E$ and $E^{\prime }$ be elliptic curves over $\mathbb{Q}$. The $E\cong E^{\prime }$ over $\mathbb{C}$ if and only if $j(E)=j(E^{\prime })$. In general, given a field $K$ and elliptic curves $E,E^{\prime }$ over $K$ then $E\cong E^{\prime }$ over $\overline{K}$ if and only if $j(E)=j(E^{\prime })$.
Equality of $j$ - invariants does not guarantee an isomorphism over ${\mathbb{F}}_q$. Curves with same $j$ can be twists of each other.
Example: Consider the quadratic twists of a given curve. We will work with the elliptic curves $E:y^2=x^3+x$ over ${\mathbb{F}}_5$. The quadratic twists of $E$ is define as follow: here
Consider a quadratic nonresidue $d$ of ${\mathbb{F}}_5$. That is, choose an element $d$ such that $d\in {\mathbb{F}}_p$ but $\sqrt{d}\in \overline{{\mathbb{F}}_p}$ , i.e the algebraic closure of our field.
Then we can define another curve with the same $j$ - invariant as $E$:

$$E^{\prime }:d{y}^2=x^3+x\to y^2=x^3+x{d}^{-2}$$

And we have

$$E^{\prime }:y^2=x^3+2x$$

We can calculate the $j$ - invariant by sagemath

sage: F = GF(5)
sage: E = EllipticCurve(F,[1,0])
sage: print(E)
Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 5
sage: E_ = EllipticCurve(F, [2,0])
sage: print(E.j_invariant())
3
sage: print(E_.j_invariant())
3
sage:

Degree and separability

We have the following definition:
Degree of map: Let $\varphi :E_1\to E_2$ be a map of curves defined over $K$. If $\varphi$ is constant, we define the degree of $\varphi$ to be 0. Otherwise we say that $\varphi$ is a finite map and we define its degree to be

$$\mathrm{deg}\varphi =[K(E_1):{\varphi }^{\ast }K(E_2)]$$

We say that $\varphi$ is separable, inseparable, or purely inseparable if the field extension $K(E_1)/{\varphi }^{\ast }K(E_2)$ has the corresponding property, and we the separable and inseparable degrees of the extension by ${\mathrm{deg}}_s\varphi$ and ${\mathrm{deg}}_i\varphi$ .
Let make it more clear. We have known that every non-zero isogeny $\varphi :E_1\to E_2$ between elliptic curves of the form $y^2=f(x)$ can be written in the standard affine form

$$\varphi (x,y)=\left(\frac{u(x)}{v(x)},\frac{s(x)}{t(x)}y\right)$$

where $u\perp v$ and $s\perp t$ are pairs of relatively prime polynomials in $K[x]$
The degree of this map is actually equal to $\max \{\mathrm{deg}p,\mathrm{deg}q\}$ . The isogeny $\varphi$ is separable if we have $(u/v{)}^{\prime }\ne 0$ where $(u/v{)}^{\prime }$ denote the derivatives of rational function.
For example, consider the isogeny that map $P\to 2P$ as follow:

$$\left(\frac{x^4-2A{x}^2-8Bx+A^2}{4(x^3-Ax+B)},\frac{s(x)}{t(x)}y\right)$$

This is a map of degree 4 and is separable. So basically the degree of a non-zero separable isogeny is the number of elements in its kernel and it is also the degree of the isogeny as a rational map
For more details you should read this lecture notes. (i think i will skip this since the maths is too intense lol)

Another important key fact is that the finite subgroups $G\subset E_1$ are in one-to-one correspondence with the separable isogenies $\varphi :E_1\to E_2$, up to isomorphism of the codomain.
That is

$$G\leftrightarrow \varphi :E_1\to E_1/G$$

where $E_1/G$ is the quotient elliptic curve and $\ker (\varphi )=G$.
Knowing the kernel, one can write down the isogeny explicitly base on the fact that each kernel uniquely define the map. We will later learn how to calculate this by using Velu’s formula

Isomorphisms are actually a special case of an isogeny where the kernel is trivial, in this case, the kernel is just $\{\mathcal{O}\}$

Isomorphisms vs isogenies

We know that if $\varphi :E_1\to E_2$ is an isomorphism then there is an inverse map ${\varphi }^{-1}:E_2\to E_1$ and their compose map gives us the identity map. Recall that an isogeny is a group homomorphism between two curves that map the identity on $E_1$ to the identity on $E_2$. So in general, there is no guarantee of invertibility because $\varphi$ usually has a nontrivial kernel.
However, every isogeny $\varphi$ has a unique dual isogeny which we denote as $\hat{\varphi }$ . Rather than composing to give the identity, if $\varphi :E_1\to E_2$ is an isogeny of degree $d$, then $\hat{\varphi }$ is an isogeny of degree $d$ and the composition gives us $\varphi \circ \hat{\varphi }=[d]$ where $[d]:E_1\to E_2$ is the multiplication by $d$ map.

$$[d](P)=\underset{dtimes}{\underbrace{P+P+...+P}}$$

Torsion Points

The group of all points $P$ on $E_1$ such that $[d]P=\mathcal{O}$ is denoted by $E_1[d]$ and are called the $d$-torsion points. In other words, these are the points that are in the kernel of the multiplication by $d$ map.

Theorem. Let $E/k$ be an elliptic curve and $d$ a non zero integer. If $char(k)=p>0$, factor $d$ as $m\times p^r$ with $m\notin p\mathbb{Z}$, otherwise, let $m=d$. Then as groups:

$$\begin{array}{c}E[d]\cong \mathbb{Z}/m\times \mathbb{Z}/d\text{or}E[d]\cong \mathbb{Z}/m\times \mathbb{Z}/m\end{array}$$

In particular $E[p]\cong \mathbb{Z}/p$ or $E[p]\cong \{0\}$ and if $char(k)\nmid d$ then $E[d]\cong \mathbb{Z}/d\times \mathbb{Z}/d$.

This come from the fact that every finitely generated abelian groups classify as products of cyclic groups.
Furthermore we have $\#E[d]=d^2$
You can also read this notes for further research https://www.math.uchicago.edu/~may/VIGRE/VIGRE2008/REUPapers/Travis.pdf
For an elliptic curve over $\mathbb{C}$, it can be written as a torus

$$E(\mathbb{C})\cong \mathbb{C}/\Lambda$$

The map $[d]$ corresponds to scaling by $d$ which gives us

$$z\to dz\mathrm{mod}\Lambda$$

The kernel is actually the lattice points $\frac{1}{d}\Lambda /\Lambda$ which forms a grid of size $d^2$. That’s why we always get $d^2$ torsion points.

Divisor and division polynomials

The divisor of a curve $E$ denote by $div(E)$ is the free abelian group generated by the points of $E$. Thus a divisor $D\in div(E)$ is a formal sum:

$$\begin{array}{c}D=\sum _{P\in E}{n}_p(P)\end{array}$$

where $n_p\in \mathbb{Z}$ and $n_p=0$ for all but finitely many $P\in E$. The degree of $D$ is defined by

$$\begin{array}{c}\mathrm{deg}D=\sum _{P\in E}{n}_p\end{array}$$

For example we have $D=2[P]-[Q]+[R]$ then the degree of $D$ will be $2-1+1=2$.

For more detail see here: https://crypto.stanford.edu/pbc/notes/elliptic/funcfield.html

Division polynomials are built from divisors of multiplication maps, and they encode torsion points. They also provide a way to calculate multiples of points on elliptic curves.
Definition (see also exercise 3.7 in silverman boook for a more generic formula)
Let $E:y^2=x^3+Ax+B$ be an elliptic curve over some field $K$ . The set of division polynomials is a sequence of polynomials in $\mathbb{Z}[x,y,A,B]$ that is recursively defined by

$$\begin{array}{c}{\psi }_0=0\\ {\psi }_1=1\\ {\psi }_2=2y\\ {\psi }_3=3x^4+6A{x}^2+12Bx-A^2\\ {\psi }_4=4y\left(x^6+5A{x}^4+20B{x}^3-5A^2{x}^2-4ABx-8B^2-A^3\right)\end{array}$$

and then inductively by the formulas

$$\begin{array}{c}{\psi }_{2m+1}={\psi }_{m+2}{\psi }_m^3-{\psi }_{m-1}{\psi }_{m+1}^3,m⩾2\\ {\psi }_2{\psi }_{2m}={\psi }_{m-1}^2{\psi }_m{\psi }_{m+2}-{\psi }_{m-2}{\psi }_m{\psi }_{m+1}^2,m⩾3\end{array}$$

${\psi }_{2m}$ is also a polynomial for all $m⩾1$, and then define further polynomials ${\varphi }_m$ and ${\omega }_m$ by

$$\begin{array}{c}{\varphi }_m=x{\psi }_m^2-{\psi }_{m+1}{\psi }_{m-1}\\ 4y{\omega }_m={\psi }_{m-1}^2{\psi }_{m+2}+{\psi }_{m-2}{\psi }_{m+1}^2\end{array}$$

Given a point $P=(x_p,y_p)$ on the elliptic curve $E:y^2=x^3+Ax+B$ over some field $K$, we can express the coordinates for the $n^{th}$ multiple of $P$ in terms of division polynomials:

$$\begin{array}{c}nP=\left(\frac{{\varphi }_n(x)}{{\psi }_n^2(x)},\frac{{\omega }_n(x,y)}{{\psi }_n^3(x,y)}\right)=\left(x-\frac{{\psi }_{n-1}{\psi }_{n+1}}{{\psi }_n^2(x)},\frac{{\psi }_{2n}(x,y)}{2{\psi }_n^4(x)}\right)\end{array}$$

In sage, we can use E.division_polynomial(k) to call the $k^{th}$ division polynomial

sage: E = EllipticCurve(GF(101),[2,3])
sage: print(E.division_polynomial(5))
5*x^12 + 23*x^10 + 29*x^9 + 85*x^8 + 26*x^7 + 86*x^6 + 31*x^5 + 2*x^4 + 27*x^3 + 62*x^2 + 30*x + 52

Read more: Docs
Another method to call is E.multiplication_by_m(k).

Practice

https://cryptohack.org/challenges/isogenies/

Image Point Arithmetic

For this challenge we can applied the property $\varphi (P)+\varphi (Q)=\varphi (P+Q)$ since the isomorphism preserves the group structure

from sage.all import *
p=63079
Px = 48622
Py = 27709
Qx = 9460
Qy = 13819
a = (((Py**2-Qy**2)-(Px**3-Qx**3))*pow(Px-Qx,-1,p)) % p 
b = (Py**2  - Px**3 - a*Px )% p
E = EllipticCurve(GF(p), [a,b])
P = E(Px,Py)
Q = E(Qx,Qy)
print(P+Q)

Montgomery Curves

Here we are given an elliptic curve over $p=1912812599$,

$$E:y^2=x^3+312589632x+654443578$$

There are three solutions to this problem.
The first one we can simply use the function E.montgomery_model(). This should be available in the newest version of sagemath
The second solution can be explained by following the approach in https://eprint.iacr.org/2017/212.pdf. ince the two curves are related by a degree-one isogeny, their $j$-invariants are equal. For Montgomery curves, the $j$-invariant is calculated as follows:

$$j({\mathcal{E}}_{(A,B)})=\frac{256{\left(A^2-3\right)}^3}{A^2-4}$$

from sage.all import *
p = 1912812599
E = EllipticCurve(GF(p),[312589632,654443578])
j = E.j_invariant()
P = PolynomialRing(GF(p),'A')
A = P.gen()
f = 256*(A**2-3)**3-j*(A**2-4)
roots = f.roots(multiplicities = False)
for r in roots:
    r_ = int(r)
    EM = EllipticCurve(GF(p),[0,r_,0,1,0])
    if EM.j_invariant() == j:
        print(r_)

The third solution relies on the two-torsion trick. By mapping a 2-torsion point from the short Weierstrass model to $(0:0:1)$ on the Montgomery model, we can derive the corresponding Montgomery coefficient.

So indeed, the 2-torsion point of $E$ correspond to another 2-torsion point of $E^{\prime }$. We can pick a 2-torsion point of $E$, for example $(r,0)$ and make the translation $x\to X+r$ that send our original curve to its Montgomery form

This guarantees that the chosen torsion point $(r,0)$ in Weierstrass form becomes $(0,0)$ in the new coordinate system.

DLOG on the Surface

Source code:

import os
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad
 
proof.all(False)
 
FLAG = b"crypto{?????????????????????????????????????????????????????????????}"
 
p = 2**127 - 1
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [1,0])
P, Q = E.gens()
 
a = randint(0, p) | 1
b = randint(0, p) | 1
c = randint(0, p) | 1
d = randint(0, p) | 1
 
R = a*P + b*Q
S = c*P + d*Q
 
def encrypt_flag(a, b, c, d):
    data_abcd = str(a) + str(b) + str(c) + str(d)
    key = SHA256.new(data=data_abcd.encode()).digest()[:128]
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ct = cipher.encrypt(pad(FLAG, 16))
 
    return iv.hex(), ct.hex()
 
iv, ct = encrypt_flag(a, b, c, d)
 
print(f"{P = }")
print(f"{Q = }")
print(f"{R = }")
print(f"{S = }")
print()
print(f"{iv = }")
print(f"{ct = }")

In this challenge, we are given four points $P,Q,R,S$ of elliptic curve $E$. The curve is described as follow:

p = 2**127 - 1
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [1,0])
P, Q = E.gens()

Our base field is ${\mathbb{F}}_{p^2}\cong {\mathbb{F}}_p[X]/\left(X^2+1\right)$ and we choose $p\equiv 3\mathrm{mod}4$ so that the polynomial $X^2+1$ has no root and is irreducible.

Moreover, there are relations between our given points:

$$\begin{array}{c}R=aP+bQ\\ S=cP+dQ\end{array}$$

Our goal is to find $a,b,c,d$ and recover the secret key.

Because we are working on supersingular elliptic curves over ${\mathbb{F}}_{p^2}$, the abelian group of points on the curve is isomorphic to $\mathbb{Z}/(p+1)\times \mathbb{Z}/(p+1)$. Every point in $E({\mathbb{F}}_{p^2})$ an be expressed as a combination of two independent generators, in our case, they are $P$ and $Q$. For the torsion subgroup $E[n]$, if $\gcd (n,p)=1$ then $E[n]\cong \mathbb{Z}/n\times \mathbb{Z}/n$.

To solve this challenge I will use the Weil’s pairing. For more details, one should read the section 1.7 and 1.9 from this notes https://yx7.cc/docs/misc/isog_bristol_notes.pdf

The order of our curve is $(p+1{)}^2$ and this is also the order of $P,Q,R,S$.
We will have

$$e(aP+bQ,Q)=e(aP,Q)e(bQ,Q)=e(P,Q{)}^a$$

Since the order is $2^{127}$, solving DLP should be easy. See also the MOV attack / Weil pairing explanation: https://risencrypto.github.io/WeilMOV/

We will do the same for $b,c,d$. Note that $e(P,Q)e(Q,P)=1$.
Solve script:

from sage.all import *
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
p = 2**127 - 1
F = GF(p**2, name='i', modulus=[1,0,1])
i = F.gen()
E = EllipticCurve(F,[1,0])
 
 
P = E(24722427318870186874942502106037863239*i + 62223422355562631021732597235582046928 , 66881667812593541117238448140445071224*i + 149178354082347398743922440593055790802)
Q = E(136066972787979381470429160016223396048*i + 52082760150043245190232762320312239515 , 37290474751398918861353632929218878189*i + 89777436105166947842660822806860901885)
R = E(115434063687215369570994517493754451626*i + 158874018596958922133589852067300239562 , 62259011436032820287439957155108559928*i + 81253318200557694469168638082106161224)
S = E(42595488035799156418773068781330714859*i + 113049342376647649006990912915011269440 , 25404988689109287499485677343768857329*i + 125117346805247292256813555413193592812)
 
iv = '6f5a901b9dc00aded4add3791812883b'
ct = '56ecb68a90cad9787a24a4511720d40d625901577f6d0f1eef9fc34cf042709110cdc061fff91e934877674a30ed911283b83927dbcc270ae358d6b1fe2d5bed18ce1b02d8805de55e5b36deb0d28883'
n = P.order()
base = P.weil_pairing(Q,n)
a = discrete_log(R.weil_pairing(Q,n),base,n)
b = (-discrete_log(R.weil_pairing(P,n),base,n)) % n 
c = discrete_log(S.weil_pairing(Q, n),base,n) 
d = (-discrete_log(S.weil_pairing(P, n),base,n)) % n
key = SHA256.new(f'{a}{b}{c}{d}'.encode()).digest()[:128]
iv = bytes.fromhex('6f5a901b9dc00aded4add3791812883b')
ct = bytes.fromhex('56ecb68a90cad9787a24a4511720d40d625901577f6d0f1eef9fc34cf042709110cdc061fff91e934877674a30ed911283b83927dbcc270ae358d6b1fe2d5bed18ce1b02d8805de55e5b36deb0d28883')
print(AES.new(key, AES.MODE_CBC, iv).decrypt(ct).strip())

You can check whether this curve is supersingular or not by using the function: E.trace_of_frobenius() % p == 0

Note:

Currently im using SageMath version 10.6 so this function should be working. Lets try it.

p = 2**127 - 1
F = GF(p**2, name='i', modulus=[1,0,1])
i = F.gen()
E = EllipticCurve(F,[1,0])
 
 
P = E(24722427318870186874942502106037863239*i + 62223422355562631021732597235582046928 , 66881667812593541117238448140445071224*i + 149178354082347398743922440593055790802)
Q = E(136066972787979381470429160016223396048*i + 52082760150043245190232762320312239515 , 37290474751398918861353632929218878189*i + 89777436105166947842660822806860901885)
R = E(115434063687215369570994517493754451626*i + 158874018596958922133589852067300239562 , 62259011436032820287439957155108559928*i + 81253318200557694469168638082106161224)
S = E(42595488035799156418773068781330714859*i + 113049342376647649006990912915011269440 , 25404988689109287499485677343768857329*i + 125117346805247292256813555413193592812)
n = P.order()
base = P.weil_pairing(Q,n)
a = discrete_log(R.weil_pairing(Q,n),base,n)
b = (-discrete_log(R.weil_pairing(P,n),base,n)) % n 
a_,b_ = E.abelian_group().discrete_log(R,[P,Q])
print(a,b, '\n')
print(a_ % n ,b_ % n ,'\n')

One should also including two generators [P,Q]. Without it the result will be different.
Docs

sage: x = polygen(ZZ, 'x')
sage: F.<t> = GF(1009**2, modulus=x**2+11); E = EllipticCurve(j=F(940))
sage: P, Q = E(900*t + 228, 974*t + 185), E(1007*t + 214, 865*t + 802)
sage: E.abelian_group().discrete_log(123 * P + 777 * Q, [P, Q])
(123, 777)
sage:

SIDH

Now , lets talk about SIDH and Velu’s formula. There are some prequisite topics that need to be mention again.

Supersingular curve

Slide

Theorem. Let $K$ be a field of characteristic $p$, and let $E/K$ be an elliptic curve. For each integer $r\ge 1$, let

$${\varphi }_r:E\to E^{\left(p^r\right)},\widehat{{\varphi }_r}:E^{\left(p^r\right)}\to E$$

be the $p^r$ - power frobenius map and its dual.
Then the following are equivalent:
i/ $E\left[p^r\right]=0$ for one(all) $r⩾1$

ii/ ${\hat{\varphi }}_r$ is purely inseparable for one(all) $r⩾1$

iii/ The map $[p]:E\to E$ is purely inseparable and $j(E)\in {\mathbb{F}}_{p^2}$.

iv/ $End(E)$ is an order in a quaternion algebra

If E has the properties given above, then we say that $E$ is supersingular or that $E$ has hasse invariant 0

Some deeper properties are unnecessary to mention here, however it is important to note that supersingular curves are all define over ${\mathbb{F}}_{p^2}$

SIDH Scheme

At first, I was reading from this paper: https://eprint.iacr.org/2011/506.pdf

The SIDH Scheme revolve around the following commutative diagram

Setup: Fix the finite field ${\mathbb{F}}_q={\mathbb{F}}_{p^2}$, where

$$p=l_A^{e_A}{l}_B^{e_B}f\pm 1$$

In the original SIDH paper, we choose $(l_A,l_B)=(2,3)$ and an integer $f$ is chosen such that $p$ is a prime number.

We want the same security level for Bob and Alice , then we set $l_A^{e_A}\approx l_B^{e_B}=2^{O(\lambda )}$, where $\lambda$ is a security parameter.
Then we choose a random supersingular curve $E$ over ${\mathbb{F}}_q$ such that $E({\mathbb{F}}_q)\cong (\mathbb{Z}/(p\pm 1)\mathbb{Z}{)}^2\supseteq (\mathbb{Z}/l_A^{e_A}\mathbb{Z}{)}^2\oplus (\mathbb{Z}/l_B^{e_B}\mathbb{Z}{)}^2$.

We use isogenies, ${\varphi }_A,{\varphi }_B$ with kernels of order $l_A^{e_A},l_B^{e_B}$, respectively and the following commutative diagram for the SIDH key exchange between Alice and Bob

From the diagram we can see: We first start with an supersingular curve $E=E_0$ over ${\mathbb{F}}_{p^2}$. Alice then choose a subgroup $⟨R_A⟩\subseteq E\left[l_A^{e_A}\right]$, Bob also choose a subgroup $⟨R_B⟩=E\left[l_B^{e_B}\right]$. The two isogenies are ${\varphi }_A:E\to E_A$ and ${\varphi }_B:E\to E_B$. Both paths end up at the same final curve $E_{AB}=E_{BA}=E/⟨R_A,R_B⟩$

The torsion subgroup $E\left[l_A^{e_A}\right]$ will have two torsion bases $P_A,Q_A$. Same for $P_B,Q_B$.

We define the generators as $p{k}^{\text{sidh}}=(g=(E;P_A,Q_A,P_B,Q_B)),e=(l_A,l_B,e_A,e_B))\leftarrow Ge{n}^{\text{sidh}}\left(1^{\lambda }\right)$

The remaining question is: Why does this work?(still dont know why tf this work )

Implement: You can also see this talk by Lorenz Panny

#public
lA, eA, lB, eB = 2, 91, 3, 57
p = lA^eA * lB ^ eB - 1
F.<i> = GF(p^2, modulus=x^2+1)
E0 = EllipticCurve(F, [1, 0])
PA, QA = (lB^eB * G for G in E0.gens())
PB, QB = (lA^eA * G for G in E0.gens())
 
#Alice
privA = randrange(lA^eA)
KA = PA + privA*QA
phiA = E0.isogeny(KA, algorithm="factored")
pubA = (phiA.codomain(), phiA(PB), phiA(QB))
 
#Bob
privB = randrange(lB^eB)
KB = PB + privB*QB
phiB = E0.isogeny(KB, algorithm="factored")
pubB = (phiB.codomain(), phiB(PA), phiB(QA))
 
#Alice 
LA = pubB[1] + privA*pubB[2]
psiA = pubB[0].isogeny(LA, algorithm="factored")
sharedA = psiA.codomain()
 
#Bob
LB = pubA[1] + privB*pubA[2]
psiB = pubA[0].isogeny(LB, algorithm="factored")
sharedB = psiB.codomain()
 
assert sharedA == sharedB
print(sharedA)

Velu’s formula

We have seen that abstractly, isogenies are determined by their kernels. There are some algorithms to compute separable isogenies from their kernel given the following results: Let $E/k$ be an elliptic curve in Weierstrass form, and $G$ a finite subgroup of $E(\overline{k})$. Let $G_{\ne 0}$ denote the set of nonzero points in $G$, which are affine points $Q=(x_Q,y_Q)$.

For all affine points $P=(x_P,y_P)$ in $E(\overline{k})$ and not in $G$ define:

$$\begin{array}{c}\alpha (x_P,y_P):=\left(x_P+\sum _{Q\in G_{\ne 0}}(x_{P+Q}-x_Q),y_P+\sum _{Q\in G_{\ne 0}}(y_{P+Q}-y_Q)\right)\end{array}$$

Here $x_P,y_P$ are variables, $x_Q,y_Q$ are elements of $\overline{k}$ and $x_{P+Q},y_{P+Q}$ are rational functions of $x_P,y_P$ giving coordinates of $P+Q$ in term of $x_P$ and $y_P$.

For $P\notin G$ we have $\alpha (P)=\alpha (P+Q)$ if and only if $Q\in G$ so $\ker \alpha =G$

In general, these formulas are just rational functions of the output mentioned above and the degrees of these functions are the same size as the size of the kernel $G$.

We can see that to evalute Velu’s formula takes $O(|G|)$ operation and the cost is exponential in $\log (\mathrm{deg}(\varphi ))$ where $\varphi$ is the map that map $E\to E/G$ and $P\to \alpha (P)$

In practice, we will use the two following theorems:

Theorem 1. Let $E:y^2=x^3+Ax+B$ be an elliptic curve over $k$ and let $x_0\in \overline{k}$ be a root of $x^3+Ax+B$. Define $t:=3x_0^2+A$ and $w:=x_{0}t$. The rational map

$$\begin{array}{c}\alpha (x,y):=\left(\frac{x_0^2-x_{0}x+t}{x-x_0},\frac{(x-x_0{)}^2-t}{(x-x_0{)}^2}y\right)\end{array}$$

is a separable isogeny from $E$ to $E^{\prime }:y^2=x^3+A^{\prime }x+B^{\prime }$ where $A^{\prime }:=A-5t$ and $B^{\prime }:=B-7w$. The kernel of $\alpha$ is the group of order 2 generated by $(x_0,0)$.

Theorem 2. Let $E:y^2=x^3+Ax+B$ be an elliptic curve over $k$ and let $G$ be a finite subgroup of $E(\overline{k})$ of odd order. For each non zero $Q=(x_Q,y_Q)$ in $G$ define

$$\begin{array}{c}{t}_Q:=3x_Q^2+A,u_Q=2y_Q^2,w_Q=u_Q+t_Q{x}_Q\\ t:=\sum _{Q\in G_{\ne 0}}{t}_Q,w:=\sum _{Q\in G_{\ne 0}}{w}_Q,r(x):=x+\sum _{Q\in G_{\ne 0}}\left(\frac{t_Q}{x-x_Q}+\frac{u_Q}{(x-x_Q{)}^2}\right)\end{array}$$

The rational map

$$\begin{array}{c}\alpha (x,y):=(r(x),r^{\prime }(x)y)\end{array}$$

is a separable isogeny from $E$ to $E^{\prime }:y^2=x^3+A^{\prime }x+B^{\prime }$ where $A^{\prime }:=A-5t$ and $B^{\prime }=B-7w$ with $\ker \alpha =G$.

Practice - 2

Two Isogenies

Using the 2-isogeny formula above and implement it in sage like this:

p = 2**18*3**13-1
F = GF(p**2, names = 'i', modulus = [1,0,1])
i = F.gen()
E = EllipticCurve(F,[1,0])
K = E(i,0)
P.<x> = PolynomialRing(F)
f = x**3+x
roots = f.roots()
print(roots)
A = 1 
B = 0 
for i in range(len(roots)):
    r = roots[i]
    try:
        x0 = r[0]
        t = 3*x0**2 + A 
        w = x0 * t 
        A_ = A - 5*t 
        B_ = B - 7*w
        E2 = EllipticCurve(F,[A_,B_])
        print(E2.j_invariant())
    except Exception as e:
        continue

We can use any roots of the equation above to calculate the isogeny or we can use x0 = K.x() instead.

Note that the j_invariant() of $E$ and $E^{\prime }$ are different because “an isogeny is not an isomorphism”. The j-invariant classifies elliptic curves up to isomorphism, not up to isogeny — so two curves can be isogenous but have different j-invariants.

Newest version of sagemath also give us some useful built-in to work with this:

p = 2**18*3**13-1
F = GF(p**2, names = 'i', modulus = [1,0,1])
i = F.gen()
E = EllipticCurve(F,[1,0])
K = E(i,0)
phi = E.isogeny([K])
print(phi.codomain().j_invariant())

Three Isogenies

We can do the same as the previous challenge

p = 2**18*3**13-1
F = GF(p**2, names = 'i', modulus = [1,0,1])
i = F.gen()
E = EllipticCurve(F,[1,0])
K= E(483728976, 174842350631)
phi = E.isogeny([K,2*K])
print(phi.codomain().j_invariant())

This is easy but lets calculate it using the above formula for isogenies with odd degree.

p = 2**18*3**13-1
F = GF(p**2, names = 'i', modulus = [1,0,1])
i = F.gen()
E = EllipticCurve(F,[1,0])
K= E(483728976, 174842350631)
Kernel = [K,2*K]
A = 1 
B = 0 
# tQ 
tQ = [3*Q.x()**2 + A for Q in Kernel]
t = sum(tQ)
uQ = [2*Q.y()**2 for Q in Kernel]
wQ = [uQ[i]+tQ[i]*Q.x() for i,Q in enumerate(Kernel)]
w = sum(wQ)
A_ = A-5*t 
B_ = B-7*w 
E2 = EllipticCurve(F,[A_,B_])
print(E2.j_invariant())
phi = E.isogeny(Kernel)
print(phi.rational_maps())

Composite Isogenies

For isogenies with composite degree we can calculate it in sage by phi = E.isogeny(K,algorithm = 'factored').
The idea

SIDH Key Exchange

Implement:

# This file was *autogenerated* from the file SIDH.sage
from sage.all_cmdline import *   # import sage library
 
_sage_const_110 = Integer(110); _sage_const_67 = Integer(67); _sage_const_2 = Integer(2); _sage_const_3 = Integer(3); _sage_const_1 = Integer(1); _sage_const_0 = Integer(0); _sage_const_118242575052254473701407051403380184157502700009529430046122822477 = Integer(118242575052254473701407051403380184157502700009529430046122822477); _sage_const_57638278144985143549644316704182130279784191379170896458696787312 = Integer(57638278144985143549644316704182130279784191379170896458696787312); _sage_const_80915735815367072410310689908590367651933218830435520913424043510 = Integer(80915735815367072410310689908590367651933218830435520913424043510); _sage_const_35228327576503752484578273317308597612913304063200715424014549037 = Integer(35228327576503752484578273317308597612913304063200715424014549037); _sage_const_27856673727210297071672501895829918842041821446996051944738115273 = Integer(27856673727210297071672501895829918842041821446996051944738115273); _sage_const_101349537690838191347553037323956940169953967852439843389873653018 = Integer(101349537690838191347553037323956940169953967852439843389873653018); _sage_const_45955772915614774101614751673022340983778200451506382887743008335 = Integer(45955772915614774101614751673022340983778200451506382887743008335); _sage_const_76499786039494489791183573966490259392789635716963920208794989512 = Integer(76499786039494489791183573966490259392789635716963920208794989512); _sage_const_68702305424425607424554396971378391833152415806389206440833676844 = Integer(68702305424425607424554396971378391833152415806389206440833676844); _sage_const_63162905189208938201083385603424075109355856156240516441321158383 = Integer(63162905189208938201083385603424075109355856156240516441321158383); _sage_const_14452401602439328239712793251073780692192036710425129093829067649 = Integer(14452401602439328239712793251073780692192036710425129093829067649); _sage_const_110903430163815016394569999096524527007769669322432532390635606190 = Integer(110903430163815016394569999096524527007769669322432532390635606190); _sage_const_50967992419888058158544483269655763559879646024537212566396940681 = Integer(50967992419888058158544483269655763559879646024537212566396940681); _sage_const_39165103284419354968504615023980382940222714919046676966425620242 = Integer(39165103284419354968504615023980382940222714919046676966425620242); _sage_const_113476160032430656302485251779124302915433268423829474022852380544 = Integer(113476160032430656302485251779124302915433268423829474022852380544); _sage_const_74814862075401178218909769629701747112662266906635780085603780902 = Integer(74814862075401178218909769629701747112662266906635780085603780902); _sage_const_225902606209514408534212339057054 = Integer(225902606209514408534212339057054); _sage_const_38410379124791756271891302485727 = Integer(38410379124791756271891302485727); _sage_const_128 = Integer(128); _sage_const_16 = Integer(16)
import os
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad,unpad
 
FLAG = b"crypto{?????????????????????????????????????}"
 
# Base field
ea, eb = _sage_const_110 , _sage_const_67 
p = _sage_const_2 **ea*_sage_const_3 **eb - _sage_const_1 
F = GF(p**_sage_const_2 , modulus=[_sage_const_1 ,_sage_const_0 ,_sage_const_1 ], names=('i',)); (i,) = F._first_ngens(1)
 
# Public curve
E0 = EllipticCurve(F, [_sage_const_1 ,_sage_const_0 ])
 
# Torsion points
P2 = E0(_sage_const_118242575052254473701407051403380184157502700009529430046122822477 *i + _sage_const_57638278144985143549644316704182130279784191379170896458696787312 , _sage_const_80915735815367072410310689908590367651933218830435520913424043510 *i + _sage_const_35228327576503752484578273317308597612913304063200715424014549037 )
Q2 = E0(_sage_const_27856673727210297071672501895829918842041821446996051944738115273 *i + _sage_const_101349537690838191347553037323956940169953967852439843389873653018 , _sage_const_45955772915614774101614751673022340983778200451506382887743008335 *i + _sage_const_76499786039494489791183573966490259392789635716963920208794989512 )
P3 = E0(_sage_const_68702305424425607424554396971378391833152415806389206440833676844 *i + _sage_const_63162905189208938201083385603424075109355856156240516441321158383 , _sage_const_14452401602439328239712793251073780692192036710425129093829067649 *i + _sage_const_110903430163815016394569999096524527007769669322432532390635606190 )
Q3 = E0(_sage_const_50967992419888058158544483269655763559879646024537212566396940681 *i + _sage_const_39165103284419354968504615023980382940222714919046676966425620242 , _sage_const_113476160032430656302485251779124302915433268423829474022852380544 *i + _sage_const_74814862075401178218909769629701747112662266906635780085603780902 )
 
# Secret Keys
sA = _sage_const_225902606209514408534212339057054 
sB = _sage_const_38410379124791756271891302485727 
 
# TODO
def gen_public_key():
    KA = P2 + sA*Q2
    phiA = E0.isogeny(KA, algorithm = 'factored')
    KB = P3 + sB*Q3
    phiB = E0.isogeny(KB, algorithm = 'factored')
    Alice_pub = [phiA(P3),phiA(Q3)]
    Bob_pub = [phiB(P2),phiB(Q2)]
    EA = phiA.codomain()
    EB = phiB.codomain()
    return Alice_pub, Bob_pub, EA, EB
 
# TODO
def gen_shared_secret():
    Alice_pub, Bob_pub, EA, EB= gen_public_key()
    ker_SA = Bob_pub[_sage_const_0 ] + sA*Bob_pub[_sage_const_1 ]
    phi_SA = EB.isogeny(ker_SA,algorithm='factored')
    ker_SB = Alice_pub[_sage_const_0 ] + sB*Alice_pub[_sage_const_1 ]
    phi_SB = EA.isogeny(ker_SB, algorithm='factored')
    E_SA = phi_SA.codomain()
    E_SB = phi_SB.codomain()
    j_SA = E_SA.j_invariant()
    j_SB = E_SB.j_invariant()
    assert j_SA == j_SB
    return j_SA
# TODO
shared_secret = gen_shared_secret()
s_ = E0.isogeny([P2 + sA * Q2, P3 + sB * Q3], algorithm="factored").codomain().j_invariant()
print(s_)
print(shared_secret)
def encrypt_flag(shared_secret):
    key = SHA256.new(data=str(shared_secret).encode()).digest()[:_sage_const_128 ]
    iv = os.urandom(_sage_const_16 )
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ct = cipher.encrypt(pad(FLAG, _sage_const_16 ))
 
    return iv.hex(), ct.hex()
 
 
def decrypt_flag(shared_secret, iv_hex, ct_hex):
    # build same key
    key = SHA256.new(data=str(shared_secret).encode()).digest()[:_sage_const_128 ]
    iv = bytes.fromhex(iv_hex)
    ct = bytes.fromhex(ct_hex)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    m = cipher.decrypt(ct)
    msg = unpad(m, int(_sage_const_16 ))
    return msg.decode()
 
iv = "05a4cfbce59acb952128af83c9694390"
ct = "755b72b2e3bef2e7a4b2ce4a370f287ad04c1359bace25f3def8be23c0c49e89b4302408ad2dcb02d4875fe58c543d91"
print(decrypt_flag(s_, iv, ct))

Breaking SIDH

Resources

1 Note của anh Giáp
2 Supersingular Isogeny Key Exchange for Beginners
3 Isogeny School Week 3
4 Sage’s Syntax for Isogenies
5 COSIC Mathematical Foundations of Post-Quantum Cryptography
6 Mathematics of Isogeny Based Cryptography
7 Benjamin Wesolowski’s Talk
8 Silverman - AEC
9 Isogenies for Cryptography, Maria’s Blog
10 https://eprint.iacr.org/2011/506.pdf
11 Lorenz Panny’ Thesis
12 https://www.math.auckland.ac.nz/~sgal018/Yi-Fu-Lai-PhD.pdf