网站首页 公文大全 个人文档 实用范文 讲话致辞 实用工具 心得体会 哲学范文 总结范文 范文大全 报告 合同 文书 信函 实用
  • 汇报体会
  • 节日庆典
  • 礼仪
  • 毕业论文
  • 评语寄语
  • 导游词
  • 口号大全
  • 其他范文
    • 百花范文网 > 实用范文 > 其他范文 > SIDH,中3e3,-挠基的快速生成*

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

    时间：2023-01-13 08:35:24来源：百花范文网本文已影响人

    王 颖 李梦东 朱屹霖

    北京电子科技学院，北京市 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 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.1 naïve 算法

    2.2 3-下降算法

    2.3 算法分析

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

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

    Zanon 等人[7]通过实验观察到，l= 2 时，naïve 方法总是比3-下降算法快。

    但两者都需要大量的余因子乘来判断阶数，计算成本较高。本文对此进行了优化，具体描述在下一节给出。

    为了降低余因子乘的次数，本文在已有的挠基生成技术基础上，对随机点的阶数是否为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.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 倍的计算。

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

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

    猜你喜欢 公钥同源密钥 药食同源 药膳产品成就养生新风潮今日农业(2022年1期)2022-11-16山西恩予：打造药食同源新业态今日农业(2022年2期)2022-11-16幻中邂逅之金色密钥故事作文·低年级(2022年2期)2022-02-23幻中邂逅之金色密钥故事作文·低年级(2022年1期)2022-02-03神奇的公钥密码知识就是力量(2018年10期)2018-10-18Android密钥库简析计算机与网络(2018年2期)2018-09-10同源宾语的三大类型与七项注意新高考·英语进阶（高二高三）(2018年8期)2018-01-15国密SM2密码算法的C语言实现中国新通信(2017年18期)2017-10-22基于身份的聚合签名体制研究成长·读写月刊(2017年4期)2017-05-16一种新的动态批密钥更新算法西安交通大学学报(2009年12期)2009-02-08

    相关热词搜索：生成 快速 SIDH

    • 范文大全
    • 说说大全
    • 学习资料
    • 语录
    • 生肖
    • 解梦
    • 十二星座
    最新文章

    推荐访问

    SIDH 快速 快速原型制造 快速原型制造技术 快速发展 快速增长 快速提高公文写作能力的方法 快速提高初中数学成绩方法 快速提高新闻写作能力 快速消费品 快速看完继续教育 快速翻译文言文的十个方法 快速蒙版使用方法 快速血脂仪检测仪的应用 快速血脂检测仪 快速跑途中跑教案|高二快速跑教案 快速阅读的训练五种方法 生成 生成物

    本文SIDH,中3e3,-挠基的快速生成*由百花范文网整理提供，版权归原作者、原出处所有。

    Copyright © 百花范文网 All Rights Reserved.