摘　要：密碼技術是保障信息安全的核心技術，其中公鑰密碼得到了廣泛應用，其基本運算中的乘法運算是最耗時、最關鍵的運算，設計高效的乘法器對公鑰密碼的有效實現(xiàn)具有重要意義。為提高公鑰密碼的計算速率，設計了一種高效且適合于現(xiàn)場可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）內(nèi)并行計算、多核調用的Montgomery模乘設計方法，該方法通過預計算的方式減少一次模乘計算耗用的時間，通過查表替代實時計算的方式減少對FPGA內(nèi)部邏輯資源的占用，詳細介紹了所研究、設計的內(nèi)容及方法的思想、原理和工程實現(xiàn)結果，并從FPGA的資源和速度2個方面與其他文獻進行了對比分析，給出了對工作的總結和未來應用展望。

內(nèi)容目錄：

0　引　言
1　Montgomery模乘運算
1.1　基本的Montgomery模乘算法
1.2　基于流水線乘法器的FPGA實現(xiàn)Montgomery模乘方法
1.3　基于CSA模乘加法器的FPGA實現(xiàn)Montgomery模乘方法
2　改進后基于預計算方式實現(xiàn)Montgomery模乘方法
3　實現(xiàn)結果及性能分析
4　結論與展望

０ 引　言 

保障信息安全的核心技術是密碼技術，密碼技術為解決信息安全問題提供了重要的科學途徑，其中公鑰密碼解決了傳統(tǒng)對稱密碼面臨的密鑰分發(fā)、密鑰管理和提供過程中不可否認性的難題，在加/解密、數(shù)字簽名等方面得到了廣泛使用，在密碼學中有著持續(xù)的發(fā)展?jié)摿土己玫膽们熬啊?nbsp;

傳統(tǒng)的公鑰密碼算法有橢圓曲線加密算法（Elliptic Curve Cryptography，ECC） 和RSA密碼算法兩種，主要依賴于公鑰基礎設施建設，由具有絕對公信力的證書認證中心為用戶頒發(fā)數(shù)字證書，并將其作為安全憑證，依賴數(shù)字證書和用戶私鑰，對要傳輸?shù)男畔⑦M行簽名和加密，以此保障信息的安全傳輸。為避免傳統(tǒng)數(shù)字證書頒發(fā)和驗證引起的效率問題，產(chǎn)生了標識密碼學理念，該理念提倡將用戶的郵箱、地址等身份標識直接作為用戶公鑰，無須數(shù)字證書即可確保公鑰的可靠性，讓密碼方案更加輕便高效。隨著我國自主設計的商用標識密碼SM9成為行業(yè)標準，標識密碼成為公鑰密碼領域內(nèi)的焦點，并得到廣泛的應用，眾多學者更是進一步為標識密碼引入更為豐富的功能與安全屬性。

目前，常見的公鑰密碼算法設計無論是以 SM9為代表的標識密碼算法還是傳統(tǒng)的ECC、RSA密碼算法，均以模算術運算為基本運算規(guī)則，其操作數(shù)通常是大整數(shù)，具有運算量大、耗時多的弊端，其計算速度成為制約公鑰密碼推廣的瓶頸。其中，RSA密碼算法的基本運算由一系列的模乘構成，ECC密碼算法的有效實現(xiàn)依賴于橢圓曲線群上的點乘與點加等運算，標識密碼算法中涉及復雜的數(shù)據(jù)結構和數(shù)學運算的雙線性對，是構造基于身份標識的加密機制的關鍵技術。因此，模算術運算效率的提升決定了公鑰密碼系統(tǒng)的運行效率和快速推廣的能力，其中模加、模減等運算性能是模乘的數(shù)十倍，設計出高效模乘乘法器一直是公鑰研究領域的關注焦點。Montgomery模乘算法是一種非常高效的模乘算法，該算法使用一系列的加法和除2來代替取模階段的模除運算，因此該算法很適合用硬件實現(xiàn)，通過靈活的資源配置可實現(xiàn)并行計算，提高算法的執(zhí)行效率。

FPGA作為通用可編程芯片，內(nèi)部集成了豐富的可編程邏輯資源及隨機訪問存儲器（Random Access Memory，RAM）資源，成為高速、高效實現(xiàn)密碼算法的絕佳選擇，具有可實現(xiàn)并行計算、靈活編程的優(yōu)點。

本文結合FPGA內(nèi)部基本結構單元的特性、資源分布特性及公鑰密碼算法的運算特點，在速度和資源（即面積）兩個方面進行優(yōu)化以尋求二者的折中平衡，設計了一種預先計算并以查表方式快速高效實現(xiàn)Montgomery模乘的方法。

1  Montgomery模乘運算

Montgomery模乘算法主要用來避免模乘操作或者約簡中耗時的求逆運算，本文對幾種較常規(guī)的Montgomery模乘算法的實現(xiàn)方式進行了簡要介紹。

1.1　基本的Montgomery模乘算法

Montgomery 模乘算法的主要思想是通過簡單的移位操作來代替除法，其基本思想是計算原始的算法1如下：

其中，M為K bit的整數(shù)，即R為整數(shù)，通常取且R>M，X<R，Y<R；為R模M的逆，即 T，u和P為計算過程的變量。

1.2　基于流水線乘法器的FPGA實現(xiàn)Montgomery模乘方法 

常用的Montgomery模乘運算采用流水線乘法器實現(xiàn)的一般方法如下：將長度為K bit的數(shù)據(jù)按照長度r（K可被r整除）分割為L個數(shù)據(jù)， 分割后的數(shù)據(jù)按照權重從小到大依次添加下標進行表示。例如，X可以分割為則P 可以分割為則

遵循1.1節(jié)對各計算要素的描述，基于流水線乘法器的Montgomery模乘算法如下：

其中，M為K bit整數(shù)，D，m和P為計算過程的變量。

1.3　基于CSA模乘加法器的FPGA實現(xiàn)Montgomery模乘方法

文獻[5] 對Montgomery模乘算法進行了改進，設計了一種基于多步CSA加法器實現(xiàn)的Montgomery模乘計算方法，相當于在算法2的基礎上將分割字長定為1 bit（即r=1，L=K），該設計通過在一個時鐘內(nèi)做多次CSA加法迭代運算，達到降低一次模乘運算過程所需時鐘個數(shù)的目的，進而提高模乘運算的速度。

遵循1.1節(jié)對各計算要素的描述，基于CSA模乘加法器的Montgomery模乘算法如下：

其中，M為K bit整數(shù)，A和P為計算過程的變量。

以上算法將模乘運算簡化分解為K個K bit大數(shù)的加法，將乘法運算完全轉換成加法運算。與乘法運算相比，加法運算更適用于通過FPGA芯片來進行工程實現(xiàn)，同時文獻[5]在此基礎上，通過在一個時鐘內(nèi)自主進行步長調整完成多次累加的方式，提高了工程實現(xiàn)的執(zhí)行效率及靈活性。此外，該設計方法中模乘的實現(xiàn)僅使用通用邏輯資源，不依賴任何FPGA提供的IP核，具有很好的可移植性。 

２ 改進后基于預計算方式實現(xiàn)Montgomery模乘方法

在實際的工程應用中，為提高公鑰密碼算法的計算效率，對應用端提供更快速、高效的密碼服務，通常需要在單一芯片中例化多個公鑰算法核，以進行多核調度使用，而單個公鑰密碼算法在執(zhí)行過程中，也會反復多次、盡可能多地并行調用底層Montgomery模乘運算模塊以完成乘法計算，因此如果能通過減少模乘運算所需的時鐘周期數(shù)的方式提高單算法核效率、 減少或均衡利用FPGA硬件資源，那么就可以使單芯片內(nèi)集成更多的算法核，對算法計算整體性能的提高起到重要作用。 

算法2和算法3均能在一定程度上達到較高效的工程應用效果，對這2種設計方法進行進一步分析，算法2在一次乘法運算內(nèi)需進行 2×L次r bit 數(shù)據(jù)與K bit數(shù)據(jù)相乘，在公鑰算法中K值通常較大，自行設計的長位寬乘法難度大、對開發(fā)人員能力的要求較高且通常效率較低，而FPGA提供的乘法器IP核位寬有限，以 Xilinx 公司的 XC7K325T 芯片為例，其提供的乘法算法核最大僅支持64 bit×64 bit的運算，無法直接支撐現(xiàn)有公鑰算法的長位寬大數(shù)運算的需求，因此，只能選擇先拆解再拼裝的方式進行大數(shù)運算。采用芯片自帶乘法器的設計方法，一方面大大增加了設計復雜度，且從低位乘法 拼接成高位乘法的計算過程需要耗費較多的時鐘周期；另一方面FPGA芯片內(nèi)部集成的乘法器資源有限，而在高速計算應用場景下為了提高計算效率，通常需在單一的設計中包含多個例化的Montgomery模乘模塊，以支撐在單一算法核中多路模乘計算的并行運行或支撐多個公鑰密碼算法核各自獨立的并行運行，芯片中自帶乘法器的硬件資源難以滿足該并行使用需求， 因此工程實用過程難以達到預期效果。而算法將算法2中的乘法完全轉換成加法，并以分步長的方式在一個時鐘周期內(nèi)完成多步加法運算，運算設計被大幅簡化，僅需實現(xiàn)多個長位寬加法即可，且不再需要依靠FPGA內(nèi)部有限的乘法IP核資源，具有可忽略芯片型號、便于在不同芯片間快速移植的優(yōu)點。但同時也面臨以下問題：一方面，與乘數(shù)位寬相等的加法步數(shù)計算需占用的FPGA內(nèi)查找表（Look Up Table，LUT）等邏輯資源較多，大數(shù)乘法及多個乘法器例化時耗用的資源成倍增長，難以支撐高速率應用場景下高速、多核并行的計算需求；另一方面，該方法依靠在一個時鐘內(nèi)完成多步加法計算來減少一次運算所需的時鐘數(shù)，雖然有很多關于大整數(shù)加法在FPGA內(nèi)快速實現(xiàn)的研究，但因其進位鏈長，通常所能運行的時鐘頻率不高，而將多步加法計算集中在一個時鐘周期內(nèi)完成也將降低設計整體的工作頻率。

本文在繼承算法2與算法3優(yōu)點的基礎上，突破其工程實現(xiàn)的局限，對模乘的運算環(huán)節(jié)進行了重新拆分和整合，提出了一種通過先預先計算、后查表的方式進行模乘計算的方法，即基于算法2，預先計算長度為K bit的大整數(shù)M、X 分別與字長為r的所有整數(shù)相乘的結果，生成預計算的2個預計算表，每個表的容量均為后續(xù)運算只需對2個預計算表進行算法查找，并基于算法進行相應的加法操作、r bit的小位寬乘法操作即可完成1次Montgomery模乘計算。

遵循1.1節(jié)對各計算要素的描述，基于預計算方式的Montgomery模乘算法如下（其中L=K/r）：

其中，M為K bit整數(shù)，D，m和P為計算過程的變量。

計算過程如圖1所示。

圖1　改進后的Montgomery模乘實現(xiàn)

改進后的算法將1次Montgomery模乘運算分解為預計算查找表的生成過程和循環(huán)迭代的加法、移位、小數(shù)乘法、查表運算過程2個部分。將原本復雜的數(shù)學計算流程簡化為簡單的查表流程，在減少整體計算所需時鐘周期的同時，將原算法3中對FPGA邏輯資源的大量占用部分轉化為豐富的RAM資源，達到對FPGA內(nèi)可工程實現(xiàn)資源的均衡利用的目的。

在FPGA中，加法、移位、小數(shù)乘法和查表等運算的執(zhí)行效率高，因此預計算查找表的生成方式是本設計方法的關鍵所在。本文以一種對 256 bit 被乘數(shù)進行移位、每個時鐘周期內(nèi)2個大整數(shù)相加的方式設計了一種查找表的快速生成方法（4個時鐘周期完成1次查找表的生成計算），其他更優(yōu)秀的設計方法將更快捷、高效地生成預計算查找表，如采用更高效率的加法器、編碼器等設計，能更有效地提高模乘運算整體的運行速度，但該項設計不在本文的研究范圍內(nèi)，故不對其一一進行說明。由于在FPGA中，對數(shù) 據(jù)的倍乘運算可以采用移位的方式簡單實現(xiàn)，非倍乘部分可采用倍乘結果結合加法運算實現(xiàn)，因此本設計將生成預計算表的乘法轉化為一系列的移位和加法操作。同時，考慮到預計算表的容量與r的取值相關，預計算表含個數(shù)據(jù)，即r的取值關系到預計算表大小及生成預計算表所需的時鐘周期。若r取值過大，則預計算表耗費過多FPGA的存儲資源及生成時間，且考慮到本設計方法中K應被r整除。當r取值為4時，乘法更易于轉化為一系列的移位和加法操作，預計算表的計算生成方式更為簡單，同時公鑰算法中大數(shù)的長度普遍為4的倍數(shù)，綜合分析將本設計方法中r的值固定為4較為合適。本文選取在ECC、標識等密碼算法實現(xiàn)中常用的256 bit Montgomery模乘進行說明，以r取為4時，K bit的整數(shù)M的預計算表生成為例，其生成轉換過程如圖2所示。

圖2 r值取4時以整數(shù)M為例的預計算表生成

由圖2可知，被乘數(shù)的數(shù)值每發(fā)生1次變化，即可以生成預計算表。預計算表的生成過程通過簡單移位和1次加法計算（耗用3組長整數(shù)加法的邏輯資源，各自獨立實現(xiàn)2個長整數(shù)的 1 次相加）即可以完成，且每個過程的計算結果可以并行計算得出，在4個周期內(nèi)即可以完成 1 個256 bit Montgomery模乘 4×256 bit 預計算查找表的生成，過程簡單且高效。預計算表生成后， 再通過64次的查表并輔以簡單的加法、1個乘數(shù)固定的4位小數(shù)乘法、移位等計算即可完成 1 次Montgomery乘法運算（從生成預計算表到 生成結果共耗用68個時鐘周期）。

３ 實現(xiàn)結果及性能分析 

為分析本文所提出的設計方法的實現(xiàn)效果，分別在Xilinx 公司Virtex7系列的XC7VX330T器件和Virtex5的XC5VLX30T器件上，以256 bit Montgomery模乘為例對本文設計方法完成實際的工程設計，同時收集了其他文獻中的同長度、多 種類型相關設計成果，以便進行性能的對比分析。 

本文所設計的模乘方法及其他文獻中的相關工程實現(xiàn)的資源開銷和性能情況如表1所示，分別從時鐘頻率、完成一次模乘所需要的時鐘數(shù)和時間，以及硬件占用的資源開銷和類型等 幾項性能指標進行了詳細的對比分析。

表1　資源開銷和性能情況與其他文獻的比較（位寬256 bit）

與文獻[6]相比，本文設計方法在對LUT邏輯資源占用相差不大的情況下，能夠以更高的工作頻率、更少的時鐘數(shù)將一次模乘的計算速度提升超過1/3，在同等硬件資源情況下，具有較明顯的計算速度優(yōu)勢。與文獻[7]相比，本文設計方法在僅使用文獻[7]中約63%邏輯資源的 情況下，達到了文獻[7]中超過90%的一次模乘速率，在多核并行調用時，具有達到相同計算速度所需資源面積更小的優(yōu)勢。且與文獻[6]和文獻[7]中大量采用可移植性差且面積受限的數(shù)字信號處理器（Digital Signal Processor，DSP）資源相比，本文設計方法采用了更易于移植且資源更豐富的RAM資源，在硬件資源的綜合利用方面更貼近FPGA器件內(nèi)部的結構特性，也更便于在芯片內(nèi)例化更多的模乘模塊。與文獻[8]相比，本文設計方法在僅使用文獻[8]中不到 20%邏輯資源的情況下，以更高的工作頻率將一次模乘的計算速度提升了超過3.6倍，在計算速度和資源占用方面均具有較大優(yōu)勢。綜合上述比對分析可知，本文設計方法在硬件資源的均衡占用、運算速率優(yōu)化方面均有較大的優(yōu)勢， 且具有很好的可移植性，更適用于公鑰密碼算法對模乘多組例化、并行調度。 

4 結論與展望 

本文對Montgomery模乘算法原理進行了分析與改進，通過對已有的部分工程實現(xiàn)成果進行優(yōu)化的方式，提出了一種提高Montgomery模乘計算效率的方法。以預計算的方式減少了單時鐘周期內(nèi)的復雜計算，提升了FPGA的工作時鐘頻率并降低整體計算耗用時間；通過查表替代實時大數(shù)計算的方式，平衡減少對FPGA內(nèi)部LUT邏輯資源的占用。該方法在提高計算速度的同時，能夠均衡地利用FPGA內(nèi)部硬件資源，使得在單一芯片內(nèi)可例化更多組Montgomery模乘模 塊，即可以支撐單個公鑰算法盡可能多地并行執(zhí)行乘法運算，進而提高自身運算性能，也能更好地支撐在同等硬件資源情況下，單一設備內(nèi)集成更多組公鑰算法核，以提供更高效便捷的公鑰密碼服務。此外，模乘運算速率的提升打破了標識密碼算法當前計算效率的瓶頸，為進一步取代傳統(tǒng)公鑰體制提供了有利支撐。

引用格式：劉賀,王小驥,劉星江,等.一種適用于FPGA實現(xiàn)的Montgomery模乘設計方法[J].信息安全與通信保密,2024(5):54-61.
作者簡介 >>>
劉　賀，男，學士，高級工程師，主要研究方向為保密通信系統(tǒng)；
王小驥，男，學士，正高級工程師，主要研究方向為保密通信系統(tǒng)； 
劉星江，男，碩士，高級工程師， 主要研究方向為通信保密； 
楊　競，男，博士，高級工程師， 主要研究方向為網(wǎng)絡空間安全、密碼學。
選自《信息安全與通信保密》2024年第5期（為便于排版，已省去原文參考文獻）
重要聲明：本文來自信息安全與通信保密雜志社，經(jīng)授權轉載，版權歸原作者所有，不代表銳成觀點，轉載的目的在于傳遞更多知識和信息。