高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

椭圆曲线Diffie-Hellman密钥交换协议的比特安全性研究

魏伟 陈佳哲 李丹 张宝峰

魏伟, 陈佳哲, 李丹, 张宝峰. 椭圆曲线Diffie-Hellman密钥交换协议的比特安全性研究[J]. 电子与信息学报, 2020, 42(8): 1820-1827. doi: 10.11999/JEIT190845
引用本文: 魏伟, 陈佳哲, 李丹, 张宝峰. 椭圆曲线Diffie-Hellman密钥交换协议的比特安全性研究[J]. 电子与信息学报, 2020, 42(8): 1820-1827. doi: 10.11999/JEIT190845
Wei WEI, Jiazhe CHEN, Dan LI, Baofeng ZHANG. Research on the Bit Security of Elliptic Curve Diffie-Hellman[J]. Journal of Electronics and Information Technology, 2020, 42(8): 1820-1827. doi: 10.11999/JEIT190845
Citation: Wei WEI, Jiazhe CHEN, Dan LI, Baofeng ZHANG. Research on the Bit Security of Elliptic Curve Diffie-Hellman[J]. Journal of Electronics and Information Technology, 2020, 42(8): 1820-1827. doi: 10.11999/JEIT190845

椭圆曲线Diffie-Hellman密钥交换协议的比特安全性研究

doi: 10.11999/JEIT190845
基金项目: 国家重点研发计划(2016YFB0800902),国家自然科学基金(61802439, U1936209)
详细信息
    作者简介:

    魏伟:女,1985年生,助理研究员,研究方向为密码学

    陈佳哲:男,1985年生,副研究员,研究方向为密码学

    李丹:女,1991年生,讲师,研究方向为侧信道分析技术

    张宝峰:男,1983年生,副研究员,研究方向为信息技术产品的安全测评

    通讯作者:

    张宝峰 zhangbf@itsec.gov.cn

  • 中图分类号: TP309

Research on the Bit Security of Elliptic Curve Diffie-Hellman

Funds: The National Key Research and Development Program of China (2016YFB0800902), The National Natural Science Foundation of China (61802439, U1936209)
  • 摘要: 椭圆曲线Diffie-Hellman密钥交换协议与其他公钥密码体制相比,能够以较小的密钥尺寸来达到相同的安全强度,因此在实际应用中对带宽和存储的要求较低,从而在很多计算资源受限的环境中有更多应用价值。该文从理论和应用角度,评估该类型协议共享密钥建立过程中的部分信息泄漏对安全性的威胁至关重要。基于隐藏数问题和格分析技术,该文讨论了椭圆曲线Diffie-Hellman密钥交换协议的比特安全性,启发式地证明了椭圆曲线Diffie-Hellman共享密钥的x坐标的中间11/12 bit的计算困难性近似于恢复整个密钥。进一步地,给出了信息泄露量与泄漏位置的显式关系式。该文的研究结果放松了对泄露比特位置的限制,更加符合应用场景,显著改进了以往工作中得出的结论。
  • 表  1  主要符号对照表

    符号代表意义
    ${\mathbb{R}^m}$$m$维实数向量空间
    $\mathbb{Z}$整数集
    ${\mathbb{F}_p}$$p$元有限域
    $\mathbb{E}({\mathbb{F}_p})$椭圆曲线$\mathbb{E}$在${\mathbb{F}_p}$中的有理点群
    $\parallel \cdot \parallel $欧几里得范数
    ${\rm{det}}(L)$格$L$的基本域体积
    ${\lambda _1}(L)$格$L$的最短格向量的长度
    ${{{B}}^{\rm{T}}}$矩阵${{B}}$的转置矩阵
    下载: 导出CSV
  • [1] KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987, 48(177): 203–209. doi:  10.1090/S0025-5718-1987-0866109-5
    [2] MILLER V S. Use of elliptic curves in cryptography[C]. Proceedings of Conference on the Theory and Application of Cryptographic Techniques, California, USA, 1986: 417–426.
    [3] BONEH D and VENKATESAN R. Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes[C]. The 16th Annual International Cryptology Conference, California, USA, 1996: 129–142.
    [4] LIU Mingjie, CHEN Jiazhe, and LI Hexin. Partially known nonces and fault injection attacks on SM2 signature algorithm[C]. The 9th International Conference on Information Security and Cryptology, Guangzhou, China, 2014: 343–358.
    [5] NGUYEN P Q and SHPARLINSKI I E. The insecurity of the elliptic curve digital signature algorithm with partially known nonces[J]. Designs, Codes and Cryptography, 2003, 30(2): 201–217. doi:  10.1023/A:1025436905711
    [6] FAN Shuqin, WANG Wenbo, and CHENG Qingfeng. Attacking OpenSSL implementation of ECDSA with a few signatures[C]. 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 2016: 1505–1515.
    [7] GANJI F, KRÄMER J, SEIFERT J P, et al. Lattice basis reduction attack against physically unclonable functions[C]. The 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, USA, 2015: 1070–1080.
    [8] BREITNER J and HENINGER N. Biased nonce sense: lattice attacks against weak ECDSA signatures in cryptocurrencies[J]. Financial Cryptography and Data Security, 2019: 3–20.
    [9] MOGHUMI D, SUNAR B, EISENBARTH T, et al. TPM-FAIL: TPM meets timing and lattice attacks[J]. arXiv: 2019, 1911.05673.
    [10] BONEH D, HALEVI S, and HOWGRAVE-GRAHAM N. The modular inversion hidden number problem[C]. The 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, 2001: 36–51.
    [11] XU Jun, SARKAR S, HU Lei, et al. New results on modular inversion hidden number problem and inversive congruential generator[C]. The 39th Annual International Cryptology Conference, Santa Barbara, USA, 2019: 297–321.
    [12] SHANI B. On the bit security of elliptic curve Diffie-Hellman[C]. The 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, 2017: 361–387.
    [13] XU Jun, HU Lei, and SARKAR S. Cryptanalysis of elliptic curve hidden number problem from PKC 2017[J]. Designs, Codes and Cryptography, 2020, 88(2): 341–361. doi:  10.1007/s10623-019-00685-y
    [14] HLAVÁČ M and ROSA T. Extended hidden number problem and its cryptanalytic applications[C]. The 13th International Workshop on Selected Areas in Cryptography, Montreal, Canada, 2007: 114–133.
    [15] WEI Wei, CHEN Jiazhe, LI Dan, et al. Partially known information attack on SM2 key exchange protocol[J]. Science China Information Sciences, 2019, 62(3): 032105. doi:  10.1007/s11432-018-9515-9
    [16] 张江, 范淑琴. 关于非对称含错学习问题的困难性研究[J]. 电子与信息学报, 2020, 42(2): 327–332. doi:  10.11999/JEIT190685

    ZHANG Jiang and FAN Shuqin. On the hardness of the asymmetric learning with errors problem[J]. Journal of Electronics &Information Technology, 2020, 42(2): 327–332. doi:  10.11999/JEIT190685
    [17] NGUYEN P Q and SHPARLINSKI I E. The insecurity of the digital signature algorithm with partially known nonces[J]. Journal of Cryptology, 2002, 15(3): 151–176. doi:  10.1007/s00145-002-0021-3
    [18] 谢天元, 李昊宇, 朱熠名, 等. FatSeal: 一种基于格的高效签名算法[J]. 电子与信息学报, 2020, 42(2): 333–340. doi:  10.11999/JEIT190678

    XIE Tianyuan, LI Haoyu, ZHU Yiming, et al. FatSeal: An efficient lattice-based signature algorithm[J]. Journal of Electronics &Information Technology, 2020, 42(2): 333–340. doi:  10.11999/JEIT190678
    [19] LENSTRA A K, LENSTRA H W JR, and LOVÁSZ L. Factoring polynomials with rational coefficients[J]. Mathematische Annalen, 1982, 261(4): 515–534. doi:  10.1007/BF01457454
    [20] SCHNORR C P. A hierarchy of polynomial time lattice basis reduction algorithms[J]. Theoretical Computer Science, 1987, 53(2/3): 201–224.
    [21] MICCIANCIO D and GOLDWASSER S. Complexity of Lattice Problems: A Cryptographic Perspective[M]. Boston, USA: Kluwer Academic Publishers, 2002.
    [22] NGUYEN P Q. Hermite’s Constant and Lattice Algorithms[M]. NGUYEN P Q and VALLÉE B. The LLL Algorithm: Survey and Applications. Berlin, Germany: Springer, 2009: 19–69.
    [23] GAMA N, NGUYEN P Q, and REGEV O. Lattice enumeration using extreme pruning[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010: 257–278.
    [24] AONO Y and NGUYEN P Q. Random sampling revisited: Lattice enumeration with discrete pruning[C]. The 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, 2017: 65–102.
  • [1] 陈华, 习伟, 范丽敏, 焦志鹏, 冯婧怡.  密码产品的侧信道分析与评估, 电子与信息学报. doi: 10.11999/JEIT190853
    [2] 张彦华, 胡予濮, 刘西蒙, 张启坤, 贾惠文.  格上本地验证者撤销属性基群签名的零知识证明, 电子与信息学报. doi: 10.11999/JEIT190587
    [3] 谢天元, 李昊宇, 朱熠铭, 潘彦斌, 刘珍, 杨照民.  FatSeal:一种基于格的高效签名算法, 电子与信息学报. doi: 10.11999/JEIT190678
    [4] 王明强, 庄金成.  基于列表译码方法在查询访问模型下含错学习问题的分析, 电子与信息学报. doi: 10.11999/JEIT190624
    [5] 闫玺玺, 刘媛, 李子臣, 汤永利, 叶青.  新的格上多机构属性基加密方案, 电子与信息学报. doi: 10.11999/JEIT170628
    [6] 喻昕, 许治健, 陈昭蓉, 徐辰华.  拉格朗日神经网络解决带等式和不等式约束的非光滑非凸优化问题, 电子与信息学报. doi: 10.11999/JEIT161049
    [7] 张敏情, 柯彦, 苏婷婷.  基于LWE的密文域可逆信息隐藏, 电子与信息学报. doi: 10.11999/JEIT150702
    [8] 杨孝鹏, 马文平, 张成丽.  一种新型基于环上带误差学习问题的认证密钥交换方案, 电子与信息学报. doi: 10.11999/JEIT141506
    [9] 张彦华, 胡予濮, 江明明, 来齐齐.  格上可撤销的基于身份的适应性安全的加密方案, 电子与信息学报. doi: 10.11999/JEIT140421
    [10] 江明明, 胡予濮, 王保仓, 来齐齐, 刘振华.  格上基于身份的单向代理重签名, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.00818
    [11] 夏峰, 杨波, 张明武, 马莎, 雷涛.  基于LWE的集合相交和相等的两方保密计算, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.00541
    [12] 王凤和, 胡予濮, 王春晓.  格上基于盆景树模型的环签名, 电子与信息学报. doi: 10.3724/SP.J.1146.2009.01491
    [13] 杨威, 黄刘生, 王启研.  基于椭圆曲线的三方比特承诺, 电子与信息学报. doi: 10.3724/SP.J.1146.2008.00443
    [14] 程义民, 钱振兴, 王以孝, 田源.  基于数位信息的信息隐藏方法, 电子与信息学报.
    [15] 郝林, 罗平.  椭圆曲线密码体制中点的数乘的一种快速算法, 电子与信息学报.
    [16] 张方国, 王常杰, 王育民.  GF(p)上安全椭圆曲线及其基点的选取, 电子与信息学报.
    [17] 刘胜利, 郑东, 王育民.  域GF(2n)上安全椭圆曲线及基点的选取, 电子与信息学报.
    [18] 马建峰, 王育民.  几类格的快速译码, 电子与信息学报.
    [19] 岳殿武.  关于Goppa码的维数问题, 电子与信息学报.
    [20] 崔大富, 李亚亭, 王保国, 蔡金娥, 范杰.  一兆比特汉字信息存储管, 电子与信息学报.
  • 加载中
  • 计量
    • 文章访问数:  679
    • HTML全文浏览量:  473
    • PDF下载量:  34
    • 被引次数: 0
    出版历程
    • 收稿日期:  2019-11-01
    • 修回日期:  2020-04-16
    • 网络出版日期:  2020-04-24
    • 刊出日期:  2020-08-18

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注