高性能Ed25519算法硬件架構(gòu)設(shè)計與實現(xiàn)

于 斌 黃 海 劉志偉 趙石磊 那 寧

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

1 引言

數(shù)字簽名算法在信息安全領(lǐng)域中具有重要作用，常用的算法有RSA 和橢圓曲線數(shù)字簽名算法(Elliptic Curve Digital Signature Algorithm,ECDSA)等。在最新的傳輸層安全性協(xié)議1.3版(the Transport Layer Security protocol version 1.3,TLS1.3)中，橢圓曲線算法被收錄為基本算法[1]，其中愛德華茲曲線數(shù)字簽名算法(Edwards-curve Digital Signature Algorithm, EdDSA)作為主要的數(shù)字簽名算法之一，受到研究者的廣泛關(guān)注。

Curve25519曲線最初由Bernstein提出，用于密鑰交換時稱為X25519[2]，其Edwards曲線形式用于數(shù)字簽名算法，稱為Ed25519，與另一同類曲線算法Ed448一起被收入到TLS1.3中，成為重要的簽名算法。業(yè)界對相關(guān)算法做了大量研究，如Faz-Hernández等人[3]使用矢量指令的方式使計算機執(zhí)行E d 2 5 5 1 9 的速度得到大幅提升；I s l a m 等人[4]在P-256的曲線上兼容了Ed25519的計算，使其具有更好的通用性；戴紫彬等人[5]改善了架構(gòu)，使密碼處理器能夠高效并行；Kim等人[6]討論了Curve25519和Edwards25519曲線上加法運算的轉(zhuǎn)換效率；Salarifard等人[7]通過快速約簡實現(xiàn)模乘并完成了Curve25519曲線上標(biāo)量乘的設(shè)計；Turan等人[8]在可編程門陣列(Field Programmable Gate Array, FPGA)上實現(xiàn)了完整的Ed25519功能；Mehrabi等人[9]做了低功耗低面積的設(shè)計，完成了X25519功能并支持ED25519的標(biāo)量乘運算；魏偉等人[10]研究了橢圓曲線密鑰交換協(xié)議的比特安全問題；在低延遲、側(cè)信道保護方面的研究也有諸多進展[11–13]。

上述各類研究多使用在物聯(lián)網(wǎng)(Internet of Things, IoT)設(shè)備中，偏重于輕量級設(shè)計，對簽名和驗簽速度無特別要求。但在特定應(yīng)用領(lǐng)域，如服務(wù)器端，每秒內(nèi)需要進行大量的簽名驗簽，運算量巨大，現(xiàn)有算法難以滿足應(yīng)用需求。針對這個問題，本文設(shè)計了一種高性能Ed25519算法的硬件實現(xiàn)架構(gòu)，并在TSMC的55 nm互補金屬氧化物半導(dǎo)體(Complementary Metal OxideSemiconducto,CMOS)工藝下完成了硬件實現(xiàn)。首先分析了完整的Ed25519算法，劃分關(guān)鍵的運算單元；其次對其中的標(biāo)量乘單元、模L單元和解壓單元進行了設(shè)計，并充分考慮復(fù)用以減小硬件開銷，采用速度較快的模約簡方式實現(xiàn)模乘，配合此模乘結(jié)構(gòu)調(diào)整了點加倍點操作步驟，并使用窗口法完成了標(biāo)量乘功能；然后利用已有的模乘結(jié)構(gòu)完成模L單元和解壓單元；最后實現(xiàn)完整設(shè)計并進行性能分析。仿真結(jié)果表明，所設(shè)計的Ed25519算法硬件實現(xiàn)架構(gòu)具有速度高、硬件使用率高、計算周期少等優(yōu)點。

2 Ed25519算法介紹

Ed25519是橢圓曲線簽名算法的一種，選用的曲線為Edwards25519曲線，方程為

在EdDSA的標(biāo)準(zhǔn)中，共描述了公鑰生成、簽名和驗簽3個功能的算法[14]。按其工作過程，首先需進行公鑰生成，如表1所示。

表1 Ed25519公鑰生成算法流程

由公鑰生成算法流程可以看出，運算部分主要是1次SHA-512和1次對橢圓曲線基點B的標(biāo)量乘。最后的壓縮過程實際是保留y的全部信息和x的末位信息，組合成為256 bit公鑰。

當(dāng)有待簽名消息M時，需進行的簽名過程如表2所示。模操作中的參數(shù)L與參數(shù)p一樣，均為橢圓曲線的固定參數(shù)。簽名算法的運算部分主要是2次SHA-512、1次標(biāo)量乘以及對L的模乘和約簡運算。

當(dāng)接收方獲得消息M及簽名結(jié)果R||S，結(jié)合發(fā)送方的公鑰pk，可進行驗簽操作，具體過程如表3所示。驗簽過程的解壓操作是表1和表2中壓縮操作的逆運算，根據(jù)壓縮結(jié)果來計算x的原值。驗簽算法的運算主要來自2次解壓操作、1次SHA-512、2次標(biāo)量乘和1次點加運算。

表2 Ed25519簽名算法流程

表3 Ed25519驗簽算法流程

3 高速ED25519算法及硬件架構(gòu)設(shè)計

根據(jù)Ed25519算法的工作流程，其硬件實現(xiàn)架構(gòu)設(shè)計如圖1所示。在整個架構(gòu)中，SHA-512的設(shè)計目前已相對成熟，故不作重點討論，本文主要針對運算量大的標(biāo)量乘、模L和解壓3部分進行研究和設(shè)計，包括標(biāo)量乘中的點加倍點和模運算等具體操作。

標(biāo)量乘單元由標(biāo)量乘控制、乘法器、模約簡單元、模逆和模加減構(gòu)成。其中標(biāo)量乘控制完成了標(biāo)量乘算法及點加倍點算法的控制，但僅是對數(shù)據(jù)的選擇控制和部分臨時數(shù)據(jù)的暫存，最終的實現(xiàn)依托模運算，而乘法器和模約簡單元配合完成模乘運算。模L單元由模L控制、模加減、乘法器和模約簡單元構(gòu)成，解壓單元由解壓控制、模加減、乘法器和模約簡單元構(gòu)成，由于標(biāo)量乘、模L和解壓是串行運算關(guān)系，故復(fù)用了模加減、乘法器和模約簡。圖1中的SHA-512使用通用結(jié)構(gòu)[15]，乘法器使用單元庫中現(xiàn)有結(jié)構(gòu)以保證性能，此兩部分不做單獨設(shè)計。最終，Ed25519控制調(diào)用各部分實現(xiàn)公鑰生成、簽名和驗簽功能。

圖1 Ed25519完整結(jié)構(gòu)圖

3.1 標(biāo)量乘單元設(shè)計

標(biāo)量乘單元性能的優(yōu)劣是整個Ed25519的直接體現(xiàn)，完整的標(biāo)量乘運算分為標(biāo)量乘算法、點加倍點算法和模運算算法3個層次，標(biāo)量乘調(diào)用點加倍點來實現(xiàn)，而點加倍點調(diào)用模運算完成。為了提高簽名驗簽速度，在最底層的模運算中采用快速模約簡的方式來設(shè)計模乘，點加倍點也需隨之調(diào)整操作流程，最頂層的標(biāo)量乘算法采用窗口法來實現(xiàn)。

3.1.1 標(biāo)量乘算法

本設(shè)計中標(biāo)量乘算法采用窗口法[16]，窗口寬度為2 bit，并針對Ed25519驗簽進行了設(shè)計，增加了1次點加操作，如表4所示。

表4 寬度為2的窗口法

并未采用較熱門的非相鄰形式(Non-Adjacent Form, NAF)算法，是因為整個系統(tǒng)中有統(tǒng)一時鐘，采用NAF算法需對k進行預(yù)處理，會消耗額外周期而導(dǎo)致標(biāo)量乘的總周期數(shù)增加，寬度為2 bit的窗口法比NAF算法額外計算11次點加和1次倍點，需要108個周期數(shù)完成(詳見3.1.2節(jié))，小于NAF算法預(yù)計算k所需的平均周期數(shù)128個。窗口大小若繼續(xù)增加，雖會帶來總周期數(shù)的減少，但會導(dǎo)致存儲單元數(shù)量的指數(shù)增加，預(yù)計算所需周期數(shù)也會同樣增多，故本文最終選定窗口大小為2 bit。

3.1.2 點加倍點算法

點加和倍點運算在標(biāo)準(zhǔn)文檔中給出了計算步驟，為得到更好的性能，將2元射影坐標(biāo)(x, y)轉(zhuǎn)換為4元擴展齊次坐標(biāo)(X, Y, Z, T)，轉(zhuǎn)換公式為

點加和倍點計算按表5的步驟完成，左側(cè)完成點加，右側(cè)完成倍點，其中d與式(1)中相同，等式左側(cè)均為計算中涉及的臨時變量或輸出結(jié)果。

由于底層的模乘采用模約簡來實現(xiàn)，乘法結(jié)果需等待一個周期約簡后才能再次相乘，考慮到乘法器的使用效率，把表5的操作流程做重新排布，表6是排布后倍點的操作流程，點加也按同樣考慮，排布為表7所示操作流程。

表5 點加和倍點操作流程[14]

表6 倍點操作流程

表4窗口法的預(yù)計算中2P1按倍點操作，4倍點則執(zhí)行兩次倍點，所以循環(huán)過程按“倍點→倍點→點加”的順序來進行，表6中的步驟(7)，(8)能與表7中的步驟(1)，(2)同時完成，還可以和表6中的步驟(1)，(2)同時完成，兩種運算最后的等待約簡步驟也可以與下一運算的初始步驟同時運行，即倍點和點加無論如何搭配工作，乘法器均可連續(xù)工作，整個標(biāo)量乘循環(huán)只有在結(jié)束時等待約簡1次即可，乘法器的使用率近似達到百分之百。按此計算，1次“倍點→倍點→點加”實際只需25個周期，無點加時1次“倍點→倍點”實際只需16個周期。

3.1.3 模運算算法

模運算包含模加減、模乘和模逆。為保證表6和表7中的操作可以執(zhí)行，需正常的模加和模減單元各1個。由于模乘設(shè)計采用快速模約簡的方式實現(xiàn)，考慮到乘法器延遲較大，在模約簡單元輸出端連接1個模加和1個模減單元，可以在1個周期內(nèi)對模約簡的結(jié)果多做1次模加減操作。此外模逆也需要復(fù)用模加和模減單元來簡單完成，整個模運算部分的結(jié)構(gòu)如圖2所示。

圖2 模運算單元

表7 點加操作流程

計算標(biāo)量乘只需255 bit乘法，但模L運算需要計算257 bit乘法，故選用單元庫中的257 bit乘法器，可同時滿足標(biāo)量乘和模L運算需求。模約簡公式通?？梢愿鶕?jù)模數(shù)特點利用多項式來推導(dǎo)[17]。在Ed25519中，參數(shù)p＝2255–19＝2255–24–22+1，位寬為255 bit，乘法結(jié)果A的位寬為510 bit，根據(jù)p值的形式特點，設(shè)A＝A254·2508+A253·2506+···+A1·22+A0,Ai的寬度為2 bit。其中低256 bit即A127·2254+···+A0，設(shè)為T；高254 bit即A254·2508+···+A128·2256做兩輪多項式除法，第1輪后得到剩余項A254·2257+(A253+A254)2255+ (A252+A253–A254)2253+(A251+A252–A253)2251+···+(A128+A129–A130)25+(A128–A129)23+(–A128)21，第2輪消去A254·2257+(A253+A254)2255，得到新增剩余項A254·26+(A253+2A254)24+A25322–(A253+A254)，把各部分重新整理后，可得表8所示的快速模約簡算法。其中T值是256 bit，Si和Di是255 bit，最后一步待約簡的9個和差結(jié)果的范圍在–2p～5p內(nèi)，然后接入一個加減法陣列計算出所有可能，并根據(jù)標(biāo)志位來選擇正確的輸出，整個模約簡結(jié)構(gòu)如圖3所示。

表8 Ed25519快速約簡算法

圖3中額外增加了選擇信號來選擇輸入?yún)?shù)是L或p，以及增加了+3q的輸出，這兩處是為了在模L約簡過程中使用，由于模L時不會同時進行模p，可以最大限度復(fù)用硬件資源，模L約簡算法及設(shè)計見3.2節(jié)。

圖3 模約簡整體結(jié)構(gòu)

模逆只在從4元坐標(biāo)轉(zhuǎn)換為2元坐標(biāo)時使用1次，采用二進制右移算法[18]，至多512個周期即可完成運算，每次循環(huán)向右移位1次，并做除2操作，可用模加完成。

以上各部分按層次調(diào)用，即可完成標(biāo)量乘運算。

3.2 模L單元的硬件設(shè)計

模L運算中的L值形式復(fù)雜，不適合做快速約簡；且L為253 bit，待約簡數(shù)值最大為512 bit，異于常規(guī)約簡的2倍位寬形式；同時考慮到模L運算使用次數(shù)較少，單獨設(shè)計會造成資源閑置；綜合以上幾點，對比較常用的Barrett約簡[19]做改進，復(fù)用已有的257 bit乘法器，得到基于Barrett約簡的模L算法如表9所示，其中“[ ]”為取整操作。

表9 基于Barrett約簡的模L算法

原Barrett約簡是對256 bit做模約簡，在步驟4中判斷輸出結(jié)果是否大于模數(shù)，并進行修正。由于L是253 bit，將L擴大8倍，變?yōu)?56 bit 8L，采用Barrett約簡會得到一個范圍在0～8L的值，減去3L后送入圖3所示的模約簡單元，復(fù)用該單元便可得到最終結(jié)果，所以直接在步驟(4)中把修正的數(shù)值改為減11L和減3L。此方法只需將乘法器擴展2 bit、模約簡單元增加少量結(jié)構(gòu)、模減單元擴展1 bit以及額外增加部分控制邏輯即可實現(xiàn)模L約簡。

3.3 解壓單元的硬件設(shè)計

解壓的目的是根據(jù)坐標(biāo)x值的最后一位和坐標(biāo)y值，來計算x的完整坐標(biāo)值，計算公式為

解壓運算采用標(biāo)準(zhǔn)中推薦的算法來實現(xiàn)[14]，需計算

再對t進行判斷和修正即可，主要計算量集中在模冪操作，由于參數(shù)p固定，可得

根據(jù)其形式特點，復(fù)用快速模約簡的模乘結(jié)構(gòu)，為達到乘法器的最高使用率，設(shè)計了如圖4的模冪操作步驟圖，其中的b＝uv7，是模冪的底數(shù)。按此操作步驟運行，完成b的(2252–3)次模冪只需506個周期。

圖4 b的2252–3次模冪操作步驟圖

4 硬件實現(xiàn)與性能分析

最終設(shè)計采用55 nmCMOS工藝庫進行綜合，可得表10和表11所示的性能參數(shù)結(jié)果。整個設(shè)計能夠工作在360 MHz主頻下，約占用746×103個等效門，平均每秒可以運行11.12×104次的公鑰生成、10.76×104次的簽名和4.81×104次的驗簽，即使對于極端特殊的情況，理論上也能達到每秒9.06×104次的公鑰生成、8.82×104次的簽名和3.99×104次的驗簽。由于未設(shè)置額外存儲器，1次待簽名信息需小于512 bit。

表10 Ed25519性能參數(shù)

表11 周期及運算次數(shù)

由于Ed25519的實現(xiàn)多用于IoT設(shè)備，習(xí)慣基于短位寬乘法的迭代來設(shè)計，而FPGA中的DSP單元可以更靈活地提供乘法性能，故已知研究常在FPGA上進行。文獻[8]在FPGA上完成了Ed25519的全過程，其優(yōu)化算法每秒分別可以計算474次的公鑰生成、621次的簽名和272次驗簽，表12使用的是文獻[8]中每個功能所需的平均時間。

完整的Ed25519硬件實現(xiàn)很少，為了進一步評估性能，用Xilinx的Zynq-7035對本設(shè)計的標(biāo)量乘做簡單約束實現(xiàn)，并給出表13的對比結(jié)果。本設(shè)計中并未投入精力對257 bit乘法器做進一步時序優(yōu)化，用以在FPGA上達到較高工作頻率，所以使用了周期數(shù)來衡量運算速度，用消耗的Slices和Cycles的乘積再乘以10–6得到的結(jié)果值做性能對比的參考，其中文獻[9]未給出Slices參數(shù)，使用LUT/4來近似計算。

由表13可以看出，文獻[8]的標(biāo)量乘使用了15個DSP做循環(huán)迭代來計算256 bit模乘，這樣消耗的硬件資源很少，對于IoT設(shè)備是較好的選擇，但需要消耗很多周期。最終使用該標(biāo)量乘來完成的Ed25519，在其執(zhí)行速度上也如表12所列一樣，并未有太多競爭性。文獻[9]采用基8的循環(huán)移位模乘，所以沒有DSP單元的消耗，但整體性能稍差。文獻[11]使用快速模約簡，分為高128 bit和低128 bit來進行模乘，所以所需周期數(shù)是所有文獻中最少的，同樣，硬件資源的消耗情況也是所有文獻中最大的。文獻[12,13]也是使用FPGA中的DSP單元按17 bit分段進行模乘，只是迭代過程各有區(qū)別。與上述文獻相比，本設(shè)計中標(biāo)量乘的整體性能可提高約10%，具備一定的優(yōu)勢，而標(biāo)量乘是整個Ed25519的核心單元，也能從一定層面上反映整體的性能。

表12 Ed25519運算速度對比(μs)

表13 標(biāo)量乘單元性能對比

5 結(jié)論

本文對橢圓曲線簽名算法中的Ed25519算法進行了研究，使用快速模約簡計算模乘，并據(jù)此完成了點加倍點操作步驟的重新排布，然后使用窗口法實現(xiàn)了標(biāo)量乘運算。設(shè)計中改進Barrett約簡用于模L的實現(xiàn)，還為解壓算法設(shè)計模冪的操作步驟，充分復(fù)用已有單元，在保證運算速度的前提下，盡可能地減小硬件開銷。最后實現(xiàn)的硬件電路能夠完成Ed25519的完整操作，相較于其他設(shè)計，在運算速度上具有顯著優(yōu)勢。