前文再续，书接上一回，上回讲到，SIDH喺2022年就被宣布畀人完全破解咗……
前言
本来没想过写这一篇的，因为本来想着既然都有现成代码了，那用起来应该会很方便吧，但是在NSS上刷题的时候做到CryptoCTF 2023的一道题：[CryptoCTF 2023]Shevid | NSSCTF，其实就是SIDH中已知Alice私钥以及双方公钥来恢复Bob私钥，但是在用GiacomoPope/Castryck-Decru-SageMath: A SageMath implementation of the Castryck-Decru Key Recovery attack on SIDH给出的代码时四处碰壁，所以想着写这篇博客记录一下如何使用这些代码。
对SIDH的破解
有现成代码，原理似乎也不是很重要
大致扫了一眼论文和GitHub项目上的样例代码（baby_SIDH.sage），发现我们要做的似乎其实仅仅是需要构造一个曲线上的自同态\([2i]\)，使得\([2i]\circ[2i]=[-4]\)（实际上就是\(2i\)倍点映射吧，但是sage并不能直接给\(GF(p^2)\)上的点乘上\(2i\)），所以这个过程其实要我们自己写，但是在Github的项目里面其实是有给由方程\(y^2=x^3+6x^2+x\)所定义的椭圆曲线上的\(2i\)倍点映射的算法，而通过阅读论文，我们也可以写出由方程\(y^2=x^3+x\)所定义的椭圆曲线上的\(2i\)倍点映射：\([2i]:(x,y)\mapsto[2](-x,iy)\)（其中\([2]\)为二倍点映射），在论文里面也只讨论了这两种方程定义的曲线。
代码使用实例
在这里通过两个例子来公式化地使用Github项目中给出的代码解决分别由\(y^2=x^3+6x^2+x\)与\(y^2=x^3+x\)定义的曲线上的SIDH：
[CryptoCTF 2023]Shevid
题目给出代码如下：
#!/usr/bin/env sage
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from flag import flag
def gen_param(B):
while True:
a = randint(B >> 1, B)
b = randint(B >> 2, B >> 1)
p = 2**a * 3**b - 1
if is_prime(p):
return a, b
def gen_dmap(E):
return E.isogeny(E.lift_x(ZZ(1)), codomain = E)
def gen_tpt(E, a, b):
P, Q = [((p + 1) // 2**a) * _ for _ in E.gens()]
R, S = [((p + 1) // 3**b) * _ for _ in E.gens()]
return P, Q, R, S
def keygen(EC, b, P, Q, R, S):
skey = randint(1, 3**b)
T = R + skey * S
phi = EC.isogeny(T, algorithm = "factored")
_phi_dom, _phi_P, _phi_Q = phi.codomain(), phi(P), phi(Q)
return skey, _phi_dom, _phi_P, _phi_Q
a, b = gen_param(190)
p = 2**a * 3**b - 1
F.<x> = GF(p^2, modulus = x**2 + 1)
EC = EllipticCurve(F, [0, 6, 0, 1, 0])
P, Q, R, S = gen_tpt(EC, a, b)
print(f'P = {P.xy()}')
print(f'Q = {Q.xy()}')
print(f'R = {R.xy()}')
print(f'S = {S.xy()}')
skey, _phi_dom, _phi_P, _phi_Q = keygen(EC, b, P, Q, R, S)
print(f'_phi_dom = {_phi_dom}')
print(f'_phi_P = {_phi_P.xy()}')
print(f'_phi_Q = {_phi_Q.xy()}')
key = md5(long_to_bytes(skey)).digest()
iv = md5(str(skey).encode()).digest()
cipher = AES.new(key, AES.MODE_CFB, iv=iv)
enc = cipher.encrypt(flag)
print(f'enc = {enc.hex()}')其实就是要我们通过Alice的公开点\(P,Q\)和Bob的公钥\((\phi(E),\phi(P),\phi(Q))\)还原Bob的秘密值\(k_B\)，这里定义的曲线是由\(y^2=x^3+6x^2+x\)所定义的，所以我们可以用public_values_aux.py中的generate_distortion_map函数来计算该曲线上的\([2i]\)，那么可以写出代码如下：
from sage.all import *
from public_values_aux import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
load('castryck_decru_shortcut.sage')
p = ...
Fd.<i> = GF(p^2, modulus=[1, 0, 1])
E = EllipticCurve(Fd, [0, 6, 0, 1, 0])
E.set_order((p+1)^2)
a = 142
b = 69
a2 = 6
a4 = 2070374075904221348548347954672740119972290047985052548426161483408084160515*i+896749506444795652787374405713981306103783874504413776724865996633074195878
a6 = 2497300913991521538985990865799426081199023429830552981773916386651958830387*i+4243320791854592301388975795466391442631117041175807728844738724691845270777
_phi_dom = EllipticCurve(Fd, [0, a2, 0, a4, a6])
_phi_P = _phi_dom(...)
_phi_Q = _phi_dom(...)
P2 = E(...)
Q2 = E(...)
P3 = E(...)
Q3 = E(...)
two_i = generate_distortion_map(E)
check_torsion_points(E, a, b, P2, Q2, P3, Q3)
enc = "..."
recovered_key = CastryckDecruAttack(E, P2, Q2, _phi_dom, _phi_P, _phi_Q, two_i, num_cores=1)
key = md5(long_to_bytes(int(recovered_key))).digest()
iv = md5(str(recovered_key).encode()).digest()
cipher = AES.new(key, AES.MODE_CFB, iv=iv)
flag = cipher.decrypt(bytes.fromhex(enc))
print(flag)注意，这里的P2,Q2,P3,Q3分别对应的是题目代码中的P,Q,R,S，我们可以修改函数CastryckDecruAttack中的num_cores参数可以改变并行进程数，从而提高运行效率，开4个线程运行结果如下图所示： 
一道自制题
找不到\(y^2=x^3+x\)的题目，自己出一道举个例子：
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from Crypto.Util.Padding import pad
flag = b'Aurora{Test_Flag_for_Isogeny_with_y^2=x^3+x}'
def gen_param(B):
while True:
a = randint(B >> 1, B)
b = randint(B >> 2, B >> 1)
p = 2**a * 3**b - 1
if is_prime(p):
return a, b
def gen_tpt(E, a, b):
P, Q = [((p + 1) // 2**a) * _ for _ in E.gens()]
R, S = [((p + 1) // 3**b) * _ for _ in E.gens()]
return P, Q, R, S
def encrypt(shared_key, plaintext):
key = sha256(str(shared_key).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
return cipher.encrypt(pad(plaintext, 16))
a, b = gen_param(64)
p = 2**a * 3**b - 1
F.<i> = GF(p^2, modulus=[1, 0, 1])
E = EllipticCurve(F, [1, 0])
P1, Q1, P2, Q2 = gen_tpt(E, a, b)
print(f"p = {p}")
print(f"a = {a}")
print(f"b = {b}")
print(f"P1 = E{P1.xy()}")
print(f"Q1 = E{Q1.xy()}")
print(f"P2 = E{P2.xy()}")
print(f"Q2 = E{Q2.xy()}")
# Alice
ka = randint(1, 2**a)
RA = P1 + ka * Q1
phiA = E.isogeny(RA, algorithm='factored')
EA = phiA.codomain()
phiA_P2 = phiA(P2)
phiA_Q2 = phiA(Q2)
print(f"EA = {phiA.codomain()}")
print(f"phiA_P2 = EA{phiA_P2.xy()}")
print(f"phiA_Q2 = EA{phiA_Q2.xy()}")
# Bob
kb = randint(1, 3**b)
RB = P2 + kb * Q2
phiB = E.isogeny(RB, algorithm='factored')
EB = phiB.codomain()
phiB_P1 = phiB(P1)
phiB_Q1 = phiB(Q1)
print(f"EB = {phiB.codomain()}")
print(f"phiB_P1 = EB{phiB_P1.xy()}")
print(f"phiB_Q1 = EB{phiB_Q1.xy()}")
RA1 = phiB_P1 + ka * phiB_Q1
shared1 = EB.isogeny(RA1, algorithm='factored').codomain().j_invariant()
RB1 = phiA_P2 + kb * phiA_Q2
shared2 = EA.isogeny(RB1, algorithm='factored').codomain().j_invariant()
assert shared1 == shared2
shared_key = shared1
enc = encrypt(shared_key, flag)
print(f'enc = {enc.hex()}')
"""
p = 69007679864054552199167
a = 41
b = 22
P1 = E(42941883561232695204126*i + 41565179451593292417697, 32012113025288545049970*i + 67447792731782782239107)
Q1 = E(25302850366663243334175*i + 28499745867760697777766, 45519069949265761361669*i + 38091523002955621484376)
P2 = E(64295307603787694858622*i + 23124820300292317471971, 56390657452217097859549*i + 36392449137376185120691)
Q2 = E(5592769293100950710186*i + 10812888045531269729601, 6826865383103204422537*i + 20863179574507545233583)
EA = Elliptic Curve defined by y^2 = x^3 + (55136237696257287853765*i+57833844773073644952221)*x + (52942153600632609877190*i+15361822390228021806871) over Finite Field in i of size 69007679864054552199167^2
phiA_P2 = EA(62489625132170888252802*i + 63808521833396900819332, 49433807014900669675197*i + 38317557157701506341329)
phiA_Q2 = EA(3850966740889085851852*i + 45392830987593111886391, 14326935923982120143676*i + 32443933495898500654626)
EB = Elliptic Curve defined by y^2 = x^3 + (535570609910458761019*i+55847628242608619214131)*x + (52895838204408953951990*i+40402487899485896459107) over Finite Field in i of size 69007679864054552199167^2
phiB_P1 = EB(67880173178064709758833*i + 5128007695857513878729, 67090026125242047708224*i + 36228875668588115708933)
phiB_Q1 = EB(42637972539717898085377*i + 30589197453944790040489, 62900893992599911017947*i + 53504295506770245599626)
enc = c63958e914ecac186888aa578719cc8e21bd3f1df3eba0a36dee5a425e487db180f52502552e19495ca7fdf0071fe8cb
"""可以通过如下代码来获得flag：
from public_values_aux import *
from Crypto.Cipher import AES
from hashlib import sha256
load('castryck_decru_shortcut.sage')
def two_i(P):
E = P.curve()
if P == E(0):
return E(0)
else:
x, y = P.xy()
return 2*E(-x, i*y)
p = 69007679864054552199167
a = 41
b = 22
F.<i> = GF(p^2, modulus=[1, 0, 1])
E = EllipticCurve(F, [1, 0])
P2 = E(42941883561232695204126*i + 41565179451593292417697, 32012113025288545049970*i + 67447792731782782239107)
Q2 = E(25302850366663243334175*i + 28499745867760697777766, 45519069949265761361669*i + 38091523002955621484376)
P3 = E(64295307603787694858622*i + 23124820300292317471971, 56390657452217097859549*i + 36392449137376185120691)
Q3 = E(5592769293100950710186*i + 10812888045531269729601, 6826865383103204422537*i + 20863179574507545233583)
check_torsion_points(E, a, b, P2, Q2, P3, Q3)
EA = EllipticCurve(F, [55136237696257287853765*i+57833844773073644952221, 52942153600632609877190*i+15361822390228021806871])
phiA_P3 = EA(62489625132170888252802*i + 63808521833396900819332, 49433807014900669675197*i + 38317557157701506341329)
phiA_Q3 = EA(3850966740889085851852*i + 45392830987593111886391, 14326935923982120143676*i + 32443933495898500654626)
EB = EllipticCurve(F, [535570609910458761019*i+55847628242608619214131, 52895838204408953951990*i+40402487899485896459107])
phiB_P2 = EB(67880173178064709758833*i + 5128007695857513878729, 67090026125242047708224*i + 36228875668588115708933)
phiB_Q2 = EB(42637972539717898085377*i + 30589197453944790040489, 62900893992599911017947*i + 53504295506770245599626)
enc = "c63958e914ecac186888aa578719cc8e21bd3f1df3eba0a36dee5a425e487db180f52502552e19495ca7fdf0071fe8cb"
kb = CastryckDecruAttack(E, P2, Q2, EB, phiB_P2, phiB_Q2, two_i, num_cores=4)
R = phiA_P3 + kb * phiA_Q3
R._order = 3^b
phi = EA.isogeny(R, algorithm="factored")
shared_key = phi.codomain().j_invariant()
key = sha256(str(shared_key).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(bytes.fromhex(enc))
print(flag)注意，这里的P2,Q2,P3,Q3对应题目代码中的P1,Q1,P2,Q2，运行结果如下：
