臺灣博碩士論文加值系統

在這篇論文裡面，我們設計了一個適合於 IC 智慧卡所使用的字元基礎 RSA公開金鑰處理器核心。由於 IC 智慧卡上電路的是屬於系統晶片 (system-on-chip)，也就是說在智慧卡上的晶片除了我們這個密碼電路外，尚有記憶體和中央處理器單元 (central processor unit)，因此在成本的考量下，密碼電路的面積絕對不能太大，基於此，我們將字元基礎 (word-based) 的架構運用在密碼電路上。
在字元基礎架構的作用下，除了可以大幅降低我們這個 RSA 公開金鑰處理器核心的面積，還可以使電路變成具有執行可擴充性金鑰長度 (scalable key length) 的能力。這種功能可以提供給使用者在運算時間和安全性上做一個選擇，如果覺得安全性重要的話，就選擇較長的金鑰長度來執行 RSA 的加解密，反之，就可以選較短的金鑰長度，來讓整個加解密的動作加速許多。
雖然字元基礎的架構，能帶來上述的好處，但其付出的代價是大量的運算時間，因此我們在其他的地方做了一些速度上的補救，像在一開始模數乘法反元素的產生上，捨棄了以往用軟體來產生，我們設計了硬體電路來加以完成，並能將這個硬體與內部原先執行模數乘法的硬體大部分可以共享，因此在面積上只增加了一點點。而另一方面，蒙哥馬利的演算法會需要有最後的化減 (final reduction)步驟才能得到正確的結果，這步驟會帶來速度和面積上的負擔，因此在這個我們也將稍微改變蒙哥馬利的演算法把這步驟給消除。最後我們 16位元的字元基礎 RSA公開金鑰處理器核心電路在Avant! 0.35μm 元件庫 (cell library) 的合成下，用125MHZ的速度執行1024位元金鑰長度的RSA 加解密，鮑率 (baud rate)是 20k位元/秒。
ACP是可以直接受智慧卡中的8051 CPU所控制來執行 RSA 加解密，而後來我們就將這個16位元核心電路運用在 ACP 中，並在TSMC 0.35μm 1P4M的製成技術下，我們將 ACP 予以實際製成晶片。

With a fast development of network communication, the application of IC smart card becomes more and more frequent. Since many personalized data are stored in the chip of IC smart card, the capability of high data security is an important issue of IC smart card. Therefore, a word-based RSA crypto-processor for IC smart card is proposed.
Due to the lower cost issue on smart card, an RSA crypto-processor core with small area is essential. In order to reduce silicon area, the word-based architecture is attached to RSA crypto-processor core. Using word-based architecture, the different key length can be implemented by appropriately controlling the iteration of loop. This feacture provides the flexibility between security and computation time for user. Since our RSA crypto-processor core is based on Montgomery's
algorithm, the final reduction will decrease the speed. Therefore, we modify word-based Mongomery's algorithm to eliminate this problem. Moreover, instead of using software, we
design hardware to generate modular multiplicative inverse N0'
. The resulting 16-bit word-based RSA crypto-processor core, which is synthesized by 0.35um cell library, can output 1024 bits encrypted/decrypted data in 51ms at the operating frequency is 125 MHZ. Finally, we applied 16-bit
word-based RSA crypto-processor core to asymmetric crypto processor (ACP). Based on TSMC 0.35um 1P4M technology, an ACP chip is implemented.

1 Introduction
1.1 Overview of Cryptosystem
1.2 PreviousWorks
1.3 Proposed Word-Based RSA Crypto-Processor Core
1.4 Organization
2 Review of RSA Cryptosystem
2.1 Cryptosystem
2.1.1 Secret Key Cryptosystem
2.1.2 Public Key Cryptosystem
2.2 RSA Cryptosystem
2.2.1 Encryption and Decryption Method
2.2.2 A Simple Example of RSA Operation
3 Modular Exponentiation Algorithm
3.1 Modular Multiplication
3.1.1 Montgomery's Algorithm
3.1.2 Chen's Modified Montgomery's Algorithm
3.1.3 Yang's Modified Montgomery's Algorithm
3.2 Word-Based Modular Multiplication
3.2.1 Word-Based Yang's Modified Montgomery's Algorithm
3.2.2 The Word-Based Montgomery's Algorithm
3.3 Modular Exponentiation
4 A Word-Based RSA Crypto-Processor Core Design
4.1 A Word-Based RSA Crypto-Processor Core
4.1.1 Modular Inverse Design
4.1.2 Word-Based Modular Multiplier Design
4.1.3 Improved Word-Based Modular Multiplier Design
4.1.4 Modular Exponentiation and instruction set
4.2 Complexity Analysis and Comparisons
5 Asymmetric Crypto Processor
5.1 The Architecture of ACP
5.2 Implementation Flow
5.3 Experimental Results
6 Conclusions and Future Works

[1] Y. H. Hsieh, “Design and implementation of an RSA encryption/decryption processor on IC smart card,” Master's Thesis, National Taiwan University, Taiwan, June 1999.
[2] W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Trans. Information Theory, vol. 22, pp. 644—654, Nov. 1976.
[3] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystem,” Communications of the ACM, vol. 21, pp. 120—126, Feb. 1978.
[4] E. F. Brickell, “A survey of hardware implementations of rsa,” in Advances in Cryptology, Proc. CRYPTO’89, (Berlin), pp. 368—370, 1989.
[5] P. L. Montgomery, “Modular multiplication without trial division,” Mathematics of Computation, vol. 44, pp. 519—521, Apr. 1985.
[6] P. S. Chen, “VLSI implementation for a systolic RSA public key cryptosystem,” Master's Thesis, National Tsing-Hua University, Taiwan, June 1995.
[7] C.-C. Yang, T.-S. Chang, and C.-W. Jen, “A new RSA cryptosystem hardware design based on Montgomery's algorithm,” IEEE Trans. Circuits and Systems II: Analog and Digital Signal
Processing, vol. 45, pp. 908—913, July 1998.
[8] C. D. Walter, “Systolic modular multiplication,” IEEE Trans. Computers, vol. 42, pp. 376—378, Mar. 1993.
[9] J.-H. Hong, “RSA public key crypto-processor core design and hierarchical system test using IEEE 1149 family,” Phd Thesis, National Tsing-Hua University, Taiwan, June 2000.
[10] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers. John Wiley & Sons, 1991.
[11] M. Shand and J. Vuillemin, “Fast implementation of RSA cryptography,” in Proc. 11th IEEE Symp. Computer Arithmetic, (Windsor, Ontario), pp. 252—259, June 1993.
[12] C. K. Koc, “RSA hardware implementation,” Technical Report, No.2, RSA Laboratories, RSA Data Security, Inc., Redwood City, CA, 1995.