Bintou's Blog

Reader, Writer and Thinker.

0%

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

Posted on Edited on In Views: Valine:

引言

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

Diffie-Hellman算法

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

Diffie-Hellman基本协议

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

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

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

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

抽象Diffie-Hellman

这是一种抽象描述，但是它表达了一种直观的思路。\(G\)是公共参数，Alice的秘密是\(A\)，Bob的秘密是\(B\)。比如，假想这样的情况，\(G\)是一个乘法群，\(A\)和\(B\)是\(G\)的正规子群。Alice和Bob如果还是按照上面的做法，都可以计算出商群\(G/AB\)，\(AB\)理解为\(A \cap 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

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

SIDH构造的简化版本

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

基本SIDH

首先，超奇异椭圆曲线群\(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, R_A \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\)决定，可理解为群同态\(\phi_A\)映射到\(E\)上的像 (Image)形成的子群。同理，\(E_{BA}\)是Isogeny \(\phi_{BA}\) 映射到\(E\)上的子群，而Isogeny \(\phi_{BA}\) 是由\(\langle R_B, R_A \rangle\)决定的，即Isogeny \(\phi_{BA}\) 的Kernel是\(\langle R_B, R_A \rangle\)。

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

SIDH

SIDH构造的细化版本

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

SIDH参数设计

首先，选择超奇异椭圆曲线\(E\)作为公开参数。然后Alice随机选择两个元素\(P_A, Q_A \in E\)，并公开作为自己的公共参数。同样，Bob也随机选择两个元素$ P_B, Q_B 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(R_A)\) 计算\(E_{BA}\)。\(E_{BA}\)是曲线群\(E\) 的子群，是以\(\phi_B (R_A)\) 为Kernel的群同态映射到\(E\)上的子群。这个群同态也就是Isogeny，这个Isogeny我们记为 $ _{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} \ne E_{AB}\)，至少它们不显然相等！其次，\(E_{BA}\) 同构于\(E_{AB}\) 。然后利用同构曲线的一个属性：所有同构曲线的 J-Invariant值相同。于是Alice和Bob分别计算\(J(E_{BA})\)和 \(J(E_{AB})\) ，这就是他们共同拥有的秘密。J-Invariant的计算定义可在标准教科书中找到，本文把它视为黑盒子使用。

Sage代码展示SIDH的思路

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

参数设置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#选取一条在素域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 的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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

Bob的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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

秘密值计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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的文献 。代码源自Lvh的Blog，总算找回这个网站，我撰写的内容则基本与Lvh没关系。

--