本文涉及：抽象代数、非对称密码

在SIDH受攻击后，本文已过时

带*的可略过

SIDH:Supersingular Isogeny Diffie-Hellman

1.超奇异椭圆曲线

1.1.同构

isomorphism

令K为一个域，$\overline{K}$ 为K的代数闭包

定义在K上的两条椭圆曲线在 $\overline{K}$ 中同构当且仅当它们有相同的 j-不变量。

1.2.扭子群

torsion group

该小节建议在看完 2.2 后再回来看

有限域椭圆曲线E的m阶扭子群定义为

$E[m] = ker([m]) = \{ p \in E(\overline{K}) | mP = O\}$

其中 O 为 E 的单位元

E的扭子群

$E_{tors} = \bigcup_{m=1}^{\infty} E[m]$

当 $p \nmid m$ 时，$E[m] \cong (Z/mZ)^2$ ，对于 r ≥ 1 ，$E[p^r]$有两种情况：

(1) $E[p^r] = 0$ 对任意 r 同时成立

(2) $E[p^r] = Z/p^rZ$ 对任意 r 同时成立

1.3.超奇异

supersingular

$q = p^r$ , p为素数，r为正整数

对于有限域 $F_q$ 上的椭圆曲线 E ，若 $E[p^r] = 0$，则称 E 为超奇异(supersingular)的；若 $E[p^r] = Z/p^rZ$ , 则称 E 为正常(ordinary)的

2.同源

2.0.定义

isogeny

isogenous

若 $\phi:E_1 \rightarrow E_2$ 是椭圆曲线间的态射(morphism)且 $\phi(O_{E_1}) = O_{E_2}$，则称 $\phi$ 是椭圆曲线间的同源(isogeny)

同源有两种情况：

(1) $\phi(E_1) = O$ , 此时称为零同源

(2) $\phi(E_1) = E_2$，此时 $K(E_1)$ 是 $K(E_2)$ 的有限扩张，且 $\phi$ 是有限加法满同态，故 $ker(\phi)$ 是有限子群

SIDH仅考虑后者

两条椭圆曲线是同源的(isogenous)，如果存在同源(isogeny) $\phi:E_1 \rightarrow E_2$ 使得 $\phi(E_1) \neq O$

isogenous是等价关系。

Tate定理：

设 $E_1$, $E_2$ 为有限域 $F_q$ 上的椭圆曲线，则存在定义在 $F_q$ 上的同源 $\phi:E_1 \rightarrow E_2$ 当且仅当 $\#E_1(F_q)=\#E_2(F_q)$

然而，给定有限域上的两条椭圆曲线 $E_1,E_2$，满足 $\#E_1(F_q)=\#E_2(F_q)$，找到 $E_1$与 $E_2$ 之间的同源是困难的。我们称该问题为标准的同源计算问题。

某个命题：

令 $\Phi$ 是 $E$ 的一个有限子群，有且仅有一条椭圆曲线 E’ 和一个可分同源(separable isogeny)

$\phi:E \rightarrow E'$ 满足 $ker(\phi) = \Phi$

通常把 $E'$ 记作 $E/\Phi$

这个命题也可以表述为：

令 $\phi:E_1 \rightarrow E_2$ 是一个非零同源，那么

$ker \phi = \phi^{-1}(O)$ 是一个有限群

2.1.自同态环(*)

从 $E_1$ 到 $E_2$ 的所有isogeny的集合定义为

$Hom(E_1,E_2) = \{all\ isogenies :E_1 \rightarrow E_2\}$

令 P 是 $E_1$ 中一点

两个isogenies之间的加法：

$(\phi+\psi)(P) = \phi(P) + \psi(P)$

可以证明$(\phi + \psi) \in Hom(E_1,E_2)$

所以 $Hom(E_1,E_2)$ 成群

特别地

$End(E) = Hom(E,E)$

是E的自同态环

加法如上所述，乘法如下：

$(\phi\psi)(P) = \phi(\psi(P))$

2.2.乘以 m 同源

其实就是椭圆曲线的倍点操作

对每个 $m \in Z$ 定义multiplication-by-m isogeny

$[m]:E \rightarrow E$

如果 m > 0 ，则 $[m](P) = P + P + ... + P$

即m个P相加

如果 m < 0，则 $[m](P) = [-m](-P)$

如果 m = 0 , 定义 $[m](P) = O$

由定义不难推出

[m] 的 kernel 即为 E[m] (E的m阶扭子群)

如果m与q互素，那么

$\#E[m] = m^2 , E[m] \cong (Z/dZ) \times (Z/mZ)$

2.3.Q平移映射 (*)

令 $Q \in E$ ,

translation-by-Q map 定义为

$\tau_Q:E\rightarrow E, \tau_Q(P) = P+Q$

显然 $\tau_Q$ 是一个同构映射，因为 $\tau_{-Q}$ 是它的逆。

除非 Q = O ,否则它不是一个同源

现在任意选取一个态射：

$F:E_1 \rightarrow E_2$

令 $\phi = \tau_{-F(O)} \circ F$

显然 $\phi$ 是一个同源，因为 $\phi(O) = O$

这证明了任何态射 F 都可以表示为一个同源及一个平移的组合：

$F = \tau_{F(O)} \circ \phi$

2.4.同源是一种群同态

令 $\phi:E_1 \rightarrow E_2$ 是一个同源，以下等式恒成立

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

即 $\phi$ 是一种群同态

2.5.可分同源

字面意思，$\phi$ 是可分同源，若存在至少两个非零同源 $g,f$ 使得

$\phi = g \circ f$

具有此性质的同源可以像快速幂一样加快加密时间

一个同源映射要么是可分的，要么是不可分的。

对于可分同源而言，最重要的一个性质是它们与一个有限子群一一对应。

具体而言，对于 $E_1$ 的任意子群 $G$，有且仅有一个同源

$\phi:E_1 \rightarrow E_2$ 的kernel是 G

反之亦然。

在这种情况下，我们通常把 $E_2$ 记作 $E_1/G$

2.6.degree(*)

一个同源的 度 定义为kernel的元素个数。

且恒有如下等式

$deg(\phi \circ \psi)=deg(\phi) \times \deg(\psi)$

正题：SIDH

1.参数选择

取定素数

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

其中 $l_A$, $l_B$ 为素数，f 为与其互素的数(一般取$l_A = 2,l_B=3$ , 且$l_A^{e_A} \approx l_B^{e_B}$)

$e_A,e_B$ 为正整数

$E$ 为 $F_{p^2}$ 上的超奇异椭圆曲线，且

$E[l_A^{e_A}]=\langle P_A,Q_A\rangle ,E[l_B^{e_B}]=\langle P_B,Q_B\rangle$

曲线为Montgomery form，即：

$by^2 = x^3 + ax^2 + x$

公开 $p,E,P_A,P_B,Q_A,Q_B$

2.私钥选择

Alice选择私钥

$a \in \{0,...,l_A^{e_A}-1\}$

构造循环子群

$G_A =\langle P_A+[a]Q_A\rangle$

(这里也可以选择两个整数作为私钥构造$\langle s_AP_A+t_AQ_A\rangle$, 其中 $s_A$,$t_A$ 不都 整除 $l_A^{e_A}$)

计算同源

$\phi_A: E \rightarrow E_A = E/G_A$

同样地，Bob选择私钥

$b \in \{0,...,l_B^{e_B}-1\}$

构造循环子群

$G_B = \langle P_B+[b]Q_B \rangle$

（同理这里也可以选择两个整数作为私钥构造子群）

计算同源

$\phi_B:E \rightarrow E_B = E/G_B$

3.公钥交换

Alice公开

$\{E_A,\phi_A(P_B),\phi_A(Q_B) \}$

Bob公开

$\{E_B,\phi_B(P_A),\phi_B(Q_A) \}$

Alice计算子群

$G_A' = \langle \phi_B(P_A)+[a]\phi_B(Q_A) \rangle$

用这个子群计算同源

$\phi_{BA}:E_B \rightarrow E_{BA} = E_B/G_A'$

同样地，Bob计算

$G_B' = \langle \phi_A(P_B)+[b]\phi_A(Q_B) \rangle$

用这个子群计算同源

$\phi_{AB}:E_A \rightarrow E_{AB} = E_A/G_B'$

$E_{AB}$ 与 $E_{BA}$ 同构，因此有相同的j-不变量

4.安全性与困难问题

其实上面已经提及过了，这里重申一遍：

给定有限域上的两条超奇异椭圆曲线 $E_1,E_2$，找到 $E_1$与 $E_2$ 之间的同源是困难的。我们称该问题为标准的超奇异同源计算问题。

SIDH的安全性依赖于计算两个超奇异椭圆曲线间的同源是困难的，Biasse-Jao-Sankar在2014年提出了一个算法，先将在 $F_p^2$ 上的超奇异椭圆曲线通过量子 Grover 算法找到定义在 $F_p$ 上的超奇异椭圆曲线的同源，其时间复杂度是$O(p^{1/4})$ 。而计算定义在 F_p 上的超奇异椭圆曲线的同源的时间复杂度是亚指数的。所以在量子算法下改进从 $F_{p^2}$ 上的超奇异椭圆曲线到定义在 $F_p$ 上的超奇异椭圆曲线的同源的寻找是其中的关键。总之，计算超奇异椭圆曲线同源在量子计算机下的时间复杂度是指数时间。

4.1.DSSI

Decisional Supersingular Isogeny (DSSI) problem

令 $E_A$ 是定义在 $F_{p^2}$下的另一条超奇异椭圆曲线，确定 $E_A$ 是否是 $l_A^{e_A}$-同源于 $E$

4.2.CSSI

Computational Supersingular Isogeny (CSSI) problem

令 $\phi_A:E \rightarrow E_A$ 是kernel为 $<[m_A]P_A+[n_A]Q_A>$ 的同源，其中 $m_A,n_A \in Z/l_A^{e_A}Z$ 且不都被 $l_A$ 整除，给定 $E_A$ 和 $\phi_A(P_B), \phi_B(P_A)$ ，找到 $<[m_A]P_A+[n_A]Q_A>$ 的生成元 $R_A$

需要注意的是，给定生成元 $R_A = [m_A]P_A+[n_A]Q_A$ , 求出 $(m_A,n_A)$ 是容易的，因为 $E$ 的阶光滑以至于求它的扩展离散对数问题是简单的。

4.3.SSCDH

Supersingular Computational Diffie-Hellman problem

令 $\phi_A:E \rightarrow E_A$ 是kernel为 $<[m_A]P_A+[n_A]Q_A>$ 的同源

令 $\phi_B:E \rightarrow E_B$ 是kernel为 $<[m_B]P_B+[n_B]Q_B>$ 的同源

其中 $m_A,n_A \in Z/l_A^{e_A}Z$ 且不都被 $l_A$ 整除

$m_B,n_B \in Z/l_B^{e_B}Z$ 且不都被 $l_B$ 整除

给定 $E_A,E_B,\phi_A(P_B),\phi_A(Q_B),\phi_B (P_A),\phi_B(Q_A)$

找到 $E/<[m_A]P_A+[n_A]Q_A,[m_B]P_B+[n_B]Q_B>$ 的 j-不变量

4.4.SSDDH

Supersingular Decision Diffie-Hellman problem

给定两个元组，以1/2概率随机选取其中一元组，确定该元组是从哪个分布抽取的：

• $(E_A,E_B,\phi_A(P_B),\phi_A(Q_B),\phi_B(P_A),\phi_B(Q_A),E_{AB})$

其中 $E_{AB} \cong E/<[m_A]P_A+[n_A]Q_A,[m_B]P_B+[n_B]Q_B>$

• $(E_A,E_B,\phi_A(P_B),\phi_A(Q_B),\phi_B(P_A),\phi_B(Q_A),E_{C})$

  
  

其中 $E_C \cong E/<[m'_A]P_A+[n'_A]Q_A,[m'_B]P_B+[n'_B]Q_B>$

$m'_A,n'_A(m'_B,n'_B)$ 与 $m_A,n_A(m_B,n_B)$ 的选择方式相同

4.5.规约

如果存在 CSSI(SSCDH) 问题的解决方法, 那么 SSCDH(SSDDH) 问题就很容易解决. 如果存在 DSSI 问题的解决方法, 那么 SSDDH 问题也很容易解决. 这是目前知道的归约.

DLC：图论相关(*)

其实SIDH算法的机密性和可用性与所谓的“同源图”有关，但笔者还没学到位，暂时更不了

可移步至：

Trusted Setup with Isogenies - Maria Corte-Real Santos (mariascrs.com)

一个可视化的网站：

Isogeny Explorer - Isogeny Database (enricflorit.com)

Sage代码展示

这里的代码搬运自 bintou的博客 ，有极少量的修改

更详细的工程研究请移步超奇异椭圆曲线同源密钥协商工程研究

0.参数设置

#选取一条在素域k上的超奇异椭圆曲线，这里f = 1
lA, lB = 2, 3
eA, eB = 6, 7
p = lA ^ eA * lB ^ eB - 1
assert p.is_prime()
assert p % 4 == 3
k = GF(p) # 注意，这里并不是标准做法，只是因为Sage的局限不得已;
E = EllipticCurve(k, [1, 0]) #选取曲线
E
E.is_supersingular() # 看看所生成的曲线是否超奇异.
E.j_invariant()

#选取四个随机点作为公共参数
points = []
while len(points) != 4:
    p = E.random_point()
    if p not in points:
        points.append(p)
PA, PB, QA, QB = points
PA, PB, QA, QB

1.Alice的操作

#Alice选择两个随机数并计算自己的秘密值RA
#RA定义了phi_A的kernel
sA, tA = 123, 525
RA = sA * PA + tA * QA
print(RA)

#phiA就是同源也是群同态
phiA = E.isogeny(RA)

#Alice的公共信息EA
EA = phiA.codomain()
print(E.is_isogenous(EA)) # 确认EA与E同源.

#Alice发送以下值给Bob
EA, phiA_PB, phiA_QB = EA, phiA(PB), phiA(QB)
EA, phiA_PB, phiA_QB

2.Bob的操作

#Bob的工作类似
sB, tB = 812, 580
RB = sB * PB + tB * QB
print(RB)

# phiB就是从E到EB同态映射,Kernel是RB
phiB = E.isogeny(RB)
print(phiB)
EB = phiB.codomain()
print(EB)
print(E.is_isogenous(EB))

# Bob发送以下信息给Alice:
EB, phiB_PA, phiB_QA = EB, phiB(PA), phiB(QA)
EB, phiB_PA, phiB_QA

3.秘密值计算

# Alice计算秘密值
R_BA = sA * phiB_PA + tA * phiB_QA
print(R_BA)
phiBA = EB.isogeny(R_BA)
print(phiBA)
KA = phiBA.codomain().j_invariant()

# Bob计算秘密值
R_AB = sB * phiA_PB + tB * phiA_QB
print(R_AB)
phiAB = EA.isogeny(R_AB)
print(phiAB)
KB = phiAB.codomain().j_invariant()

#测试秘密值是否相等
if KA == KB:
    print("Success!")

参考

[1] 后量子安全密钥交换协议SIDH简介 | Bintou’s Blog

[2] The Arithmetic of Elliptic Curves

[3] TOWARDS QUANTUM-RESISTANT CRYPTOSYSTEMS FROM SUPERSINGULAR ELLIPTIC CURVE ISOGENIES

[4] A Friendly Introduction to Supersingular Isogeny Diffie-Hellman

[5] Isogenies for Cryptography - Maria Corte-Real Santos (mariascrs.com)

[6] SIDH - Maria Corte-Real Santos (mariascrs.com)