0 引言

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

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

1 背景介紹

1.1 Kogge-Stone加法器

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

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

1.2 進位保留加法器

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

    CSA用表達式可以表示為：

1.3 模乘算法分析

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

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

2 模乘結(jié)構(gòu)

2.1 模乘總體結(jié)構(gòu)

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

    該結(jié)構(gòu)由運算單元、控制器和中間數(shù)據(jù)寄存器組成。

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

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

    控制器基于狀態(tài)機設(shè)計，產(chǎn)生數(shù)據(jù)路徑中數(shù)選器的選擇信號，以控制數(shù)據(jù)路徑中的數(shù)據(jù)流向，完成雙域模乘運算時各個模塊的調(diào)度控制。并根據(jù)域選擇信號以及數(shù)據(jù)長度，進行判斷執(zhí)行素數(shù)域還是二元域運算，以及迭代輪數(shù)。

2.2 雙域模乘器運算單元

2.2.1 素數(shù)域

    （1）2Amod P結(jié)構(gòu)

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

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

    (2)4Amod P結(jié)構(gòu)

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

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

    (3)x+y+zmod P結(jié)構(gòu)

    實現(xiàn)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的結(jié)果分三種情況：

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

2.2.2 二元域

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

    (1)加法結(jié)構(gòu)

    本文中，二元域三操作數(shù)異或通過復用x+y+zmod P結(jié)構(gòu)中的CSA0實現(xiàn)。

    (2)x乘結(jié)構(gòu)

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

    其結(jié)構(gòu)如圖6所示，將此結(jié)構(gòu)進行級聯(lián)，即可實現(xiàn)。

3 性能分析

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

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

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

4 結(jié)論

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

參考文獻

[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模乘的硬件設(shè)計[J].微電子學與計算機，2013(9)：17-21.

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

[4] 李泉龍.基于Kogge-Stone算法與多米諾邏輯的64位高性能加法電路設(shè)計[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] 廖望，萬美琳，戴葵，等.可擴展雙域模乘器設(shè)計與研究[J].華中科技大學學報(自然科學版)，2015(9)：51-54.

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

作者信息:

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

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