應用中國餘數定理之RSA與指數運算之錯誤攻擊分析

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：73

、訪客IP：18.221.52.77

姓名

吳啟典(Chi-Dian Wu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

應用中國餘數定理之RSA與指數運算之錯誤攻擊分析
(Fault Cryptanalysis of RSA with Chinese Remainder Theorem and Exponentiation)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

隨著電腦與網路科技的進步，許多電子消費系統已經被廣泛地應用在我們日常生活之中，這些系統需要透過網路傳遞大量的資訊，為了保護個人資料與隱私，資訊安全的重要性逐漸地受到大家的重視。
自從Bellcore實驗室於1996年提出錯誤攻擊之後，此攻擊已經對密碼系統的實作造成重大的威脅，尤其是實作在智慧卡上之系統。到目前為止，許多常用的密碼系統皆被證實會遭受到錯誤攻擊，為了維護安全性，在實作密碼系統時我們必需考慮如何防禦錯誤攻擊。
RSA是一個被廣泛使用的密碼系統，利用中國餘數定理（CRT）可以加速RSA的運算，然而CRT -RSA卻會遭受到錯誤攻擊，造成模數N被輕易地分解。錯誤傳染（fault infection）是種防禦錯誤攻擊的方式，此方式可以移除檢查程序會遭受錯誤攻擊的危機。在本論文的第一部分，我們將先分析舊有錯誤傳染防禦法之缺點，然後根據這些缺失設計新的防禦法，新的防禦法將可以抵擋已被提出的錯誤攻擊方式。
指數運算是許多公開金鑰密碼系統的核心運算，也和系統的安全性息息相關。過去有不少針對右到左指數運算演算法的錯誤攻擊被提出，在本論文的第二部分，我們將舊有的錯誤攻擊方式經改良後，延伸來攻擊左到右指數運算演算法，而改良過後的錯誤攻擊也能適用於Montgomery ladder指數運算演算法。

摘要(英)

With the growing of computer technology and networks, many applications, such as micropayment and on-line shopping, have been widely used in our daily life. These applications need to transport much information through the Internet connections. Consequently, to protect personal secrets and privacy, the security has become more and more important.
Since Bellcore laboratory proposed the fault attacks, the fault attacks have become serious threats to the implementation of cryptography, especially on smart cards, and many kinds of fault attacks have been proposed to break various cryptosystems. For security, to resist fault attacks is an important thing when implementing cryptosystems.
RSA is a widely used cryptosystem nowadays, and an efficient method to speed up the computation of RSA is using Chinese Remainder Theorem (CRT). However, it has been presented that the RSA modulus N can be factored easily under fault attacks on CRT-RSA. Many countermeasures have been proposed, and the fault infection is a kind of method which can remove the danger of fault attacks against checking procedures. However, most countermeasures based on fault infection have been proved insecure. In this thesis, we will first show that the Yang et al.’’s countermeasure based on fault infection is still insecure, and then propose two countermeasures with secure fault infective computation. We prove that our countermeasures can resist all known fault attacks against CRT-RSA. Moreover, the proposed infective computation can combine with other fast checking methods to improve the efficiency.
The exponentiation (or scalar multiplication on ECC) is a critical operation in most publickey cryptosystems. Some fault attacks against the exponentiation or the scalar multiplication have been proposed. In this thesis, based on the previous fault attacks against right-to-left exponentiation, we propose an extended fault attack against the left-to-right exponentiation (or scalar multiplication) on discrete logarithm based publickey cryptosystems. Our attack can also extend to the Montgomery ladder algorithm.

關鍵字(中)

★ 指數運算
★ 錯誤攻擊
★ 中國餘數定理

關鍵字(英)

★ CRT
★ exponentiation
★ fault attack
★ RSA

論文目次

1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Review of Public Key Cryptography 5
2.1 RSA and Chinese Remainder Theorem . . . . . . . . . . . . . . . . . 5
2.2 Publickey Cryptosystems Based on Discrete Logarithms . . . . . . . . 6
2.3 Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Review of Fault Attacks against CRT-RSA 11
3.1 FaultModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Fault Attacks against CRT-RSA . . . . . . . . . . . . . . . . . . . . . 12
3.3 Countermeasures against Fault Attacks on CRT-RSA . . . . . . . . . 13
3.3.1 Extended Modulus Based Countermeasures . . . . . . . . . . 13
3.3.2 Self-secure Exponentiation . . . . . . . . . . . . . . . . . . . . 14
3.4 Fault Infection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4.1 CRT-1 and CRT-2 Protocols . . . . . . . . . . . . . . . . . . . 16
3.4.2 BOS Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4.3 Ciet and Joye’s Algorithm . . . . . . . . . . . . . . . . . . . . 19
3.4.4 Yang et al.’s Algorithm . . . . . . . . . . . . . . . . . . . . . . 20
4 Secure Fault Infective Computation on CRT-RSA 22
4.1 Fault Cryptanalysis of Yang et al.’s Countermeasure . . . . . . . . . . 22
4.2 Two New Countermeasures with Secure Infective Computation . . . . 24
4.3 Security Analysis of Algorithm 1 . . . . . . . . . . . . . . . . . . . . 25
4.4 Security Analysis of Algorithm 2 . . . . . . . . . . . . . . . . . . . . 28
4.5 Performance and Comparison . . . . . . . . . . . . . . . . . . . . . . 29
4.6 Combination with Fast Checking Mechanisms . . . . . . . . . . . . . 30
5 Extended Differential Fault Attacks against Exponentiation 33
5.1 Review of Fault Attacks against Exponentiation . . . . . . . . . . . . 33
5.1.1 Fault Attack on Exponent . . . . . . . . . . . . . . . . . . . . 33
5.1.2 Bellcore’s DFA against Right-to-left Exponentiation Algorithm 34
5.1.3 Berzati et al.’s Differential Fault Attack . . . . . . . . . . . . 35
5.2 Proposed Differential Fault Attack . . . . . . . . . . . . . . . . . . . 36
5.2.1 FaultModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2.2 Principle of the Proposed DFA . . . . . . . . . . . . . . . . . 37
5.2.3 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.3 Extension to Montgomery Ladder . . . . . . . . . . . . . . . . . . . . 39
6 Conclusions 43
6.1 Review of Main Contribution . . . . . . . . . . . . . . . . . . . . . . 43
6.2 Further Research Topics and Directions . . . . . . . . . . . . . . . . . 43

參考文獻

[1] C. Aumuller, P. Bier, W. Fischer, P. Hofreiter, and J.P. Seifert, "Fault Attacks on RSA with CRT: Concrete Results and Practical countermeasures," CHES 2002, LNCS 2523, pp. 260--275, Springer-Verlag, 2003.
[2] R. J. Anderson and M. G. Kuhn, "Tamper Resistance - a Cautionary Note," Second USENIX, pp. 1--11, 1996.
[3] R. J. Anderson and M. G. Kuhn, "Low Cost Attacks on Tamper Resistant Devices," International Workshop on Security Protocols 1997, LNCS 1361, pp. 125--136, Springer, 1997.
[4] Z. Abid and W. Wang, "Countermeasures for Hardware Fault Attack in Multi-Prime RSA Cryptosystems," International Journal of Network Security, Vol. 6, No. 2, pp. 190--200, 2008.
[5] A. Berzati, C. Canovas, and L. Goubin, "(In)security Against Fault Injection Attacks for CRT-RSA Implementations," Proc. of the Workshop on Fault Diagnosis and Tolerance in Cryptography--FDTC 2008, pp. 101--107, 2008.
[6] A. Berzati, C. Canovas, and L. Goubin, "Perturbing RSA Public Keys: An Improved Attack," CHES 2008, LNCS 5154, pp. 380--395, Springer-Verlag, 2008.
[7] H. Bar-El, H. Choukri, D. Naccache, M. Tunstall, and C. Whelan, "The Sorcerer's Apprentice Guide to Fault Attacks," Proc. of the Workshop on Fault Diagnosis and Tolerance in Cryptography--FDTC 2004, pp. 330--342, 2004.
[8] H. Bar-El, H. Choukri, D. Naccache, M. Tunstall, and C. Whelan, "The Sorcerer's Apprentice Guide to Fault Attacks," Proceedings of the IEEE, Vol. 94, No. 2, pp. 370--382, 2006.
[9] F. Bao, R.H. Deng, Y. Han, A. Jeng, A.D. Narasimbalu, and T. Ngair, "Breaking Public Key Cryptosystems on Tamper Resistant Devices in the Presence of Transient Faults," Security Protocols Workshop 1997, LNCS 1361, pp. 115--124, Springer-Verlag, 1998.
[10] D. Boneh, R. A. DeMillo, and R. J. Lipton, "On the Importance of Checking Cryptographic Protocols for Faults," EUROCRYPTO'97, LNCS 1233, pp. 37--51, Springer-Verlag, 1997.
[11] I. Biehl, B. Meyer, and V. Muller, "Differential Fault Attacks on Elliptic Curve Cryptosystems," CRYPTO 2000, LNCS 1880, pp. 131--146, Springer-Verlag, 2000.
[12] A. Boscher, R. Naciri, and E. Prouff, "CRT RSA Algorithm Protected Against Fault Attacks," WISTP 2007, LNCS 4462, pp. 229--243, Springer-Verlag, 2007.
[13] J. Blomer, M. Otto, and J.-P. Seifert, "A New CRT-RSA Algorithm Secure Against Bellcore Attacks," ACM CCS 2003, pp. 311--320, ACM Press, 2003.
[14] J. Blomer, M. Otto, and J.P. Seifert, "Sign change Fault Attacks on Elliptic Curve Cryptosystems," Proc. of the Workshop on Fault Diagnosis and Tolerance in Cryptography--FDTC 2006, LNCS 4236, pp. 36-52, Springer-Verlag, 2006.
[15] E. Biham and A. Shamir, "Differential Fault Analysis of Secret Key Cryptosystems," CRYPTO 1997, LNCS 1294, pp. 513--525, Springer-Verlag, 1997.
[16] M. Ciet and M. Joye, "Practical Fault Countermeasures for Chinese Remaindering Based RSA," Proc. of the Workshop on Fault Diagnosis and Tolerance in Cryptography--FDTC 2005, pp. 124--132, 2005.
[17] W. Diffie and M.E. Hellman, "Multiuser Cryptographic Techniques," AFIPS National Computer Conference, Vol. 45, pp. 109--112, 1976.
[18] W. Diffie and M.E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory, Vol. 22, No. 6, pp. 644--654, 1976.
[19] T. ElGamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms," CRYPTO'84, pp. 10--18, Springer-Verlag, 1985.
[20] C. Giraud, "An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis," IEEE Transactions on Computers, Vol. 55, No. 9, pp. 1116--1120, 2006.
[21] D.M. Gordon, "A Survey of Fast Exponentiation Methods," Journal of Algorithms, Vol. 27, pp. 129-146, 1998.
[22] M. Joye, A.K. Lenstra, and J.-J. Quisquater," Chinese Remaindering Based Cryptosystems in the Presence of Faults," Journal of Cryptology, Vol. 12, no. 4, pp. 241--245, Springer-Verlag, 1999.
[23] M. Joye, J.J. Quisquater, F. Bao, and R.H. Deng, "RSA-type Signatures in the Presence of Transient Faults," Cryptography and Coding 1997, LNCS 1355, pp. 155--160, Springer-Verlag, 1997.
[24] M. Joye and S.M. Yen, "The Montgomery Powering Ladder," CHES2002, LNCS 2523, pp. 291--302, Springer-Verlag, 2002.
[25] C.H. Kim and J.-J. Quisquater,"Fault Attacks for CRT Based RSA: New Attacks, New Results, and New Countermeasures," WISTP 2007, LNCS 4462, pp. 215--228, 2007.
[26] N. Koblitz, "Elliptic curve cryptosystems," Mathematics of Computation, Vol. 48, pp. 203--209, 1987.
[27] P. Kocher, "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems," Advanced in Cryptology - CRYPTO'96, LNCS 1109, pp. 104--113, Springer-Verlag, 1996.
[28] P. Kocher, J. Jaffe, and B. Jun, "Differential Power Analysis," Advanced in Cryptology - CRYPTO'99, LNCS 1666, pp. 388--397, Springer-Verlag, 1999.
[29] V.S. Miller, "Use of elliptic curves in cryptography," Advanced in Cryptology - CRYPTO'85, LNCS 218, pp. 417--426, Springer-Verlag, 1986.
[30] P.L. Montgomery, "Speeding the Pollard and Elliptic Curve Methods of Factorization," Mathematics of Computation, Vol. 48, pp. 243--264, 1987.
[31] M. Rivain, "Securing RSA against Fault Analysis by Double Addition Chain Exponentiation," CT-RSA 2009, LNCS 5473, pp. 459--480, Springer-Verlag, 2009.
[32] R. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public Key Cryptosystems," Comm. of the ACM, Vol. 21, No. 2, pp. 120--126, 1978.
[33] A. Shamir, "Method and Apparatus for Protecting Public Key Schemes from Timing and Fault Attacks," United States Patent 5991415, 1999.
[34] C.P. Schnorr, "Efficient Identification and Signatures for Smart Cards," Advanced in Cryptology - Crypto'89, LNCS 435, pp. 239--252, Springer-Verlag, 1990.
[35] Sun Microsystems, "Application Programming Interface - Java Card Plateform," version 2.2.2, http://java.sun.com/products.havacard.soecs.html, 2006.
[36] D. Vigilant, "RSA with CRT: A New Cost-Effective Solution to Thwart Fault Attacks," CHES 2008, LNCS 5154, pp. 130--145, Springer-Verlag, 2008.
[37] D. Wagner, "Cryptabalysis of a Provably Secure CRT-RSA Algorithm," ACM CCS'04, pp. 311--320, ACM press, 2004.
[38] Y. Yang, Z. Abid, and W. Wang, "Two-Prime RSA Immune Cryptosystem and Its FPGA Implementation," GLSVLSI'05, pp. 164--167, ACM press, 2005.
[39] Y. Yang, Z. Abid, W. Wang, Z. Zhang, and C. Yang, "Efficient Multi-Prime RSA Immune Against Hardware Fault Attack," ISCAS 2005, pp. 4649--4652, 2005.
[40] S.M. Yen and D. Kim, "Cryptanalysis of Two Protocols for RSA with CRT Based on Fault Infection," Proc. of the Workshop on Fault Diagnosis and Tolerance in Cryptography--FDTC 2004, pp. 381--385, 2004.
[41] S.M. Yen, S. Kim, S. Lim, and S. Moon, "RSA Speedup with Residue Number System Immune Against Hardware Fault Cryptanalysis," ICISC 2001, LNCS 2288, pp. 397--413, Springer-Verlag, 2002.
[42] S.M. Yen and C.S. Laih, "Fast Algorithm for the LUC Digital Signature Computation," IEE proceedings: Computers and Digital Techniques, Vol. 142, No. 2, pp. 165--169, 1995.

指導教授

顏嵩銘(Sung-Ming Yen)

審核日期

2010-12-6

推文