SIDH 中3e3 -挠基的快速生成*

2022-11-04 02:23李梦东朱屹霖
北京电子科技学院学报 2022年2期
关键词:公钥同源密钥

王 颖 李梦东 朱屹霖

北京电子科技学院,北京市 100070

引言

同源密码是一种新型的后量子密码形式,其基本方案是SIDH(Supersingular Isogeny Diffie-Hellman)密钥交换协议[1]。 同源密码具有高安全性和公钥长度较小的优点,根据SIDH 的改进而成的SIKE 算法,已经成为NIST 后量子密码征集活动第三轮的备用算法之一。 但相对于其他后量子密码类型,SIDH 也有相对较长的计算时间的缺点,如何提升SIDH 实现效率是需要加以解决的问题。

在SIDH 密钥交换协议中公钥生成和传输方面,最初的公钥是使用(E,xP,xQ) 形式的三元组完成的[2],其中E:y2=x3+ax+b,xP,xQ是P 和Q 的横坐标。 因此,公钥的传输实质上是使用四个元素a,b,xP,xQ∈Fp2,需要8log p比特。

文献[3] 等人提出形如PK= [xφ(P),xφ(Q),xφ(Q-P)]∈F3p2的公钥表示,将其大小减小为6log p比特,这也方便在解压缩过程中使用三点阶梯函数[4],使计算效率更高。

文献[5]提出SIDH 公钥压缩的思路,将公钥中的点展开为挠基的线性组合,只传递其中的系数可进一步实行公钥长度的缩短。 首先用j不变量来表示曲线E, 它也是Fp2的一个元素,同源类是由j不变量唯一决定的。 其次用ℤt⊕ℤt中的元素来表示点P、Q,将公钥表示减小到4log p比特。 然而,这种公钥尺寸的减少也带来了相当高的计算开销。

文献[6]等人进一步压缩点P、Q 的表示,将公钥大小减少到3.5log p比特,并在挠基的生成阶段采用2-下降算法进行提速。 文献[7]等人提出纠缠基和反向基分解的概念,很大程度上减少了SIDH 压缩和解压缩的运行时间。 文献[8]等人对公钥压缩技术进一步的研究,降低了生成2e2-挠基的复杂度,对生成3e3-挠基的解压过程也提出了改进。 文献[9]等人提出对偶同源,对生成3e3-挠基和配对过程进行了结合,提高了整体实现效率。

本文详细分析和描述了之前学者提出的关于生成3e3-挠基的实现步骤,并进行补充。 同时提出了新的改进方法,使得生成挠基时在随机点的阶为2r的情况下,减少e2-r次点2 倍计算,从而提高整体生成基的效率。

1 预备知识

1.1 SIDH 密钥交换协议

超奇异同源Diffie-Hellman(SIDH)密钥交换算法是依赖同源问题的Diffie-Hellman 算法,不受量子攻击的影响[10],文献[2]中也证明了:在SSDDH(Supersingular Decision Diffie-Hellman)假设下,SIDH 密钥协商协议在Canetti 和Krawczyk[11]的认证链路对抗模型中具有会话密钥安全性。

SIDH 协议双方需要交换他们的公开密钥,每个公开密钥由椭圆曲线E′和E′上的两点P,Q 组成[12]。 设有限域Fp2上定义一个形式为p=lelmem ±1 的大素数,其中l和m都是小素数且lel≈mem,l和m通常分别等于2 和3。 选择一个超奇异椭圆曲线E, 满足#EA(Fp2)= (lelmem)2。SIDH 密钥交换过程可以概括为以下步骤:

①Alice 和Bob 分别在公共椭圆曲线E/Fp2上产生两个独立点PA,QA和PB,QB;

②Alice 通过两个阶为lel的独立点生成E的挠子群E[lel]=PA,QA,群中元素阶为lel;Bob通过两个阶为mem的独立点生成E的挠子群E[mem]=PB,QB,群中元素阶为mem;

③Alice 随机选取秘密整数sA和tA∈ℤ /lelℤ ,且两者都不能被l整除,生成点RA=[sA]PA+ [tA]QA,RA的阶为lel;Bob 随机选取秘密整数sB和tB∈ℤ /memℤ ,且两者都不能被m整除,生成点RB= [sB]PB+ [tB]QB,RB的阶为mem;

④Alice 得到RA生成的循环群RA,#RA=lel;Bob 得到RB生成的循环群RB,#RB=mem;

⑤Alice 根据核KerφA=RA,得到同源φA:E→EA(唯一)[13],作为Alice 的私钥,这里EA=E/RA; Bob 根据核KerφB=RB,得到同源φB:E→EB(唯一)[13],作为Bob 的私钥,这里EB=E/RB;

⑥ Alice 将φA(PB)、φA(QB)、EA发送给Bob;Bob 将φB(PA)、φB(QA)、EB发给Alice,这些是双方的公开信息;

⑦Alice 和Bob 通过计算得到的EAB=EBA=E/RA,RB,可以作为对称加密的共享秘钥。

1.2 SIDH 公钥压缩

SIDH 的公钥压缩是指将传输的公钥以更小比特的形式表示出来,文献[6]将公钥大小压缩到了3.5log p比特,但是其压缩过程所用的计算成本仍然较高。

以Alice 端为例,定义在Fp2上的椭圆曲线E和E/RA,挠子群E[lel] 的生成点PA和QA, 点φA(PB) 和φA(QB) 作为她公开参数。

公钥压缩(解压缩)过程可以概括为以下步骤:

①生成挠基:压缩时Alice 生成挠子群E/RA[lel] 的二维挠基{R1,R2}∈Fp2[lel];解压缩时Bob 按照顺序生成相同的挠基{R1,R2};

1.3 Elligator 2 生成随机点

2 已有3e3 -挠基生成的算法分析

2.1 naïve 算法

2.2 3-下降算法

2.3 算法分析

生成2e2-挠基的过程通过纠缠基技术在实现效率上得到了很大的提升,但是由于很难应用到3e3的情况下,现有的方法仍然需要分别生成不相关挠点。

下降算法减少了在判断阶数时使用余因子乘法的频率,但是在寻找3 阶点P3时,也需要大量的余因子乘法来判断阶数。

Zanon 等人[7]通过实验观察到,l= 2 时,naïve 方法总是比3-下降算法快。 但两者都需要大量的余因子乘来判断阶数,计算成本较高。本文对此进行了优化,具体描述在下一节给出。

3 改进后的SIDH 的3e3 -挠基生成

为了降低余因子乘的次数,本文在已有的挠基生成技术基础上,对随机点的阶数是否为2r进行判断,在生成3e3-挠基的情况下,减少e2-r次点2 倍计算。 因为naïve 算法和3-下降算法都需要余因子乘来判断阶数,所以本文的这项优化分别应用在两种算法上,同时提高生成基效率。

3.1 在naïve 方法中的改进

3.2 在3-下降方法中的改进

在3-下降方法中,寻找3-挠点P3时也通过乘余因子的方法来判断阶数。 所以同样在计算点2 倍算法时添加判断,若出现Z=0 的情况,就舍弃,立即进入下一轮的迭代来减少不必要的成本本支出。

针对3-下降算法改进如下:

3.3 点2 倍算法改进

无论是naïve 算法还是3-下降算法,都应用了最基础的点2 倍算法,所以本文提出的改进是在点2 倍算法中实现的。 在SIKE 说明文件[17]中点2 倍算法也就是用Double 函数来完成的。根据本文的改进,在循环的最后一步添加了判断,如果得到了可以使z= 0 的点,就立即终止计算,主函数就要重新生成随机点。

改进后的算法1 如下:

算法1 在Montgomery 曲线E/Fp2:y2 = x3 +Ax2 +x 上计算r次点2 倍后的x 坐标输入:曲线系数A24 = (A + 2)/4,点(x,z) 和整数r。输出:点(x’,z’) = [2r](x,z) ∈E。1for j = 1 to r do 2a ←x + z;3b ←x - z;4 aa ←a2;5bb ←b2;6c ←aa - bb;7x ←aa·bb;8 z ←c(bb + A24·c);9 if z = 0 then 10 Abort; / /说明生成点的阶为2i 11return x,z;

4 改进算法效果分析

4.1 在naïve 算法中的改进效果分析

表1 列出了优化方案的成本对比。

表1 减少成本对比

4.2 在3-下降算法中的改进效果分析

在3-下降算法中确定一个非平凡3-挠点P3仍然是一个需要乘余因子的高消耗过程,本文观察到,在寻找3-挠点P3时,同样没有考虑Elligator 2 的生成点阶数为2r(1<r≤e2)的可能性,当生成点R∈[3e3]E时,无法得到阶为3的点或者是阶为3e3的点,所以立即重新生成随机点可以省去e2-r次点2 倍的计算。

5 结论

在SIDH 公钥压缩生成3e3-挠基的这一步中,已有的naïve 和3-下降算法都无法避免大量的余因子乘法,而余因子乘法所用成本又相对较高,所以本文通过在点2 倍乘法的过程中判断随机点阶数是否为2r,来排除[3e3]E中的点,从而加快生成正确阶数挠点的速度。

提高SIDH 公钥压缩计算速度的是一项十分有意义的工作,本文只针对生成随机点阶数为2r(1<r≤e2)的情况进行了优化,其他情况下仍然需要高成本的计算,所以仍然有进一步研究的必要。

猜你喜欢
公钥同源密钥
药食同源 药膳产品成就养生新风潮
山西恩予:打造药食同源新业态
幻中邂逅之金色密钥
幻中邂逅之金色密钥
神奇的公钥密码
Android密钥库简析
同源宾语的三大类型与七项注意
国密SM2密码算法的C语言实现
基于身份的聚合签名体制研究
一种新的动态批密钥更新算法