請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/76968完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳君明(Jiun-Ming Chen) | |
| dc.contributor.author | Kai-Chieh Chang | en |
| dc.contributor.author | 張凱傑 | zh_TW |
| dc.date.accessioned | 2021-07-10T21:41:54Z | - |
| dc.date.available | 2021-07-10T21:41:54Z | - |
| dc.date.copyright | 2020-08-28 | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2020-08-03 | |
| dc.identifier.citation | [1] M. Adamoudis, K. A. Draziotis, and D. Poulakis. Enhancing an attack to dsaschemes. In Algebraic Informatics, pages 13–25. Springer Cham, 2019. [2] D. F. Aranha, P.A. Fouque, B. Gérard, J.G. Kammerer, M. Tibouchi, and J.C. Zapalowicz. Glv/gls decomposition, power analysis, and attacks on ecdsa signatures with singlebit nonce bias. In Advances in Cryptology – ASIACRYPT 2014, pages 262–281. Springer Berlin Heidelberg, 2014. [3] L. Babai. On lovász’ lattice reduction and the nearest lattice point problem. pages 13–20, 1985. [4] P. Belgarric, P.A. Fouque, G. MacarioRat,and M. Tibouchi. Side-channel analysis of weierstrass and koblitz curve ecdsa on android smartphones. In Topics in Cryptology CTRSA 2016, pages 236–252. Springer Cham, 2016. [5] N. Benger, J. van de Pol, N. P. Smart, and Y. Yarom. “ooh aah... just a little bit” : A small amount of side channel can go a long way. In Cryptographic Hardware and Embedded Systems – CHES 2014, pages 75–92. Springer Berlin Heidelberg, 2014. [6] D. J. Bernstein, N. Duif, T. Lange, P. Schwabe, and B.Y. Yang. High-speed high-security signatures. In Cryptographic Hardware and Embedded Systems – CHES 2011, pages 124–142. Springer Berlin Heidelberg, 2011. [7] I. F. Blake and T. Garefalakis. On the security of the digital signature algorithm. Designs, Codes and Cryptography, 26(13):87–96, 2002. [8] D. Boneh, S. Halevi, and N. Howgrave-Graham. The modular inversion hidden number problem. In Advances in Cryptology — ASIACRYPT 2001, pages 36–51. Springer Berlin Heidelberg, 2001. [9] D. Boneh and I. E. Shparlinski. On the unpredictability of bits of the elliptic curve diffie-hellman scheme. In Advances in Cryptology — CRYPTO 2001, pages 201–212. Springer Berlin, Heidelberg, 2001. [10] D. Boneh and R. Venkatesan. Hardness of computing the most significant bits of secret keys in diffie-hellman and related schemes. In Advances in Cryptology — CRYPTO ’96, pages 129–142. Springer Berlin, Heidelberg, 1996. [11] F. Dall, G. De Micheli, T. Eisenbarth, D. Genkin, N. Heninger, A. Moghimi, and Y. Yarom. Cachequote: Efficiently recovering long-term secrets of sgx epid via cache attacks. IACR Transactions on Cryptographic Hardware and Embedded Systems,pages 171–191, 2018. [12] E. De Mulder, M. Hutter, M. E. Marson, and P. Pearson. Using bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ecdsa: extended version. Journal of cryptographic engineering, 4(1):33–45, 2014. [13] K. Draziotis and D. Poulakis. Lattice attacks on dsa schemes based on lagrange’s algorithm. In Algebraic Informatics, pages 119–131. Springer Berlin Heidelberg, 2013. [14] K. A. Draziotis. Dsa lattice attacks based on coppersmith’s method. Information Processing Letters, 116(8):541–545, 2016. [15] P. Dutta. Modular inversion hidden number problem- a lattice approach. IACR Cryptology ePrint Archive, 2015:1140, 2015. [16] S. Fan, W. Wang, and Q. Cheng. Attacking openssl implementation of ecdsa with a few signatures. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 1505–1515, 2016. [17] D. Genkin, L. Pachmanov, I. Pipman, E. Tromer, and Y. Yarom. Ecdsa key extraction from mobile devices via nonintrusive physical side channels. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, page 1626–1638. Association for Computing Machinery, 2016. [18] A. I. Gomez, D. GomezPerez, and G. Renault. A probabilistic analysis on a lattice attack against dsa. Designs, Codes and Cryptography, 87(11):2469–2488, 2019. [19] M. I. González Vasco, M. Näslund, and I. E. Shparlinski. New results on the hardness of diffie-hellman bits. In Public Key Cryptography – PKC 2004, pages 159–172. Springer Berlin Heidelberg, 2004. [20] M. Hlaváč and T. Rosa. Extended hidden number problem and its cryptanalytic applications. In Selected Areas in Cryptography, pages 114–133. Springer Berlin Heidelberg, 2007. [21] N. A. Howgrave-Graham and N. P. Smart. Lattice attacks on digital signature schemes. Designs, Codes and Cryptography, 23(3):283–290, 2001. [22] H. W. Lenstra, A. K. Lenstra, L. Lovfiasz, et al. Factoring polynomials with rational coeficients. Mathematische Annalen, 261, 1982. [23] W.C. W. Li, M. Näslund, and I. E. Shparlinski. Hidden number problem with the trace and bit security of xtr and luc. In Advances in Cryptology — CRYPTO 2002, pages 433–448. Springer Berlin Heidelberg, 2002. [24] S. Ling, I. E. Shparlinski, R. Steinfeld, and H. Wang. On the modular inversion hidden number problem. Journal of Symbolic Computation, 47(4):358–367, 2012. [25] E. E. Mahassni, P. Q. Nguyen, and I. E. Shparlinski. The insecurity of nyberg-rueppel and other dsa-like signature schemes with partially known nonces. In Cryptography and Lattices, pages 97–109. Springer Berlin Heidelberg, 2001. [26] D. Naccache, P. Q. Nguyên, M. Tunstall, and C. Whelan. Experimenting with faults, lattices and the dsa. In Public Key Cryptography PKC 2005, pages 16–28. Springer Berlin Heidelberg, 2005. [27] P. Q. Nguyen. The dark side of the hidden number problem: Lattice attacks on dsa. In Cryptography and Computational Number Theory, pages 321–330. Birkhäuser Basel, 2001. [28] P. Q. Nguyen and I. E. Shparlinski. The insecurity of the digital signature algorithm with partially known nonces. Journal of Cryptology, 15(3), 2002. [29] P. Q. Nguyen and I. E. Shparlinski. The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Designs, codes and cryptography, 30(2):201–217, 2003. [30] D. Poulakis. Some lattice attacks on dsa and ecdsa. Appl. Algebra Eng., Commun. Comput., 22(5–6):347–358, 2011. [31] D. Poulakis. New lattice attacks on dsa schemes. Journal of Mathematical Cryptology, 10:135–144, 2016. [32] K. Ryan. Hardware-backed heist: Extracting ecdsa keys from qualcomm’s trustzone. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 181–194, 2019. [33] C.P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical computer science, 53(23):201–224, 1987. [34] B. Shani. On the bit security of elliptic curve diffie–hellman. In PublicKey Cryptography – PKC 2017, pages 361–387. Springer Berlin Heidelberg, 2017. [35] I. E. Shparlinski. On the generalised hidden number problem and bit security of xtr. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pages 268–277. Springer Berlin Heidelberg, 2001. [36] The Sage Developers. SageMath, the Sage Mathematics Software System (Version 8.7), 2019. https://www.sagemath.org. [37] J. van de Pol, N. P. Smart, and Y. Yarom. Just a little bit more. In Topics in Cryptology — CTRSA 2015, pages 3–21. Springer Cham, 2015. [38] W. Wei, J. Chen, D. Li, and B. Wang. Partially known information attack on sm2 key exchange protocol. Science China Information Sciences, 62(3):32105, 2019. [39] J. Xu, S. Sarkar, L. Hu, Z. Huang, and L. Peng. Solving a class of modular polynomial equations and its relation to modular inversion hidden number problem and inversive congruential generator. Designs, Codes and Cryptography, 86 (9):1997–2033, 2018. [40] J. Xu, S. Sarkar, L. Hu, H. Wang, and Y. Pan. New results on modular inversion hidden number problem and inversive congruential generator. In Advances in Cryptology – CRYPTO 2019, pages 297–321. Springer Cham, 2019. [41] F. Zhang. Bit security of the hyperelliptic curves diffie-hellman problem. In Provable Security, pages 219–235. Springer Cham, 2017. [42] K. Zhang, S. Xu, D. Gu, H. Gu, J. Liu, Z. Guo, R. Liu, L. Liu, and X. Hu. Practical partial-nonce-exposure attack on ecc algorithm. In 2017 13th International Conference on Computational Intelligence and Security (CIS), pages 248 -252. IEEE, 2017. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/76968 | - |
| dc.description.abstract | 1996 年，Boneh 和Venkatesan 提出隱藏數問題，並在位元安全性和隱藏數問題之間建立聯繫。隱藏數問題最初用於證明一些密碼架構的位安全性。然而，隱藏數問題也被用於攻擊數位簽章演算法。在特定情況下，我們可以藉助晶格縮減、最接近向量問題演算法和特定假設來恢復私鑰。本文旨在實現基於隱藏數問題在特定密鑰交換協定、數位簽章演算法(DSA) 和橢圓曲線數位簽章算法（ECDSA）上的晶格攻擊。 | zh_TW |
| dc.description.abstract | In 1996, Boneh and Venkatesan introduced the Hidden Number Problem (HNP) and built the connection between bit security and HNP. The HNP was originally used in the proof of the bit security of several cryptographic schemes. Nevertheless, the HNP was also applied to break the certain digital signature schemes. In the particular situation, we can recover the private key with help of the lattice reduction, closest vector problem (CVP) algorithms, and specific assumptions. In this paper, we aim to implement the lattice attack based on HNP against the certain key exchange protocol, digital signature algorithm (DSA), and elliptic curve digital signature algorithm (ECDSA). | en |
| dc.description.provenance | Made available in DSpace on 2021-07-10T21:41:54Z (GMT). No. of bitstreams: 1 U0001-3107202015553600.pdf: 641719 bytes, checksum: c9d80e37f2121daf3eaf4c70262c8a5c (MD5) Previous issue date: 2020 | en |
| dc.description.tableofcontents | 誌謝 iii 摘要 v Abstract vii 1 Introduction 1 2 Preliminaries 5 2.1 Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Basic definitions and properties . . . . . . . . . . . . . . . . . . 5 2.1.2 Shortest vector problem and Closest vector problem . . . . . . . 7 2.1.3 Lattice Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.4 Babai’s nearest plane algorithm . . . . . . . . . . . . . . . . . . 8 2.2 Elliptic curve digital signature algorithm (ECDSA) . . . . . . . . . . . . 9 2.3 Edwardscurve Digital Signature Algorithm (EdDSA) . . . . . . . . . . 10 2.4 Specific ECC algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.1 Specific ECC signature algorithm . . . . . . . . . . . . . . . . . 12 2.4.2 Specific ECC key exchange protocol . . . . . . . . . . . . . . . 14 3 Hidden Number Problem (HNP) 17 3.1 The original Hidden Number Problem . . . . . . . . . . . . . . . . . . . 17 3.2 Extended Hidden Number Problem (EHNP) . . . . . . . . . . . . . . . . 22 4 Applications of HNP 29 4.1 The Lattice Attack on ECDSA and EdDSA . . . . . . . . . . . . . . . . 30 4.2 The Lattice Attack on Specific ECC signature algorithm . . . . . . . . . 33 4.3 The Lattice Attack on Specific ECC key exchange protocol . . . . . . . . 35 4.3.1 Recover LSBs of private key . . . . . . . . . . . . . . . . . . . . 35 4.3.2 Recover MSBs of private key . . . . . . . . . . . . . . . . . . . 37 5 Experiments 41 5.1 Experiment Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6 Conclusion 47 References 49 Appendix A. 55 Appendix B. 59 | |
| dc.language.iso | en | |
| dc.subject | 隱藏數問題 | zh_TW |
| dc.subject | 晶格縮減 | zh_TW |
| dc.subject | 最短向量問題 | zh_TW |
| dc.subject | 橢圓曲線數位簽章 | zh_TW |
| dc.subject | 最接近向量問題 | zh_TW |
| dc.subject | 晶格攻擊 | zh_TW |
| dc.subject | Hidden number problem | en |
| dc.subject | Lattice reduction | en |
| dc.subject | Lattice attack | en |
| dc.subject | Closest vector problem (CVP) | en |
| dc.subject | Shortest vector problem (SVP) | en |
| dc.subject | ECDSA | en |
| dc.title | 基於隱藏數問題在(EC)DSA 上的部份洩漏攻擊 | zh_TW |
| dc.title | Partially Leakage Attacks against (EC)DSA based on the Hidden Number Problem | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 108-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳君朋(Jiun-peng Chen),陳榮傑(Rong-Jaye Chen),謝致仁(Jyh-Ren Shieh),楊柏因(Bo-Yin Yang) | |
| dc.subject.keyword | 隱藏數問題,晶格縮減,晶格攻擊,最接近向量問題,最短向量問題,橢圓曲線數位簽章, | zh_TW |
| dc.subject.keyword | Hidden number problem,Lattice reduction,Lattice attack,Closest vector problem (CVP),Shortest vector problem (SVP),ECDSA, | en |
| dc.relation.page | 74 | |
| dc.identifier.doi | 10.6342/NTU202002164 | |
| dc.rights.note | 未授權 | |
| dc.date.accepted | 2020-08-03 | |
| dc.contributor.author-college | 理學院 | zh_TW |
| dc.contributor.author-dept | 數學研究所 | zh_TW |
| 顯示於系所單位： | 數學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-3107202015553600.pdf 未授權公開取用 | 626.68 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。