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

魏伟; 陈佳哲; 李丹; 张宝峰

doi:10.11999/JEIT190845

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

doi: 10.11999/JEIT190845

魏伟¹,
陈佳哲¹,
李丹³,
张宝峰^{1, 2, ,}

1.
中国信息安全测评中心北京 100085
2.
清华大学北京 100084
3.
国家开放大学北京 100039

基金项目: 国家重点研发计划(2016YFB0800902)，国家自然科学基金(61802439, U1936209)

详细信息

作者简介:
魏伟：女，1985年生，助理研究员，研究方向为密码学

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

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

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

通讯作者:
张宝峰　zhangbf@itsec.gov.cn

中图分类号: TP309
计量
- 文章访问数: 3688
- HTML全文浏览量: 1439
- PDF下载量: 138
- 被引次数: 0
出版历程
- 收稿日期: 2019-11-01
- 修回日期: 2020-04-16
- 网络出版日期: 2020-04-24
- 刊出日期: 2020-08-18

Research on the Bit Security of Elliptic Curve Diffie-Hellman

Wei WEI¹,
Jiazhe CHEN¹,
Dan LI³,
Baofeng ZHANG^{1, 2
, ,}

1.
China Information Technology Security Evaluation Center, Beijing 100085, China
2.
Tsinghua University, Beijing 100084, China
3.
The Open University of China, Beijing 100039, China

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的计算困难性近似于恢复整个密钥。进一步地，给出了信息泄露量与泄漏位置的显式关系式。该文的研究结果放松了对泄露比特位置的限制，更加符合应用场景，显著改进了以往工作中得出的结论。
- 椭圆曲线Diffie-Hellman /
- 比特安全 /
- 信息泄露 /
- 格 /
- 隐藏数问题
Abstract: The elliptic curve Diffie-Hellman key exchange protocol enjoys great advantages since it could achieve the same security level with significantly smaller size of parameters compared with other public key cryptosystems. In real-world scenarios, this type of protocol requires less bandwidth and storage which leads to more application especially to computing resource constrained environments. Hence, it is important to evaluate the threat aroused by the partial information leakage during the establishment of shared keys. In this paper, the bit security of elliptic curve Diffie-Hellman with knowledge of partial inner bits based on the combination of hidden number problem and lattice-based cryptanalysis technique is recisited. 11/12 of the inner bits of the x-coordinate of the elliptic curve Diffie-Hellman key are approximately as hard to compute as the entire key. Moreover, the explicit relationship between the leakage fraction and the leakage position is elaborated. This result which relaxes the restriction on the location of leakage position dramatically improves the trivial one which stemmed from prior work.
- Elliptic curve Diffie-Hellman /
- Bit security /
- Information leakage /
- Lattice /
- Hidden Number Problem(HNP)

HTML全文

表 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

参考文献(24)

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

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.

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.

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.

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

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.

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.

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.

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

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.

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.

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.

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

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.

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

张江, 范淑琴. 关于非对称含错学习问题的困难性研究[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

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

谢天元, 李昊宇, 朱熠名, 等. 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

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

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

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

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.

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.

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.

施引文献

资源附件(0)

访问统计