應用於RSA實作之能量攻擊與防禦措施之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：15

、訪客IP：18.225.95.186

姓名

邱志銘(Chih-Ming Chiu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

應用於RSA實作之能量攻擊與防禦措施之研究
(On the Research of Power Analysis and Countermeasure of RSA Implementations)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

傳統的密碼安全研究，只著重於密碼系統中的各類元件(primitive)在數學上的安全性。然而，實體密碼安全(physical security)的觀念被提出後，密碼系統的實作的安全分析開始受到重視，各類型的攻擊法及對應的防禦法相繼被提出。而指數運算是多數公開金鑰密碼系統的核心運算，因此對於公開金鑰密碼系統的實體密碼分析，多半著重於其中的指數運算演算法。
在此論文中，我們首先利用multi-exponentiation 及side-channel atomicity 的觀念，提出了一個高效率的指數運算防禦法。此指數運算防禦法可同時抵抗目前
已知的簡單能量攻擊法(SPA)及差分能量攻擊法(DPA)，同時此指數運算防禦法未
使用填充運算(dummy operation)，因此提出的指數運算防禦法也可抵抗計算安全錯誤攻擊法(C safe-error attack)。
根據相關文獻，有些防禦法的安全性仍然是有爭論的，隨著新的實體攻擊法相繼被提出，有些防禦法已無法防禦這些新的攻擊法。在此論文中，我們提出了一個新的能量攻擊法，利用統計上的差異，攻擊一種可抵抗差分攻擊法的從左到右隨機編碼防禦法。

摘要(英)

The security of classical cryptography depends on the difficult mathematical problems. However, when physical security is proposed, many researchers turn their attention to the implementations of cryptosystems, and related attacks and corre-sponding countermeasures are also proposed. In many public-key cryptosystems,
modular exponentiation is the main operation. Hence, the physical cryptanalysis about public-key cryptosystems always focus on modular exponentiation algorithm.
In this thesis, firstly, both techniques of multi-exponentiation and side-channel atomicity are employed to propose a more efficient exponentiation countermeasure. The proposed countermeasure can resist against SPA and DPA at the same time, and we also notice that the proposed countermeasure can be free from well known C safe-error attack.
According to related lectures, some countermeasures are still controversial and
insecure in advanced physical attacks. Hence, we point out one of the existent countermeasure is still insecure by the proposed new power analysis. In this thesis, we propose a new power analysis against left-to-right Ha-Moon’’s countermeasure which is based on a randomized binary signed digit representation to resist against differential power analysis.

關鍵字(中)

★ 差分能量攻墼法
★ 多指數運算
★ 簡單能量攻擊法
★ 能量攻擊法

關鍵字(英)

★ C safe-error attack
★ RSA
★ DPA
★ SPA
★ Power analysis
★ Multi-exponentiation
★ Side-channel atomicity

論文目次

1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Review of RSA Cryptosystem 5
2.1 Public-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . .5
2.2 RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Modular Exponentiation Algorithms . . . . . . . . . . . . . . . . . . .8
3 Review of Physical Cryptanalysis 11
3.1 Simple Power Analysis -- SPA . . . . . . . . . . . . . . . . . . . . .11
3.2 SPA Countermeasures . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Di®erential Power Analysis -- DPA . . . . . . . . . . . . . . . . . . 14
3.4 DPA Countermeasures . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.5 Computational Safe-error Attack -- C Safe-error Attack . . . . . . . .18
3.6 C Safe-error Attack Countermeasures . . . . . . . . . . . . . . . . . 20
4 Segment Exponentiation Countermeasure against Side-Channel Analysis 22
4.1Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Multi-Exponentiation . . . . . . . . . . . . . . . . . . . . .. . . . 22
4.3 Side-Channel Atomicity . . . . . . . . . . . . . . . . . . . . . . . 24
4.4 The Proposed Countermeasure by Segment Exponentiation . . . . . . . . 26
4.5 Security Analysis on The Proposed Countermeasure . . . . . . . . . . 29
4.6 Performance Analysis of The Proposed Countermeasure . . . . . . . . .30
4.7 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.8 Experimental Result . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5 A Power Analysis against Left-to-Right Ha-Moon's Countermeasure Based on
Randomized BSD 38
5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Non-adjacent Form -- NAF . . . . . . . . . . . . . . . . . . . . . . 39
5.3 Right-to-Left Ha-Moon's Countermeasure . . . . . . . . . . . . . . . 40
5.4 Left-to-Right Ha-Moon's Countermeasure . .. . . . . . . . . . . . . . 42
5.5 Proposed Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.5.1 Attack Model and Notation . . . . . . . . . . . . . . . . . . . 43
5.5.2 Main Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.5.3 Description of The Proposed Attack . . . . . . . . . . . . . . 45
5.5.4 Attacking Algorithm . . . . . . . . . . . . . . . . . . . . . . 46
5.6 Experimental Result and Analysis. . . . . . . . . . . . . . . . . . . 47
5.6.1 Experimental Result . . . . . . . . . . . . . . . . . . . . . . 47
5.6.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6 Conclusions 52
6.1 Brief Review of Main Contributions . . . . . . . . . . . . . . . . . 52
6.2 Future Research Topics and Directions . . . . . . . . . . . . . . . . . 53
7 Bibliography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55

參考文獻

[1] C. AumÄuller, P. Bier, W. Fischer, P. Hofreiter, and J. P.
Seifert, "Fault Attacks on RSA with CRT: Concrete Results and Practical
Countermeasures," In Cryptographic Hardware and Embedded Systems-
CHES'02, LNCS 2523, pp. 260-275, Springer-Verlag, 2003.
[2] D. Boneh, R. A. DeMillo, and R. J. Lipton, "On the Importance of Check-
ing Cryptographic Protocols for Faults," In Advances in Cryptology - EURO-
CRYPT'97, LNCS 1233, pp. 37-51, Springer-Verlag, 1997.
[3] D. Boneh, R. A. DeMillo, and R. J. Lipton, "On the Importance of
Eliminating Errors in Cryptographic Computations," In Journal of
Cryptology, Vol. 14, No. 2, pp. 101-119, Springer-Verlag, 2001.
[4] E. Biham and A. Shamir, "Differential Fault Analysis of Secret Key
Cryptosystems," In Advances in Cryptology - CRYPTO'97, LNCS 1294, pp. 513-
525, Springer-Verlag, 1997.
[5] H. Handschuh, P. Paillier, and J. Stern, "Probing Attacks on Temper-
Resistant Devices," In Cryptographic Hardware and Embedded Systems-
CHES '99, LNCS 1717, pp. 303{315, Springer-Verlag, 1999.
[6] M. Joye, A. K. Lenstra, and J.-J. Quisquater, "Chinese Remaindering Based
Cryptosystems in the Presence of Faults," In Journal of Cryptology, Vol. 12,
No. 4, pp. 241-245, 1999.
[7] A. K. Lenstra, "Memo on RSA Signature Generation in the Presence of
Faults," manuscript, Sept. 28, 1996.
[8] A. Shamir, "Method and Apparatus for Protecting Public Key Schemes from
Timing and Fault Attacks," In United States Patent 5991415, November 23,
1999.
[9] P. Kocher, "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS,
and Other Systems," In Advances in Cryptology-CRYPTO'96, LNCS 1109,
pp. 104-113, Springer-Verlag, 1996.
[10] J. F. Dhem, F. Koeune, P. A. Leroux, P. Mestre, J. J. Quisquater, and J. L.
Willems, "A Practical Implementation of the Timing Attack," In Smart Card
Research and Advanced Application Conference-CARDIS '98, LNCS 1820,
pp. 167-182, Springer-Verlag, 2000.
[11] G. Hachze, F. Koeune, and J. J. Quisquater, "Timing Attack: What can be
Achieved by a Powerful Adversary?," In 20th Symposium on Information The-
ory in the Benelux, pp. 63-70, 1999.
[12] F. Koeune and J.-J. Quisquater, "Timing Attack against Rijndael," In Tech-
nical Report CG-1999/1, Universit¶e catholique de Louvain, June 1999.
[13] W. Schindler, "A Timing Attack against RSA with the Chinese Remainder
Theorem," In Cryptographic Hardware and Embedded Systems - CHES '00,
LNCS 1965, pp. 109-124, Springer-Verlag, 2000.
[14] P. Kocher, J. Jaffe, and B. Jun, Differential Power Analysis,"In Adavnces
in Cryptology - CRYPTO'99, LNCS 1666, pp. 388-397, Springer-Verlag, 1999.
[15] T. S. Messerges, E. A. Dabbish, and R. H. Sloan, "Power Analysis Attacks
of Modular Exponentiation in SmartCards," In Cryptographic Hardware and
Embedded Systems - CHES '99, LNCS 1717, pp. 144-157, Springer-Verlag, 1999.
[16] N. Koblitz, 'Elliptic Curve Cryptosystems," In Mathematics of Computation,
Vol. 48, pp. 203-209, 1987.
[17] W. Diffe and M. E. Hellman, "Multiuser Cryptographic techniques," , In
AFIPS National Computer Conference, Vol. 45, pp. 109-112, 1976.
[18] R. L. Rivest, A. Shamir, and L. M. Adleman, "A Method for Obtaining Digi-
tal Signatures and Public-key Cryptosystems," Communications of the ACM,
21(2):120-126, 1978.
[19] D. E. Kunch, "Seminumerical Algorithm," In The Art of Computer Program-
ming, Vol. 2, Addison-Wesley, 1981.
[20] National Bureau of Standards. "Data Encryption Standard," U.S. Department
of Commerce, FIPS Pub. 46, January 1997.
[21] P. A. Fouque, G. Martinet, and G. Poupard, "Attacking Unbalanced RSA-CRT
Using SPA," In Cryptographic Hardware and Embedded Systems - CHES '03,
LNCS 2779, pp. 254-468, Springer-Verlag, 2003.
[22] S. Mangard, "A Simple Power-Analysis (SPA) Attack on Implementations of
the AES Key Expansion," In International Conference on Information Security
and Cryptology - ICISC '02, LNCS 2587, pp. 343-358, Springer-Verlag, 2003.
[23] R. Mayer-Sommer, "Smartly Analyzing the Simplicity and the Power of Sim-
ple Power Analysis on Smartcards," In Cryptographic Hardware and Embedded
Systems - CHES '00, LNCS 1965, pp. 78{92, Springer-Verlag, 2000.
[24] S. Chari, C. Jutla, J. R. Rao, and P. Rohatgi, "A Cautionary Note regarding
Evaluation of AES Candidates on Smart Cards," In Second Advanced Encryp-
tion Standard Candidate Conference, pp. 135-150, 1999.
[25] 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.
[26] M. Joye and S. M. Yen, "The Montgomery Powering Ladder," In Crypto-
graphic Hardware and Embedded Systems - CHES '02, LNCS 2523, pp. 291-302,
Springer-Verlag, 2003.
[27] P. L. Montgomery, "Speeding the Pollard and Elliptic Curve Methods of Fac-
torization," Mathematics of Computation, Vol. 48, pp. 243-264, 1987.
[28] S. M. Yen and C. S. Laih, "Fast Algorithm for the LUC Digital Signature
Computation," In IEEE proceedings: Computers and Digital Techniques,
Vol. 142, No.2, pp. 165-169, 1995.
[29] S. M. Yen, S. J. Kim, S. G. Lim, and S. J. Moon, "A Countermeasure against
One Physical Cryptanalysis May Benefit Another Attack," In International
Conference on Information Security and Cryptology-ICISC '01, LNCS 2288,
pp. 414-427, Springer-Verlag, 2002.
[30] B. Chevallier-Mames, M. Ciet, C. Mathieu, and M. Joye, "Low-Cost Solu-
tions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity,"
In IEEE Transaction on Computers, Vol. 53, No. 6, pp. 760-768, 2004.
[31] T. Akishita and T. Takagi, "Zero-Value Point Attacks on Elliptic Curve
Cryptosystem," In Information Security Conference-ISC '03, LNCS 2851, pp.
218-233, Springer-Verlag, 2003.
[32] E. Brier, C. Clavier, and F. Olivier, "Correlation Power Analysis with a
Leakage Model," In Cryptographic Hardware and Embedded Systems-CHES '04,
LNCS 3156, pp. 16-29, Springer-Verlag, 2004.
[33] R. Bevan and E. Knudsen, "Ways to Enhance Differential Power Analysis," In
International Conference on Information Security and Cryptology-ICISC '02,
LNCS 2587, pp. 327-342, Springer-Verlag, 2003.
[34] L. Goubin, "A Refined Power-Analysis Attacks on Elliptic Curve
Cryptosystems," In Public Key Cryptography-PKC'03, LNCS 2567, pp. 199-210,
Springer-Verlag, 2003.
[35] K. Itoh, T. Izu, and M. Takennake, "Address-Bit Differential Power
Analysis of Cryptographic Schemes OK-ECDH and OK-ECDSA," In Cryptographic
Hardware and Embedded Systems-CHES '02, LNCS 2523, pp. 129-143, Springer-
Verlag, 2003.
[36] B. Chevallier-Mames, "Self-Randomized Exponentiation Algorithms," In Cryp-
tography Track RSA Conference - CT-RSA '04, LNCS 2964, pp. 236-249,
Springer-Verlag, 2004.
[37] C. D. Walter, "MIST: An E±cient Randomized Exponentiation Algorithm
for Resisting Power Analysis," In Cryptographer's Track RSA Conference-CT-
RSA '02, LNCS 2271, pp. 53-66, Springer-Verlag, 2002.
[38] J. C. Ha and S. J. Moon, "Randomized Signed-Scalar Multiplication of ECC
to Resist Power Attacks," In Cryptographic Hardware and Embedded System-
CHES'02, LNCS 2523, pp. 551-563, Springer-Verlag, 2003.
[39] E. Oswald and K. Aigner, "Randomized Addition-Subtraction Chain as a Coun-
termeasures anainst Power Attacks," In Cryptographic Hardware and Embedded
Systems-CHES '01, LNCS 2162, pp. 39-50, Springer-Verlag, 2001.
[40] C. Clavier and M. Joye, "Universal Exponentiation Algorithm-A First Step
toward Provable SPA-resistance," In Cryptographic Hardware and Embedded
Systems-CHES '01, LNCS 2162, pp. 300-308, Springer-Verlag, 2001.
[41] National Institute of Standards and Technology(NIST), "Digital Signature
Standard(DSS)," FIPS PUB 186-2, 2000.
[42] American National Standards Institute(ANSI), "Public key cryptography for
the finnancial services industry: The elliptic curve digital signature
algorithm(ECDSA)," ANSI X9.62, 1998.
[43] T. ElGmal, "A Public-Key Cryptosystem and a Signature Scheme Based on
Discrete Logarithms," In Advances in Cryptology-CRYPTO'96, LNCS 2523,
pp. 129-143, Springer-Verlag, 2003.
[44] I. Biehl, J. Buchmann, S. Hamdy, and A. Meyer, "A Signature Scheme Based
on the Intractability of Extracting Roots," Designs, Codes and
Cryptography, To appear.
[45] B. MÄoller, "Improved Techniques for Fast Exponentiation," In
International Conference on Information Security and Cryptology-
ICISC '03 , LNCS 2587, pp. 298-312, Springer-Verlag, 2003.
[46] W. C. Yang, D. J. Guan, and C. S. Laih, "Fast Multi-computations with In-
teger Similarity Strategy," In Public Key Cryptography{PKC'05, LNCS 3386,
pp. 138-153, 2005.
[47] V. S. Dimitrov, G. A. Jullien, and W. C. Miller, "Complexity and Fast
Algorithms for Multiexponentiation," IEEE Trans. Computers, 49(2):141-
147, Feb. 2000.
[48] J. A. Solinas, "Low-weight Binary Representations for Pairs of Integers,"
Technique Report CORR 2001-41, http://www.cacr.math.uwaterloo.ca, 2001.
[49] S. G. Sim, D. J. Park, and P. J. Lee, "New Power Analysis on the Ha-Moon
Algorithm and the MIST Algorithm," In International Conference on
Information Security and Cryptology{ICICS '04, LNCS 3269, pp. 291-304,
Springer-Verlag, 2004.
[50] C. K. Kim, J. C. Ha, S. J. Moon, S. M. Yen, W. C. Lien, and
S. M. Kim, "An Improved and Efficient Countermeasure against Power
Analysis Attacks," Cryptology ePrint Archive, 2005/022. Available from
http://eprint.iacr.org/2005/022
[51] H. Mamiya, A. Miyaji, and H. Morimoto, "Efficient Countermeasure against
RPA, DPA, and SPA," In Cryptographic Hardware and Embedded Systems-
CHES'04, LNCS 3156, pp. 343-356, Springer-Verlag, 2004.
[52] S. M. Yen, C. N. Chen, S. J. Moon, and J. C. Ha, "Improvement on Ha-
Moon Randomized Exponentiation Algorithm," In International Conference
on Information Security and Cryptology-ICISC'04, LNCS 3506, pp. 154-167,
Springer-Verlag, 2005.
53] D. J. Park and P. J. Lee, "A DPA Attack on the Improved Ha-Moon
Algorithm," Cryptology ePrint Archive, 2004/349/2004. Available from
http://eprint.iacr.org/2004/349
[54] P. A. Fouque, F. Muller, G. Poupard, and F. Valette, "Defeating Countermea-
sures Based on Randomized BSD Representation," In Cryptographic Hardware
and Embedded Systems-CHES '04, LNCS 3156, pp. 312-327, Springer-Verlag,
2004.
[55] ÄO E·gecio·glu and C. K. Koc, "ExponentiationUsing Canonical Recoding," In
Theoretical computer science, Vol. 129, pp. 407-417, 1994.
[56] G. W. Reitwiesner, "Binary Arithmetic," In Advances in Computers, Vol. 1,
pp. 231-308, 1960.
[57] C. N. Zhang, "An Improved Binary Algorithm for RSA," In Computer Math.
Applic., Vol. 25, no. 6, pp. 15-24, 1993.
[58] T. S. Messerges, "Using Second-Order Power Analysis to Attack DPA Resis-
tant Software," In Cryptographic Hardware and Embedded System-CHES '00,
LNCS 1965, pp. 238-251, Springer-Verlag, 2000.
[59] K. Okeya and K. Sakuria, "A Second-Order DPA Attack Breaks a Window-
Method Based Countermeasure aginst Side Channel Attacks," In Information
Security Conference-ISC '02, LNCS 2433, pp. 389-401, Springer-Verlag, 2002.
[60] J. Waddle and D. Wagner, "Towards Efficient Second-Order Power Analy-
sis," In Cryptographic Hardware and Embedded Systems-CHES '04, LNCS 3156,
pp. 1-15, Springer-Verlag, 2004.

指導教授

顏嵩銘(Sung-Ming Yen)

審核日期

2006-7-17

推文