isogeny

感觉大家都会同源，就我不会，花了两天的时间对着鸡块blog和huangx607087学习了一下

数学基础

超奇异椭圆曲线

对于有限域 $GF(p^r)$ 下的椭圆曲线 $E$ 其的阶 $O$ 满足 $1\equiv O\mod p$ 那么称 $E$ 为超奇异曲线。

p = 283
E = EllipticCurve(GF(p ^ 2, name="i", modulus=[1, 0, 1]), [1, 0])
print(E.order() % p == 1, E.is_supersingular())
# True True
E = EllipticCurve(GF(p ^ 2, name="i", modulus=[1, 0, 1]), [1, 1])
print(E.order() % p == 1, E.is_supersingular())
# False False

一般来说，超奇异椭圆曲线是在 $GF(p^2)$ 下工作的，所以满足 $p\%4=3$。

j-不变量

对于有限域 $GF(p^r)$ 下的椭圆曲线 $E:y^2=x^3+ax+b$，我们定义其的的j-不变量：

$$j=\frac{1728(4a)^3}{-\Delta}$$

其中 $\Delta=-16(4a^3+27b^2)$，若 $\Delta=0$ 时，该曲线为奇异曲线不存在j-不变量。

from Crypto.Util.number import getPrime

p = getPrime(256)
a = getRandomRange(1, p)
b = getRandomRange(1, p)
E = EllipticCurve(GF(p), [a, b])
j1 = E.j_invariant()
Δ = -16 * (4 * a ^ 3 + 27 * b ^ 2)
j2 = 1728 * (4 * a) ^ 3 * inverse_mod(-Δ, p) % p
assert j1 == j2

如果两条曲线的j-不变量相同，则两条曲线同构，即存在映射:

$$\phi:E_1(x,y)\mapsto E_2(x',y')$$

对于 $GF(418051^2)$ 下的椭圆曲线 $E_1:y^2 = x^3 + x + 1,E_2:y^2 = x^3 + 146258*x + 405280$ 存在映射:

$$\phi:E_1(x,y)\mapsto E_2(-122373x,-206462y)$$

可以使用sage计算

p = 418051
R.<i> = GF(p ^ 2, name="i", modulus=[1, 0, 1])
E1 = EllipticCurve(R, [1, 1])
E2 = EllipticCurve(R, [146258, 405280])
assert E1.j_invariant() == E2.j_invariant()
assert E1.is_isomorphic(E2)
phi = E1.isomorphism_to(E2)
phi.rational_maps()
# (-122373*x, -206462*y)
G = E1.random_point()
E2([-122373*G[0], -206462*G[1]])

而对于任意的p，其上面超奇异椭圆曲线j-不变量的个数为 $\lfloor\frac{p}{12}\rfloor+z$，其中 $z$ 的取值为1,2,3。

下图为当 $p=431$ 时在$GF(p^2)$上超奇异椭圆曲线j-不变量的个数

Montgomery Curve

我们在ECC中常用的曲线形式一般都为 Short Weierstrass curves 即 $y^2=x^3+ax+b$，而 Montgomery Curve 的形式为 $y^2=x^3+Ax^2+x$。对于任意一条 Short Weierstrass curves 都可以映射为 Montgomery Curve。

p = 418051
R.<i> = GF(p ^ 2, name="i", modulus=[1, 0, 1])
E1 = EllipticCurve(R, [1, 1])
E1.montgomery_model()
# Elliptic Curve defined by y^2 = x^3 + 398605*i*x^2 + x over Finite Field in i of size 418051^2

对于 Montgomery Curve 而言其得j-不变量的计算方式为

$$j=\frac{256(A^2-3)^3}{A^2-4}$$

同源

概念

相较于ECC点对点的运算，同源可以相当于两条曲线之前的映射关系，其实前面在里面也已经提到过了。举一个简单的例子，将一条曲线对自己的二倍点进行映射

p = 418051
R.<i> = GF(p ^ 2, name="i", modulus=[1, 0, 1])
E = EllipticCurve(R, [1, 0])
phi = E.scalar_multiplication(2)
print(phi.rational_maps())
# ((x^4 - 2*x^2 + 1)/(4*x^3 + 4*x), (8*x^6*y + 40*x^4*y - 40*x^2*y - 8*y)/(64*x^6 + 128*x^4 + 64*x^2))

可以得到映射为

$$\phi:(x,y)\mapsto \left(\frac{x^{4} - 2 x^{2} + 1}{4 x^{3} + 4 x}, \frac{x^{6} y + 5 x^{4} y - 5 x^{2} y - y}{8 x^{6} + 16 x^{4} + 8 x^{2}}\right)$$

当然，我们可以令 $4 x^{3} + 4 x=0$，可以得到 $[0,i,-i]$​，也就相当于实现了division_points

E(0).division_points(2)
# [(0 : 1 : 0), (0 : 0 : 1), (i : 0 : 1), (418050*i : 0 : 1)]

同样的，其也可以对自己的四倍点进行映射

phi = E.scalar_multiplication(2)
print(phi.rational_maps())
E(0).division_points(4)

可以得到

$$\phi:(x,y)\mapsto \left(\frac{x^{16} - 40 x^{14} + 348 x^{12} + 1000 x^{10} + 1478 x^{8} + 1000 x^{6} + 348 x^{4} - 40 x^{2} + 1}{16 x^{15} + 176 x^{13} + 400 x^{11} - 592 x^{9} - 592 x^{7} + 400 x^{5} + 176 x^{3} + 16 x}, \frac{32 x^{24} y + 2176 x^{22} y - 54208 x^{20} y - 104832 x^{18} y + 208870 x^{16} y + 62991 x^{14} y + 160405 x^{12} y + 62991 x^{10} y + 208870 x^{8} y - 104832 x^{6} y - 54208 x^{4} y + 2176 x^{2} y + 32 y}{2048 x^{24} + 34816 x^{22} + 186368 x^{20} - 198915 x^{18} + 168454 x^{16} + 102918 x^{14} - 102918 x^{12} - 168454 x^{10} + 198915 x^{8} - 186368 x^{6} - 34816 x^{4} - 2048 x^{2}}\right)$$

总的来说，对于阶为 $l$ 的点，我们称为 $l$-torsion。

因此一个可分的同源可以描述为：对于曲线E和其的一个子群 $G$，都可以构造一个以 $G$ 为核的映射 $\phi:E_1(x,y)\mapsto E_2(x',y')$，我们称这个映射为同源，而曲线 $E_2$ 为其的陪域。

sage上的实现

当然，在sage上同源有很好的实现

我们选择 $(350i + 68,0)$ 来计算同源

p = 431
R.<i> = GF(p ^ 2, name="i", modulus=[1, 0, 1])
E = EllipticCurve(R, [0, 161+208*i, 0, 1, 0])
G = E(350*i + 68,0)
phi = E.isogeny(G)
phi.codomain()
# Elliptic Curve defined by y^2 = x^3 + (208*i+161)*x^2 + (343*i+209)*x + (363*i+398) over Finite Field in i of size 431^2
phi.rational_maps()
# ((x^2 + (81*i - 68)*x + (190*i - 214))/(x + (81*i - 68)), (x^2*y + (162*i - 136)*x*y + y)/(x^2 + (162*i - 136)*x + (190*i - 213)))

我们可以注意到同源得到的曲线的j-不变量和原曲线不同，所以同源并不是同构，而同构可以算是同源的一种特殊情况。

性质

一条曲线一个子群只能唯一对应一个同源

同源是同态的，即有 $\phi(P+Q)=\phi(P)+\phi(Q)$

同源是对偶的

同源图

可以发现我们选择的 $(350i + 68,0)$ 是 $2$-torsion 的点，其映射后的j-不变量发生了变换：

$$364i + 304\mapsto 344i + 190$$

而在 $2$-torsion 还有其它的点，我们将其都进行同源的话可以得到如下j-不变量：

$$364i + 304\mapsto 67\\ 364i + 304\mapsto 319$$

而如果我们以E的j-不变量为起点，将映射得到的曲线的j-不变量视为终点。然后持续这么做把所有点的 $2$-torsion 都画出来，就可以得到完整的$2$-torsion 的同源图

而同源是对偶的，所以同源图图也是无向图。

modular polynomial

https://math.mit.edu/~drew/ClassicalModPolys.html

SIDH

算法实现

首先要选取类似如下形式的质数p

$$p=2^{e_a}3^{e_b}-1$$

然后在其二次扩域下定义曲线 $E_0:y^2=x^3+ax^2+x$

Alice在 $E_0$ 中要选择两个阶为 $2^{e_a}$ 的点 $(P_2,Q_2)$，Bob在 $E_0$ 中要选择两个阶为 $3^{e_b}$ 的点 $(P_3,Q_3)$,这些点和 $E_0$ 均为公共参数

只后Alice和Bob要分别选择自己的私钥 $s_A,s_B$

对于公钥生成，Alice需计算 $K_A=P_2+s_AQ_2$，然后计算 $E_0$ 由 $K_A$ 产生的同源 $\phi_A$，计算 $\phi_A(P_3),\phi_A(Q_3)$。公钥为($\phi_A,\phi_A(P_3),\phi_A(Q_3)$)

而Bob则计算 $K_B=P_3+s_BQ_3$，然后计算 $E_0$ 由 $K_B$ 产生的同源 $\phi_B$，计算 $\phi_B(P_2),\phi_B(Q_2)$。公钥为($\phi_B,\phi_B(P_2),\phi_B(Q_2)$)

对于共享密钥，Alice计算$K_{SA}=\phi_B(P_2)+s_A\phi_B(Q_2)$，然后计算 $E_B$ 由 $K_{SA}$ 产生的同源 $\phi_{SA}$，Bob计算$K_{SB}=\phi_A(P_3)+s_B\phi_A(Q_3)$，然后计算 $E_A$ 由 $K_{SB}$ 产生的同源，最后有$j(\phi_{SA})=j(\phi_{SB})$，也就是同源得到的曲线的j-不变量作为共享密钥。

ea, eb = 110, 67
p = 2**ea*3**eb - 1
F.<i> = GF(p**2, modulus=[1,0,1])

E0 = EllipticCurve(F, [1,0])
# public parameters
P2 = E0(118242575052254473701407051403380184157502700009529430046122822477*i + 57638278144985143549644316704182130279784191379170896458696787312, 80915735815367072410310689908590367651933218830435520913424043510*i + 35228327576503752484578273317308597612913304063200715424014549037)
Q2 = E0(27856673727210297071672501895829918842041821446996051944738115273*i + 101349537690838191347553037323956940169953967852439843389873653018, 45955772915614774101614751673022340983778200451506382887743008335*i + 76499786039494489791183573966490259392789635716963920208794989512)
P3 = E0(68702305424425607424554396971378391833152415806389206440833676844*i + 63162905189208938201083385603424075109355856156240516441321158383, 14452401602439328239712793251073780692192036710425129093829067649*i + 110903430163815016394569999096524527007769669322432532390635606190)
Q3 = E0(50967992419888058158544483269655763559879646024537212566396940681*i + 39165103284419354968504615023980382940222714919046676966425620242, 113476160032430656302485251779124302915433268423829474022852380544*i + 74814862075401178218909769629701747112662266906635780085603780902)

# Secret Keys
sA = 225902606209514408534212339057054
sB = 38410379124791756271891302485727

def gen_public_key(P2,Q2,P3,Q3,s):
    KA = P2+s*Q2
    phiA = E0.isogeny(KA,algorithm="factored")
    EA = phiA.codomain()
    return EA,phiA(P3),phiA(Q3)

def gen_shared_secret(EB,pb2,qb2,sA):
    KSA = pb2+sA*qb2
    phiSA =  EB.isogeny(KSA,algorithm="factored")
    return phiSA.codomain().j_invariant()

# public key
EA,pa3,qa3 = gen_public_key(P2,Q2,P3,Q3,sA)
EB,pb2,qb2 = gen_public_key(P3,Q3,P2,Q2,sB)

# shared secret
s1 = gen_shared_secret(EB,pb2,qb2,sA)
s2 = gen_shared_secret(EA,pa3,qa3,sB)
assert s1==s2
s1

attack

SIDH在2022年就已经完蛋了XD

在 Castryck-Decru-SageMath 就有对SIDH的攻击方式