RSA公開金鑰系統之實體密碼分析研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：21

、訪客IP：3.137.187.233

姓名

吳明勳(Ming-Hsun Wu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

RSA公開金鑰系統之實體密碼分析研究
(The Research of RSA Implementations against Physical Cryptanalysis)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

隨著網路科技的快速進步，過去繁瑣的溝通程序都可以藉由網路的便利性來快速完成，也刺激了人們對資訊安全的重視。然而，從今日的角度來觀察，傳統密碼學的架構並不能完全符合網路環境的需求。無疑地，在網路的環境下，公開金鑰系統是傳統密碼學的最佳替代方案，它不只提供保護資料隱密的加密機制，也提供驗證身份的簽章機制。因此，保障公開金鑰系統的安全性是目前學者努力的課題之ㄧ。
近年來，實體密碼分析也吸引了越來越多國內外學者的重視，特別是應用於密碼系統實作在諸如智慧卡（smartcard）等的防篡改之電子設備中。其中主要的原因是，實體密碼分析已經跨越了密碼系統數學假設的安全性，當密碼系統實作在考慮不周嚴的情形下，往往會遭受實體密碼分析的攻擊。在本論文中將針對目前最為普遍的公開金鑰系統RSA與實體密碼分析進行更深入的討論。
在許多提出的實體攻擊法中，能量攻擊法為目前最可行的實體攻擊法。本論文的重點之ㄧ就是討論RSA指數運算針對能量攻擊法的安全性分析。首先，合併改良的指數分割防禦法以及變數隨機交換機制來防禦能量攻擊法的防禦機制會被提出。藉由最後的安全性及效能分析，本論文所提出的防禦機制相較於過去的防禦法來得更有效率，所需要的記憶體空間也更少。
本論文的另一重點主要是分析由Coron所提出之簡單能量防禦法（square-and-multiply always method）的安全性。由於Coron的簡單能量防禦法會遭受安全錯誤攻擊法（safe error attack）的攻擊，因此，本論文將提出兩個防禦安全錯誤攻擊法的防禦機制，這兩個防禦機制只需要額外一個模乘法的運算複雜度。最後將提出地防禦機制延伸到能量攻擊法的防禦法中，並且討論其效能及安全性。

摘要(英)

The rapid development of network technology
stimulates a strong demand for information security. However, the
conventional cryptography is not able to meet some requirements
for network environment. Undoubtedly, public-key systems are the
most adaptive replacement for conventional cryptosystems. They
provide not only traditional cryptographic applications, but also
authentication. Thus, to guarantee the security of public-key
systems has became an essential issue in modern cryptography.
pq Besides, in the past half-decade, physical cryptanalyses have
also attracted more and more attentions, especially if the
cryptographic operations run on temper resistant devices, such as
smart cards. Various types of physical cryptanalysis were
introduced and a large number of researches was devoted to power
analysis attacks. In this thesis, we help the robustness of the
RSA algorithm, which is the most widespread public-key system
nowadays, against physical cryptanalysis.
pq One consideration of this thesis is to prevent the RSA
exponentiation from power analysis attacks. An efficient
countermeasure against power analysis attacks is proposed. It is
shown that this countermeasure is more efficient and requires less
memory spaces than the previous works.
pq Another is to analyze the weakness of the square-and-multiply
always method, which is one sort of SPA countermeasure, under safe
error attacks. Two simple methods against safe error attacks are
suggested. Finally, an extension of the proposed countermeasure is
given along with the completed security and efficiency
comparisons.

關鍵字(中)

★ 錯誤攻擊法
★ 能量攻擊法
★ 公開金鑰系統
★ 實體密碼分析
★ 防禦

關鍵字(英)

★ power analysis attack
★ fault-based cryptanalysis
★ countermeasure
★ physical cryptanalysis
★ RSA

論文目次

Contents
1 Introduction 1
1.1 Motivation.......................................................1
1.2 Overview of the Thesis...........................................2
2 Review of RSA Algorithm 5
2.1 Principles of Public-Key Cryptosystems...........................5
2.1.1 Framework of public-key cryptosystems..........................6
2.1.2 Applications for public-key cryptosystems......................7
2.2 The RSA Algorithm................................................8
2.2.1 Description of RSA................ ............................9
2.2.2 Exponentiation algorithms.....................................10
3 Review of Power Analysis Attack against RSA 14
3.1 Overview of Power Analysis Attack...............................14
3.2 Simple Power Analysis-SPA.......................................15
3.2.1 Cryptanalysis procedures......................................15
3.2.2 Possible countermeasures......................................16
3.3 Differential Power Analysis-DPA.................................18
3.3.1 Cryptanalysis procedures......................................19
3.3.2 Possible countermeasures......................................19
3.4 Address-bit Differential Power Analysis-ADPA....................23
3.4.1 Cryptanalysis procedures......................................23
3.4.2 Possible countermeasures......................................24
4 Randomized Exponentiation Algorithm 27
4.1 Motivation......................................................27
4.2 Proposed Countermeasure.........................................27
4.2.1 Randomly swap variables.......................................28
4.2.2 Randomly split exponent.......................................29
4.2.3 A countermeasure against power analysis.......................30
4.2.4 Apply to L-to-R RSA algorithm.................................33
4.3 Security Analysis...............................................34
4.4 Comparison......................................................35
4.5 Summary.........................................................37
5 An Improvement of the SPA Resistant Algorithms....................40
5.1 Motivation......................................................40
5.2 Vulnerability of the Square-and-multiply Always Method..........41
5.2.1 Memory safe error attack......................................41
5.2.2 Computational safe error attack...............................42
5.2.3 A conclusion of safe error attack.............................42
5.3 An Improvement against M-SEA ...................................43
5.4 An Improvement against C-SEA....................................45
5.5 Extension of Randomized Exponentiation Algorithm................46
5.5.1 The extended countermeasure...................................46
5.5.2 Security analysis on the Montgomery power ladder..............48
5.5.3 Comparisons...................................................49
5.6 Summary.........................................................50
6 Conclusions 52
6.1 Brief Review of Main Contributions..............................52
6.2 Further Research Topics and Directions..........................53

參考文獻

[1] W. Diffie and M. Hellman, "New Directions in Cryptography,"
IEEE Transactions on Information Theory, November 1976.
[2] I.F. Blake, G. Seroussi, and N.P. Smart. "Elliptic Curves in
Cryptography," London Mathematical Society Lecture Note
Series, vol. 265, Cambridge University Press, 1999.
[3] A.K. Lenstra and E.R. Verheul, "The XTR Public Key System," In
Advances in Cryptology - CRYPTO 2000, LNCS 1880, pp. 1-19,
Springer Verlag, 2000.
[4] R.L. Rivest, A. Shaimr, and L. Adleman, "A Method for Obtaining
Digital Signtures and Public-key Cryptosystem," Commun. of
ACM, vol. 21, no. 2, pp.120-126, 1978.
[5] P. Ribenboim, The New Book of Prime Number Records,
Springer-Verlag, 1996.
[6] B. Kaliski and M. Robshaw, "The Secure Use of RSA,"
CryptoBytes, Autumn 1995.
[7] P. Kocher, "Timing Attacks on Implementations of Diffie-Hellman,
RSA, DSS, and Other Systems," In Advance in Cryptology -
CRYPTO 1996, LNCS 1109, pp.104-113, Springer-Verlag, 1996.
[8] J.F. Dhem, F. Koeune, P.A. Leroux, P. Mestre, J.J. Quisquater, and
J.L. Willems, "A Practical Implementation of the Timing Attack,"
Technical Report CG-1998/1, UCL Crypto Group, Universite
catholique de Louvain, June 1998.
[9] F. Koeune and J.-J. Quisquater, "A Timing Attack against
Rijndael," Technical Report CG-1999/1, Universite
catholique de Louvain, June 1999.
[10] P. Kocher, J. Jaffe and B. Jun, "Introduction to Differential
Power Analysis and Related Attacks," 1998, avaluable at URL
.
[11] P. Kocher, J. Jaffe and B. Jun, "Differential Power Analysis,"
In Advances in Cryptology - CRYPTO 1999, LNCS 1666,
pp.388-397, Springer-Verlag, 1999.
[12] E. Oswald and M. Aigner, "Randomized Addition-Subtraction Chains
as a Countermeasure against Power Attacks," In Cryptographic
Hardware and Embedded Systems - CHES 2001, LNCS 2162, pp.39-50,
Springer-Verlag, 2001.
[13] S.M. Yen, "Amplified Differential Power Cryptanalysis on Rijndael
Implementations with Exponentially Fewer Power Traces," In
Information Security and Privacy - ACISP 2003, LNCS 2727,
pp.106-117, Springer-Verlag, 2003.
[14] S.M. Yen, S. Kim, S. Lim and S. Moon, "A Countermeasure against
One Physical Cryptanalysis May Benfit Another Attack," In
Information Security and Cryptology - ICISC 2001, LNCS 2288,
pp.414-427, Springer-Verlag, 2002.
[15] J. Coron, "Resistance against Differential Power Analysis for
Elliptic Curve Cryptosystems," In Cryptographic Hardware and
Embedded Systems - CHES 1999, LNCS 1717, pp.292-302,
Springer-Verlag, 1999.
[16] S.M. Yen and M. Joye, "Check Before Output May not be Enough
against Fault-based Cryptanalysis," IEEE Trans. on
Computer, vol. 49, no. 9, pp.967-970, Sept. 2000.
[17] K. Itoh, T. Izu, and M. Takenaka, "Address-bit Differential Power
Analysis of Cryptographic Schemes OK-ECDH and OK-ECDSA," In
Cryptographic Hardware and Embedded Systems - CHES 2002, LNCS
2523, pp.129-143, Springer-Verlag, 2003.
[18] 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.
[19] W. Fischer, C. Giraud, E. Knudsen, and J. Seifert, "Parallel
Scalar Multiplication on General Elliptic Curves over Fp Hedged
Against Non-Differential Side-Channel Attacks," Cryptology ePrint
Archive, 2002/007, 2002. Available from
.
[20] T. Izu and T. Takagi, "A Fast Parallel Elliptic Curve
Multiplication Resistant against Side Channel Attacks," In
Public Key Cryptography - PKC 2002, LNCS 2274, pp.280-296,
Springer-Verlag, 2002.
[21] 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 1999, LNCS
1717, pp.114-157, Springer-Verlag, 1999.
[22] D. Chaum, "Security without Identification: Transaction Systems
to Make Big Brother Obsolete," Communications of the ACM,
vol. 28, no. 10, pp.1030-1044, 1985.
[23] C. Clavier and M. Joye, "Universal Exponentiation Algorithm - A
First Step toward Provable SPA-resistance," In Cryptographic
Hardware and Embedded Systems - CHES 2001, LNCS 2162, pp.300-308,
Springer-Verlag, 2001.
[24] K. Itoh, J. Yajima, M. Takenaka, and N. Torii, "DPA
Countermeasures by Improving the Window Method," In
Cryptographic Hardware and Embedded Systems - CHES 2002, LNCS
2523, pp.303-317, Springer-Verlag, 2002.
[25] C.D. Walter, "An Efficient, Randomized Exponentiation Algorithm
for Resisting Power Analysis," In Progress in Cryptology -
CT-RSA 2002, LNCS 2271, pp.53-66, Springer-Verlag, 2002.
[26] S. Chari, C.S. Jutla, J.R. Rao, and P. Rohatgi, "Towards Sound
Approaches to Counteract Power Analysis Attacks," In
Advances in Cryptology - CRYPTO 1999, LNCS 1666,
pp.398-412, Springer-Verlag, 1999.
[27] T.S. Messerges, E.A. Dabbish, and R.H. Sloan, "Investigations of
Power Analysis Attacks on Smartcards," preprint, USENIX Workshop
on Smartcard Technology, 1999.
[28] K. Itoh, T. Izu, and M. Takenaka, "A Practical Countermeasure
against Address-bit Differential Power Analysis," In
Cryptographic Hardware and Embedded Systems - CHES 2003, LNCS
2779, pp.382-396, Springer-Verlag, 2003.
[29] D. May, H.L. Muller, and N.P. Smart, "Random Register Renaming to
Foil DPA," In Cryptographic Hardware and Embedded Systems -
CHES 2001, LNCS 2162, pp.28-38, Springer-Verlag, 2001.
[30] R. Anderson, Security Engineering, John Wiley & Sons, New
York, 2001.
[31] R. Anderson and M.Kuhn, "Tamper Resistance - a cautionary note,"
Proc. of 2nd USENIX Workshop on Electronic Commerce,
pp.1-11, 1996.
[32] R. Anderson and M.Kuhn, "Low Cost Attacks on Tamper Resistant
Devices," In Security Protocols 1997, LNCS 1361,
pp.125-136, Springer-Verlag, 1997.
[33] C. Aumuller, 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 2002, LNCS 2523, pp.260-275,
Springer-Verlag, 2002.
[34] A. Shamir, "Method and Apparatus for Protecting Public Key
Schemes from Timing and Fault Attacks," U.S. Patent Number
5,991,415, November 1999; also presented at rump session of
EUROCRYPT 1997
[35] S.M. Yen, S. Kim, S. Lim, and S. Moon, "RSA Speedup with Residue
Number System Immune from Hardware Fault Cryptanalysis," In
Information Security and Cryptology - ICISC 2001, LNCS 2288,
pp.397-413, Springer-Verlag, 2002.

指導教授

顏嵩銘(Sun-Ming Yen)

審核日期

2004-6-24

推文