高级搜索

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

魏伟 陈佳哲 李丹 张宝峰

引用本文: 魏伟, 陈佳哲, 李丹, 张宝峰. 椭圆曲线Diffie-Hellman密钥交换协议的比特安全性研究[J]. 电子与信息学报, doi: 10.11999/JEIT190845 shu
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, doi: 10.11999/JEIT190845 shu

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

    作者简介: 魏伟: 女,1985年生,助理研究员,研究方向为密码学;
    陈佳哲: 男,1985年生,副研究员,研究方向为密码学;
    李丹: 女,1991年生,讲师,研究方向为侧信道分析技术;
    张宝峰: 男,1983年生,副研究员,研究方向为信息技术产品的安全测评
    通讯作者: 张宝峰,zhangbf@itsec.gov.cn
  • 基金项目: 国家重点研发计划(2016YFB0800902),青年科学基金项目(61802439),国家自然科学基金(U1936209)

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

English

    1. [1]

      KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987, 48(177): 203–209. doi: 10.1090/S0025-5718-1987-0866109-5

    2. [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. [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. [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. [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. [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. [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. [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. [9]

      MOGHUMI D, SUNAR B, EISENBARTH T, et al. TPM-FAIL: TPM meets timing and lattice attacks[J]. arXiv: 1911.05673, 2019.

    10. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [20]

      SCHNORR C P. A hierarchy of polynomial time lattice basis reduction algorithms[J]. Theoretical Computer Science, 1987, 53(2/3): 201–224.

    21. [21]

      MICCIANCIO D and GOLDWASSER S. Complexity of Lattice Problems: A Cryptographic Perspective[M]. Boston, USA: Kluwer Academic Publishers, 2002.

    22. [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, Heidelberg: Springer, 2009: 19–69.

    23. [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. [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  主要符号对照表

    符号代表意义
    ${\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
  • 加载中
计量
  • PDF下载量:  9
  • 文章访问数:  328
  • HTML全文浏览量:  270
文章相关
  • 通讯作者:  张宝峰, zhangbf@itsec.gov.cn
  • 收稿日期:  2019-11-01
  • 录用日期:  2019-04-16
  • 网络出版日期:  2020-04-24
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章