《電子技術應用》
您所在的位置:首頁 > 模拟設計 > 設計應用 > 基于Kogge-Stone加法器改進的雙域模乘器
基于Kogge-Stone加法器改進的雙域模乘器
2019年電子技術應用第8期
楊丹陽1,楊 萱2,陳 韬1,戴紫彬1,李 偉1
1.信息工程大學,河南 鄭州450001;2.江南計算技術研究所,江蘇 無錫214083
摘要: 模乘作為橢圓曲線公鑰密碼算法的核心運算,調用頻率最高,提高其運算速度對于提高橢圓曲線密碼處理器的性能具有重要意義。基于Kogge-Stone加法結構,結合可重構技術,實現一種能夠同時支持素數域GF(p)和二元域GF(2m)上模乘運算的雙域模乘器,并對模塊進行合理複用,節省硬件資源。用Verilog VHDL語言對該模乘器進行RTL級描述,并采用0.18 μm CMOS工藝标準單元庫進行邏輯綜合。實驗結果表明,該雙域模乘器的最大時鐘頻率為476 MHz,占用硬件資源66 518 gates,實現256位的模乘運算僅需0.27 μs。
中圖分類号: TP309.7
文獻标識碼: A
DOI:10.16157/j.issn.0258-7998.190106
中文引用格式: 楊丹陽,楊萱,陳韬,等. 基于Kogge-Stone加法器改進的雙域模乘器[J].電子技術應用,2019,45(8):75-78,82.
英文引用格式: Yang Danyang,Yang Xuan,Chen Tao,et al. Dual-field modular multiplier using Kogge-Stone adder[J]. Application of Electronic Technique,2019,45(8):75-78,82.
Dual-field modular multiplier using Kogge-Stone adder
Yang Danyang1,Yang Xuan2,Chen Tao1,Dai Zibin1,Li Wei1
1.Information Engineering University,Zhengzhou 450001,China;2.Jiangnan Institute of Computing Technology,Wuxi 214083,China
Abstract: As the key operation, modular multiplication is the highest frequency of use in elliptic curve cryptography algorithm. Improving its operation speed is great significant to improve the performance of elliptic curve cryptography processor. Based on Kogge-Stone add structure, and combined with reconfigurable technology, this paper implemented a modular multiplier which support the operation in both prime field GF(p) and finite field GF(2m). And this modular multiplier reuse logic unit reasonably to save hardware resources. The modular multiplier was described by Verilog VHDL, and integrated in CMOS 0.18 μm technology library. The experimental results show that the maximum clock frequency of this modular multiplier circuit is about 476 MHz and use about 66 518 gates of hardware resources. The 256 bit Dual-field modular multiplication can be finished in 0.27 μs.
Key words : dual-field operation;modular multiplication;Kogge-Stone adder;elliptic curve cryptograph

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(2m)的模乘運算。根據操作數位寬控制疊代輪數,靈活适配各種長度的模乘運算。

1 背景介紹

1.1 Kogge-Stone加法器

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

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

wdz7-t1.gif

1.2 進位保留加法器

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

    CSA用表達式可以表示為:

wdz7-1.3-s1.gif

1.3 模乘算法分析

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

wdz7-1.3-x1.gif

wdz7-1.3-x2.gif

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

2 模乘結構

2.1 模乘總體結構

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

wdz7-t2.gif

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

    運算單元是雙域模乘器的核心部分,主要包括2Amod P結構、4Amod P結構、x+y+zmod P結構、x·A(x)mod f(x)結構和x2·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的結果分兩種情況:

     wdz7-t3-s1.gif

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

wdz7-t3.gif

    (2)4Amod P結構

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

     wdz7-t3-x1.gif

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

wdz7-t4.gif

    (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的結果分三種情況:

     wdz7-t4-x1.gif

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

wdz7-t5.gif

2.2.2 二元域

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

    (1)加法結構

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

    (2)x乘結構

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

     wdz7-t5-x1.gif

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

wdz7-t6.gif

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%。綜上,本文的雙域模乘器在速度和面積上具有綜合優勢。

wdz7-b1.gif

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

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)