模指數運算通常是由一連串的模乘法所組成，而在公開金鑰密碼系統中，為了安全的考量，我們常會選用非常大的模數。為了加速運算，可使用Montgmery演算法來避免商數預估，同時可以更進一步地使用進位儲存加法器(CSA)來減少最長延遲路徑。在本論文中，我們觀察到用於實現模指數運算的H演算法中乘法與平方運算的相依性，佐以數學上的推導，減少CSA樹中運算元的個數，進而提出了一個統合乘法與平方的模組。此外，我們更提出了一種嶄新的模簡化方法，可以更進一步地加速我們所提出的演算法。
我們所提出的架構具有下列幾項優點：(1)在每一次的模乘法之間不需要將進位儲存型式的運算元轉換為二進位型式，因此，除了最後在模指數運算中需要做一次轉換以得到結果，其餘的情況下皆可省去因轉換所需耗費的時間;(2)以一種非常有效率的方式減少CSA樹中運算元個數;(3)可用一種節省硬體且不會對最長延遲路徑造成太大影響的方式來設計乘法與平方的元件; (4)藉由所提出的模簡化方法，可以在不增加太多硬體成本的前提下，有效地提升運算速度。
最後，我們以分析的方式來得到所設計出硬體的複雜度，可以歸納出在現存的架構中，本論文所提出的模指數設計不只擁有最低的硬體複雜度，同時，從面積-時間複雜度的角度來看，也擁有最傑出的表現。

Modular exponentiation with a large modulus, which is usually accomplished by repeated modular multiplications, has been widely used in public key cryptosystems for secured data communications. To speed up the computation, the Montgomery modular multiplication algorithm is used to relax the process of quotient determination, and the carry-save addition (CSA) is employed to reduce the critical path delay. In this thesis, based on the inherent data dependency between the modular multiplication and square operations in the H-algorithm of modular exponentiation, we present a new modular exponentiation architecture with a unified modular multiplication/square module and show how to reduce the number of input operands for the CSA tree by mathematical manipulation. Furthermore, we propose a novel modular reduction method to speed up our algorithm. The developed architecture has the following advantages. (1) There is no need to convert the carry-save form of an operand into its binary representation at the end of each modular multiplication. In this way, except the final step to get the result of modular exponentiation, the time-consuming carry propagation can then be eliminated. (2) The number of input operands for the CSA tree is reduced in a very efficient way. (3) The hardware saving is achieved with very limited impact on the original critical path delay when designed with two distinct modular multiplication and square components. (4) The computation time can be reduced by the novel modular reduction with limited area overhead. Analytic results show that our modular exponentiation design obtains the least hardware complexity compared with the existing work and outperforms them in terms of area-time (AT) complexity as well.

[1] 賴溪松, 韓亮, and 張真誠, 近代密碼學及其應用. 台北市: 旗標出版股份有限公司, 2003.
[2] W. Diffie and M. Hellman, "New directions in cryptography," IEEE Transactions on Information Theory, vol. 22, pp. 644-654, 1976.
[3] B. Schneier, Applied Cryptography second edition: protocols, algorithm, and source code in C: John Wiley & Sons, Inc., 1996.
[4] R. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems," Communications of the ACM, vol. 21, pp. 120-126, Feb. 1976.
[5] T. ElGamal, "A public key cryptosystem and a signature scheme based on discrete logarithms," IEEE Transactions on Information Theory, vol. 31, pp. 469-472, 1985.
[6] "Proposed federal information processing standard for digital signature standard (DSS)," Federal Register, vol. 56, pp. 42980-42982, Aug. 30, 1991.
[7] P. L. Montgomery, "Modular multiplication without trial division," Mathematics of computation, vol. 44, pp. 519-521, Apr. 1985.
[8] D. E. Knuth, The art of computer programming: seminumeral algorithms, vol. 2: Addison-Wesley, 1981.
[9] N. Nedjah and L. M. Mourelle, "Three hardware architectures for the binary modular exponentiation: sequential, parallel, and systolic," IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 53, pp. 627-633, 2006.
[10] C. D. Walter, "Systolic modular multiplication," IEEE Transactions on Computers, vol. 42, pp. 376-378, Mar. 1993.
[11] A. Cilardo, A. Mazzeo, L. Romano, and G. P. Saggese, "Carry-save Montgomery modular exponentiation on reconfigurable hardware," Proceedings of Design, Automation and Test in Europe Conference and Exhibition, vol. 3, pp. 206-211 Vol.3, 2004.
[12] T. W. Kwon, C. S. You, W. S. Heo, Y. K. Kang, and J. R. Choi, "Two implementation methods of a 1024-bit RSA cryptoprocessor based on modified Montgomery algorithm," IEEE International Symposium on Circuits and Systems, vol. 4, pp. 650-653, May 2001.
[13] K. Manochehri and S. Pourmozafari, "Fast Montgomery modular multiplication by pipelined CSA architecture," IEEE International Conference on Microelectronics, pp. 144-147, Jan. 2004.
[14] C. McIvor, M. McLoone, and J. V. McCanny, "Fast Montgomery Modular multiplication and RSA cryptographic processor architectures," the 37th Asilomar Conference on Signals, Systems and Computers, vol. 1, pp. 379-384, Nov. 2003.
[15] C. McIvor, M. McLoone, and J. V. McCanny, "Modified Montgomery modular multiplication and RSA exponentiation techniques," IEE Procceedings-Computers and Digital Techniques, vol. 151, pp. 402-408, Nov. 2004.
[16] A. P. Fournaris and O. Koufopavlou, "A new RSA encryption architecture and hardware implementation based on optimized Montgomery multiplication," IEEE International Symposium on Circuits and Systems, pp. 4645-4648, Vol. 5, May 2005.
[17] J. H. Hong and C. W. Wu, "Cellular-array modular multiplier for fast RSA public-key cryptosystem based on modified Booth's algorithm," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 11, pp. 474-484, Jun. 2003.
[18] Q. Liu, F. Ma, D. Tong, and X. Cheng, "A regular parallel RSA processor," IEEE Midwest Symposium on Circuits and Systems, vol. 3, pp. iii-467-70 vol.3, Jul. 2004.
[19] P. S. Chen, S. A. Hwang, and C. W. Wu, "A systolic RSA public key cryptosystem," IEEE International Symposium on Circuits and Systems, vol. 4, pp. 408-411, 1996.
[20] C. C. Yang, T. S. Chang, and C. W. Jen, "A new RSA cryptosystem hardware design based on Montgomery's algorithm," IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 45, pp. 908-913, Jul. 1998.
[21] H. Orup, "Simplifying quotient determination in high-radix modular multiplication," 12th Symposium on Computer Arithmetic, pp. 193–199, 1995.
[22] "TSMC 0.13 μm (CL013G) Process 1.2-Volt SAGE-XTM Standard Cell Library Databook," in Artisan Components, Jan. 2004.
[23] D. I. Moldovan and J. A. B. fortes, "Partitioning and mapping algorithms into fixed size systolic arrays," IEEE Transactions on Computers, vol. 35, pp. 1-12, Jan. 2002.
[24] D. Harris, R. Krishnamurthy, M. Anders, S. Mathew, and S. Hsu, "An improved unified scalable radix-2 Montgomery multiplier," 17th IEEE Symposium on Computer Arithmetic, pp. 172-178, 2005.
[25] A. F. Tenca and C. K. Koc, "A scalable architecture for modular multiplication based on Montgomery's algorithm," IEEE Transactions on Computers, vol. 52, pp. 1215-1221, 2003.