臺灣博碩士論文加值系統

RSA加密演算法是目前通訊及資料加密的主流之一，然而為了確保資訊的安全性，它的運算元長度通常必須大於512位元，使得RSA加密演算法的運算量非常大、因而計算時間非常長。因此如何發展一個運算快速、電路閘數少和容易佈局的RSA加解密電路，將是一大挑戰。
在本論文中，我們提出一個由兩個1024位元加法器構成的RSA加解密電路。為達成快速加法的目的，1024位元加法器採用階層性的Carry skip adder，其中每一個加法器由8個位元的漣波進位加法器構成。在使用0.35μm SPQM元件庫建構電路下，它執行1024位元加法僅需要9.4ns。此加密解電路晶片的工作頻率可至72MHz，而一筆1024位元RSA加解密運算平均花22ms，晶片面積為3.7x3.7 mm^2，功率消耗為633mw。此外因為電路在位元切割的形式下具有模組性與階層性，極易再擴充為更高位元的RSA加解密電路。

The RSA encryption algorithm is widely used in communication and data security system. It takes much time to perform because of the RSA algorithm using more than 512-bit word lengths to guarantee security. Developing a high speed RSA encryption circuit which takes less gate count and can carry out its layout easily, will be a challenge.
In this thesis, a 1024-bit RSA encryption circuit that is constructed by two 1024-bit adders is proposed. Based on the consideration of speed and regularity, a 1024-bit hierarchical carry skip adder consisting of 8 bits ripple adders is proposed. The adder only takes 9.4ns to perform a 1024-bit addition with 0.35μm SPQM cell library. The resulting RSA circuit can output a 10240-bit encrypted message every 22ms at the operating frequency of 72 MHz. Its die size is 3.7x3.7mm^2 and consumes 633mw. Moreover, the design of the proposed RSA circuit is modularized in a bit-sliced manner so that it can be expanded easily to a longer word length.

第一章 緒論 1
1.1 簡介 1
1.2 研究方向 1
1.3 章節的安排 2
第二章 RSA演算法相關研究 3
2.1 RSA加密演算法 3
2.2 模指數計算 4
2.3 模乘法演算法 5
2.3.1 乘完再除方法 5
2.3.2 乘除交錯方法 7
2.3.3 Montgomery方法 8
2.4 三種模乘法演算法比較 9
第三章 加法器設計 11
3.1 Carry skip adder 基本原理 11
3.2 Carry skip adder 的問題 13
3.3 加法器的比較 15
3.4 Carry skip adder變形架構 16
3.5 1024位元加法器的架構 18
3.6 加法器進位延遲分析 20
3.7 相近架構加法器的比較 24
第四章 RSA加解密電路架構 26
4.1 模指數運算電路的架構 26
4.2 模乘法電路的組成 27
第五章 RSA加解密電路建立與模擬 31
5.1 純行為模型 32
5.2 混合模型 36
5.3 純架構模型 38
5.4 資料路徑的位元切割 39
5.5 晶片佈局與佈局後驗證 41
第六章 結論 43
參考文獻 44

[1] R. L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems," Communications of the ACM, vol. 21, no. 2, pp. 120-126, Feb. 1978.
[2] D. Naccache and D. M'Raihi, "Cryptographic smart cards," IEEE Micro, vol. 16, no. 3, pp. 16-24, June 1996.
[3] A. Vandemeulebroecke, E. Vanzieleghem, T. Denayer, and P. G. A. Jespers, "A new carry-free division algorithm and its application to a single-chip 1024-b RSA processor," IEEE J. Solid-Stat Circuits, vol. 25, pp. 748-756, June 1990.
[4] S. Ishii, K. Ohyama, and K. Yamanaka, "A single-chip RSA processor implemented in a 0.5 μm rule gate array" ASIC Conference and Exhibit, Proceedings, Seventh Annual IEEE International, pp. 433-436, 1994.
[5] G. A. Orton, M. P. Roy, P. A. Scott, L. E. Peppard, and S. E. Tavares, "VLSI implementation of public-key encryption," in Advances in Cryptology- CRYPTO '86, Springer-Verlag, pp. 277-301, 1986.
[6] T. Beth and D. Gollmann, "Algorithm Engineering for Public key Algorithm" IEEE J. Selected Areas in Communications, vol. 7, pp. 458-465, May 1989.
[7] H. Orup, E. Svendsen, and E. Andreasen, "VICTOR: An efficient RSA hardware implementation", in Advances in Cryptology-CRYPTO '90, Springer-Verlag, pp. 245-252, 1990.
[8] D. de Waleffe and J. J. Quisquater, "CORSAIR: A smart card for public key Cryptosystem," in Advances in Cryptology-CRYPTO '90, Springer-Verlag, pp. 502-513, 1990.
[9] N. Takagi and S. Yajima, "Modular multiplication hardware algorithms with a redundant representation and their application to RSA Cryptosystem," IEEE Trans. Compt., vol. 41, pp. 887-891, July 1992.
[10] A. Satoh, Y. Kobayashi, H. Niijima, N. Ooba, S. Munetoh, and S. Sone, " A high-speed small RSA encryption LSI with low power dissipation", Information Security Workshop 1997, Springer-Verlag, pp. 174-187, 1997.
[11] P. L. Montgomery, "Modular multiplication without trial division", Math. of Computation, vol. 44, pp. 519-521, Apr. 1985.
[12] S. Even, "Systolic modular multiplication," in Advances in Cryptology- CRYPTO '90, pp. 619-624, Springer-Verlag, 1990.
[13] M. Shand and J. Vuillemin, "Fast implementations of RSA cryptography," in Proc. 11th IEEE symp. Computer Arithmetic, pp. 252-259, 1993.
[14] C. D. Walker, "Systolic modular multiplication," IEEE Trans. Compt., vol. C-42, no. 3, pp. 376-278, Mar. 1993.
[15] C. K. Koc, T. Acar, and B. S. Kaliski, "Analyzing and comparing Montgomery multiplication algorithm," IEEE Micro, vol. 16, no. 3, pp. 26-33, June 1996.
[16] P. S. Chen, S. A. Hwang, and C. W. Wu, " A systolic RSA public key cryptosystem," in Proc. IEEE Symp. Circuits System, pp. 408-411, May 1996.
[17] S. R. Dusse and B. S. Kaliski, "A cryptographic library for the Motorola DSP56000," in Advances in Cryptology-Eurocrypt '90, Springer-Verlag, pp. 230-244, 1990.
[18] J. F. Dhem, D. Veithen and, J. J. Quisquater, " SCALPS:Smart Card for Limited Payment System," IEEE Micro, vol. 16, no. 3, pp. 42-51, June 1996.
[19] T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, The MIT Press, 1990.
[20] A. Guyot, B. Hochet, and J. M. Muller, "A way to build efficient carry-skip adders," IEEE Trans. Compt., vol. 36, no. 10, pp. 1144-1152, Oct. 1987.
[21] C. K. Chan, M. D. F. Schlag, and C. D. Thomborson, "Delay optimization of carry-skip adders and block carry-lookahead adder," in Proc. 10th Symp. Computer Arithmetic, pp. 154-164, 1991.
[22] J. M. Rabaey, Digital Integrated Circuits: A Design Perspective, Prentice-Hall, 1996.
[23] Behrooz Parhami, Computer Arithmetic: Algorithms and Hardware Designs, Oxford University Press, 2000.
[24] M. G. Arnold, Verilog Digital Computer Design: Algorithms into Hardware, Prentice-Hall, 1999.