橢圓曲線密碼系統之計算加強研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：78

、訪客IP：3.17.76.174

姓名

吳柏青(Bo-Ching Wu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

橢圓曲線密碼系統之計算加強研究
(Enhancement on Scalar Multiplication in Elliptic Curve Cryptosystems)

相關論文

★ 多種數位代理簽章之設計	★ 小額電子支付系統之研究
★ 實體密碼攻擊法之研究	★ 商業性金鑰恢復與金鑰託管機制之研究
★ AES資料加密標準之實體密碼分析研究	★ 電子競標系統之研究
★ 針對堆疊滿溢攻擊之動態程式區段保護機制	★ 通用型數域篩選因數分解法之參數探討
★ 於8051單晶片上實作可防禦DPA攻擊之AES加密器	★ 以非確定式軟體與遮罩分割對策防禦能量攻擊之研究
★ 遮罩保護機制防禦差分能量攻擊之研究	★ AES資料加密標準之能量密碼分析研究
★ 小額電子付費系統之設計與密碼分析	★ 公平電子現金系統之研究
★ RSA公開金鑰系統之實體密碼分析研究	★ 保護行動代理人所收集資料之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

近十年來，橢圓曲線密碼系統逐漸受到許多重視，與其他公開金鑰密碼系統相較，如RSA公開金鑰密碼系統，橢圓曲線密碼系統可採用更短長度之金鑰而達成相同安全等級，因此更適用於計算資源有限的裝置，例如智慧卡。然而，當橢圓曲線密碼系統被實作於這類裝置時，必須考量採取有效率的計算方法，以及顧及是否會遭受到基於硬體特性設計之攻擊法。
在橢圓曲線密碼系統中，最重要的核心計算為純量乘積計算，本篇論文研究將探討純量乘積計算之相關主題，並且廣泛討論編碼技術、效率分析、效率提升、物理攻擊法與其防禦法等等。這些主題將分為三大主題深入探討，並且提出改進方法。
首先探討編碼技術應用於純量乘積計算。為了觀察編碼技術之行為，通常會採用機率分析法，而傳統機率分析法其估計結果具有錯誤偏差之現象，因此我們改良傳統分析法，並且提出精確分析法。
在第二部分探討如何在橢圓曲線密碼系統加速計算。我們將利用合併點運算以及運算操作之技巧去加速純量乘積計算，與Han等人之方法相較，所提出之計算加速方法可提升效率31.836%。此外我們也利用合併點運算去建立更有計算效率之防禦法，可用來抵禦簡單能量攻擊法，與 Coron之防禦方法相較，所提出之防禦法可提升45.553%計算效率。
在第三部分將探討資料碰撞式能量攻擊法。Kim 等人提出了兩倍攻擊法針對 Yen 等人之防禦法進行攻擊，他們所提出之攻擊法仍需要20.35n次數搜尋金鑰。因此我們提出改良之攻擊法，可以更有效率直接揭露密碼系統所使用的金鑰。並且我們在8051單晶片上實作能量量測，去驗證攻擊法所基於的資料碰撞假設可以被實現。在我們的研究指出，由左到右計算之演算法皆遭受到所提出兩倍攻擊法的威脅，因此，基於Yen等人演算法，我們提出由右到左計算之變形來抵禦兩倍攻擊法。

摘要(英)

For decade, elliptic curve cryptosystems (ECCs) have received a lot of attention due to having the ability to provide an equivalent security level with a smaller key size in comparison with other public key cryptosystems such as RSA. Hence, in terms of memory storage, it is attractive to apply ECCs to resource-constrained devices like smart cards. While an ECC is operated in such low speed devices, efficient computations are urgently required, and security issues should be reconsidered especially for some attacks based on special-purpose hardware.
This thesis primarily revolves around the topics related to scalar multiplication, the most essential computation of ECCs. The arithmetic of ECCs, recoding techniques, performance analysis, performance enhancement, side-channel attacks and countermeasures are extensively discussed in this thesis. These related topics are divided into three main subjects in which we will investigate the matters in detail and then propose novel methods for enhancement.
First, recoding techniques applied to scalar multiplication in ECCs are discussed. In order to investigate behaves of recoding systems, a probability analysis is usually employed for analysis, but its analysis results often have bias in error estimation. Hence we propose a precise analysis to replace the traditional one.
In the second subject, how to improve the performance of scalar multiplication in ECCs will be discussed. We propose a fast scalar multiplication method by utilizing the merged point operations, and a trick called EOSR for manipulating operation sequence. Compared with the work presented by Han et al., the proposed method yields 31.836% improvement. Additionally, an efficient SPA countermeasure based on the merged operations is proposed, and it is significantly better than Coron’’s double-and-add-always algorithm by at least 45.553% in performance.
In the third subject, we explore data collision-based power attacks. Kim et al. proposed a doubling attack against the Yen-Lu-Tseng downward algorithm, but their attack on average required 2^{0.35n} operations to test key candidates. Thus, we provide an enhanced doubling attack which can efficiently and directly reveal all the secret key bits. Moreover, an experiment on an 8051 compatible microcontroller is conducted to show that the data collision assumption which our proposed doubling attack is based on can be realized. Our study indicates that almost all the left-to-right algorithms are vulnerable to the proposed attack. Therefore, an upward variant of the Yen-Lu-Tseng algorithm against doubling attacks is proposed.

關鍵字(中)

★ 橢圓曲線密碼系統
★ 純量乘積
★ 公開金鑰密碼系統.

關鍵字(英)

★ elliptic curve cryptosystems
★ scalar multiplication
★ public key cryptosystems

論文目次

1 Introduction (1)
1.1 Motivation (1)
1.2 Overview of the Thesis (2)
2 Preliminary (4)
2.1 Elliptic Curves and Scalar Multiplication (4)
2.2 Side-Channel Attacks (5)
2.3 Doubling Attacks (6)
2.4 Relative Doubling Attacks (8)
3 Precise Analysis of Recoding (11)
3.1 Radix-r Representation (12)
3.2 The Markov Model of gNAF (13)
3.2.1 The Simplified Markov Model (15)
3.2.2 The Last Three Steps (17)
3.3 Precise Estimators (18)
3.3.1 Hamming Weight Estimator (18)
3.3.2 Significant Length Estimator (19)
3.4 Experimental Result (20)
4 Efficiency Improvement on Scalar Multiplication (22)
4.1 Review of Merged Point Operations (23)
4.2 EOSR for Yen-Lu-Tseng Algorithm (24)
4.3 Fast Scalar Multiplication 25
4.3.1 Improvement on D.G. Han et al.'s Work (26)
4.3.2 Doubling-Run Length Enhancement (27)
4.3.3 Performance Analysis (28)
4.4 Efficient SPA Countermeasure (31)
4.4.1 Proposed SPA Countermeasure in Affine Coordinates (32)
4.4.2 Performance Analysis (33)
5 Data Collision-Based Power Analysis Attacks (34)
5.1 Review of Kim et al.'s Work (35)
5.1.1 Kim et al.'s Analysis (35)
5.1.2 Kim et al.'s Doubling Attack (37)
5.2 Proposed Enhanced Doubling Attack (40)
5.3 Experiment for Data Collision (42)
5.4 Proposed Upward Variant of Yen-Lu-Tseng Algorithm (47)
6 Conclusion (52)

參考文獻

[1] D. Boneh, and M. Franklin, "Identity-based encryption from the Weil pairing," In Advances in Cryptology - CRYPTO 2001, LNCS 2139, pp. 213-229, Springer-Verlag, 2001.
[2] M. Brown, D. Hankerson, J. Lopez, and A. Menezes, "Software implementation of the NIST elliptic curves over prime fields," In Topics in Cryptology - CT-RSA 2001, LNCS 2020, pp. 250-265, Springer-Verlag, 2001.
[3] E. Brier, and M. Joye, "Weierstrass elliptic curves and side-channel attacks," In Public Key Cryptography - PKC 2002, LNCS 2274, pp. 335-345, Springer-Verlag, 2002.
[4] B. Chevallier-Mames, M. Ciet, and M. Joye, "Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity," In IEEE Trans. Computers, Vol. 53, No. 6, pp. 760-768, 2004.
[5] J. Cathalo, F. Koeune, and J.J. Quisquater, "A mew type of timing attack: application to GPS," In Cryptographic Hardware and Embedded Systems - CHES 2003, LNCS 2779, pp.291-303, Springer-Verlag, 2003.
[6] W. Clark, and J. Liang, "On arithmetic weight for a general radix representation of integers," In IEEE Transactions on Information Theory, IT-19, pp.823-826, 1973.
[7] M. Ciet, M. Joye, and K. Lauter, "Trading inversions for multiplications in elliptic curve cryptography," In Designs, Codes and Cryptography, Vol. 39, No. 2, 2006.
[8] J.S. Coron, "Resistance against differential power analysis for elliptic curve cryptosystems," In Cryptographic Hardware and Embedded Systems - CHES '99, LNCS 1717, pp. 292-302, Springer-Verlag, 1999.
[9] M. Ciet, G. Piret, and J.J. Quisquater, "Several optimizations for elliptic curves implementation on smart card," UCL Crypto Group Technical Report Series, 2001. Available at http://www.dice.ucl.ac.be/crypto/
[10] N. Ebeid, and A. Hasan, "On randomizing private keys to counteract DPA attacks," Technical reports, 2003. Available at http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-11.ps
[11] P.A. Fouque, and F. Valette, "The Doubling Attack - Why Upwards is Better than Downwards," In Cryptographic Hardware and Embedded Systems - CHES 2003, LNCS 2779, pp. 269-280, Springer-Verlag, 2003.
[12] J. Guajardo, and C. Paar, "Efficient algorithms for elliptic curve cryptosystems," In Advances in Cryptology - CRYPTO '97, LNCS 1294, pp. 342-356, Springer-Verlag, 1997.
[13] D.G. Han, T. Izu, and T. Takagi, "Some explicit formulae of NAF and its left-to-right analogue," In ePrint Archive, eprint 2005/384, 2005. Available at http://eprint.iacr.org/2005/384.pdf
[14] J.C. Ha, and S.J. Moon, "Randomized signed-scalar multiplication of ECC to resist power attack," In Cryptographic Hardware and Embedded Systems - CHES 2002, LNCS 2523, pp. 551-563, Springer-Verlag, 2003.
[15] D.G. Han, and T. Takagi, "Some analysis of radix-$r$ representations," In Cryptology ePrint Archive, Report No.402, 2005. Available at http://eprint.iacr.org/2005/402.pdf
[16] M. Joye, and J.J. Quisquater, "Hessian elliptic curves and side-channel attacks," In Cryptographic Hardware and Embedded Systems - CHES 2001, LNCS 2162, pp. 412-420, Springer-Verlag, 2001.
[17] M. Joye, and S.M. Yen, "Optimal left-to-right binary signed-digit recoding," In IEEE Transactions on Computers, Vol. 49, No. 7, pp. 740-748, 2000.
[18] M. Joye, and S.M. Yen, "New minimal modified radix-$r$ representation with applications to smart cards," In Public Key Cryptography - PKC 2002, LNCS 2002, pp. 375-383, Springer-Verlag, 2002.
[19] M. Joye, and S.M. Yen, "The Montgomery Powering Ladder," In Cryptographic Hardware and Embedded Systems - CHES 2002, LNCS 2523, pp. 291-302, Springer-Verlag, 2003.
[20] S.K. Kim, D.G Han, H.W. Kim, K.U. Chung, and J. Lim, "SPA countermeasure based on unsigned left-to-right recodings", In Autonomic and Trusted Computing - ATC 2007, LNCS 4610, pp. 286-295, Springer-Verlag, 2007.
[21] P. Kocher, J. Jaffe, and B. Jun, "Differential power analysis," In Advances in Cryptology - CRYPTO '99, LNCS 1666, pp. 388-397, Springer-Verlag, 1999.
[22] D.E. Knuth, "The art of computer programming - Vol. 2 Seminumerical Algorithms (3rd ed.)," Addison-Wesley, 1998.
[23] N. Koblitz, "Elliptic curve cryptosystems," In Mathematics of Computation, Vol. 48, pp. 203-209, 1987.
[24] C.H. Kim, and J.J. Quisquater, "Method for detecting vulnerability to doubling attacks," In 10th International Conference on Information and Communications Security - ICICS 2008, LNCS 5308, pp. 97-110, Springer-Verlag, 2008.
[25] V.G. Kulkarni, "Modeling, analysis, design, and control of stochastic systems," Springer-Verlag, 1999.
[26] C. Karlof, and D. Wangner, "Hidden markov model cryptanalysis," In Cryptographic Hardware and Embedded Systems - CHES 2003, LNCS 2779, pp. 17-34, Springer-Verlag, 2003.
[27] C.H. Lim, "A new method for securing elliptic scalar multiplication against side-channel attack," In Information Security and Privacy: 9th Australasian Conference - ACISP 2004, LNCS 3108, pp. 289-300, Springer-Verlag, 2004.
[28] V.S. Miller, "Use of elliptic curve in cryptography," In Advances in Cryptology - CRYPTO '85, LNCS 218, pp. 417-426, Springer-Verlag, 1986.
[29] B. Moller, "Securing elliptic curve point multiplication against side-channel attack," In Information Security - ISC 2001, LNCS 2200, pp. 324-334, Springer-Verlag, 2001.
[30] B. Moller, "Parallelizable elliptic curve point multiplication method with resistance against side-channel attacks," In Information Security Conference - ISC 2002, LNCS 2433, pp. 402-413, Springer-Verlag, 2002.
[31] B. Moller, "Improved techniques for fast exponentiation," In Information Security and Cryptology - ICISC 2002, LNCS 2587, pp. 298-312, Springer-Verlag, 2003.
[32] E. Oswald, "Enhancing simple power-analysis attacks on elliptic curve cryptosystems," In Cryptographic Hardware and Embedded Systems - CHES 2002, LNCS 2523, pp. 82-97, Springer-Verlag, 2003.
[33] K. Okeya, and T. Takagi, "The width-$w$ NAF method provides small memory and fast elliptic scalar multiplications secure against side channel attacks," In Topics in Cryptology - CT-RSA 2003, LNCS 2612, pp. 328-342, Springer-Verlag, 2003.
[34] G.W. Reitwiesner, "Binary arithmetic," In Advances in Computers, Vol. 1, pp. 231-308, 1960.
[35] Y. Sakai, and K. Sakurai, "On the power of multidoubling in speeding up elliptic scalar multiplication," In Selected Areas in Cryptography - SAC 2001, LNCS 2259, pp. 268-283, Springer-Verlag, 2001.
[36] Y. Sakai, and K. Sakurai, "Efficient scalar multiplications on elliptic curves with direct computations of several doublings," In IEICE Trans. Fundamentals, Vol. E84-A, No. 1, pp. 120-199, 2001.
[37] K. Schramm, T. Wollinger, and C. Paar, "A New Class of Collision Attacks and its Application to DES," In Fast Software Encryption - FSE 2003, LNCS 2887, pp. 206-222, Springer-Verlag, 2003.
[38] T. Takagi, S.M. Yen, and B.C. Wu, "Radix-r non-adjacent form," In Information Security, 7th International Conference - ISC 2004, LNCS 3225, pp. 99-110, Springer-Verlag, 2004.
[39] E.G. Thurber, "On addition chains $l(mn) leq l(n)-b$ and lower bounds for $c(r)$." In Duke Mathematical Journal, Vol. 40, No. 4, pp. 907-913, 1973.
[40] C. Vuillaume, and K. Okeya, "Flexible Exponentiation with Resistance to Side Channel Attacks," In Applied Cryptography and Network Security - ACNS 2006, LNCS 3989, pp. 268-283, Springer-Verlag, 2006.
[41] C.D. Walter, "Mist: An efficient, randomized exponentiation algorith for resisting power analysis," In Topics in Cryptology - CT-RSA 2002, LNCS 2271, pp. 53-66, Springer-Verlag, 2002.
[42] S.M. Yen, S.J. Kim, S.G. Lim, and S.J. Moon, "A countermeasure against one physical cryptanalysis may benefit another attack," In Information Security and Cryptology - ICISC 2002, LNCS 2288, pp. 414-427, Springer-Verlag, 2002.
[43] S.M. Yen, L.C. Ko, S. Moon, and J. Ha, "Relative doubling attack against Montgomery ladder," In ICISC 2005, LNCS 3935, pp.117-128, Springer-Verlag, 2006.
[44] S.M. Yen, C.C. Lu, and S.Y. Tseng, "Method for protecting public key schemes from timing, power, and fault attacks," U.S. Patent Number US2004/0125950 A1, 2004.

指導教授

顏嵩銘(Sung-Ming Yen)

審核日期

2010-7-14

推文