RSA公匙密碼系統之架構設計

Abstract

RSA密碼系統是目前最廣為使用的公匙密碼系統之一。通常為確保資料的 安全性，大數值之 運算常造成耗面積的硬體設計與冗長的計算時間。在 這篇論文中，我們針對RSA密碼系統提 出一個新的架構以降低硬體設計 的複雜性而無損計算之速度。藉由Montgomery演算法在模 乘法上所提 供的優點並採取次方從最低位元開始處理之乘冪方式，一種有別於以往的 管線 設計得以順利運作，且形成了進一步面積最佳化的基礎。此外， 為提昇計算速度，我們也 提出了兩種不同的方式來修改Montgomery演 算法。其一為透過交錯連續之運算，將臨界路 徑再加以管線化細分， 使得最小之時序週期約可降至一個全加器的延遲時間左右。其二， 藉 由針對Montgomery演算法中平行輸入項的特殊安排，此演算法被修改成可 以只接受循序 輸入項來計算模平方，因而大大增加了乘冪運算的效率 。我們已完成Verilog在暫存器轉 移層次的模擬，證實所提出的架構 與加速技巧確實可行。 RSA public-key cryptosystem is one of the best known and most widely used cryptosystems. For reasons of data security is usually involves huge computations that require lots of hardware area and processing time. In this thesis, we propose a new architecture to reduce the hardware complexity with no compromise in speed. By combining the advantage of Montgomery algorithm in modular multiplication with that of LSB-first algorithm in modular exponentiation, a different pipelining method is presented for further area optimization. As for speed, we modify the Montgomery algorithm in two way. Interleave each iteration to pipeline the critical path, and update the parallel input on every cycle for serial squaring. The first technique implies that the minimum cycle time can be reduced to approximately a single full adder delay, and the second enables more efficient computations. Verilog simulation on register- transfer-level has proved that our design and speed-up techniques are feasible.