面向物聯(lián)網(wǎng)領域的低成本ECC密碼處理器設計

摘 "要： 為了保障物聯(lián)網(wǎng)設備的隱私和安全，同時更好地滿足其資源受限的特性，采用橢圓曲線密碼（ECC）算法方案，通過優(yōu)化底層算法和電路結構，設計了基于加法器的低成本架構的點乘硬件電路。采用硬件復用技術來減少資源消耗，每個模運算電路只用一個超前進位加法器；優(yōu)化模運算算子調度，改進電路結構，點運算只使用兩個模加減模塊、一個模逆模塊和一個模乘模塊設計實現(xiàn)。在Xilinx公司XCZU3CG?SFVC784?1?E的FPGA平臺上進行分析，該點乘電路共使用了8 927個CLB LUTs，7 789個CLB Registers，電路總功耗為0.371 W，工作頻率可達247.3 MHz，對比其他架構，處理器硬件資源節(jié)省了39.10%～72.44%。

關鍵詞： 物聯(lián)網(wǎng)； 橢圓曲線密碼； 密碼處理器； 模運算； 硬件復用； FPGA

中圖分類號： TN919?34； TN492?34 " " " " " " " " " 文獻標識碼： A " " " " " " " " "文章編號： 1004?373X（2024）18?0095?06

Design of low?cost ECC processor for IoT domain

MA Jingwan， QU Yingjie

（College of Information Science and Technology， Qingdao University of Science and Technology， Qingdao 266061， China）

Abstract： In order to ensure the privacy and security of Internet of Things （IoTs） devices， and better meet the resource?limited characteristics， the elliptic curve cryptography （ECC） algorithm scheme is used to design a low?cost architecture for a dot multiplication hardware circuit based on the adder by optimizing the underlying algorithm and circuit structure. Hardware resource consumption is minimized by means of hardware reuse technology， with each modular arithmetic circuit using only one carry?save adder. By optimizing modular arithmetic operator scheduling and improving circuit structure， point operations are designed and implemented using only two modular addition and subtraction modules， one modular inverse module and one modular multiplication module. The analysis are conducted on Xilinx's XCZU3CG?SFVC784?1?E FPGA platform， a total of 8 927 CLB LUTs and 7 789 CLB Registers are used in the dot multiplication circuit， with a total power consumption of 0.371 W and an operating frequency of 247.3 MHz. In comparison with other architectures， the processor hardware resources are saved from 39.10% to 72.44%.

Keywords： Internet of Things; elliptic curve cryptography; cryptography processor; modular operation; hardware reuse; FPGA

0 "引 "言

當物聯(lián)網(wǎng)（Internet of Things， IoT）技術迎來蓬勃發(fā)展之際，物聯(lián)網(wǎng)設備的隱私和安全問題愈發(fā)引人關注[1?2]。由于這些設備的資源有限，無法過多耗費于密碼計算，因此，迫切需要安全、高效且占用資源小的密碼處理器，以滿足資源受限的物聯(lián)網(wǎng)設備的安全需求[3?4]。目前通用的幾種密碼算法[5]中，橢圓曲線密碼（Elliptic Curve Cryptography， ECC）算法能以較小的密鑰尺寸提供更高的安全級別，在許多資源有限的設備中被廣泛使用[6?7]。

對于電池供電的物聯(lián)網(wǎng)設備[8]而言，低面積、低功耗的設計尤為關鍵，因為這直接影響設備的成本、性能、可靠性和使用壽命[9]。通常情況下，面積、功耗都與硬件資源的利用情況密切相關。一般而言，在相同頻率條件下，硬件資源占用越小，面積就越小，功耗就越低，同樣成本也會越小。低成本架構設計旨在減少硬件資源的使用，為此，本文通過優(yōu)化底層硬件算法和采用硬件復用技術改進電路結構，從而降低硬件的消耗。此外，在降低資源消耗的基礎上，將加法器設計為超前進位加法器并優(yōu)化加法器調度，以提高設備性能。

1 "橢圓曲線算法總體架構

橢圓曲線密碼算法是一種非對稱公鑰密碼算法，其基于橢圓曲線離散對數(shù)難題[10]。與RSA算法基于大整數(shù)因子分解難題相比，ECC算法具有諸多優(yōu)勢，包括密鑰長度更短、安全性更高、運算速度更快以及所需存儲空間更少等[11]。橢圓曲線密碼體制應用廣泛，主要涉及加解密和數(shù)字簽名兩個方面。在橢圓曲線算法中，點乘運算是最關鍵也是最復雜的一部分。

本文主要研究基于有限域GF（[2256]）的點乘運算硬件電路。如圖1所示，點乘算法的實現(xiàn)可分為三個層次[12]。首先是有限域上的基本算術運算，包括模加、模減、模乘和模逆運算；其次是橢圓曲線點運算層，包括點加和倍點運算；最后是點乘運算。點乘由多次點加和倍點運算組成，點加和倍點運算則由多次模運算（模加、模減、模乘、模逆）組成。

2 "模運算模塊設計

2.1 "模加和模減運算

素數(shù)域[Fp]上的模加和模減運算與數(shù)學中的整數(shù)加減法相比，通常需要多一步取模運算來保證最后的結果仍在素數(shù)域上。素數(shù)域上模加和模減運算的具體算法如下。

算法1：素數(shù)域[Fp]上的模加算法

輸入：模數(shù)[p]和整數(shù)[a，b∈0，p-1]

輸出：[c=a+bmod p]

1. [c=a+b];

2. 若[c≥p]，則[c=c-p];

3. 返回[c].

算法2：素數(shù)域[Fp]上的模減算法

輸入：模數(shù)[p]和整數(shù)[a，b∈0，p-1]

輸出：[c=a-bmod p]

1. [c=a-b];

2. 若[clt;0]，則[c=c+p];

3. 返回[c].

算法1和算法2中的加法和減法采用補碼實現(xiàn)，這里將加法器設計為32位的超前進位（BCLA）加法器，256位的加法由8次累加完成，從而使得電路在提高速度的同時避免規(guī)模較大的情況。對算法中的兩個大數(shù)進行比較時，采用先相減再判斷借位的方式來設計電路，這樣可以避免兩個256 bit大數(shù)的直接比較，從而避免在綜合時被綜合成256 bit的比較器多占用資源。圖2為模加減模塊的電路結構。

因為模加和模減算法相近，所以使它們共用一套電路，通過設置一個選擇信號來控制電路進行模加或者模減運算。

2.2 "模乘運算

在橢圓曲線中，模乘運算是重要的基礎運算之一，為了保證兩數(shù)乘積還在素數(shù)域范圍內，通常要進行多次取模運算，所以模乘運算比模加、模減運算更為復雜。目前常見的素數(shù)域模乘算法有：整數(shù)乘和快速約減算法、Montgomery模乘算法、交錯模乘算法[13]。模乘電路的設計方案不同會使得整個密碼處理器的實際用途不同，因本文設計的初衷是用于資源有限的IoT設備，所以選擇復雜度較低且消耗硬件資源較少的快速約減算法，具體算法如下。

算法3：素數(shù)域[Fp]上的模乘算法

輸入：模數(shù)[p]和整數(shù)[a，b∈0，p-1]

輸出：[c=a×bmod p]

1. [c=0].

2. 重復執(zhí)行：

1） 若[a0=1]，則[c=c+b];

2） 若[c≥p]，則[c=c-p];

3） [b=b?1];

4） 若[b≥p]，則[b=b-p];

5） [a=a?1];

6） 若[a=0]，則執(zhí)行步驟3.

3. 返回[c]，算法結束.

對比其他眾多模乘約減算法，算法3的優(yōu)點在于能同時完成乘法和約減運算，但是該算法還可以進一步優(yōu)化，優(yōu)化后的模乘算法步驟如下。

算法4：優(yōu)化后的素數(shù)域[Fp]模乘算法

輸入：模數(shù)[p]和整數(shù)[a，b∈0，p-1]

輸出：[c=a×bmod p]

1. [c=0];

2. 若[a0=1]，則[c=c+b];

3. 若[c≥p]，則[c=c-p];

4. [a=a?1];

5. 若[a=0]，則返回[c]，算法結束;

6. [b=b?1];

7. 若[b≥p]，則[b=b-p];

8. 轉到第2步.

與算法3相比，算法4先對[a]進行判斷，若[a]=0則直接結束運算，這樣調整可以減少一次移位、一次比較以及一次減法運算。另外，對于算法中出現(xiàn)的兩數(shù)比較的情況，和前面模加模塊一樣，都設計為先相減再判斷借位的方式。在資源使用方面，本文以盡可能少地使用256位寄存器為目的，除三個必要的初始數(shù)據(jù)寄存器[a]、[b]、[p]和一個結果寄存器[c]之外，只額外使用一個臨時變量寄存器[d]。通過結果寄存標志flag來充分使用這幾個寄存器，合理利用資源。除此之外，模乘模塊只使用了一個BCLA加法器，通過設計多路選擇器來選擇操作數(shù)據(jù)，從而減少硬件資源的使用。

2.3 "模逆運算

在橢圓曲線中，模逆運算是非常復雜且耗時的運算，目前常用的模逆算法包括Montgomery模逆算法和擴展的整數(shù)Euclidean模逆算法。針對基于加法器的架構設計，本文采用改進后的擴展的整數(shù)Euclidean算法，具體步驟如下。

算法5：改進的Euclidean模逆算法

輸入：模數(shù)[p]和[a∈1，p-1]

輸出：[a-1mod p]

1. [u←a，v←p].

2. [x1←1，x2←0].

3.當[u≠1]且[v≠1]時，重復做下列操作：

1） 當[u]是偶數(shù)重復做下列操作：

① [u←u2];

② 如果[x1]是偶數(shù)，則[x1←x12];否則[x1←x1+p2].

2） 當[v]是偶數(shù)重復做下列操作：

① [v←v2];

② 如果[x2]是偶數(shù)，則[x2←x22];否則[x2←x2+p2].

3） 如果[u≥v]，則[u←u-v]，[x1←（x1-x2）mod p]; 否則[v←v-u]，[x2←（x2-x1）mod p].

4. 如果[u=1]，則返回[x1];否則返回[x2].

傳統(tǒng)的Euclidean算法帶有除法運算，不利于硬件的實現(xiàn)，故改進后的算法將所有的除法都轉換成移位和減法來實現(xiàn)。此外，現(xiàn)有算法中都是在第4步對[x1]或者[x2]進行取模操作，但是因為無法提前判斷運算過程中[x1]、[x2]的大小，為了避免步驟3）中計算[x1-x2]或者[x2-x1]時出現(xiàn)負值，所以在每次減法完成后都進行一次取模運算，從而保證[x1]、[x2]的值非負，同時確保[x1]、[x2]都在[1，p-1]內。這樣省去了輸出時的取模運算，使得求逆運算和取模運算同時完成，提高求逆運算的效率。

根據(jù)改進的Euclidean算法步驟可以看出，計算主要集中在步驟3，在設計電路時，步驟1）和步驟2）可以并行執(zhí)行，但代價是各需要一個加法器以及其他的硬件資源，另外步驟3）中也需要4個加法器（[u-v]、[x1-x2]、[（x1-x2）mod p]、[u≥v]）。因為本文設計的目標是低成本、小面積的處理器，所以這里采取以時間換面積的策略，通過硬件復用，全局只使用一個加法器來完成模逆模塊電路的設計。圖3所示為改進后的模逆模塊的電路結構。

另外需要說明的是，模除算法與模逆算法只是在步驟2中給[x1]賦的初值不同，模逆算法[x1]=1，模除算法[x1]=[b]，其余完全相同，并且兩個算法的執(zhí)行時間幾乎相同，所以素數(shù)域模逆運算和模除運算可以共用一套電路，這將大大節(jié)省處理器電路規(guī)模。

3 "點運算模塊設計

3.1 "點加運算

素數(shù)域點加運算是指：設橢圓曲線[y2=x3+ax+b]上存在兩個點[A（x1，y1）]和[B（x2，y2）]，按照下面的運算規(guī)則，求得第三個點[C（x3，y3）]，使其滿足[C=A+B]。

點加運算公式為：

[x3=r2-x1-x2y3=rx1-x3-y1]

式中[r=（y2-y1）（x2-x1）]。

點加運算公式中的加減乘除運算都是基于素數(shù)域的，即模加、模減、模乘、模逆。在設計點加模塊時，最主要的工作在于模運算算子的合理調度。按照點加公式，從模減開始到計算出[x3]、[y3]的值結束，一共需要9步，但是根據(jù)硬件的優(yōu)勢，有些步驟可以同時執(zhí)行，在經(jīng)過優(yōu)化后7步即可完成，步驟如下。

Step1： [y2←y2-y1]，[r←x2-x1];

Step2： [r←y2r];

Step3： [y2←r×r]， [x2←x1+x2];

Step4： [x3←y2-x2];

Step5： [x1←x1-x3];

Step6： [r←r×x1];

Step7： [y3←r-y1].

上述算法除了代表運算步驟，還顯示了寄存器重復利用的過程，該算法共使用8個寄存器：[x1]、[y1]、[x2]、[y2]、[p]、[x3]、[y3]、[r]，其中[x1]、[y1]、[x2]、[y2]、[p]是初始值寄存器，[x3]、[y3]是結果寄存器，設計只額外使用了一個臨時變量寄存器[r]。

圖4所示為點加模塊的硬件實現(xiàn)框圖，除了上述提到的寄存器模塊外，還包括控制狀態(tài)機以及基礎運算單元。在設計時，考慮到點加運算的復雜度主要在于一次模逆、兩次模乘運算，所以在硬件實現(xiàn)時采用時分復用的方法，通過對運算流程的分析，考慮每一步運算之間的依賴關系，最終設計只使用了1個模逆運算模塊、1個模乘運算模塊以及2個模加減運算模塊。圖5所示為模運算器的使用分配圖，相比于例化不同的運算器來說節(jié)省將近一半的資源。

器使用分配圖

3.2 "倍點運算

在實現(xiàn)倍點模塊時，由于其與點加模塊具有相似的特征，因此可以采用類似的方法來完成該模塊的設計。

素數(shù)域倍點運算是指：設橢圓曲線[y2=x3+ax+b]上存在一個點[P（x1，y1）]，按照下面的運算規(guī)則，求得另一個點[R（x3，y3）]，使其滿足[R=2P]。

倍點運算公式為：

[x3=r2-2x1y3=rx1-x3-y1]

式中[r=（3x21+a）（2y1）]。

倍點運算順序執(zhí)行需要12步才能得到最終結果，在經(jīng)過優(yōu)化后需要9步即可完成，步驟如下。

1. [x3←x1×x1];

2. [y3←x3+x3]，[a←x3+a];

3. [a←y3+a]，[r←y1+y1];

4. [r←ar];

5. [a←r×r]，[x3←x1+x1];

6. [x3←a-x3];

7. [a←x1-x3];

8. [a←r×a];

9. [y3←a-y1].

該算法共使用7個寄存器：[x1]、[y1]、[p]、[a]、[x3]、[y3]、[r]，其中最終值[x3]、[y3]分別在第6步和第9步求出并存放在寄存器中，其余[x3]、[y3]寄存器均是存儲中間變量。

經(jīng)統(tǒng)計，倍點運算共經(jīng)歷了8次模加模減、3次模乘以及1次模逆運算，復雜度較高。在硬件實現(xiàn)時，為了達到速度不變、面積減小的效果，本文對電路結構做了改進，最終只使用了2個模加減模塊、1個模逆模塊、1個模乘模塊，大大節(jié)省了硬件資源。

3.3 "點乘運算

點乘是橢圓曲線密碼算法的核心，對密碼處理器的性能影響很大。設在橢圓曲線上存在一點P，[k]個P點相加即為點乘運算，其中k為正整數(shù)。在計算kP時可以分為多次點加和倍點運算。目前最常用的點乘算法有兩種：二進制方法和NAF方法。因為NAF方法需要使用額外的電路提前計算k的NAF值，所以本文采用二進制點乘算法，算法如下。

算法6：二進制點乘算法

輸入：[k=（km-1，km-2，…，k2，k1，k0）]，[P]為橢圓曲線上一點

輸出：[kP]

1. [Q=0].

2. 對[i]從[m-1]到[0]，循環(huán)執(zhí)行：

1） [Q=2Q];

2） 若[ki=1]，則[Q=Q+P];

3） 返回[Q].

算法7：改進后的二進制點乘算法

輸入：[k=（km-1，km-2，…，k2，k1，k0）]，[P]為橢圓曲線上一點

輸出：[kP]

1. [Q=0].

2. 循環(huán)執(zhí)行：

1） 若[k0=1]，則[Q=Q+P];

2） [P=2P];

3） [k=k?1];

4） 若[k=0]，結束循環(huán).

3. 返回[Q].

與算法6相比，算法7更加靈活，增加了一個對k的判斷操作，在執(zhí)行完一次步驟2后判斷k的高位是否都為0，若都為0則直接結束循環(huán)，返回最終結果，這樣可以減少無效操作時間。

4 "實驗結果與分析

本設計在FPGA平臺上用Xilinx公司的XCZU3CG?SFVC784?1?E進行分析和驗證，使用Xilinx的ISE14.7工具進行綜合（Synthesis）和實現(xiàn)（Implementation）。經(jīng)過生成報告分析，點乘電路在5 ns時鐘約束下，最壞路徑建立時間裕量為0.956 ns，最壞路徑保持時間裕量為0.043 ns，最壞路徑脈沖寬度裕量為1.927 ns，估算電路主頻可達247.3 MHz，完成一次點乘的時間為23.4 ms，電路總功耗為0.371 W，共使用8 927個CLB LUTs、7 789個CLB Registers。表1是現(xiàn)有的橢圓曲線點乘架構與本文設計的低成本架構在FPGA平臺下的各項性能對比。

由表1可知，本文提出的低成本架構消耗的硬件資源最少，對比其他架構節(jié)省了39.10%～72.44%LUT資源。由于該架構是基于32 bit超前進位加法器設計的，在計算256 bit的數(shù)據(jù)時需要8個周期的累加，所以總體執(zhí)行時間相對較長，但是本文設計的工作頻率較高并且功耗較低，這是其他設計不具備的優(yōu)勢?？傮w而言，在面積、功耗和頻率方面，很好地滿足了資源受限的物聯(lián)網(wǎng)設備的需求，結果符合預期。

5 "結 "語

針對物聯(lián)網(wǎng)設備的資源有限性和安全性，本文提出了一種基于加法器的低成本架構的ECC密碼處理器。設計從細節(jié)著手，最大程度地復用硬件資源，改進基礎模運算單元算法，優(yōu)化點加和倍點的運算調度，合理安排電路結構，必要時采取時間換面積的策略，最終完成了規(guī)模小、功耗低且工作頻率高的橢圓曲線點乘電路設計，能夠滿足當前物聯(lián)網(wǎng)設備對資源和安全方面的需求。

注：本文通訊作者為馬敬萬。

參考文獻

[1] 張妍，黎家通，宋小祎，等.物聯(lián)網(wǎng)設備安全檢測綜述[J].計算機研究與發(fā)展，2023，60（10）：2271?2290.

[2] CANAVESE D， MANNELLA L， REGANO L， et al. Security at the edge for resource limited IoT devices [J]. Sensors， 2024， 24（2）： 102?108.

[3] ACHARY R， SHELKE J C， MARX K， et al. Security implementation on IoT using CoAP and elliptical curve cryptography [J]. Procedia computer science， 2023（2）： 230493?230502.

[4] UDDALAK C， SANGRAM R， DIPANWITA S， et al. An improved authentication and key mana?gement scheme for hierarchical IoT network using elliptic curve cryptography [J]. Innovations in systems and software engineering， 2023， 19（3）： 231?246.

[5] KUMAR D， KUMAR M. A comparative analysis of elliptic curve based cryptographic techniques for Internet of Things [J]. International journal of ad hoc and ubiquitous computing， 2023， 43（4）： 238?251.

[6] 蔡冕.面向物聯(lián)網(wǎng)安全芯片的SM2算法的IP設計與實現(xiàn)[D].鄭州：中原工學院，2023.

[7] WU D M， LIN Y H， HAN J G， et al. FPGa implementation for elliptic curve cryptography algorithm and circuit with high efficiency and low delay for IoT applications [J]. Micromachines， 2023， 14（5）： 10251?10261.

[8] PABLO J G， ANTONIO T， EDUARDO H， et al. IoT solution for smart water distribution networks based on a low?power wireless network， combined at the device level： a case study [J]. Internet of Things， 2023， 22： 21?30.

[9] 黃和聰.低功耗設備測試系統(tǒng)和測試方法研究[J].電子質量，2022（8）：41?44.

[10] 馮經(jīng)緯.橢圓曲線公鑰密碼學[D].合肥：中國科學技術大學，2023.

[11] SHAMSHER U， ZHENG J B， NIZAMUD D， et al. Elliptic curve cryptography： applications， challenges， recent advances， and future trends： a comprehensive survey [J]. Computer science review， 2023， 47： 530.

[12] 程雪曉.橢圓曲線加密系統(tǒng)點乘模塊的設計與實現(xiàn)[D].西安：西安理工大學，2022.

[13] 賈斌斌.工業(yè)控制系統(tǒng)中可信計算的國密SM2算法研究[D].太原：中北大學，2023.

[14] 胡湘宏.基于FPGA的卷積神經(jīng)網(wǎng)絡及橢圓曲線算法的硬件加速研究[D].廣州：廣東工業(yè)大學，2020.

[15] 王騰飛，張海峰，許森.SM2專用指令協(xié)處理器設計與實現(xiàn)[J].計算機工程與應用，2022，58（2）：102?109.

[16] 劉曉東.基于ZYNQ的SM2密鑰交換系統(tǒng)設計與實現(xiàn)[D].哈爾濱：黑龍江大學，2023.

[17] JAVEED K， WANG X J. Low latency flexible FPGA impleme?ntation of point multiplication on elliptic curves over GF （p） [J]. International journal of circuit theory and applications， 2017， 45（2）： 214?228.