基于流水線的RSA 加密算法硬件實現*

楊龍飛，盧 仕，彭 曠

（湖北大學 微電子學院，湖北 武漢 430062）

0 引言

從古到今，信息安全都是一項值得注意的問題，如今也有許多可考究的古代密碼學的應用。直到1976 年，幾乎所有的加密方法都是同一種模式：加解密使用同樣的密鑰。但在1976 年兩位美國計算機學家提出了Diffie-Hellman 密鑰交換算法，非對稱加密算法便由此誕生[1?2]。非對稱加密算法有兩個不同密鑰——公鑰和私鑰，公鑰用來加密明文，私鑰用來解密密文。而RSA 加密算法便是非對稱加密算法中的一種。密碼學不斷發展的今天，RSA 加密算法已經成為國際公認的比較理想的一種加密算法[3?5]。

在RSA 的安全性研究上已經比較深入了，有不少提高安全性的手段，如使用SMM 算法，改進算法的結構，增加質數的個數等方法[6?8]。但提高安全性的最簡單手段就是提高RSA 加密位數，目前推薦使用1 024 位的大數進行數字加密可以獲得良好的安全性。且在RSA 加密算法一般使用蒙哥馬利算法完成大數計算，但硬件完成基于蒙哥馬利算法的RSA 加密，存在著硬件實現成本較高、運算時間較長等問題。本文針對以上問題實現了一種基于流水線形式的蒙哥馬利算法，并行運算RSA 加密算法，提高了其工作的頻率，加快了其運算的速度。

1 算法介紹

1.1 RSA 加密算法

RSA 加密算法是3 位數學家1977 年提出的非對稱密碼體制，其主要步驟如下：先選擇2 個大素數p和q，然后求出它們的乘積n以及歐拉函數φ(n)=(q?1)·(p?1)；接著選擇一個加密密鑰e，滿足1 ＜e＜φ(n)且e與φ(n)互質；在保證(e，n)作為公鑰對外公開之后，利用公式c=me%n將明文m加密為密文c；此后，將密文發送給接收者進行解密，在保證(d，n)作為私鑰僅為接收者所知之后，利用公式m=cd%n將密文c解密為明文m獲取信息[9?10]。

RSA 算法可以同時應用于數字簽名和加密，由于RSA 加密算法的加解密過程在公式上的一致性，故本文主要研究的是RSA 加密算法的加密過程c=me%n。

1.2 蒙哥馬利模乘算法

RSA 加密算法中所運算的數是1 024 位以上的大數，因此無法直接進行模冪運算。在RSA 中，模冪的運算速度是限制RSA 加密速度的關鍵因素之一。模冪本質上是除法運算，但除法運算是又是四則運算中最耗時的一種運算方式，因此如何通過優化除法運算來加速RSA 運算速度是非常重要的一步。1985 年，Peter Montgomery 發現了一種靈巧的算法，該算法只需要通過乘法和數的位移就可以實現模乘運算，這就是著名的蒙哥馬利模乘算法[11]。

（1a）的q用來補償（1b）中余數被舍棄的問題，其中N[0]·N[0]'%r=1，解q的問題等價于求解二元一次方程A·B?N·M=1 中的最小整數解，其中A=C[0] +A[i]·B[0]，N=r，M=r?N`[0]。借助輾轉相除法，可以計算出B的值，從而得到q的解。特別地，當r=2 時，q=C[0] +A[i]·B[0][13]。

在文獻[14]中提出了其中r=2 的CSA 改進蒙哥馬利算法，使用選擇器代替乘法，使用CSA 鏈完成大數的計算，其算法過程如下所示，其中SUM 和CRY 表示CSA鏈計算出的和與進位，CSA_ADD 表示使用CSA 鏈計算2 個大數的和，B_N表示B和N的總和：

以上代碼中，為了避免出現C超過N的情況，運行時需要進行兩次額外的循環，整個計算過程只需要一個CSA 鏈實現。CSA 改進的蒙哥馬利算法的硬件結構如圖1 所示。在計算中，每一輪循環只能計算一位數據。對于一個n位的數據，最后需要n+2 個周期才能得到結果，因此需要較長時間的運算。

圖1 CSA 改進蒙哥馬利算法

為了提高蒙哥馬利算法的計算速度，在文獻[15]中提出了一種r=4 的蒙哥馬利算法，在計算時將乘法轉換成了加法，下文稱MON4，其硬件結構如圖2 所示。代碼如下其中Bc 和Bs 是上一級蒙哥馬利模塊輸入的數據，Sc、Ss 以及Zc、Zs 分別是從CSA 輸出的和與進位：

在上述的算法中一次迭代會計算A中的兩位數，所以比二進制的蒙哥馬利算法的迭代次數少一半，運算的速度提升了一倍。

而且在硬件實現中做了以下的優化：

（1）在預處理之后使用一個選擇器完成（3c）與（3d）中的形如2·A[2i+1]·Bs +A[2i]·Bs 的乘加計算，省去了乘法運算，降低了邏輯復雜度。

（2）使用CSA 加法器完成大數的計算，（3c）使用一個了CSA 加法器，（3d）使用兩個了CSA 加法器，可以快速地完成大數運算。

當實現了上述的蒙哥馬利算法之后可以將RSA 加密算法改寫成以下計算：

可以看出，其中最重要的就是C=MON(C,M)與M=MON(M,M)兩個大數相乘求余的算式。在當前的ei下進行運算時，M值之間沒有先后順序的關系。也就是，M的平方模乘和(C，M)模乘在計算時是相互獨立且不會互相影響的。因此，在硬件實現中，一般可以采用兩個模乘器，讓平方和模乘兩個操作在一個時鐘周期內并行執行，以達到省時和提速的目的[16?17]。

1.3 改進的高進制蒙哥馬利算法

文獻[15]在實現RSA 加密算法的四進制蒙哥馬利算法中，采用R-L 的并行迭代形式，需要兩個相同的四進制蒙哥馬利算法模塊，共需6 個CSA 鏈。當計算1 024位的大數加密時，一個CSA 鏈需要一千多個CSA 模塊，因此需要大量的硬件資源。此外，該模塊的關鍵路徑較長，無法以較高的頻率工作。針對以上的情況，本文改進了四進制蒙哥馬利算法，下文稱PMON，其中Sc、Ss以及SUM、CRY 同樣是CSA 鏈輸出的和與進位：

在進行蒙哥馬利算法的預處理階段中，按照文獻[15]的方法計算3·B和3·N的值。此時，僅需使用一級CSA 鏈即可完成（4a）的計算。對于q的求解，可觀察到（4a）中 的C[0] +A[i]·B[0]即 為Sc 和Ss 低兩位之和。這可以直接利用（4a）計算的結果得出。在計算（4c）時，同樣只需要使用一個一級CSA 鏈。相關結構示意圖如圖3 所示。進行四進制蒙哥馬利算法的改進后，考慮到RSA 加密算法需要同時計算M=MON(M,M) 以及P=MON(P,M)，還是需要兩個此類模塊，因此本文引入了流水線機制，并將所需的兩個蒙哥馬利模塊合并為一個。

圖3 改進的蒙哥馬利算法

在（4b）和（4c）中加入寄存器片將計算劃分為P1 和P2 兩部分，P1 具有一個CSA 鏈和一個選擇器，P2 具有一個用于計算SUM[i+1]和CRY[i+1]的CSA 鏈。如圖4所示，在第X個時鐘周期中，P1 負責計算M=PMON(M,M) 中的（4b）和（4c）部分，而P2 負責計算P=PMON(P,M)中的（4d）部分；在第X+1 個時鐘周期中，P1負責計算M=PMON(M,M) 中的（4b）和（4c）部分，而P2負責計算M=PMON(M,M)中的（4d）部分。重復以上過程直到計算完成。

圖4 蒙哥馬利算法的流水示意圖

在預處理以及后處理部分需要兩個32 位CPA 加法器，在開始時使用CPA 加法器計算2M+M以及2N+N的值，在結束時分別計算流水線出來的兩級SUM[m/2 +1]+CRY[m/2+1]，最 后RES_PM 與RES_MM 即 為PMON 模塊的輸出結果。

表1 列出了PMON（本文）與MON4（文獻[15]）兩種蒙哥馬利算法實現RSA 加密算法硬件模塊的一些性能參數，n表示計算RSA 加密算法的位數，k表示指數E的位數。使用PMON 計算1 024 位的RSA 加密算法時，考慮最壞的一種情況，即E的寬度也是1 024 位時，使用PMON 完成一次RSA加密需要1 090×1 026=1.12 M 個時鐘周期，在50 MHz 的時鐘下一秒可以完成44 次RSA加密。

表1 文獻[15]與本文方案對比

2 性能分析

本文基于Xilinx 公司XC7K410T 系列的FPGA 開發板，實現了蒙哥馬利算法以及RSA 加密算法，并用Python 實現了相同的算法。為了驗證其正確性，本文首先使用Python 計算C=ME%N完成加密過程，然后計算Q=CD%N完成解密過程，若M與Q相等則證明Python編寫的算法正確。接著，使用VCS 工具對硬件代碼進行仿真，將其結果與Python 代碼的輸出結果進行對比，從而驗證RTL 實現的RSA 加密算法在功能上的正確性。

使用以下的數據對模塊做正確性判定：M=0x1538ebf833ffca2a01d6099faccea21238473afba693cba06 3edfe4c6a420c20；E=65537；N=0x439aeab34eaee973e968 ebdd11d6d3ef7302072c4bfd4f7fe2b0cf9889277f6d；求 出私鑰D=0x2a66af6d669c2daf956549098e76becfae00a8dd7 50ffe85c9c795776014b601。其計算過程如圖5 所示，可以看出最后計算的Q與M相等，可以驗證Python 代碼的正確性。然后查看Verilog 代碼的仿真波形將其輸出結果與Python 代碼的輸出結果做對比。從圖6 可以看出最后的輸出結果output_data 與上述結果相同。

圖5 RSA 加密算法結果示意圖

圖6 RSA 加密算法仿真波形圖

表2 對比了本文所設計的RSA 加密算法模塊和其他文獻設計方案在對1 024 位大數進行加密時的相關數據。除了文獻[18]中在最大工作頻率超過本文的方案外，本文的方案表現出了資源占用更少和工作頻率更高的特點。與文獻[18]相比，本文的方案所占用的資源更少，頻率也沒有顯著下降，因此本文設計的RSA 加密模塊已經達到了優化的目標。

表2 各種方案的性能對比

3 結論

本文對四進制蒙哥馬利模算法進行了優化，實現了硬件資源的節約，減少了關鍵路徑，并在計算RSA 加密算法過程中引入了流水線。在此基礎上，完成了RSA 加密算法模塊的RTL 代碼構建，并進行了仿真驗證。最后，與相關的一些RSA 加密算法模塊的設計進行了性能分析。未考慮拓展性及功耗等方面，下一步需要進行模塊參數化的調整，使該模塊的加密能力不僅限于1 024位，并進行功耗等性能的優化。