擴充式字元基礎蒙哥馬利乘法演算法之改進

Abstract

隨著有線、無線通訊的發展，安全性的考量也日益重要。許多網路上的應用如電子商務、網路銀行…等，都需要一個完整的安全機制來保證其安全性；其基本上的安全需求，包含有隱密性，可認證性，資料的完整性和不可否認性。為了提供上述的安全服務，大多的網路系統使用公開金鑰密碼系統。而在各種公開金鑰密碼系統的演算法中，現今最著名的是RSA 密碼系統，且由於其多功能性，所以被公開金鑰密碼系統廣泛使用。在公開金鑰密碼系統演算法中，其最主要的運算是模數的乘法，它是被利用來計算模數的指數運算。然而，模數的指數運算，當模數的位元數高達512 位元以上，將使得RSA 密碼系統，很難有較快速運算的處理能力。因此擁有較高的資料處理能力是RSA 密碼系統最主要改善的地方。另外，隨著破密學的發展以及硬體製程的進步，破解RSA密碼系統所需要的時間愈來愈短；因此，增加RSA金鑰位元數來達成更佳的安全性也是未來的趨勢之一 在RSA加密演算法中，長整數模數指數運算是主要的運算，模數指數運算是由連續的模數乘法所組成，所以一個快速的模數乘法演算法是非常重要的。因此我們提出一個改進的字元基礎蒙哥馬利乘法演算法(Modified Word based Montgomery Multiplication Algorithm)來加速RSA加密演算法的運算。字元基礎的架構同時可以提供硬體的可擴充性；若是想加強系統安全性而增加金鑰位元數，僅需要調整舊有的硬體即可，並不需要重新換一套新的硬體，而其所需付出的代價是時間的增加。這對於目前的企業來說是相當的有吸引力的，若是因為想增加系統安全性而必須另外買一套硬體，對企業或是使用者而言都是極重的負擔。而我們提出的硬體架構，不但延續了“可擴充性”這個優點，其速度及效能更較之前所提出的方法佳。在TSMC 0.25μm的製程以及Synopsys Design Analyzer軟體的模擬環境下，我們8位元單一元件的設計總共只需要784個邏輯閘，並且糸統整體能達到588.23Mbps的高速資料處理量。

With the rapid growth of Internet applications and various information devices, security of our data becomes an important issue. RSA algorithm is the most popular public key system in the world. The main computation of RSA algorithm is modular exponentiation. Therefore, how to make the computation of modular exponentiation faster is the major problem. In this thesis, we present a Modified Word-Based Montgomery Multiplication Algorithm. The proposed multiplier is able to work with any precision of the input operands, limited only by memory or control constraints. Its architecture gives enough freedom to select the word size and the degree of parallelism to be used, according to the available area and/or desired performance. We use the ASIC design flow to implement this modified architecture. Using TSMC 0.25μm CMOS process technology and Synopsis Design Analyzer, the 8 bits single processing element of our design costs 784 gate counts , and our system can achieve a high throughput of 588.23Mbps.