高速Ed25519 驗簽算法硬件架構的設計與實現(xiàn)

薛一鳴，劉樹榮，郭書恒，李巖，胡彩娥

（1.中國農(nóng)業(yè)大學信息與電氣工程學院，北京 100083；2.中國農(nóng)業(yè)大學理學院，北京 100083；3.國網(wǎng)北京市電力公司，北京 100031）

0 引言

隨著區(qū)塊鏈、云計算、車聯(lián)網(wǎng)等技術的快速發(fā)展，全球每天都有海量的數(shù)據(jù)產(chǎn)生，如何保證數(shù)據(jù)的安全性受到了學術界、產(chǎn)業(yè)界等的高度關注。數(shù)字簽名可以驗證數(shù)據(jù)源的真實性和數(shù)據(jù)內(nèi)容的完整性，是保障數(shù)據(jù)安全的核心技術之一，目前使用最廣泛的算法為基于橢圓曲線密碼體制[1-2]（ECC，elliptic curve cryptography）構建的數(shù)字簽名算法[3]。2012 年，Bernstein 等[4-5]設計了愛德華曲線Edwards25519，并根據(jù)Schnorr 算法在該曲線上構建了Ed25519 數(shù)字簽名算法。與其他橢圓曲線構建的數(shù)字簽名算法相比，Ed25519 設計結構簡單、采用的參數(shù)完全公開，憑借著高性能、高安全性且安全性易于證明的特點[6]，該算法受到了廣泛的研究。目前Ed25519 數(shù)字簽名算法已被大多數(shù)公有鏈的密碼貨幣項目采用[7]，并被收錄在傳輸層安全協(xié)議TLS 1.3[8]中。

與Ed25519 簽名算法相比，其驗簽算法運算復雜度更高、需要的存儲需求更大[9]，因此Ed25519驗簽算法的高性能實現(xiàn)逐漸成為研究重點。Faz-Hernández 等[10]使用矢量指令的方式在計算機上實現(xiàn)了高速Ed25519 驗簽功能；文獻[11-12]分別在 STM32F401和ESP32 平臺上實現(xiàn)了曲線Edwards25519 上的點乘運算；文獻[13-15]通過對模乘算法和點乘算法進行優(yōu)化在現(xiàn)場可編輯門陣列（FPGA，field programmable gate array）上設計了點乘運算加速結構；Turan 等[16]在FPGA 上使用DSP單元實現(xiàn)了快速模乘運算，設計了能夠?qū)崿F(xiàn)Ed25519 簽名和驗簽功能的點乘運算結構，但是偏重于輕量級設計，更適合使用于對運算速度要求較低的嵌入式設備；于斌等[17]在TSMC 的55 nm 工藝下設計了一種高性能Ed25519 算法的硬件實現(xiàn)架構，根據(jù)Ed25519 模數(shù)的特點設計了快速模約簡電路并使用257 位的乘法器來實現(xiàn)模乘運算，設計了兼容簽名和驗簽功能的點乘結構，但是整體面積較大；Bisheh-niasar 等[18]在FPGA 上實現(xiàn)了高性能和輕量級的Ed25519 驗簽算法硬件實現(xiàn)架構，使用Shamir 方法來實現(xiàn)點乘運算，提高了驗簽的性能，但是使用Shamir 方法存在窗口寬度不能過大的限制；文獻[19-20]討論了使用多基數(shù)表示方法實現(xiàn)素數(shù)域橢圓曲線點乘運算的復雜度和實現(xiàn)效率，但是并未完成具體的硬件實現(xiàn)。

本文提出了一種高速Ed25519 驗簽算法的硬件架構。首先針對Ed25519 驗簽算法中耗時的點乘運算進行優(yōu)化，提出了基于交錯非相鄰形式（NAF，non-adjacent form）的多點乘算法；其次設計了可供解壓運算、模L約簡、坐標轉換和多點乘運算復用的算術邏輯單元（ALU，arithmetic and logic unit），針對解壓過程中耗時的模冪運算提出了模逆和模乘并行的計算方法，針對模L約簡提出了運算周期固定的快速約簡方法；最后基于Zynq-7020 平臺進行設計和實現(xiàn)，最高工作頻率為81.61 MHz，平均每秒完成8 347 次驗簽運算，相比于文獻[18]提高了63.28%。

1 基礎知識

Edwards25519 曲線的方程如式(1)所示，其中

文獻[5]給出了Ed25519 算法的簽名和驗簽流程，如算法1和算法2 所示。其中G為曲線Edwards25519的基點，R′和A為曲線上的動點，L為253 位的素數(shù)2252+27742317777372353535851937790883648493，H(x)為整數(shù)x的SHA-512 運算結果，R和pk 分別為點R′和點A的256 位壓縮結果，壓縮過程為pk=Ay+(Ax&1)。

算法1Ed25519 數(shù)字簽名算法的簽名流程

輸入256 位的公鑰pk，任意長度的消息M，256 位的私鑰sk

輸出512 位的簽名結果(R，S)

算法2Ed25519 數(shù)字簽名算法的驗簽流程

輸入256 位的公鑰pk，任意長度的消息M，512 位的簽名結果(R，S)

輸出驗簽的結果

1)若R，S?[1，L-1]，則驗證失敗，結束驗證流程

2)解壓R得到點R′

3)解壓pk 得到點A

4)k=H(R，pk，M)modL

5)驗證SG=R′+kA，若等號成立，則驗證成功Ed25519中的點加、倍點運算需要在拓展四元齊次坐標下完成，操作步驟如算法3和算法4 所示。其中仿射坐標(x，y)與四元齊次坐標(X，Y，Z，T)之間的轉換關系為X=xZ，Y=yZ，T=xyZ，Z的初始值取1。式(2)中SG和R′+kA的運算結果比較需要在仿射坐標下完成，通過計算x=XZ-1、y=YZ-1完成坐標的轉換，其中計算Z-1的過程需要一次模逆運算。驗簽過程中，通過對比式(2)中SG和R′+kA的運算結果來判斷簽名的真實性。

其中，SG和kA被稱為點乘運算或標量乘運算，通過調(diào)用連續(xù)的點加（PA，point addition）、倍點（PD，point double）運算實現(xiàn)。

算法3Ed25519數(shù)字簽名算法中的點加操作步驟

輸入P(X1，Y1，Z1，T1)，Q(X2，Y2，Z2，T2)

輸出Q(X3，Y3，Z3，T3)=P+Q

算法4Ed25519數(shù)字簽名算法中的倍點操作步驟

輸入P(X1，Y1，Z1，T1)

輸出Q(X2，Y2，Z2，T2)=2P

2 Ed25519 驗簽算法優(yōu)化及流程優(yōu)化

2.1 相關研究

點乘是Ed25519 數(shù)字簽名驗簽算法中的關鍵運算，其性能的優(yōu)劣直接決定了驗簽算法的效率。式(2)需要先計算點乘SG、kA，再通過對比SG和R′+kA的結果判斷驗簽是否成功，運算效率較低。

文獻[17]針對該問題設計了式(3)所示的點乘運算單元

其中，P1和P2為橢圓曲線上的點，m為255 位的標量，n∈[0，1]。n=0 時進行點乘SG的計算，n=1時進行點乘R′+kA的計算，通過對比兩次點乘運算的結果即可判斷驗簽是否成功，在點乘算法的選取上采用了窗口寬度w=2的窗口方法，通過預計算和查表的方式降低了運算量。相比于二進制展開的點乘計算方法[21]，文獻[21]使用的方法將點乘循環(huán)中的點加運算次數(shù)減少了25%，增大窗口寬度可以進一步減少所需的點加運算次數(shù)，但是也會導致預計算的運算量和存儲需求呈2w的指數(shù)級增長。

2.2 基于交錯NAF 的多點乘算法

為進一步提高Ed25519 驗簽性能，本文將式(2)進行變形，得到式(4)。基于式(4)，可以將點乘和點加運算采用多點乘的方式實現(xiàn)。

相較于常規(guī)的點乘計算方法，使用多點乘可以減少點乘循環(huán)中50%的倍點運算次數(shù)，通過選取合適的多點乘算法可以進一步減少點乘循環(huán)中點加的運算次數(shù)。常用的多點乘計算方法有Shamir 方法和交錯的NAF 方法[21]，其中Shamir 方法對標量S和k只能選用相同的窗口寬度，并且預計算過程中需要同時進行基點G和動點A的計算，隨著窗口寬度的增大，預計算的運算量和存儲需求呈 22w的指數(shù)級增長。在Ed25519 驗簽的過程中，基點G的預計算可以在系統(tǒng)初始化時完成，在存儲資源滿足設計要求的情況下可以選用較大的窗口寬度；而動點A的預計算會影響多點乘的性能，需要選用較小的窗口寬度。因此本文提出了一種基于交錯NAF 的多點乘實現(xiàn)算法，即對基點G和動點A的預計算選用不同的窗口寬度，具體算法流程如算法5 所示。其中，步驟1)中基點G的預計算和S的NAF 編碼都是在多點乘運算之前完成的，動點A的預計算過程需要一個倍點和-1個點加運算，完成預計算后再對k進行NAF 編碼；步驟6)的循環(huán)中需要計算Q=Q-|Si|G和Q=Q-kiA，預計算過程中只預先計算了SiG和kiA，因此需要兩次模減運算才能得到-|Si|G和-kiA的坐標。

算法5窗口寬度為w1，w2的交錯NAF 方法實現(xiàn)的多點乘算法

輸入253 位二進制數(shù)S=(S252，S251，…，S1，S0)2，k=(k252，k251，…，k1，k0)2，基點G=(x1，y1)，動點A=(x2，y2)

輸出多點乘Q=SG-kA=(x3，y3)

6)對于i從l-2 到0，循環(huán)計算

7)返回Q

2.3 驗簽流程優(yōu)化

在多點乘算法研究的基礎上，考慮到解壓和SHA-512 運算的性能也會影響Ed25519 簽名驗證算法的效率，本文設計了如算法6 所示的高速Ed25519 驗簽算法流程；其中步驟2 的解壓、SHA-512、NAF 編碼運算可以并行操作；步驟4的多點乘運算完成之后需要進行坐標轉換，坐標轉換過程中的模逆運算可以和解壓過程中的乘法運算并行操作。

算法6高速Ed25519 驗簽算法流程

輸入256 位的公鑰pk，任意長度的消息M，512 位的簽名數(shù)據(jù)(R，S)

輸出簽名驗證的結果

1)若R，S?[1，L-1]，則驗證失敗，結束驗證流程

2)k=H(R，pk，M)modL，解壓pk 為點坐標A，對S進行NAF 編碼

3)對k進行NAF 編碼

4)計算多點乘Q=SG-kA，解壓R為點坐標R′

5)驗證Q=R′是否成立，若成立，則驗證成功

3 硬件架構設計及實現(xiàn)

根據(jù)算法6 所提出的高速Ed25519 驗簽算法流程，構建了如圖1 所示的高速Ed25519 驗簽硬件架構。該架構由Ed25519 驗簽狀態(tài)機、控制單元、ALU 模塊、SHA-512 哈希模塊、寄存器、寄存器堆、模逆模塊等組成，通過AXI 總線實現(xiàn)與外部系統(tǒng)的交互。

圖1 高速Ed25519 驗簽硬件架構

Ed25519 驗簽狀態(tài)機用于驗簽狀態(tài)的控制，控制單元由多點乘、解壓控制、模L約簡、坐標轉換4 個子控制單元組成，ALU 模塊包括乘法器、模p約簡單元、加法器和減法器。控制單元只對數(shù)據(jù)的輸入輸出選擇進行控制，最終的數(shù)據(jù)運算是通過調(diào)用ALU和模逆等運算單元實現(xiàn)的。寄存器堆用于存儲NAF 編碼結果及預計算表；寄存器除了用于存放點加、倍點、坐標轉換單元的輸入、輸出坐標值，還用于暫存SHA-512 的運算結果和模L約簡運算過程產(chǎn)生的計算中間值。

關于模逆和SHA-512 的設計已經(jīng)相對成熟，故不作為本文設計的重點。常用的素數(shù)域求逆方法有費馬小定理和拓展歐幾里得算法[21]，基于費馬小定理實現(xiàn)的模逆算法需要的運算量較大[15，17]，且求逆的過程中無法釋放乘法器和模p約簡單元，本文采用拓展歐幾里得算法來設計模逆模塊。SHA-512 模塊的設計采用了文獻[18]的方法，一次運算需要80 個時鐘周期。

3.1 驗簽狀態(tài)機設計

高速Ed25519 驗簽狀態(tài)機的狀態(tài)及跳轉流程如圖2 所示。系統(tǒng)上電之后首先進行初始化（INIT），完成基點G的預計算，之后進入IDLE 狀態(tài)。接收到外部系統(tǒng)發(fā)出的驗簽請求后，跳轉到LOAD 狀態(tài)，將接收到的公鑰數(shù)據(jù)pk、消息M等數(shù)據(jù)存入相應的寄存器單元，判斷數(shù)據(jù)的合法性并跳轉到IDLE 狀態(tài)，若簽名數(shù)據(jù)不合法，則拒絕驗簽請求。開始驗簽流程后跳轉到SHADEC 狀態(tài)，在該狀態(tài)下SHA-512 運算、pk 的解壓運算、S的NAF 編碼操作并行執(zhí)行，若pk 解壓成功，則跳轉到MODL狀態(tài)。之后對SHA-512 的輸出結果進行模L約簡并跳轉到DPMDEC 狀態(tài)，在該狀態(tài)下，先完成多點乘運算，再并行執(zhí)行坐標轉換和R的解壓運算，若解壓成功則跳轉到COMP 狀態(tài)，對R′和多點乘的計算結果Q進行比較，若2 個點的坐標相同，則驗簽成功，否則驗簽失敗，最后跳轉回IDLE 狀態(tài)。

圖2 高速Ed25519 驗簽狀態(tài)機的狀態(tài)及跳轉過程

3.2 算術邏輯單元設計

算術邏輯單元主要完成大數(shù)乘、模p約簡、大數(shù)加減等素數(shù)域運算，是最基礎的運算單元。解壓運算、多點乘和坐標轉換過程中的模乘運算通過調(diào)用乘法器和模p約簡單元實現(xiàn)，模L約簡運算的實現(xiàn)也需要使用乘法器。基于FPGA 的大數(shù)乘法實現(xiàn)常用的方法有Karatsuba 算法和Toom-Cook 算法，其中Karatsuba 算法的性能與實現(xiàn)面積的乘積要低于Toom-Cook 算法[22]。若2m位的乘法器使用Karatsuba 算法實現(xiàn)，則表達式為

其中，φ=2m。該算法只需要2 個m位乘法器和一個m+1 位乘法器即可實現(xiàn)2m位的乘法運算，減少了乘法器的資源開銷。本文采用插入流水線的方式使用81 個DSP 單元設計了3 個130×130 的Karatsuba 乘法器，再使用130×130 的部分積構建出258×258 的乘法計算結果，其中130×130 的乘法運算需要4 個時鐘周期。

在Ed25519中，模數(shù)為p=2255-19，利用2258(modp)≡152(modp)、2255(modp)≡19(modp)的特點，使用算法7 對大數(shù)乘法的結果進行約簡。快速約簡的過程直接使用130×130 的乘法結果作為輸入，第1 輪約簡中Ch直接取乘法器的輸出，通過計算152Ch+Cl將C約簡為一個392 位的數(shù)；第2 輪約簡中取T的高137 位作為Th，取低255 位作為Tl，計算19Th+Tl將T約簡為一個256 位的數(shù)；第2 輪約簡結果的取值范圍為[0，2256-1]，最多只需要一次減p運算即可得到最終的約簡結果。乘法器單元和模p約簡單元的結構如圖3 所示。

圖3 乘法器和模約簡單元結構

算法7模p快速約簡算法

輸入130×130 的乘法結果Ho、Lo、Mo，模數(shù)p=2255-19

輸出T′′=C(modp)

根據(jù)算法3和算法4中的點加、倍點操作步驟，加法和減法運算的結果將作為乘法器的輸入數(shù)據(jù)源，由于乘法器的位寬可以滿足258 位的數(shù)據(jù)輸入，因此點加、倍點過程中加法單元、減法單元的運算結果不需要約簡，可以直接作為乘法器的輸入；模p約簡單元的第2 輪約簡結果也可以直接作為加法單元、減法單元和乘法器的輸入，第3 輪約簡結果只有在多點乘中的最后一次模乘運算才需要輸出。此外，乘法器的第一級輸入端并未插入寄存器，可以和加、減法單元共用一個時鐘周期。乘法器和模p約簡單元均采用了插入流水線的設計方式，因此連續(xù)的模乘運算完全流水只需要一個周期。

3.3 多點乘單元設計

對二進制數(shù)S和k進行NAF 編碼[21]可以減少多點乘循環(huán)的點加運算次數(shù)，但是窗口寬度的增大會導致預計算的運算量增加，如表1 所示。不同窗口寬度下多點乘中倍點運算的次數(shù)均相同，因此可以將點加運算的次數(shù)作為衡量多點乘單元性能優(yōu)劣的指標，在w1固定的情況下，w2的增大可以減少多點乘循環(huán)中的點加運算次數(shù)，但是預計算過程中的點加次數(shù)會增加，總的點加運算次數(shù)呈增加的趨勢；在w2固定的情況下，點加運算的次數(shù)隨窗口寬度w1的增大而減少，但是減少的趨勢逐漸減緩，并且w1的增大會導致存儲需求呈指數(shù)級增長，因此選用w1=10、w2=5作為多點乘單元的窗口寬度。

表1 交錯NAF 方法實現(xiàn)的多點乘運算期望性能

基于ALU 結構設計了不需要模加、模減運算的點加和倍點的操作步驟，分別如表2和表3 所示，完整的點加和倍點運算分別需要24 個和20 個時鐘周期。表2中，輸入P(X1，Y1，Z1，T1)，Q(X2，Y2，Z2，T2)，輸出Q(X3，Y3，Z3，T3)=P+Q；表3中，輸入P(X1，Y1，Z1，T1)，輸出Q(X2，Y2，Z2，T2)=2P。多點乘循環(huán)的過程中上一個點加、倍點運算的輸出需要作為下一個運算的輸入，由于乘法器和模p約簡單元采用了流水線設計，并且DSP 單元只有在乘法運算的第一個周期使用到，連續(xù)的點加、倍點運算之間可以共用部分時鐘周期，即點加-點加、點加-倍點、倍點-點加和倍點-倍點運算分別需要46 個、42 個、41 個和38 個時鐘周期。

表2 Ed25519 驗簽算法中點加算法重排布

表3 Ed25519 驗簽算法中倍點算法重排布

多點乘運算的結果需要從拓展四元齊次坐標轉換為仿射坐標，通過調(diào)用一次模逆和兩次模乘運算即可實現(xiàn)，坐標轉換的結果被存入寄存器中。

3.4 高速解壓單元設計

解壓運算使用x坐標值的最低有效位和y坐標值來計算出完整的x坐標值，計算式為

文獻[5]給出了x坐標的計算方法，其中模冪運算是該方法中的關鍵運算，計算式為

文獻[17]通過計算連續(xù)的503 個模乘完成模冪運算，雖然只使用了模乘電路，但是運算量較大。本文提出了模乘和模逆并行的模冪計算方法，設計了如圖4 所示的運算結構，只需要一次模逆和254 次模乘即可完成模冪運算。由于模逆的實現(xiàn)不依賴于模乘，解壓過程中模逆運算完成后模逆模塊就可以被坐標轉換單元調(diào)用。

圖4 高速解壓運算操作流程

3.5 模L 約簡單元設計

模L約簡運算中的模數(shù)L可以整理為L=2252+L0的形式，其中L0是一個125 位的數(shù)。模數(shù)L與模數(shù)p具有相似的結構，可以使用算法8所示的快速約簡方法。

第1輪約簡中Ch為輸入數(shù)據(jù)C的高258位，Cl為低254 位，根據(jù) 2254(modL)≡-22L0(modL)的特點，通過計算Cl-22L0Ch將C約簡為一個386 位的數(shù)，需要一個127×258 的乘法器；第2 輪約簡中，取C的高134 位為Ch，低252 位為Cl，由于 2252(modL)≡-L0(modL)，通過計算Cl-L0Ch將C約簡為一個260 位的數(shù)，需要一個125×134 的乘法器；第3 輪約簡中取C的高8 位為Ch，低252 位為Cl，通過計算Cl-L0Ch將C約簡為一個253 位的數(shù)，需要一個125×8 的乘法器。這3 種乘法運算都通過復用ALU中的乘法單元實現(xiàn)，運算結果需要與Cl進行減法運算，為了復用減法器和寄存器設計了如圖3 所示的模L約簡結構；使用130×130 的部分積H、L構建出127×258、125×134和125×8的乘法計算結果，減法運算過程中的參數(shù)C從寄存器中輸入。前2 輪約簡各需要7 個時鐘周期，其中一個周期用于將約簡結果寫入寄存器，第3 輪約簡需要5 個時鐘周期，完整的模L約簡需要19 個時鐘周期，約簡的結果被存入寄存器中。

算法8模L快速約簡算法

輸入512 位的二進制數(shù)C=(C511，C510，…，C1，C0)2，模數(shù)L=2252+L0

輸出C′=C(modL)

4 實現(xiàn)結果與性能分析

最終的高速Ed25519 驗簽算法硬件結構采用了Xilinx 的Zynq-7020 進行實現(xiàn)，設計的實現(xiàn)和功能驗證使用了 Vivado 2019.1。本文提出的高速Ed25519 驗簽硬件架構共需要22 436 個LUT、12 631 個FF和81 個DSP 單元，未消耗塊RAM（BRAM，block RAM），在81.61 MHz 的時鐘頻率下，每秒能夠完成8 347 次驗簽運算。

各模塊的資源使用及運行周期數(shù)分別如表4和表5 所示。其中模p約簡單元只有在進行多點乘循環(huán)中的最后一次點加或倍點運算時才需要4 個時鐘周期，其余情況下只需要3 個時鐘周期；完整的點加和倍點運算分別需要24和20 個時鐘周期，多點乘循環(huán)過程中連續(xù)的點加、倍點運算之間可以共用部分周期，不需要占用完整的運算周期；模逆、坐標轉換和多點乘單元的運算時間為多次驗簽測試結果的平均值，分別需要507、516和6 174 個時鐘周期。

表4 高速Ed25519 驗簽硬件架構中各模塊的資源使用

表5 FPGA 硬件加速電路各模塊的運行周期數(shù)

4.1 功能驗證

功能驗證采用了RFC8032中推薦的密鑰對，如表6 所示。使用SystemVerilog 語言和Vivado 2019.1工具構建了Testbench，參考模型使用Python 編寫，用于產(chǎn)生簽名和驗簽數(shù)據(jù)。驗簽過程中，選取任意長度的隨機數(shù)作為待簽名消息M，并將其作為參考模型的輸入得到對應的簽名數(shù)據(jù)、驗簽的結果和多點乘的計算結果；再將公鑰、消息和簽名數(shù)據(jù)作為設計的輸入得到驗簽的結果和多點乘的計算結果，通過對比設計和參考模型的輸出判斷驗簽功能的正確性；通過隨機測試，驗證了系統(tǒng)驗簽功能的正確性。待簽名消息M為“123456789abcdef0”時的仿真結果如圖5 所示，其中（X1，Y1）為式(4)右端的多點乘運算SG-kA的仿射坐標輸出，（X2，Y2）為點R′的仿射坐標。

表6 驗簽過程中使用的密鑰對

圖5 M 為“123456789abcdef0”的仿真結果

4.2 性能分析

為了客觀評估設計的性能和面積，從點乘和驗簽2 個層次對現(xiàn)有方案進行對比，分別如表7和表8 所示。

表8 Ed25519 驗簽性能對比

表7 對比了現(xiàn)有方案實現(xiàn)點乘所需的面積以及點乘運算的性能，ALU 模塊是實現(xiàn)點乘的主要運算單元，因此使用ALU 模塊的面積來衡量實現(xiàn)點乘運算所需的硬件資源[18]。文獻[16]使用了15 個DSP單元來實現(xiàn)256 位的模乘，完成一次運算平均需要18.6 個時鐘周期，雖然消耗的硬件資源較少，但是點乘運算所需的運算時間較長。文獻[15]采用基為8的交錯模乘算法，由于不需要消耗DSP 單元，因此所需的資源最少，在點乘算法的選取上使用了NAF方法來減少點加倍點運算的次數(shù)，但是完成一次模乘運算需要95 個時鐘周期，點乘的整體性能有待提升。文獻[17]采用257 位乘法器設計了模乘單元，并選用窗口方法實現(xiàn)點乘運算，雖然點乘所需的周期數(shù)較少，但是由于工作頻率的限制導致點乘的性能較低，此外生成257 位乘法器使用了225 個DSP單元，造成了較大的資源開銷。文獻[18]基于4 級展開的Karatsuba 算法使用81 個DSP 單元設計了255 位的模乘單元，所需的周期數(shù)較少，但是乘法器的位寬低于256 位，在點加、倍點過程中加法和減法運算的結果需要先取模才能作為乘法器的輸入，導致點加、倍點運算的效率較低；使用了Shamir方法來實現(xiàn)點乘運算，只適用于窗口寬度較小的情況，對于點加、倍點運算次數(shù)減少的幅度較小。與上述文獻相比，本文首先充分利用DSP 單元設計了258 位的乘法器，結合模p快速約簡算法實現(xiàn)了快速模乘運算；其次設計了不需要模加、模減的點加、倍點操作步驟，有效提高了點加、倍點運算的性能；最后使用多點乘替代了點乘，并采用交錯NAF 方法實現(xiàn)多點乘運算，對于S和k的NAF 編碼分別選用合適的窗口寬度，在系統(tǒng)初始化過程中就完成基點G的預計算，有效減少了點加、倍點的運算次數(shù)，顯著提高了點乘單元的性能。

表7 點乘單元性能對比

表8 對比了現(xiàn)有Ed25519 驗簽硬件實現(xiàn)方案的性能和面積。文獻[9-10]分別在 MSP430和STM32F401 平臺上實現(xiàn)了Ed25519 驗簽功能，具有低功耗的特點，但是受限于處理器的計算能力，需要消耗的周期數(shù)較多，導致驗簽性能較低；文獻[16]使用Zynq SoC 實現(xiàn)了Ed25519 的驗簽功能，沒有采用多點乘算法因此需要計算兩次點乘，并且模逆運算需要10 786 個時鐘周期導致坐標轉換和解壓操作較為耗時，平均每秒只能完成272 次驗簽運算；文獻[18]在XC7Z020 平臺上實現(xiàn)了Ed25519 的驗簽功能，坐標轉換和模L約簡的性能與本文相當，但是點乘運算需要消耗的周期較多，每秒只能完成5 112 次驗簽運算。點乘是Ed25519 驗簽算法中最耗時的運算，相比于其他文獻，本文使用了基于交錯NAF 的多點乘算法，在性能上具有顯著的優(yōu)勢；此外本文設計了模逆和模乘并行的模冪運算步驟，減少了解壓運算所需的周期，并且在驗簽過程中SHA-512、NAF 編碼、解壓、坐標轉換等運算可以并行操作，進一步提高了驗簽的性能。

5 結束語

本文對愛德華曲線數(shù)字簽名算法Ed25519 的驗簽流程進行了研究，針對基于標量乘方法性能較低的問題，提出了基于交錯NAF 方法的多點乘算法，使用Karatsuba 算法和快速模p約簡方法實現(xiàn)了快速模乘運算，并設計了不需要模加、模減運算的點加和倍點運算步驟，減少了多點乘運算所需的時鐘周期。針對解壓過程中耗時的模冪運算，設計了求逆和模乘并行的模冪運算步驟，減少了50%的運算量。根據(jù)模數(shù)L的特點設計了快速模L約簡算法，約簡過程中復用了乘法器，在保證運算性能的同時減少了硬件資源開銷；設計了SHA-512、解壓和NAF 編碼運算可以并行操作的Ed25519 驗簽的硬件架構。最終的設計實現(xiàn)了完整的驗簽功能，相比于其他設計，在運算速度上具有顯著優(yōu)勢，每秒能夠完成8 347 次驗簽運算。