0 引言

    公鑰密碼體制因其強大的安全性，廣泛應用于信息安全領域。橢圓曲線密碼算法與RSA相比，具有相同安全性下運算速度更快、占用資源更少、位寬更低的優點，成為新一代的公鑰密碼體制標準。橢圓曲線密碼處理器通常根據每秒鐘點乘的計算次數作為衡量其性能好壞的標準之一。實現點乘運算，要大量調用模乘、模除和模加減等有限域層模運算。模除運算最為復雜，耗時最多，通常引入投影坐標系，降低調用次數。而與模乘相比，模加減的運算量幾乎可以忽略。模乘是橢圓曲線密碼算法中最基本、最核心的一種模運算，提高其運算速度將有效提高橢圓曲線密碼處理器性能。

    如今，設計一種靈活高效、適用于多種安全場景的模乘器仍然是研究熱點。文獻[1]基于CPA和CSA結構實現了的統一的MALU單元，能夠有效完成模運算，資源復用率高，靈活性和可擴展性強，但是隨著運算位寬的增加，CPA的進位鏈會成為瓶頸，大大制約著電路的性能。文獻[2]采用64位的基4 Kogge-Stone超前進位加法器實現DFA，實現新型的Wallace數乘法單元，縮短了運算時間，但硬件資源占用較多。文獻[3]在Blakley算法的基礎上，提出改進的Radix-4快速模乘算法，采用Booth編碼減少迭代次數，并采用符號估計技術避免大整數比較，還基于擴展Euclidean求逆算法，設計統一硬件電路，雖然面積很小，但是運算速度不高。本文根據基于Radix-4交錯模乘算法^[4]，采用進位保留加法器(Carry Save Adder，)和Kogge-Stone加法器(Kogge-Stone Adder，KSA)^[5]組合的加法結構，縮短電路關鍵路徑，同時支持素數域GF(p)和二元域GF(2^m)的模乘運算。根據操作數位寬控制迭代輪數，靈活適配各種長度的模乘運算。

1 背景介紹

1.1 Kogge-Stone加法器

    在硬件電路設計中，基礎的加減乘除運算，最終都可以通過多次加法計算來實現，因此加法器是許多運算模塊的基礎單元，其性能好壞直接關系到整個電路的性能。對于傳統加法器，如串行進位加法器、進位選擇加法器，高位的計算需要低位的進位輸出。隨著運算位寬的增加，加法器的進位鏈不斷增長，大大制約著加法器的運算性能。為了減少進位時間，1973年，KOGGE P M和STONE H S提出了并行前綴的超前進位加法器，使高位的計算與前一位的進位結果無關，從而大大提高加法器的速度。

    本文中KSA采用4位一組的點操作，計算延遲是log₄N級點操作的延遲，與普通的二進制KSA加法器結構相比速度提高一倍。圖1是以計算16位加法為例的四進制KSA結構^[4]，該結構由三種基本單元構成。最上面的正方型代表前置進位信號產生電路，用于產生進位傳播信號P_i和進位產生信號G_i。最下面的菱形表示最終的進位生成電路與求和電路，用于產生每一位的進位信號C_i與加法和S_i。中間的圓形代表Kogge-Stone樹結構，用于產生進位信號C_i所需的中間結果，包括塊進位產生信號和塊進位傳播信號。

1.2 進位保留加法器

    進位保留加法器(CSA)常用于多操作數的加法。假設計算三個m比特的操作數A、B和C的和，采用CSA結構，將輸出兩個結果：本位異或結果sum與進位carry。還需要一個加法器將sum和carry相加，本文中，CSA和KSA共同完成三操作數相加。

    CSA用表達式可以表示為：

1.3 模乘算法分析

    模乘是橢圓曲線密碼的核心運算，本文中交錯模乘算法如算法1所示，支持素數域GF(p)和二元域GF(2^m)上的運算。

    二元域運算與素數域的不同在于二元域運算沒有進位，運算更加簡單。素數域中的模數P，在二元域中表示為不可約多項式F(x)。模乘素數域用進行2Amod P、4Amod P和x+y+zmod P三種運算，在二元域中表示為x·A(x)mod F(x)、x2·A(x)mod F(x)和xyz。

2 模乘結構

2.1 模乘總體結構

    根據Radix-4交錯模乘算法，本文設計了長度可變的雙域模乘器，其總體結構如圖2所示。實線框內表示素數域的模乘運算單元，長虛線框內表示用于二元域模乘的運算單元。短虛線框中標出的是本結構中的復用部分，一是x²·A(x)modf(x)結構復用了x·A(x)modf(x)結構；二是復用x+y+zmod P結構中的CSA0中三操作數的異或輸出sum，實現二元域上的三操作數相異或。

    該結構由運算單元、控制器和中間數據寄存器組成。

    運算單元是雙域模乘器的核心部分，主要包括2Amod P結構、4Amod P結構、x+y+zmod P結構、x·A(x)mod f(x)結構和x²·A(x)mod f(x)結構。

    中間數據寄存器主要用于寄存每一輪迭代計算出的U、V、A、B的值，數據選擇器選擇寄存運算單元的結果。

    控制器基于狀態機設計，產生數據路徑中數選器的選擇信號，以控制數據路徑中的數據流向，完成雙域模乘運算時各個模塊的調度控制。并根據域選擇信號以及數據長度，進行判斷執行素數域還是二元域運算，以及迭代輪數。

2.2 雙域模乘器運算單元

2.2.1 素數域

    （1）2Amod P結構

    實現2Amod P，即完成A左移一位，再判斷2A與P的大小決定是否進行“-P”操作，以實現0≤2Amod P<P。由于0≤A<P，則0≤2A<2P，故2Amod P的結果分兩種情況：

    2Amod P結構如圖3所示，該結構由一個KSA和一個數據選擇器組成。KSA主要用來計算2A-P，數據選擇器將KSA的進位輸出作為數選信號，判斷2Amod P的輸出結果。

    (2)4Amod P結構

    實現4Amod P，首先A左移兩位，再判斷4A與P的大小，重復進行“-P”操作直至0≤4Amod P<P。由于0≤A<P，則0≤4A<4P，故4Amod P的結果分四種情況：

    4Amod P結構如圖4所示，該結構由1個CSA和3個KSA組成。并行計算4A-P、4A-2P、4A-3P，根據三個KSA的進位輸出作為數選信號，選擇最后輸出結果。

    (3)x+y+zmod P結構

    實現x+y+zmod P，先計算x+y+z，再判斷x+y+z與P的大小，重復進行“-P”操作直至0≤x+y+zmod P<P。由于0≤x、y、z<P，則0≤x+y+z<3P，故x+y+zmod P的結果分三種情況：

    x+y+zmod P結構如圖5所示，該結構由3個CSA和3個KSA組成。并行計算x+y+z、x+y+z-P、x+y+z-2P，根據KSA1和KSA2的進位輸出作為數選信號，選擇最后輸出結果。

2.2.2 二元域

    二元域不同于素數域，算法更為簡單，移位與異或即可實現x乘，將操作數按位異或即可實現加法，無需考慮進位。

    (1)加法結構

    本文中，二元域三操作數異或通過復用x+y+zmod P結構中的CSA0實現。

    (2)x乘結構

    實現x·A(x)mod f(x)，即將A(x)左移一位，如果a_m-1=1，將之與f(x)進行異或。

    其結構如圖6所示，將此結構進行級聯，即可實現。

3 性能分析

    本文采用Verilog HDL硬件描述語言對雙域模乘器進行RTL級描述，并利用ModelSim進行功能仿真驗證。在0.18 μm CMOS工藝標準單元庫對雙域模乘器進行邏輯綜合，綜合工具使用Synopsys公司的Design Complier。綜合結果表明，雙域模乘器占用硬件資源66 518 gates，最高時鐘可達到476 MHz，計算256 bit的模乘運算僅需0.27 μs。

    本文中雙域模乘器結構的關鍵路徑在于CSA和KSA組合的加法結構。為了驗證模乘器的性能，將本文和其他文獻的模乘單元的性能進行比較，其結果如表1所示。本文與文獻[2]相比，模乘運算時間降低了20.59%，且面積減小了55.67%。本文的運算時間是文獻[6]的3.38倍，但面積大概只有文獻[6]的1/10。與文獻[3]相比，雖然面積略大，但256 bit的計算時間降低了87.2%。與文獻[7]相比，本文速度降低不多，但面積減小了28.26%。綜上，本文的雙域模乘器在速度和面積上具有綜合優勢。

    綜合比較，本設計能同時支持素數域GP(p)和二元域GP(2^m)的模乘運算，并且適配不同長度的位寬需求，具有較強的靈活性和可擴展性。

4 結論

    本文基于雙域Radix-4交錯模乘算法，采用CSA和KSA組合的加法結構，實現長度可伸縮的雙域模乘器。采用基于Kogge-Stone結構的并行前綴加法器，減小了進位延遲，縮短了該模乘單元的關鍵路徑，大大提高了運算頻率，尤其當運算位寬越大，優勢越明顯時。結構上復用了素數域x+y+zmod P結構的CSA0加法器中的異或門實現二元域中的三操作數的異或，減少硬件資源，提高單元利用率。

參考文獻

[1] LIU Z，LIU D，ZOU X.An efficient and flexible hardware implementation of the dual-field Elliptic curve cryptographic processor[J].IEEE Transactions on Industrial Electronics，2017，64(3)：2353-2362.

[2] 郭曉，蔣安平，宗宇.SM2高速雙域Montgomery模乘的硬件設計[J].微電子學與計算機，2013(9)：17-21.

[3] 陳光化，朱景明，劉名，等.雙有限域模乘和模逆算法及其硬件實現[J].電子與信息學報，2010，32(9)：2095-2100.

[4] 李泉龍.基于Kogge-Stone算法與多米諾邏輯的64位高性能加法電路設計[D].成都：西南交通大學，2016.

[5] KOGGE P M，STONE H S.A parallel algorithm for the efficient solution of a general class of recurrence Equations[J].IEEE Transactions on Computers，1973，C-22(8)：786-793.

[6] 廖望，萬美琳，戴葵，等.可擴展雙域模乘器設計與研究[J].華中科技大學學報(自然科學版)，2015(9)：51-54.

[7] 李嘉敏，戴紫彬，王益偉.可編程可伸縮的雙域模乘加器研究與設計[J].電子技術應用，2018，44(1)：28-32，36.

作者信息:

楊丹陽1，楊  萱2，陳  韜1，戴紫彬1，李  偉1

(1.信息工程大學，河南 鄭州450001；2．江南計算技術研究所，江蘇 無錫214083)