后量子安全秘钥交换协议SIDH简介

引言

超奇异同源Diffie-Hellman (SIDH) 秘钥交换算法是后量子安全密码研究的一大重点。本文简介SIDH的基本思路与构造，为对此后量子安全算法有兴趣的读者展示该算法的一种概貌。阅读本文不需要椭圆曲线知识，但是需要一些简单的群论知识，比如，群、子群、群同态、群同构等。

Diffie-Hellman算法

目前应用最广泛的秘钥交换协议是Diffie-Hellman (DH) 算法，其思路如图所示，任何一本密码学教材都有具体过程的描述，本文不再赘述。如果不懂DH算法，也没必要阅读本文。

一般来说，DH算法中使用的群G可以是Z_p*乘法群，也可以使用椭圆曲线群。DH算法的安全性建立在离散对数问题(DLP)的难解性，该算法不能抗量子攻击也在于DLP有多项式时间的量子算法。因此，在后量子时代，必须使用新的构造。

构造新型Diffie-Hellman算法的思路

构造新算法的思路往往源于对现有算法的高度抽象。DH算法可以抽象为这样一种过程：

Alice的秘密是a，她的计算先做→，得g^a，再做↓，得到g^{ab}。而Bob的秘密是b，他先做↓，再做→。殊途同归，得到g^{ab}。进一步扩展这种思路，我们寻求这样一种群结构，如下图所示：

这是一种抽象描述，但是它表达了一种直观的思路。G是公共参数，Alice的秘密是A，Bob的秘密是B。比如，假想这样的情况，G是一个乘法群，A和B分别是G的正规子群。Alice和Bob如果还是按照上面的做法，都可以计算出商群G/AB，AB理解为A与B的交集 。必须承认，这还不是DH，因为要算出$A \cap B$，就必须有A和B，也就是说Alice和Bob都不能隐藏自己的秘密。不过，数学家的理想就是要构造出这样一幅交换图，且满足以下两种属性：

• 给定G、G/A和B，可以算出G/AB；类似，给定G，G/B和A，可以算出G/AB。
• 给定G、G/A (或G/B)，求A (或B) 是后量子困难性问题，即不存在量子多项式时间算法。

基本上SIDH算法就是满足此要求的一种构造。再次强调，不要被上面的例子误导，这里的G、A、G/A等表达都是抽象结构的符号表达，并没有明确含义。以下的SIDH构造描述就是要给出其相对具体的构造。

SIDH构造的简化版本

SIDH的基本代数结构是超奇异椭圆曲线群E和超奇异同源（Isogeny）$\phi$。基本思路如下图所示：

首先，超奇异椭圆曲线群$E$理解为一个群即可，所谓”超奇异“这个概念可以暂时不理会它，知道要求椭圆曲线满足”超奇异“这个要求是为了安全性即可。其次，构造用到的超奇异同源$\phi : E \mapsto E'$是从群$E$到群$E'$的一种群同态。算法类似DH算法分为以下两个步骤：

• 首先，Alice选取一个点$R_A \in E$，$\langle R_A \rangle$确定了群$E$的一个子群，然后可以计算得到一个从$E$映射到其子群$E_A$的同源 $\phi_A: E \mapsto E_A$，这是Alice的秘密信息。Alice发送公开信息$E_A$给Bob。

• 同样，Bob选择点$R_B\in E$，然后计算得到$\phi_B: E \mapsto E_B$ ，把公开信息$E_B$发送给Alice。

最终Alice算出$E_{BA}$($E/\langle R_B, RA \rangle$ )，Bob算出$E{AB}$ ($E/\langle R_A, R_B \rangle$ )。解释一下，上图中的$E/\langle R_A \rangle$ 和$E/\langle R_B \rangle$)分别是$E_A$和 $E_B$，这样表达是为了与之前的表达一致，其实这里并不是做商群，而是表达说$\phi_A$的Kernel是$\langle R_A \rangle$。目前的科技文献大多使用这种表达。

再解释一下$E_{BA}$是什么。上面说到，$E_A$是曲线群$E$的子群，它由Isogeny $\phi_A$决定，可理解为群同态$\phiA$映射到$E$上的像 (Image)形成的子群。同理，$E{BA}$是Isogeny $\phi{BA}$ 映射到$E$上的子群，而Isogeny $\phi{BA}$ 是由$\langle R_B, RA \rangle$决定的，即Isogeny $\phi{BA}$ 的Kernel是$\langle R_B, R_A \rangle$。

慢着，Alice怎么算出$E_{BA}$ ($E/\langle R_B, R_A \rangle$ )？对，Alice有$E_B$但是并没有$RB$，所以她并不显然能算出$E{BA}$。当然，我们还有很多的问题并没有说清楚，还需要进一步细化解释。如果阅读到这里还基本能跟上思路且还保持兴趣的请看下图。

SIDH构造的细化版本

为了满足Alice在没有Bob的秘密信息的情况下能计算出$E_{BA}$ 的要求，SIDH需要使用更多的参数设计和相关计算。算法增加描述如下：

SIDH参数设计

首先，选择超奇异椭圆曲线$E$作为公开参数。然后Alice随机选择两个元素$P_A, Q_A \in E$，并公开作为自己的公共参数。同样，Bob也随机选择两个元素$ P_B, Q_B \in E$ 并公开。

Alice的操作

• 随机选择两个整数$s_A$和$t_A$作为秘密信息，计算 $R_A = s_A P_A + t_A Q_A\in E$，并由$R_A$计算得到一个从$E$映射到其子群$E_A$的同源 $\phi_A: E \mapsto E_A$，这也是Alice的秘密信息；
• 获取Bob的公开信息，并计算$\phi_A(P_B)$和$\phi_A(Q_B)$，这些是公开信息；
• Alice发送公开信息$E_A$、$\phi_A(P_B)$和$\phi_A(Q_B)$给Bob。

Bob的操作

• 随机选择两个整数$s_B$和$t_B$作为秘密信息，计算$R_B = s_B P_B + t_B Q_B \in E$，并由$R_B$计算得到一个从$E$映射到其子群$E_B$的同源 $\phi_B: E \mapsto E_B$，这也是Bob的秘密信息；
• 获取Alice的公开信息，计算$\phi_B(P_A)$和$\phi_B(Q_A)$，这些是公开信息；
• Bob发送公开信息$E_B$、$\phi_B(P_A)$和$\phi_B(Q_A)$给Alice。

秘密值的计算

Alice计算子群E_{BA} ，方法如下：

• 注意，此时Alice掌握的信息是 $s_A$，$t_A$，$R_A$，$\phi_B(P_A)$ 和 $\phi_B(Q_A)$ ，她想计算得到$\phi_B(R_A)$ 。并且要强调，$\phi_B$ 是一种群同态。
• 于是，利用群同态的属性可计算得到：$\phi_B(R_A) = \phi_B(s_A P_A + t_A Q_A) = s_A \phi_B(P_A) + t_A \phi_B(Q_A)$ 。
• 根据$\phi_B(RA)$ 计算$E{BA}$ 。$E_{BA}$是曲线群$E$ 的子群，是以$\phi_B (RA)$ 为Kernel的群同态映射到$E$上的子群。这个群同态也就是Isogeny，这个Isogeny我们记为 $ \phi{BA}$ 。终于我们明白了什么是$E_{BA}$ ！

类似地，Bob可以计算子群E_{AB} ：

• $\phi_A(R_B) = s_B \phi_A(P_B) + t_B \phi_A(Q_B)$ ；
• 由此可计算得 $E_{AB}$ ；

最后冲顶的一步，计算秘密值。首先要明确，E{BA} 不显然等于 E{AB}！（注：写完这篇博客后发现，原来2020年有文献已经证明了E{BA}等于E{AB}，神奇！）其次，E{BA} 同构于E{AB} 。然后利用同构曲线的一个属性：所有同构曲线的 J-Invariant值相同。于是Alice和Bob分别计算J(E{BA})和 J(E{AB})（即分别计算曲线的J-Invariant），这就是他们共同拥有的秘密。J-Invariant的计算定义可在标准教科书中找到，本文把它视为黑盒子使用。

Sage代码展示SIDH的思路

以下展示在Sage下可运行的SIDH代码片段，通过代码运行让读者强化对以上算法描述的理解。

参数设置

#选取一条在素域k上的超奇异椭圆曲线
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()
print 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

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)

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

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

秘密值计算

# 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 phiB
KB = phiAB.codomain().j_invariant()

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

总结

本文试图对SIDH算法进行最直观的描述，让初具群论知识的从业者对此算法稍有认识。正因为强调直观、直白，自然忽略了其中许多深入的知识，包括：曲线参数的选取，计算同源的具体算法，为什么SIDH可抗量子攻击等。简而言之，本文旨在抛砖引玉，能引起读者兴趣就足够了，其内涵有限，作为”茶余饭后“的聊资很恰当，但绝不是严肃的科技文献。有兴趣者可在eprint等网站获取更多的科技论文进行研究。

##致谢

本文内容插图截取自David Urbanik的文献 。代码源自网络，但是现在已经找不回原网站，抱歉！

--

20200305 首发
20200309 第一次修订

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！