前言最近在 CryptoHack 刷完了整套「Road to CSIDH」系列习题从基础 2 次、3 次素次同源到复合同源、反向扭曲同源完整走完超奇异同源密码前置知识链。很多人刚接触 SIDH/CSIDH 时会被椭圆曲线、有限域、同源、二次扭曲等概念绕晕本文结合 CryptoHack 真实例题用实操 代码拆解核心知识点适合密码学入门同学。本文选取两道代表性题目Special Isogenies5 次同源 Montgomery 转换Backward Isogeny二次扭曲实现反向 3 - 同源兼顾正向同源计算与反向扭曲核心 trick覆盖 CSIDH 最关键底层逻辑。一、基础概念速通1. 椭圆曲线两种标准形式短魏尔斯特拉斯\(y^2 x^3 a_4 x a_6\)题目初始曲线统一为 \(E_0:y^2x^3x \pmod{419}\)对应参数 \(a_41,a_60\)Montgomery 标准形式\(y^2 x^3 A x^2 x\)CSIDH 工程实现几乎全用该形式所有题目 flag 均为系数 A。2. 同源Isogeny同源是两条椭圆曲线间保持群运算的有理映射\(\ell\) 次同源由曲线上任意一个 \(\ell\) 阶点生成。SIDH\(p2^A3^B-1\)存在两组独立 torsion 生成元同源图分支极多CSIDH\(p1\) 仅含互不重复小素因子每条素数 \(\ell\) 只有唯一正向同源边图是单向环想后退必须借助二次扭曲。3. 二次扭曲Quadratic Twist对曲线 \(E:y^2f(x)\)取模 p 的非二次剩余 d扭曲曲线为 \(E^t:y^2d\cdot f(x)\)。 E 与 \(E^t\) 不同构、不同阶但可以借助扭曲曲线实现反向同源一步回退不用走完一整圈环。二、实战例题 1Special Isogenies正向 5 次同源求 Montgomery A题目描述基曲线 \(E_0:y^2x^3x \pmod{419}\)找任意 5 阶点生成 5 次同源将目标曲线转为标准 Montgomery 形式输出系数 A。完整思路有限域 \(\mathbb{F}_{419}\) 构造初始椭圆曲线遍历曲线上所有有理点筛选阶恰好为 5 的非无穷远点以该点为核生成 5 次同源映射得到目标商曲线将魏尔斯特拉斯曲线标准化转换为 Montgomery 形式计算系数 A。转换核心公式设同源后曲线 \(E:y^2x^3axb\)令 \(\alpha\) 是 \(x^3axb0\) 的根二阶点横坐标 \(C3\alpha^2a,\quad A\frac{3\alpha}{C} \pmod{p}\)SageMath 可直接运行代码sagep 419 F GF(p) # 初始曲线 y² x³ x E0 EllipticCurve(F, [0,0,0,1,0]) # 遍历寻找5阶点 five_pt None for pt in E0: if pt.is_zero(): continue if pt.order() 5: five_pt pt break # 计算5次同源 iso E0.isogeny(five_pt) E_target iso.codomain() # 魏尔斯特拉斯转标准Montgomery y²x³A x²x def weier_to_montgomery(Ew, mod): a4 Ew.a4() a6 Ew.a6() R.x GF(mod)[] poly x^3 a4*x a6 alpha poly.roots()[0][0] C (3 * alpha^2 a4) % mod invC inverse_mod(C, mod) A (3 * alpha * invC) % mod return A ans_A weier_to_montgomery(E_target, p) print(Montgomery 系数A, ans_A)关键踩坑点不能直接调用 Sage 内置.montgomery_model()内置函数不会标准化到 x 项系数为 1 的标准 CSIDH 格式遍历点时跳过无穷远点否则会生成平凡恒等同源模运算全程取模 419避免数值溢出。三、实战例题 2Backward Isogeny二次扭曲实现反向 3 - 同源题目核心考点CSIDH 单向同源环无法直接后退想走一步反向 3 - 同源必须借助二次扭曲标准流程 原曲线 \(E \xrightarrow{\text{二次扭曲}} E^t \xrightarrow{\text{正向3-同源}} E^t_{\text{new}} \xrightarrow{\text{再次扭曲}} E_{\text{back}}\) 最终 \(E_{\text{back}}\) 就是原图反向一步的曲线再转换 Montgomery 输出 A。完整代码实现sagep 419 F GF(p) E0 EllipticCurve(F, [0,0,0,1,0]) # 找模p非二次剩余d d 2 while legendre_symbol(d, p) 1: d 1 # 二次扭曲工具函数 def twist_curve(E, d_val, mod): a4 E.a4() a6 E.a6() new_a4 (a4 * d_val) % mod new_a6 (a6 * d_val^3) % mod return EllipticCurve(GF(mod), [0,0,0, new_a4, new_a6]) # 1. 原曲线扭曲得到Et Et twist_curve(E0, d, p) # 2. 扭曲曲线上找3阶点 three_pt None for pt in Et: if pt.is_zero(): continue if pt.order() 3: three_pt pt break # 3. 扭曲曲线正向3次同源 iso_t Et.isogeny(three_pt) Et_target iso_t.codomain() # 4. 再次扭曲还原普通曲线反向一步结果 E_back twist_curve(Et_target, d, p) # 复用上文转换函数得到Montgomery A def weier_to_montgomery(Ew, mod): a4 Ew.a4() a6 Ew.a6() R.x GF(mod)[] poly x^3 a4*x a6 alpha poly.roots()[0][0] C (3 * alpha^2 a4) % mod invC inverse_mod(C, mod) A (3 * alpha * invC) % mod return A flag_A weier_to_montgomery(E_back, p) print(反向3-同源曲线Montgomery系数, flag_A)原理拆解二次剩余判定legendre_symbol判断 d 是否为二次剩余仅非剩余能生成合法扭曲两次扭曲抵消操作先扭曲、同源、再扭曲等价于原图反向一步工程简化技巧x-only 同源无需完整点运算仅判断横坐标 \(x^3Ax^2x\) 是否平方即可区分正向 / 反向。四、SIDH 与 CSIDH 核心差异总结表格特性SIDHCSIDH素数格式\(p2^A3^B-1\)\(p1\) 为小无平方因子素乘积同源图多分支双向图单链单向环无直接后退边反向操作直接反向同源依赖二次扭曲实现后退安全风险存在多项式时间攻击目前无通用亚指数攻击五、学习总结正向素次同源是基础找到对应阶点调用内置isogeny()即可生成商曲线Montgomery 转换是必背公式CSIDH 所有交互都依赖该标准化形式二次扭曲是 CSIDH 灵魂解决单向同源环无法回退的痛点也是 CryptoHack 高频考点实操优先理论很多纯数学推导容易出错用 SageMath 遍历、枚举曲线点验证结果最稳妥。拓展学习建议完整刷完 Road to CSIDH 全系列2-Isogenies、3-Isogenies、复合同源、素幂同源阅读 Craig Costello《A simple and compact algorithm for SIDH with arbitrary degree isogenies》尝试实现 x-only 同源优化省去完整 y 坐标运算大幅提速有限域计算。本文所有代码可直接粘贴至 SageMathCell 在线运行适配 CryptoHack 419 模数基础例题适合密码学竞赛、本科椭圆曲线密码课程作业参考。
Road to CSIDH：超奇异同源密码入门实战
前言最近在 CryptoHack 刷完了整套「Road to CSIDH」系列习题从基础 2 次、3 次素次同源到复合同源、反向扭曲同源完整走完超奇异同源密码前置知识链。很多人刚接触 SIDH/CSIDH 时会被椭圆曲线、有限域、同源、二次扭曲等概念绕晕本文结合 CryptoHack 真实例题用实操 代码拆解核心知识点适合密码学入门同学。本文选取两道代表性题目Special Isogenies5 次同源 Montgomery 转换Backward Isogeny二次扭曲实现反向 3 - 同源兼顾正向同源计算与反向扭曲核心 trick覆盖 CSIDH 最关键底层逻辑。一、基础概念速通1. 椭圆曲线两种标准形式短魏尔斯特拉斯\(y^2 x^3 a_4 x a_6\)题目初始曲线统一为 \(E_0:y^2x^3x \pmod{419}\)对应参数 \(a_41,a_60\)Montgomery 标准形式\(y^2 x^3 A x^2 x\)CSIDH 工程实现几乎全用该形式所有题目 flag 均为系数 A。2. 同源Isogeny同源是两条椭圆曲线间保持群运算的有理映射\(\ell\) 次同源由曲线上任意一个 \(\ell\) 阶点生成。SIDH\(p2^A3^B-1\)存在两组独立 torsion 生成元同源图分支极多CSIDH\(p1\) 仅含互不重复小素因子每条素数 \(\ell\) 只有唯一正向同源边图是单向环想后退必须借助二次扭曲。3. 二次扭曲Quadratic Twist对曲线 \(E:y^2f(x)\)取模 p 的非二次剩余 d扭曲曲线为 \(E^t:y^2d\cdot f(x)\)。 E 与 \(E^t\) 不同构、不同阶但可以借助扭曲曲线实现反向同源一步回退不用走完一整圈环。二、实战例题 1Special Isogenies正向 5 次同源求 Montgomery A题目描述基曲线 \(E_0:y^2x^3x \pmod{419}\)找任意 5 阶点生成 5 次同源将目标曲线转为标准 Montgomery 形式输出系数 A。完整思路有限域 \(\mathbb{F}_{419}\) 构造初始椭圆曲线遍历曲线上所有有理点筛选阶恰好为 5 的非无穷远点以该点为核生成 5 次同源映射得到目标商曲线将魏尔斯特拉斯曲线标准化转换为 Montgomery 形式计算系数 A。转换核心公式设同源后曲线 \(E:y^2x^3axb\)令 \(\alpha\) 是 \(x^3axb0\) 的根二阶点横坐标 \(C3\alpha^2a,\quad A\frac{3\alpha}{C} \pmod{p}\)SageMath 可直接运行代码sagep 419 F GF(p) # 初始曲线 y² x³ x E0 EllipticCurve(F, [0,0,0,1,0]) # 遍历寻找5阶点 five_pt None for pt in E0: if pt.is_zero(): continue if pt.order() 5: five_pt pt break # 计算5次同源 iso E0.isogeny(five_pt) E_target iso.codomain() # 魏尔斯特拉斯转标准Montgomery y²x³A x²x def weier_to_montgomery(Ew, mod): a4 Ew.a4() a6 Ew.a6() R.x GF(mod)[] poly x^3 a4*x a6 alpha poly.roots()[0][0] C (3 * alpha^2 a4) % mod invC inverse_mod(C, mod) A (3 * alpha * invC) % mod return A ans_A weier_to_montgomery(E_target, p) print(Montgomery 系数A, ans_A)关键踩坑点不能直接调用 Sage 内置.montgomery_model()内置函数不会标准化到 x 项系数为 1 的标准 CSIDH 格式遍历点时跳过无穷远点否则会生成平凡恒等同源模运算全程取模 419避免数值溢出。三、实战例题 2Backward Isogeny二次扭曲实现反向 3 - 同源题目核心考点CSIDH 单向同源环无法直接后退想走一步反向 3 - 同源必须借助二次扭曲标准流程 原曲线 \(E \xrightarrow{\text{二次扭曲}} E^t \xrightarrow{\text{正向3-同源}} E^t_{\text{new}} \xrightarrow{\text{再次扭曲}} E_{\text{back}}\) 最终 \(E_{\text{back}}\) 就是原图反向一步的曲线再转换 Montgomery 输出 A。完整代码实现sagep 419 F GF(p) E0 EllipticCurve(F, [0,0,0,1,0]) # 找模p非二次剩余d d 2 while legendre_symbol(d, p) 1: d 1 # 二次扭曲工具函数 def twist_curve(E, d_val, mod): a4 E.a4() a6 E.a6() new_a4 (a4 * d_val) % mod new_a6 (a6 * d_val^3) % mod return EllipticCurve(GF(mod), [0,0,0, new_a4, new_a6]) # 1. 原曲线扭曲得到Et Et twist_curve(E0, d, p) # 2. 扭曲曲线上找3阶点 three_pt None for pt in Et: if pt.is_zero(): continue if pt.order() 3: three_pt pt break # 3. 扭曲曲线正向3次同源 iso_t Et.isogeny(three_pt) Et_target iso_t.codomain() # 4. 再次扭曲还原普通曲线反向一步结果 E_back twist_curve(Et_target, d, p) # 复用上文转换函数得到Montgomery A def weier_to_montgomery(Ew, mod): a4 Ew.a4() a6 Ew.a6() R.x GF(mod)[] poly x^3 a4*x a6 alpha poly.roots()[0][0] C (3 * alpha^2 a4) % mod invC inverse_mod(C, mod) A (3 * alpha * invC) % mod return A flag_A weier_to_montgomery(E_back, p) print(反向3-同源曲线Montgomery系数, flag_A)原理拆解二次剩余判定legendre_symbol判断 d 是否为二次剩余仅非剩余能生成合法扭曲两次扭曲抵消操作先扭曲、同源、再扭曲等价于原图反向一步工程简化技巧x-only 同源无需完整点运算仅判断横坐标 \(x^3Ax^2x\) 是否平方即可区分正向 / 反向。四、SIDH 与 CSIDH 核心差异总结表格特性SIDHCSIDH素数格式\(p2^A3^B-1\)\(p1\) 为小无平方因子素乘积同源图多分支双向图单链单向环无直接后退边反向操作直接反向同源依赖二次扭曲实现后退安全风险存在多项式时间攻击目前无通用亚指数攻击五、学习总结正向素次同源是基础找到对应阶点调用内置isogeny()即可生成商曲线Montgomery 转换是必背公式CSIDH 所有交互都依赖该标准化形式二次扭曲是 CSIDH 灵魂解决单向同源环无法回退的痛点也是 CryptoHack 高频考点实操优先理论很多纯数学推导容易出错用 SageMath 遍历、枚举曲线点验证结果最稳妥。拓展学习建议完整刷完 Road to CSIDH 全系列2-Isogenies、3-Isogenies、复合同源、素幂同源阅读 Craig Costello《A simple and compact algorithm for SIDH with arbitrary degree isogenies》尝试实现 x-only 同源优化省去完整 y 坐标运算大幅提速有限域计算。本文所有代码可直接粘贴至 SageMathCell 在线运行适配 CryptoHack 419 模数基础例题适合密码学竞赛、本科椭圆曲线密码课程作业参考。
