基于比特重組快速模約簡的高面積效率橢圓曲線標量乘法器設計

劉志偉 張 琦 黃 海 楊曉秋 陳冠百 趙石磊 于 斌

(哈爾濱理工大學計算機科學與技術學院 哈爾濱 150080)

1 引言

橢圓曲線密碼(Elliptic Curve Cryptography,ECC)已經被美國國家標準學會(American National Standards Institute, ANSI)[1]、美國國家標準與技術研究所(National Institute of Standards and Technology, NIST)[2]、電氣電子工程師協會(Institute of Electrical and Electronics Engineers,IEEE)[3]等國際標準組織廣泛接受和部署[4]，應用在各種各樣的場景。在比特幣的基礎技術區塊鏈中，廣泛應用ECC中的secp256k1作為區塊鏈的認證機制[5]；我國自主研發的密碼算法SM2密碼標準，是國密體系中重要環節之一。ECC的應用日益增加，不同應用性能需求各異。例如在服務器和大型計算平臺等，需要密碼芯片具有較高的運算性能。在微控制器等設備中，一般要求密碼芯片具有更小的面積。此外不同的標準通常使用不同的橢圓曲線，所以對多種曲線的兼容也一直是橢圓曲線的重點研究目標。

標量乘架構的研究成為熱點，Hu等人[6]提出SCA-256曲線的二階段快速模約簡方法，利用半字乘法器5個周期計算大數乘法實現高速標量乘的設計；文獻[7]和文獻[8]都對wNAF算法進行了優化，降低了標量乘的計算復雜度，提高了標量乘計算速度；Liu等人[9]利用軟硬結合的方式以較低的面積實現了支持任意曲線的雙域ECC處理器；Hossain等人[10]設計了同時適用于專用集成電路(Application Specific Integrated Circuit, ASIC)和現場可編程邏輯門陣列(Field Programmable Gate Array, FPGA)的標量乘操作步驟，適用于兩條曲線；Liu等人[11]優化了非相鄰形式算法，以高資源消耗實現了支持P256的高速ECC標量乘設計；Hu等人[12]和Choi等人[13]都提出高度資源復用的設計，以極低的硬件資源實現標量乘法器；Zhang等人[14]改進了蒙哥馬利階梯算法，提出了支持SCA-256的抗功耗攻擊的高性能處理器。文獻[15]改進了基2交叉模乘算法，提出了一種高面積時間效率的新型標量乘法器架構。這些設計的時間面積(Area·Time, AT)普遍較差，部分僅適用于特定曲線，ECC處理器需要兼顧速度和面積兩者之間的關系，為解決此問題本文提出了全新的設計。

本文提出了一種基于比特重組快速模約簡的高面積效率ECC標量乘法器，支持secp256k1，secp256r1和SCA-256 3條曲線。本文的主要工作為：

(1)設計了一種兼顧乘法和模逆兩種功能的硬件復用運算單元，提高硬件資源使用率。同時采用Karatsuba-Ofman算法提高運算單元計算性能；

(2)設計了基于比特重組快速模約簡算法，實現了支持secp256k1, secp256r1和SCA-256快速模約簡計算的硬件架構；

(3)優化了點加和倍點的模運算操作調度，使乘法和快速模約簡排布盡量緊密，減少標量乘計算需要的周期數量。

2 研究背景

橢圓曲線有很多種，使用較多的是Weierstrass曲線[16]。這一類曲線滿足式(1)：

NIST提出的曲線secp256r1和secp256k1以及國密sm2密碼算法提出的曲線SCA-256都屬于Weierstrass曲線。

標量乘是ECC的核心運算，定義為kP=P+...+P。其中k是整數，P是橢圓曲線上一點。標量乘算法較多，主要有二進制標量乘算法、非相鄰形式(Non-Adjacent Form, NAF)標量乘算法等[17]。NAF標量乘算法[18]如算法1所示，通過對k進行重新編碼，減少k中非0元素出現的次數以達到提高標量乘性能的目的。

標量乘運算是由一系列的點加(Point Addition, PA)和倍點(Point Doubling, PD)操作實現的。假設P1=(X1,Y1,Z1),P2=(X2,Y2,Z2),P3=(X3,Y3,Z3)是橢圓曲線上的3個點，那么點加操作可以定義為P3=P1+P2，倍點操作可以定義為P3=2P1。為了避免模逆這一復雜的操作，通常使用轉換坐標系的方式減少模逆的計算次數。仿射-雅可比混合坐標系可以產生更快的點加操作，雅可比坐標系可以產生更快的倍點操作[19]。

仿射-雅可比混合坐標系下的點加公式如式(2)所示：

算法1 NAF標量乘算法

雅可比坐標系下的倍點公式如式(3)所示：

3 標量乘法器設計

ECC應至少包含3個算術層：有限域運算層、點運算層和標量乘運算層，本節將按照標量乘法器的結構層次，自底向上介紹本文提出的標量乘法器設計。

3.1 資源共享的運算單元設計

本文使用計算速度較快的快速模約簡模乘，該模乘分為整數乘法運算和快速模約簡運算兩部分，整數乘法運算性能對模乘影響較大。使用大位寬乘法器計算乘法只需要一個周期，但是需要消耗大量硬件資源，使用小位寬乘法器計算乘法雖然面積較小，但是需要較多周期計算乘法，速度較慢，因此選擇大小合適的乘法器是設計該部分的關鍵。Karatsuba-Ofman算法[20]可以將兩個256 bit的大數乘法轉化為3個128 bit的乘法和一些加減及移位操作，如式(4)所示。

該算法雖然可以減少乘法大小，但是同樣帶來了額外一些額外的計算。為了減少這些額外的計算帶來的影響，優化了Karatsuba算法的操作調度方式，如算法2所示。

本文提出的調度方式將式(4)分為3個周期進行計算，前兩個周期使用乘法器和加法器可以得到a1b1,a0b0,a0+a1,b0+b1以及-(a1b1+a0b0)的結果，分別存入寄存器s,v,r和u中。第3個周期利用乘法器和加法器c1得到(a0+a1)(b0+b1)-(a1b1+a0b0)的結果。式(3)中可以看出(a1b12256+a0b0)可以通過位拼接直接實現，[(a0+a1)(b0+b1)-(a1b1+a0b0)]2128可以通過c1左移128 bit實現。c1左移128 bit后低位都為0，(a1b12256+a0b0)的低128 bit即a0b0的低128 bit，所以兩者相加可以先舍去低128 bit，只相加剩余部分，通過加法器c2得到這一結果，然后將c2與a0b0的低128 bit進行拼接，可以得到最終的乘法結果C。

算法2 改進的Karatsuba算法操作調度

優化后的調度方式需要使用1個乘法器和2個加法器，以及4個存儲中間結果的寄存器，經過3個時鐘周期可以得到512 bit的乘法結果C。

為進一步提高設計的面積效率，本文提出了一種乘法與模逆可以實現資源共享的運算單元設計，此設計盡可能地復用加法器和寄存器實現乘法和模逆兩種運算。模逆使用RS-A模逆算法[21]，結合算法2及RS-A模逆算法設計出的新的運算單元如圖1所示。此運算單元通過控制信號切換功能，當使用乘法功能時，進位保存加法器(Carry Save Adder,CSA)相當于算法2中的加法器c1，只需將第3個輸入置0即可，加法器1相當于算法2中的加法器c2。然后根據算法2中的調度方式控制乘法器和加法器選擇不同的輸入實現乘法計算的功能，最后512 bit乘法結果分為高256 bit和低256 bit分別存入4個寄存器中，方便后續快速模約簡模塊進行比特重組。

圖1 資源共享的運算單元

使用模逆功能時，CSA加法器負責RS-A模逆算法中加減模數p的相關計算，除2操作通過移位實現。加法器1負責RS-A模逆算法中的其他加減計算，除2也通過移位實現。然后根據RS-A模逆算法中的不同條件控制寄存器的輸入輸出選擇和加法器的輸入選擇，最終實現模逆功能。

此運算單元在不同功能的各個工作階段，通過數據選擇器選擇不同的數據來源，即可實現乘法功能或模逆功能。因為乘法和模逆運算過程中都需要使用加法器，所以兩種運算不能同時進行。通過轉換坐標系的方式，標量乘運算過程中模乘和模逆不會同時進行，所以不會影響整體性能。與文獻[6]相比，我們提出的結構乘法速度更快，也不需要額外的資源實現單獨的模逆；與文獻[22]相比乘法運算消耗周期數相同，但本文資源共享的結構使得面積更有優勢。

3.2 基于比特重組的快速模約簡設計

模約簡需要根據曲線特點進行單獨設計，不能直接套用其他曲線模約簡公式。對于secp256k1，p=2256-232-29-28-27-26-24-1=2256-232-210+26-24-1，p的位寬為256 bit。乘法結果最高為512 bit，將乘法結果表示為C=c1272508+c1262504+...+c124+c0，其中ci位寬為4 bit。根據p的特點，secp256k1有如式(5)同余關系式：

乘法結果的高256 bit可以通過式(6)右半部分的式子相加得到約簡后的結果，然后再與乘法結果的低256 bitc632252+...+c0相加。將其按冪次由高到低排列，整理為和項和差項后，得到算法3。本文使用兩個步驟完成secp256k1快速模約簡的計算。首先第1步將乘法結果C分解為128個4位數據段，然后重組為s1～s16，此過程為比特重組。然后將重組后的16個數據段進行計算得到z1∈(-3p,8p)。第1步的結果可能產生進位或借位，所以第二階段需要對其再進行處理。當z1大于0時，我們將z1高位補0然后重復一次第1步操作，約簡結果z2∈[0，2p)，最多還需要一次減法就能得到最終約簡結果。當z1小于0時，通過最多3次累加可以得到最終約簡結果。

文獻[1 4]和文獻[2 3]提供了S C A-2 5 6 和secp256r1的快速模約簡公式，是將512 bit數據拆分為16個32 bit數據段，32 bit數據段可以進一步拆分為8個4 bit數據段，因此同樣可以使用比特重組方法進行快速模約簡算法的設計。

本文利用比特重組方法提出兼容3條曲線的快速模約簡結構，如圖2所示。比特重組模塊根據不同曲線的快速模約簡公式將乘法結果進行拆分與重組，華萊士樹模塊負責快速模約簡算法中第1步和第2步中z1≥0時的計算，加法器陣列負責第2步z1＜0時的計算。為減少資源消耗和路徑延遲，將兩個步驟的快速模約簡分為3個時鐘周期計算。首先第1個時鐘周期利用比特重組模塊將輸入進行重組，重組為s1～s16，其中secp256r1只有s1～s11為有效值，s12～s16為全0。然后使用CSA加法器組計算快速模約簡公式的第1步中的s1+s2+s3+s4+s5+s6+s7-s12-s13，減法通過補碼加法實現，結果存入w中。第2個周期計算w+s8+s9+s10+s11-s14-s15-s16，結果存入w中，此時已經計算完畢z1。第3個時鐘周期先判斷w的符號位，若w ≥0則使用比特重組模塊將w重組為t1～t4，然后使用華萊士樹計算得到z2。若z2超過p-1則通過加法器完成減p操作。若w ＜0，則使用加法器陣列進行累加，通過判斷每一級加法器中間結果的符號位選擇正確的約簡結果。

圖2 兼容3條曲線快速模約簡結構

算法3 secp256k1快速模約簡算法

雖然快速模約簡相比常規方式需要周期數更多，但是本文通過對點加和倍點的模運算操作調度進行優化降低了其負面影響，將在下一節詳細介紹。

3.3 高速點加和倍點設計

標量乘運算通過點加和倍點運算實現，因此對于點加和倍點的優化也十分重要。仿射-雅可比混合坐標系下的點加和雅可比坐標系下的倍點公式模乘計算次數較少[22]，結合上文中提出的設計對點加和倍點的模運算操作調度進行了優化。為使乘法與模約簡的排布盡量緊密，減少標量乘運算所需周期數量，本文提出了倍點和點加兩種操作合一的模運算操作調度方案。

倍點和倍點點加合一的模運算操作調度如圖3所示，圖3(a)為倍點的模運算操作調度，圖3(b)為倍點點加合一的模運算操作調度。其中雅可比坐標系輸入點(X1,Y1,Z1) 用(t5,t6,t7)表示，仿射坐標系輸入點用(x2,y2)表示，得到的雅可比坐標系下點(X2,Y2,Z2)也用(t5,t6,t7)，t1～t7為寄存器。

圖3 高速點加和倍點的模運算操作調度

通過優化后的調度方法，1次模乘平均只需要3個周期，消除了因快速模約簡計算需要3個周期帶來的影響。標量乘運算過程中點加和倍點操作是連續進行的，我們提出的兩種調度方式在最后3個周期可以開始下一次運算的第1次乘法，此時需要額外的周期計算第1次模加。故1次倍點平均需要27個周期，1次倍點點加需要60個周期。

3.4 總體設計

本文將secp256k1, secp256r1, SCA-2 563條曲線的標量乘集成為1個單元進行設計，圖4給出了標量乘法器的硬件架構。標量乘法器由標量乘控制模塊、倍點和倍點點加控制模塊、NAF編碼器、模運算單元和寄存器組5部分組成。

圖4 標量乘法器

標量乘控制模塊對標量乘法器整體進行控制，控制NAF編碼器、點運算和有限域運算的開始和結束，使標量乘法器可以準確地完成標量乘運算。切換曲線也通過該模塊實現，當切換不同曲線時，標量乘控制模塊控制點運算和有限域運算選取不同的曲線參數。倍點控制和倍點點加控制模塊負責點運算的順利完成，控制底層模運算單元的開始和結束、模運算單元和寄存器組的輸入與輸出選擇。模運算單元包括模加減模塊、資源共享的運算單元和快速模約簡模塊，負責有限域運算。寄存器組存儲模運算單元產生的所有中間結果。

4 實驗結果

表1是使用55 nm CMOS工藝綜合得到標量乘法器中主要模塊面積，可以看到資源共享的運算單元為151k等效二輸入與非門，占整個標量乘法器面積的54%，是占比最大的模塊。表2給出了每個橢圓曲線操作需要的周期數量。1次標量乘共需要10 366個周期，在500 MHz的頻率下計算1次標量乘需要0.02 ms，每秒可以計算48 309次標量乘。

表1 主要模塊面積

表2 橢圓曲線操作周期

本文標量乘法器最終性能如表3所示，為了得到合理的對比，在ASIC平臺使用55 nm和130 nm的工藝進行了前端邏輯綜合，在FPGA平臺使用Virtex-7進行了實現，并與類似工作進行了比較。

表3 256位素數域下橢圓曲線標量乘法器的性能比較

文獻[22]使用快速模約簡方式模乘，支持單曲線secp256r1，使用滑動窗口NAF標量乘算法，標量乘消耗周期數少，但是主頻較低而且面積更大，所以本文AT值更有優勢。文獻[9]使用基4交錯模乘，標量乘法器面積較小，但一次模乘需要大量周期，導致吞吐量和AT較差。文獻[10]提出新的倍點和點加并行技術減少操作步驟，主頻是所有設計中最高的，但是面積大，而且標量乘計算速度慢，與之相比本文的設計在AT值和吞吐量都很有優勢。文獻[11]采用128 bit的分段模乘，一次標量乘僅需0.0125 ms，每秒可實現80 000次標量乘，是所有設計中吞吐量最高的，但是標量乘法器面積是本文的12倍，AT值遠大于本文提出的設計。文獻[6]設計面積比本文小，但一次乘法需要5個周期計算，計算標量乘需要的周期比本文多，所以標量乘計算速度比本文慢，AT值比本文高。文獻[12]和文獻[13]都以硬件資源消耗最少為目標，所以速度都較慢，AT值都遠遠大于本文。文獻[14]通過改進蒙哥馬利階梯算法，使得點加和倍點同時進行，雖然面積較小，但標量乘速度慢，吞吐量和AT值都差于本文。文獻[24]采用蒙哥馬利階梯算法實現標量乘，雖然采用了轉換坐標系方式提高標量乘計算速度，但是基2交錯模乘速度慢，吞吐量和AT都不高。文獻[25]提出了一種基于RNS的ECC處理器，可同時處理多個標量乘操作，但AT差于本文設計。

5 結論

本文提出了一種基于比特重組快速模約簡的高面積效率ECC標量乘法器設計。利用Karatsuba-Ofman算法設計出僅需3個時鐘周期的乘法器，提升了乘法的計算速度?；诖顺朔ㄆ?，又提出乘法與模逆資源共享的運算單元設計，在原乘法器結構基礎上只增加一個CSA加法器可實現乘法或模逆的計算，在不影響兩者速度的情況下進一步降低硬件資源消耗。推導了secp256k1曲線的快速模約簡公式，基于比特重組方法與secp256r1和SCA-256兩條曲線融合，設計了兼容3條曲線的快速模約簡結構。最后根據所設計的運算單元和快速模約簡結構提出了新的點加和倍點的操作調度方法，提高了乘法與快速模約簡的并行性，從而獲得了更高的吞吐量。實驗結果表明，該標量乘法器的AT值比現有的大部分設計更低，此外在吞吐量方面也具有優越性。