0 引言

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

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

1 背景介紹

1.1 Kogge-Stone加法器

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

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

1.2 進(jìn)位保留加法器

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

    CSA用表達(dá)式可以表示為：

1.3 模乘算法分析

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

    二元域運(yùn)算與素?cái)?shù)域的不同在于二元域運(yùn)算沒有進(jìn)位，運(yùn)算更加簡單。素?cái)?shù)域中的模數(shù)P，在二元域中表示為不可約多項(xiàng)式F(x)。模乘素?cái)?shù)域用進(jìn)行2Amod P、4Amod P和x+y+zmod P三種運(yùn)算，在二元域中表示為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交錯(cuò)模乘算法，本文設(shè)計(jì)了長度可變的雙域模乘器，其總體結(jié)構(gòu)如圖2所示。實(shí)線框內(nèi)表示素?cái)?shù)域的模乘運(yùn)算單元，長虛線框內(nèi)表示用于二元域模乘的運(yùn)算單元。短虛線框中標(biāo)出的是本結(jié)構(gòu)中的復(fù)用部分，一是x²·A(x)modf(x)結(jié)構(gòu)復(fù)用了x·A(x)modf(x)結(jié)構(gòu)；二是復(fù)用x+y+zmod P結(jié)構(gòu)中的CSA0中三操作數(shù)的異或輸出sum，實(shí)現(xiàn)二元域上的三操作數(shù)相異或。

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

    運(yùn)算單元是雙域模乘器的核心部分，主要包括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ù)寄存器主要用于寄存每一輪迭代計(jì)算出的U、V、A、B的值，數(shù)據(jù)選擇器選擇寄存運(yùn)算單元的結(jié)果。

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

2.2 雙域模乘器運(yùn)算單元

2.2.1 素?cái)?shù)域

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

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

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

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

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

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

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

    實(shí)現(xiàn)x+y+zmod P，先計(jì)算x+y+z，再判斷x+y+z與P的大小，重復(fù)進(jìn)行“-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個(gè)CSA和3個(gè)KSA組成。并行計(jì)算x+y+z、x+y+z-P、x+y+z-2P，根據(jù)KSA1和KSA2的進(jìn)位輸出作為數(shù)選信號，選擇最后輸出結(jié)果。

2.2.2 二元域

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

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

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

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

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

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

3 性能分析

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

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

    綜合比較，本設(shè)計(jì)能同時(shí)支持素?cái)?shù)域GP(p)和二元域GP(2^m)的模乘運(yùn)算，并且適配不同長度的位寬需求，具有較強(qiáng)的靈活性和可擴(kuò)展性。

4 結(jié)論

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

參考文獻(xiàn)

[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ì)[J].微電子學(xué)與計(jì)算機(jī)，2013(9)：17-21.

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

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

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

作者信息:

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

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