【后量子密码】超奇异椭圆曲线同源密钥协商理论研究

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

持续更新中

欢迎捉虫

带*的可略过

SIDH:Supersingular Isogeny Diffie-Hellman

1.超奇异椭圆曲线

1.1.同构

isomorphism

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

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


1.2.扭子群

torsion group

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

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

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

其中 O 为 E 的单位元

E的扭子群

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


pmp \nmid m 时,E[m](Z/mZ)2E[m] \cong (Z/mZ)^2 ,对于 r ≥ 1 ,E[pr]E[p^r]有两种情况:

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

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


1.3.超奇异

supersingular

q=prq = p^r , p为素数,r为正整数

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


2.同源

2.0.定义

isogeny

isogenous

ϕ:E1E2\phi:E_1 \rightarrow E_2 是椭圆曲线间的态射(morphism)且 ϕ(OE1)=OE2\phi(O_{E_1}) = O_{E_2},则称 ϕ\phi 是椭圆曲线间的同源(isogeny)

同源有两种情况:

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

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

SIDH仅考虑后者


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

isogenous是等价关系。


Tate定理:

E1E_1, E2E_2 为有限域 FqF_q 上的椭圆曲线,则存在定义在 FqF_q 上的同源 ϕ:E1E2\phi:E_1 \rightarrow E_2 当且仅当 #E1(Fq)=#E2(Fq)\#E_1(F_q)=\#E_2(F_q)


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


某个命题:

Φ\PhiEE 的一个有限子群,有且仅有一条椭圆曲线 E’ 和一个可分同源(separable isogeny)

ϕ:EE\phi:E \rightarrow E' 满足 ker(ϕ)=Φker(\phi) = \Phi

通常把 EE' 记作 E/ΦE/\Phi

这个命题也可以表述为:

ϕ:E1E2\phi:E_1 \rightarrow E_2 是一个非零同源,那么

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


2.1.自同态环(*)

E1E_1E2E_2 的所有isogeny的集合定义为

Hom(E1,E2)={all isogenies:E1E2}Hom(E_1,E_2) = \{all\ isogenies :E_1 \rightarrow E_2\}


令 P 是 E1E_1 中一点

两个isogenies之间的加法:

(ϕ+ψ)(P)=ϕ(P)+ψ(P)(\phi+\psi)(P) = \phi(P) + \psi(P)

可以证明(ϕ+ψ)Hom(E1,E2)(\phi + \psi) \in Hom(E_1,E_2)

所以 Hom(E1,E2)Hom(E_1,E_2) 成群


特别地

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

是E的自同态环

加法如上所述,乘法如下:

(ϕψ)(P)=ϕ(ψ(P))(\phi\psi)(P) = \phi(\psi(P))


2.2.乘以 m 同源

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

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

[m]:EE[m]:E \rightarrow E

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

即m个P相加

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

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


由定义不难推出

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

如果m与q互素,那么

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


2.3.Q平移映射 (*)

QEQ \in E ,

translation-by-Q map 定义为

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

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

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


现在任意选取一个态射:

F:E1E2F:E_1 \rightarrow E_2

ϕ=τF(O)F\phi = \tau_{-F(O)} \circ F

显然 ϕ\phi 是一个同源,因为 ϕ(O)=O\phi(O) = O

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

F=τF(O)ϕF = \tau_{F(O)} \circ \phi


2.4.同源是一种群同态

ϕ:E1E2\phi:E_1 \rightarrow E_2 是一个同源,以下等式恒成立

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

ϕ\phi 是一种群同态


2.5.可分同源

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

ϕ=gf\phi = g \circ f

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

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

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

具体而言,对于 E1E_1 的任意子群 GG,有且仅有一个同源

ϕ:E1E2\phi:E_1 \rightarrow E_2 的kernel是 G

反之亦然。

在这种情况下,我们通常把 E2E_2 记作 E1/GE_1/G


2.6.degree(*)

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

且恒有如下等式

deg(ϕψ)=deg(ϕ)×deg(ψ)deg(\phi \circ \psi)=deg(\phi) \times \deg(\psi)


正题:SIDH

1.参数选择

取定素数

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

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

eA,eBe_A,e_B 为正整数

EEFp2F_{p^2} 上的超奇异椭圆曲线,且

E[lAeA]=PA,QA,E[lBeB]=PB,QBE[l_A^{e_A}]=\langle P_A,Q_A\rangle ,E[l_B^{e_B}]=\langle P_B,Q_B\rangle

曲线为Montgomery form,即:

by2=x3+ax2+xby^2 = x^3 + ax^2 + x

公开 p,E,PA,PB,QA,QBp,E,P_A,P_B,Q_A,Q_B


2.私钥选择

Alice选择私钥

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

构造循环子群

GA=PA+[a]QAG_A =\langle P_A+[a]Q_A\rangle

(这里也可以选择两个整数作为私钥构造sAPA+tAQA\langle s_AP_A+t_AQ_A\rangle, 其中 sAs_A,tAt_A 不都 整除 lAeAl_A^{e_A})

计算同源

ϕA:EEA=E/GA\phi_A: E \rightarrow E_A = E/G_A

同样地,Bob选择私钥

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

构造循环子群

GB=PB+[b]QBG_B = \langle P_B+[b]Q_B \rangle

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

计算同源

ϕB:EEB=E/GB\phi_B:E \rightarrow E_B = E/G_B


3.公钥交换

Alice公开

{EA,ϕA(PB),ϕA(QB)}\{E_A,\phi_A(P_B),\phi_A(Q_B) \}

Bob公开

{EB,ϕB(PA),ϕB(QA)}\{E_B,\phi_B(P_A),\phi_B(Q_A) \}


Alice计算子群

GA=ϕB(PA)+[a]ϕB(QA)G_A' = \langle \phi_B(P_A)+[a]\phi_B(Q_A) \rangle

用这个子群计算同源

ϕBA:EBEBA=EB/GA\phi_{BA}:E_B \rightarrow E_{BA} = E_B/G_A'


同样地,Bob计算

GB=ϕA(PB)+[b]ϕA(QB)G_B' = \langle \phi_A(P_B)+[b]\phi_A(Q_B) \rangle

用这个子群计算同源

ϕAB:EAEAB=EA/GB\phi_{AB}:E_A \rightarrow E_{AB} = E_A/G_B'


EABE_{AB}EBAE_{BA} 同构,因此有相同的j-不变量


4.安全性与困难问题

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

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


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


4.1.DSSI

Decisional Supersingular Isogeny (DSSI) problem

EAE_A 是定义在 Fp2F_{p^2}下的另一条超奇异椭圆曲线,确定 EAE_A 是否是 lAeAl_A^{e_A}-同源于 EE


4.2.CSSI

Computational Supersingular Isogeny (CSSI) problem

ϕA:EEA\phi_A:E \rightarrow E_A 是kernel为 <[mA]PA+[nA]QA><[m_A]P_A+[n_A]Q_A> 的同源,其中 mA,nAZ/lAeAZm_A,n_A \in Z/l_A^{e_A}Z 且不都被 lAl_A 整除,给定 EAE_AϕA(PB),ϕB(PA)\phi_A(P_B), \phi_B(P_A) ,找到 <[mA]PA+[nA]QA><[m_A]P_A+[n_A]Q_A> 的生成元 RAR_A


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


4.3.SSCDH

Supersingular Computational Diffie-Hellman problem

ϕA:EEA\phi_A:E \rightarrow E_A 是kernel为 <[mA]PA+[nA]QA><[m_A]P_A+[n_A]Q_A> 的同源

ϕB:EEB\phi_B:E \rightarrow E_B 是kernel为 <[mB]PB+[nB]QB><[m_B]P_B+[n_B]Q_B> 的同源

其中 mA,nAZ/lAeAZm_A,n_A \in Z/l_A^{e_A}Z 且不都被 lAl_A 整除

mB,nBZ/lBeBZm_B,n_B \in Z/l_B^{e_B}Z 且不都被 lBl_B 整除

给定 EA,EB,ϕA(PB),ϕA(QB),ϕB(PA),ϕB(QA)E_A,E_B,\phi_A(P_B),\phi_A(Q_B),\phi_B (P_A),\phi_B(Q_A)

找到 E/<[mA]PA+[nA]QA,[mB]PB+[nB]QB>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概率随机选取其中一元组,确定该元组是从哪个分布抽取的:

  • (EA,EB,ϕA(PB),ϕA(QB),ϕB(PA),ϕB(QA),EAB)(E_A,E_B,\phi_A(P_B),\phi_A(Q_B),\phi_B(P_A),\phi_B(Q_A),E_{AB})

其中 EABE/<[mA]PA+[nA]QA,[mB]PB+[nB]QB>E_{AB} \cong E/<[m_A]P_A+[n_A]Q_A,[m_B]P_B+[n_B]Q_B>


  • (EA,EB,ϕA(PB),ϕA(QB),ϕB(PA),ϕB(QA),EC)(E_A,E_B,\phi_A(P_B),\phi_A(Q_B),\phi_B(P_A),\phi_B(Q_A),E_{C})


其中 ECE/<[mA]PA+[nA]QA,[mB]PB+[nB]QB>E_C \cong E/<[m'_A]P_A+[n'_A]Q_A,[m'_B]P_B+[n'_B]Q_B>

mA,nA(mB,nB)m'_A,n'_A(m'_B,n'_B)mA,nA(mB,nB)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.参数设置

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

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

2.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

3.秘密值计算

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(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)

文章作者: 莫折眉
文章链接: https://m0d1.top/2022/04/19/sidh/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 M0D1.TOP