橢圓曲線Diffie-Hellman密鑰交換協(xié)議的比特安全性研究

魏偉; 陳佳哲; 李丹; 張寶峰

doi:10.11999/JEIT190845

橢圓曲線Diffie-Hellman密鑰交換協(xié)議的比特安全性研究

doi: 10.11999/JEIT190845 cstr: 32379.14.JEIT190845

魏偉¹,
陳佳哲¹,
李丹³,
張寶峰^{1, 2, ,}

1.
中國(guó)信息安全測(cè)評(píng)中心北京 100085
2.
清華大學(xué) 北京 100084
3.
國(guó)家開放大學(xué) 北京 100039

基金項(xiàng)目: 國(guó)家重點(diǎn)研發(fā)計(jì)劃(2016YFB0800902)，國(guó)家自然科學(xué)基金(61802439, U1936209)

詳細(xì)信息

作者簡(jiǎn)介:
魏偉：女，1985年生，助理研究員，研究方向?yàn)槊艽a學(xué)

陳佳哲：男，1985年生，副研究員，研究方向?yàn)槊艽a學(xué)

李丹：女，1991年生，講師，研究方向?yàn)閭?cè)信道分析技術(shù)

張寶峰：男，1983年生，副研究員，研究方向?yàn)樾畔⒓夹g(shù)產(chǎn)品的安全測(cè)評(píng)

通訊作者:
張寶峰　zhangbf@itsec.gov.cn

中圖分類號(hào): TP309
計(jì)量
- 文章訪問數(shù): 3988
- HTML全文瀏覽量: 1561
- PDF下載量: 145
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-11-01
- 修回日期: 2020-04-16
- 網(wǎng)絡(luò)出版日期: 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密鑰交換協(xié)議與其他公鑰密碼體制相比，能夠以較小的密鑰尺寸來達(dá)到相同的安全強(qiáng)度，因此在實(shí)際應(yīng)用中對(duì)帶寬和存儲(chǔ)的要求較低，從而在很多計(jì)算資源受限的環(huán)境中有更多應(yīng)用價(jià)值。該文從理論和應(yīng)用角度，評(píng)估該類型協(xié)議共享密鑰建立過程中的部分信息泄漏對(duì)安全性的威脅至關(guān)重要?；陔[藏?cái)?shù)問題和格分析技術(shù)，該文討論了橢圓曲線Diffie-Hellman密鑰交換協(xié)議的比特安全性，啟發(fā)式地證明了橢圓曲線Diffie-Hellman共享密鑰的x坐標(biāo)的中間11/12 bit的計(jì)算困難性近似于恢復(fù)整個(gè)密鑰。進(jìn)一步地，給出了信息泄露量與泄漏位置的顯式關(guān)系式。該文的研究結(jié)果放松了對(duì)泄露比特位置的限制，更加符合應(yīng)用場(chǎng)景，顯著改進(jìn)了以往工作中得出的結(jié)論。
- 橢圓曲線Diffie-Hellman /
- 比特安全 /
- 信息泄露 /
- 格 /
- 隱藏?cái)?shù)問題
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 主要符號(hào)對(duì)照表

符號(hào)	代表意義
${\mathbb{R}^m}$	$m$維實(shí)數(shù)向量空間
$\mathbb{Z}$	整數(shù)集
${\mathbb{F}_p}$	$p$元有限域
$\mathbb{E}({\mathbb{F}_p})$	橢圓曲線$\mathbb{E}$在${\mathbb{F}_p}$中的有理點(diǎn)群
$\parallel \cdot \parallel $	歐幾里得范數(shù)
${\rm{det}}(L)$	格$L$的基本域體積
${\lambda _1}(L)$	格$L$的最短格向量的長(zhǎng)度
${{{B}}^{\rm{T}}}$	矩陣${{B}}$的轉(zhuǎn)置矩陣

下載: 導(dǎo)出CSV

參考文獻(xiàn)(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

張江, 范淑琴. 關(guān)于非對(duì)稱含錯(cuò)學(xué)習(xí)問題的困難性研究[J]. 電子與信息學(xué)報(bào), 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]. 電子與信息學(xué)報(bào), 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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)