臺灣博碩士論文加值系統

隨著電腦科技的進步，帶給人類極大的便利性，但伴隨而來的卻
是安全性的問題。最簡單便利的安全措施是利用使用者帳號及密碼加
以控管，但密碼太短容易被破解，密碼太長又不容易記，若在網路上
進行傳輸，利用簡單的網路封包截取工具就可取得相關之使用者帳號
及密碼，因此使用如Smart Card這種可提供身份認證及內含密碼學演
算法的低成本硬體裝置，已成現今社會的一個趨勢。
因此本篇論文乃利用低成本且取得容易的8051單晶片來完成512
位元的RSA密碼系統。而RSA密碼系統演算法中，最主要的運算為
模指數運算，但在8051內部指令中並無模指數運算的相關指令，因此
本篇設計先將模指數運算利用L-algorithm轉換成模乘法運算，再利用
Montgomery演算法轉換成加法及移位計算，以利用現有的指令完成
RSA密碼系統。
RSA密碼系統的安全性乃是基於因數分解的困難度，然而近年
來，實體密碼攻擊法(physical cryptanalysis)已在密碼學領域中成為一個
新的學門，它可因為密碼演算法設計的不周詳而加以攻擊，因此本篇
論文在完成512位元的RSA密碼系統後，將以SPA(Simple power
analysis)及DPA(Differential power analysis)加以攻擊。並針對SPA攻擊
，讓di無論是否為1都執行Montgomery運算，以進行防禦。對於DPA
攻擊，將以每次執行時都變更金鑰的方式來加以防禦，以使本篇所完
成之512位元的RSA密碼系統更為安全可靠。

As information technology has developed rapidly, it provides more convenient life for people. As the result, the security has become the main concern. Recently, user id and password are major methods to protect private information. However, the short password can be broken by hackers. Too long is not easy to memorize. Network traffic-analyzing tool provides the function to gain the user id and password while doing transaction via network. Therefore, low cost Smart Card including user name identification and cryptosystem algorithm has become new trend of
modern society.
The first object of this thesis is to present the design and implementati- on of a 512-bit RSA cryptosystem by using 8051 microcontroller. In RSA cryptosystem algorithm, modular exponentiation is the essential arithmetic operation. However, 8051 microcontroller does not provide the modular exponentiation. In order to complete RSA cryptosystem, this thesis has mentioned that using L-algorithm to transfer to modular multiplication.
Then using Montgomery to transfer addition and shift calculation.
The security of RSA cryptosystem relies on the comparative difficulty of factoring prime. Recently, physical cryptanalysis has become the new direction of cryptanalysis because it can attack the cryptosystem algorithm with careless design. Therefore, the second object of thesis focuses on SPA (Simple power analysis) and DPA (Differential power analysis). The main strategy to against SPA is to execute Montgomery Algorithm, no matter di is 1 or not. In addition, changing the private key is the method to against DPA. As the result, 512-bit RSA cryptosystem can become more safety and
reliable.

1 緒論 1
1.1 動機 . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 簡介公開金鑰密碼系統 . . . . . . . . . . . . . . . . 1
1.3 簡介實體密碼攻擊法 . . . . . . . . . . . . . . . . . 2
1.4 本篇論文概述 . . . . . . . . . . . . . . . . . . . . 3
2 RSA密碼系統介紹 4
2.1 RSA密碼系統演算法 . . . . . . . . . . . . . . . . . 4
2.1.1 金鑰產生 . . . . . . . . . . . . . . . . . . . 4
2.1.2 加密過程 . . . . . . . . . . . . . . . . . . . 4
2.1.3 解密過程 . . . . . . . . . . . . . . . . . . . 5
2.1.4 RSA密碼系統的安全性 . . . . . . . . . . . . . . 5
2.2 RSA密碼系統的數學運算 . . . . . . . . . . . . . . . 6
2.3 Montgomery演算法 . . . . . . . . . . . . . . . . . . 6
3 實體密碼攻擊法介紹 8
3.1 錯誤攻擊法 . . . . . . . . . . . . . . . . . . . . . 8
3.2 時間攻擊法 . . . . . . . . . . . . . . . . . . . . . 8
3.3 能量攻擊法 . . . . . . . . . . . . . . . . . . . . . 9
3.3.1 簡單能量攻擊法 . . . . . . . . . . . . . . . . 9
3.3.2 差分能量攻擊法 . . . . . . . . . . . . . . . . 10
4 RSA密碼系統實作 13
4.1 實作工具 . . . . . . . . . . . . . . . . . . . . . . 13
4.2 實作使用之演算法 . . . . . . . . . . . . . . . . . . 16
4.2.1 L-algorithm . . . . . . . . . . . . . . . . . . 16
4.2.2 Montgomery演算法 . . . . . . . . . . . . . . . 18
5 SPA攻擊及防禦 21
5.1 SPA攻擊實作方法 . . . . . . . . . . . . . . . . . . 21
5.2 SPA防禦實作方法 . . . . . . . . . . . . . . . . . . 22
5.3 SPA攻擊及防禦結果展示 . . . . . . . . . . . . . . . 23
6 DPA攻擊及防禦 26
6.1 DPA攻擊實作方法 . . . . . . . . . . . . . . . . . . 26
6.2 DPA防禦實作方法 . . . . . . . . . . . . . . . . . . 28
6.3 DPA攻擊及防禦結果展示 . . . . . . . . . . . . . . . 29
7 結論 33
7.1 簡略的介紹本篇論文的主要貢獻 . . . . . . . . . . . . 33
7.2 可更進一步研究的課題和方向 . . . . . . . . . . . . . 35
參考文獻 36
附錄 RSA程式(使用8051組合語言) 38

[1] J.J. Farrell III, “Smartcards Become an International Technology,” TRON Project International Symposium, TEPS '96, 1996, pp. 134-140.
[2] D. Naccache and D. M’Raihi, “Cryptographic Smart Card,” IEEE Micro, Volume 16, Issue 3, June 1996, pp. 15-24.
[3] R.L. Rivest, A. Shamir, and L.M. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, Vol. 21, No. 2, Feb 1978, pp. 120-126.
[4] J.A. Muir, “Techniques of Side Channel Cryptanalysis”, Master Thesis, Department of Mathematics, University of Waterloo, Canada, 2001.
[5] B. Schneier, “Applied Cryptography; Protocol, Algorithm, and Source Code in C,” John Wiley & Sons, Inc., 1994.
[6] P. Kocher, J. Jaffe and B. Jun, “Differential Power Analysis,” Advances in Cryptology – CRYPTO '99, Lecture Notes in Computer Science, Spring-Verlag, 1999, pp. 388-397.
[7] W. Diffie and M.E. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory, Vol. IT-22, No. 6, Nov. 1976, pp. 644-654.
[8] R. Anderson and M. Kuhn, “Tamper Resistance – a Cautionary Note,” Proceedings of the 2nd Workshop on Electronic Commerce, pp. 1-11, 1996.
[9] R. Anderson and M. Kuhn, “Low Cost attacks on Tamper Resistant Devices,” Proceedings of the 1997 Security Protocol Workshop, Paris, Lecture Notes in Computer Science 1361, Springer-Verlag, 1997, pp. 125-136.
[10] O. Kommerling and M. G. Kuhn, “Design Principles for Tamper- Resistant Smartcard Processors,” Proceedings of USENIX Workshop on smartcard Technology (Smartcard ’99), May 1999, pp. 9-20.
[11] D. Boneh, R.A. Demillo, and R.J. Lipton, “On the Importance of Checking Cryptographic Protocol for faults,” Advance in Cryptology – EUROCRYPT '97, Lecture Notes in Computer Science, Springer-Verlag, 1997, pp. 37-51.
[12] P. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems,” Advance in Cryptology – CRYPTO '96, Lecture Notes in Computer Science, Springer-Verlag, 1996, pp. 104-113.
[13] E. Biham and A. Shamir, “Power Analysis of the Key Scheduling of the AES Candidates,” Proceedings of the Second Advanced Encryption Stabdard (AES) Candidate Conference, March 1999.
[14] P.L. Montgomery, “Modular Multiplication without Trial Division,” Math. Comput., Vol. 44, Apr. 1985, pp. 519-521.
[15] T.S. Messerges, E.A. Dabbish, and R.H. Sloan, “Power Analysis Attacks of Modular Exponentiation in Smartcard,” Workshop on Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science 1717, Springer-Verlag, pp. 144-157.
[16] J.S. Coron, “Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems,” Workshop on Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science 1717, Springer-Verlag, pp. 292-302.
[17] K. Itoh, T. Izu, M. Takenaka, “A Practical Countermeasure against
Address-bit Differential Power Analysis,” CHES 2003, pp. 382-396.