GF(2m)域橢圓曲線點(diǎn)乘算法安全FPGA設(shè)計(jì)與實(shí)現(xiàn)

摘 要： 點(diǎn)乘算法是橢圓曲線密碼體制中決定速度和硬件資源的關(guān)鍵部分。在深入分析混合結(jié)構(gòu)乘法器并在FPGA上實(shí)現(xiàn)經(jīng)典橢圓曲線點(diǎn)乘算法基礎(chǔ)上，設(shè)計(jì)與實(shí)現(xiàn)了一種基于NAF編碼混合結(jié)構(gòu)乘法器思想的橢圓曲線點(diǎn)乘算法。對實(shí)現(xiàn)的點(diǎn)乘算法進(jìn)行仿真測試和性能評估表明，新設(shè)計(jì)實(shí)現(xiàn)的基于混合結(jié)構(gòu)乘法器的點(diǎn)乘算法在計(jì)算速度和資源使用上具有明顯優(yōu)勢。
關(guān)鍵詞： 有限域；FPGA；NAF；橢圓曲線點(diǎn)乘；算法安全

橢圓曲線密碼體制(ECC)作為新一代公鑰技術(shù)的典型代表，提供了更好的算法實(shí)現(xiàn)性能、更高的安全性和更低的實(shí)現(xiàn)代價[1]，同時能夠完成數(shù)據(jù)加密和數(shù)字簽名的功能。
現(xiàn)場可編程邏輯門陣列(FPGA)是一種基于4輸入查找表(LUT)、通過可編程互聯(lián)連接的可配置邏輯塊(CLB)矩陣的可編程半導(dǎo)體器件。與為特殊設(shè)計(jì)而定制的專用集成電路(ASIC)相對，F(xiàn)PGA可以針對所需的應(yīng)用或功能要求進(jìn)行編程。其邏輯資源遠(yuǎn)比一般處理器多，而且具有編程方便、集成度高、速度快的特點(diǎn)。目前以硬件描述語言（VHDL或Verilog HDL）所完成的電路設(shè)計(jì)，可以經(jīng)過簡單的綜合與布局，快速下載至FPGA上進(jìn)行測試，因而被稱作是現(xiàn)代IC設(shè)計(jì)驗(yàn)證的主流技術(shù)。
目前，ECC的實(shí)現(xiàn)方案主要有軟件和硬件兩種，其中硬件實(shí)現(xiàn)方案因具有運(yùn)算速度快、帶寬要求低等優(yōu)勢，被廣泛應(yīng)用于硬件加密設(shè)備和無線網(wǎng)絡(luò)通信等領(lǐng)域。
FPGA芯片在執(zhí)行加密過程中，會有消耗能量的晶體管充放電過程。功耗分析時，依賴于硬件的各種加密操作與功耗具有相關(guān)性，其原理是通過監(jiān)測硬件在加密過程中產(chǎn)生的功耗曲線，利用統(tǒng)計(jì)學(xué)和攻擊者的經(jīng)驗(yàn)對收集到的信息進(jìn)行分析，從而獲得加密過程的相關(guān)數(shù)據(jù)[2]。
本文采用NIST定義在有限域GF(2m)上的Koblitz曲線：y2+xy=x3+x2+1。建立在該曲線上的橢圓曲線點(diǎn)乘運(yùn)算可以快速實(shí)現(xiàn)，因此特別適合構(gòu)建高效的密碼系統(tǒng)。

ECC的安全性主要依賴于橢圓曲線離散對數(shù)問題（ECDLP）的難解性。ECDLP的定義如下：若P是橢圓曲線E上的一點(diǎn)(稱為基點(diǎn))，P的階為素?cái)?shù)n，k為一隨機(jī)選擇的正整數(shù)，已知Q=kP，無法求得或者很難求得k，把Q定義為公鑰，k為私鑰。
在橢圓曲線上建立公鑰密碼系統(tǒng)的過程中，其核心計(jì)算是點(diǎn)乘運(yùn)算，因此對橢圓曲線點(diǎn)乘算法進(jìn)行深入研究很有必要。
ECC的層次結(jié)構(gòu)由自上而下可分解為加解密層、群運(yùn)算層、域運(yùn)算層，如圖1所示。各個運(yùn)算模塊通過狀態(tài)機(jī)的合理控制，實(shí)現(xiàn)FPGA上橢圓曲線點(diǎn)乘算法。

隨著計(jì)算資源的急劇膨脹，特別是邊信道攻擊等新型的密碼攻擊方式的出現(xiàn)[5]，給ECC的安全性帶來一定的挑戰(zhàn)。針對ECC邊信道分析攻擊，采取的防御手段既有在算法實(shí)現(xiàn)方法上改進(jìn)的軟件手段，也有通過增加噪聲干擾和采用數(shù)?；旌想娐樊a(chǎn)生真隨機(jī)數(shù)來擾亂掩碼和時鐘的硬件手段[6]。
1.2 實(shí)現(xiàn)方案
在FPGA上實(shí)現(xiàn)各種密碼算法的過程中，應(yīng)考慮到FPGA的既定芯片資源限制以及如何在更少的資源量和更快的時序中找到平衡點(diǎn)這兩個因素。
由于1個求解逆元的操作在計(jì)算時間上約和70個乘法器相近[7]，因此在實(shí)施ECC的點(diǎn)乘算法時，應(yīng)盡量減少使用求逆運(yùn)算。
在設(shè)計(jì)與實(shí)現(xiàn)橢圓曲線的點(diǎn)乘算法時，本文內(nèi)容主要將作如下安排。首先，從算法級別對乘法器運(yùn)算單元進(jìn)行改進(jìn)，以提高乘法器的速度。然后，對乘法器模塊由混合結(jié)構(gòu)乘法器實(shí)現(xiàn)的點(diǎn)乘運(yùn)算進(jìn)行性能評估。最后，在經(jīng)典橢圓曲線點(diǎn)乘算法的實(shí)現(xiàn)過程中，通過使用乘法器代替模平方運(yùn)算的方法來增加計(jì)算的隱蔽性，算法內(nèi)部實(shí)現(xiàn)邏輯的改善，達(dá)到提高算法安全性的目的。
2 乘法器模塊設(shè)計(jì)
有限域上的乘法器是點(diǎn)加運(yùn)算和點(diǎn)乘運(yùn)算所要涉及的核心運(yùn)算。實(shí)現(xiàn)多項(xiàng)式乘法器最基本方法是移位相加，而移位操作在FPGA中實(shí)現(xiàn)非常方便，不需要使用任何邏輯單元。研究表明，根據(jù)FPGA的特點(diǎn)而設(shè)計(jì)的乘法器具有明顯的速度優(yōu)勢。
本文使用的StratixⅡ系列器件是ALTERA公司基于1.2 V工藝的現(xiàn)場可編程門陣列。選用擁有高達(dá)72 768個ALUTs、903個IO資源的EP2S90F1508C3芯片作為乘法器實(shí)現(xiàn)方案的硬件基礎(chǔ)，如圖2。

圖2中，A、B分別表示多項(xiàng)式乘法器的乘數(shù)與被乘數(shù)，F(xiàn)表示有限域GF(2m)的多項(xiàng)式基，CLK為主時鐘信號，reset為復(fù)位信號，start為使能信號，result和done分別表示乘法器的運(yùn)算結(jié)果和運(yùn)算結(jié)束標(biāo)志。
將混合結(jié)構(gòu)乘法器[8]與目前點(diǎn)乘算法所使用的乘法器做包括資源占用和計(jì)算性能兩方面比較。乘法器1是使用文獻(xiàn)[8]中提到的乘法器實(shí)現(xiàn)的橢圓曲線點(diǎn)乘算法在EP2S90F1508C3芯片上的實(shí)現(xiàn)，乘法器2是目前點(diǎn)乘算法所使用的乘法器。
通過使用Synplify Pro 9.6對2種乘法器進(jìn)行綜合以及ModelSim-Altera的前仿真，文獻(xiàn)[8]使用23個時鐘數(shù)、算法2使用107個時鐘周期所得到的資源和計(jì)算性能評估結(jié)果如表1和表2所示。

在200 MHz的時鐘頻率下，乘法器計(jì)算性能的評估結(jié)果如表2所示。
混合結(jié)構(gòu)乘法器的計(jì)算性能較目前使用的乘法器2的性能有顯著的提高。
為驗(yàn)證乘法器計(jì)算正確性，以163 bit的乘法器為例，其仿真結(jié)果如圖3所示。

下面將在目標(biāo)芯片上實(shí)現(xiàn)基于這兩種乘法器的點(diǎn)乘算法。
3 橢圓曲線點(diǎn)乘算法的FPGA實(shí)現(xiàn)
計(jì)算有限域GF(2m)點(diǎn)乘kP的最直接方法是使用倍點(diǎn)和點(diǎn)加相結(jié)合的double-and-add方法。如果ki=0，則僅執(zhí)行倍點(diǎn)計(jì)算；如果ki=1，則執(zhí)行倍點(diǎn)計(jì)算和點(diǎn)加計(jì)算。Double-and-add算法需要(m-1)次倍點(diǎn)運(yùn)算和m/2次點(diǎn)加運(yùn)算[12]，而使用非相鄰（NAF）編碼思想的二進(jìn)制點(diǎn)乘算法可以將計(jì)算點(diǎn)加的平均次數(shù)減少至m/3[9]。
基于上述兩種乘法器模塊，本文實(shí)現(xiàn)的是使用NAF編碼的163 bit二進(jìn)制域上的橢圓曲線點(diǎn)乘算法。
3.1 基于NAF思想的橢圓曲線點(diǎn)乘
使用NAF編碼思想計(jì)算橢圓曲線點(diǎn)乘是因?yàn)闄E圓曲線上點(diǎn)的減法和點(diǎn)的加法一樣有效，NAF編碼可以在不使用橢圓曲線倍點(diǎn)計(jì)算的環(huán)境下實(shí)現(xiàn)點(diǎn)乘運(yùn)算而僅使用點(diǎn)加和基本的域運(yùn)算的狀態(tài)下來完成二進(jìn)制域上的點(diǎn)乘操作。
在計(jì)算NAF編碼的二進(jìn)制點(diǎn)乘算法時，首先需要知道如何計(jì)算給定數(shù)的NAF值，然后使用該算法的思想完成橢圓曲線的點(diǎn)乘kP計(jì)算。其算法描述如下：

其中，m表示運(yùn)算比特位數(shù)，f(z)是有限域GF(2m)的多項(xiàng)式基，n是基點(diǎn)G的階，x和y分別表示的是基點(diǎn)G的橫坐標(biāo)和縱坐標(biāo)。
在使用工具Synplify Pro 9.6綜合后，混合結(jié)構(gòu)乘法器的點(diǎn)乘運(yùn)算和基于原有乘法器的點(diǎn)乘算法相比，在計(jì)算性能和資源占用等性能上的評估結(jié)果如表4所示。

設(shè)計(jì)實(shí)現(xiàn)的基于混合結(jié)構(gòu)乘法器的點(diǎn)乘算法（點(diǎn)乘算法1）在完成一次點(diǎn)乘運(yùn)算的時間上較原有的點(diǎn)乘算法有所提高，且在資源占用上較原有算法有所減少，與同類型的點(diǎn)乘算法相比在計(jì)算性能上有明顯提高。
4 算法安全性
基于Montgomery Ladder的橢圓曲線多倍點(diǎn)運(yùn)算是不安全的[10]。為了增加算法的抗功耗分析能力，通常的做法是采用增加計(jì)算的隱蔽性等軟件手段或者引入噪聲干擾以及掩膜方式等硬件手段[6]。
本文通過改進(jìn)橢圓曲線點(diǎn)乘算法中的內(nèi)部結(jié)構(gòu)可以做到提高算法的抗功耗分析能力，其中使用乘法器替代模平方算法能有效防范邊信道攻擊[11]。本文以經(jīng)典橢圓曲線點(diǎn)乘算法為例(算法1)，從計(jì)算安全的角度考慮，使用乘法器替代模平方算法的方法和VHDL語言在 EP2S90F1508C3芯片中(算法2)實(shí)現(xiàn)。
在使用綜合工具Synplify Pro 9.6對經(jīng)典的點(diǎn)乘算法1和算法2進(jìn)行綜合后，在50 MHz的時鐘頻率下，兩種點(diǎn)乘算法分別在9.6 ms和10.1 ms內(nèi)完成一次點(diǎn)乘操作?？梢?，為了讓經(jīng)典橢圓曲線點(diǎn)乘算法獲得更好的抗功耗能力，而使用乘法器替代模平方算法的改進(jìn)措施對點(diǎn)乘算法的計(jì)算性能沒有明顯改變。
通過對實(shí)現(xiàn)基于混合結(jié)構(gòu)乘法器的點(diǎn)乘算法仿真驗(yàn)證，結(jié)果表明，基于混合結(jié)構(gòu)乘法器的點(diǎn)乘算法在運(yùn)算速度上較改進(jìn)前有一定的提高，和同類型的橢圓曲線點(diǎn)乘算法比較有顯著提高。與此同時，為提高算法的抗功耗分析能力，使用模乘運(yùn)算取代模平方運(yùn)算的改進(jìn)措施，對點(diǎn)乘算法的執(zhí)行時間影響較小。
參考文獻(xiàn)
[1] CHOI Y，KIM H W，KIM M S.Implementation of elliptic curve cryptographic over GF(2163) for ECC protocols[S].2001.
[2] DANIEL M G.A survey of fast exponentiation methods[J]. 1998，27.
[3] IEEE P1363/D13.Standard specification for public-key cryptography[C].1999(12).
[4] 王建，蔣安平，盛世敏.橢圓曲線加密體制的雙有限域算法及其FPGA實(shí)現(xiàn)[J].北京大學(xué)學(xué)報(bào)，2008，44(6)：871-875.
[5] AIGNER M，OSWALD E.Power analysis tutorial[C].Institute for Applied Information Processing and Communication University of Technology Graz，2000.
[6] 鄭新建，張翌維，沈緒榜.SPA和DPA攻擊與防御技術(shù)新進(jìn)展[J].小型微型計(jì)算機(jī)系統(tǒng)，2009(4).
[7] 汪朝暉，陳建華.素域上橢圓曲線密碼的高效實(shí)現(xiàn)[J].武漢大學(xué)學(xué)報(bào)（理工版），2004，50(3).
[8] 高獻(xiàn)偉，靳濟(jì)方，方勇，等.GF（2m）域乘法器的快速設(shè)計(jì)及FPGA實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2004(25).
[9] JOY M，TYMEN C.Compact encoding of Non-adjacent forms with applications to elliptic curve cryptography[J]. Public Key Cryptography，LNCS 1992，Springer，pp.353-364，2001.
[10] 趙彥光，白國強(qiáng)，陳弘毅.一種針對特征2域橢圓曲線密碼芯片的差分功耗分析[J].微電子學(xué)與計(jì)算機(jī)，2006，23(12).
[11] 余榮威，陳建華.抗側(cè)信道攻擊的橢圓曲線點(diǎn)乘算法設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，2006.