摘 要： 點(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)乘算法。對(duì)實(shí)現(xiàn)的點(diǎn)乘算法進(jìn)行仿真測(cè)試和性能評(píng)估表明，新設(shè)計(jì)實(shí)現(xiàn)的基于混合結(jié)構(gòu)乘法器的點(diǎn)乘算法在計(jì)算速度和資源使用上具有明顯優(yōu)勢(shì)。
關(guān)鍵詞： 有限域；FPGA；NAF；橢圓曲線點(diǎn)乘；算法安全

橢圓曲線密碼體制(ECC)作為新一代公鑰技術(shù)的典型代表，提供了更好的算法實(shí)現(xiàn)性能、更高的安全性和更低的實(shí)現(xiàn)代價(jià)[1]，同時(shí)能夠完成數(shù)據(jù)加密和數(shù)字簽名的功能。
現(xiàn)場(chǎng)可編程邏輯門陣列(FPGA)是一種基于4輸入查找表(LUT)、通過(guò)可編程互聯(lián)連接的可配置邏輯塊(CLB)矩陣的可編程半導(dǎo)體器件。與為特殊設(shè)計(jì)而定制的專用集成電路(ASIC)相對(duì)，F(xiàn)PGA可以針對(duì)所需的應(yīng)用或功能要求進(jìn)行編程。其邏輯資源遠(yuǎn)比一般處理器多，而且具有編程方便、集成度高、速度快的特點(diǎn)。目前以硬件描述語(yǔ)言（VHDL或Verilog HDL）所完成的電路設(shè)計(jì)，可以經(jīng)過(guò)簡(jiǎn)單的綜合與布局，快速下載至FPGA上進(jìn)行測(cè)試，因而被稱作是現(xiàn)代IC設(shè)計(jì)驗(yàn)證的主流技術(shù)。
目前，ECC的實(shí)現(xiàn)方案主要有軟件和硬件兩種，其中硬件實(shí)現(xiàn)方案因具有運(yùn)算速度快、帶寬要求低等優(yōu)勢(shì)，被廣泛應(yīng)用于硬件加密設(shè)備和無(wú)線網(wǎng)絡(luò)通信等領(lǐng)域。
FPGA芯片在執(zhí)行加密過(guò)程中，會(huì)有消耗能量的晶體管充放電過(guò)程。功耗分析時(shí)，依賴于硬件的各種加密操作與功耗具有相關(guān)性，其原理是通過(guò)監(jiān)測(cè)硬件在加密過(guò)程中產(chǎn)生的功耗曲線，利用統(tǒng)計(jì)學(xué)和攻擊者的經(jīng)驗(yàn)對(duì)收集到的信息進(jìn)行分析，從而獲得加密過(guò)程的相關(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的安全性主要依賴于橢圓曲線離散對(duì)數(shù)問(wèn)題（ECDLP）的難解性。ECDLP的定義如下：若P是橢圓曲線E上的一點(diǎn)(稱為基點(diǎn))，P的階為素?cái)?shù)n，k為一隨機(jī)選擇的正整數(shù)，已知Q=kP，無(wú)法求得或者很難求得k，把Q定義為公鑰，k為私鑰。
在橢圓曲線上建立公鑰密碼系統(tǒng)的過(guò)程中，其核心計(jì)算是點(diǎn)乘運(yùn)算，因此對(duì)橢圓曲線點(diǎn)乘算法進(jìn)行深入研究很有必要。
ECC的層次結(jié)構(gòu)由自上而下可分解為加解密層、群運(yùn)算層、域運(yùn)算層，如圖1所示。各個(gè)運(yùn)算模塊通過(guò)狀態(tài)機(jī)的合理控制，實(shí)現(xiàn)FPGA上橢圓曲線點(diǎn)乘算法。

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

圖2中，A、B分別表示多項(xiàng)式乘法器的乘數(shù)與被乘數(shù)，F(xiàn)表示有限域GF(2m)的多項(xiàng)式基，CLK為主時(shí)鐘信號(hào)，reset為復(fù)位信號(hào)，start為使能信號(hào)，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)乘算法所使用的乘法器。
通過(guò)使用Synplify Pro 9.6對(duì)2種乘法器進(jìn)行綜合以及ModelSim-Altera的前仿真，文獻(xiàn)[8]使用23個(gè)時(shí)鐘數(shù)、算法2使用107個(gè)時(shí)鐘周期所得到的資源和計(jì)算性能評(píng)估結(jié)果如表1和表2所示。

在200 MHz的時(shí)鐘頻率下，乘法器計(jì)算性能的評(píng)估結(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)下來(lái)完成二進(jìn)制域上的點(diǎn)乘操作。
在計(jì)算NAF編碼的二進(jìn)制點(diǎn)乘算法時(shí)，首先需要知道如何計(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ì)算性能和資源占用等性能上的評(píng)估結(jié)果如表4所示。

設(shè)計(jì)實(shí)現(xiàn)的基于混合結(jié)構(gòu)乘法器的點(diǎn)乘算法（點(diǎn)乘算法1）在完成一次點(diǎn)乘運(yùn)算的時(shí)間上較原有的點(diǎn)乘算法有所提高，且在資源占用上較原有算法有所減少，與同類型的點(diǎn)乘算法相比在計(jì)算性能上有明顯提高。
4 算法安全性
基于Montgomery Ladder的橢圓曲線多倍點(diǎn)運(yùn)算是不安全的[10]。為了增加算法的抗功耗分析能力，通常的做法是采用增加計(jì)算的隱蔽性等軟件手段或者引入噪聲干擾以及掩膜方式等硬件手段[6]。
本文通過(guò)改進(jìn)橢圓曲線點(diǎn)乘算法中的內(nèi)部結(jié)構(gòu)可以做到提高算法的抗功耗分析能力，其中使用乘法器替代模平方算法能有效防范邊信道攻擊[11]。本文以經(jīng)典橢圓曲線點(diǎn)乘算法為例(算法1)，從計(jì)算安全的角度考慮，使用乘法器替代模平方算法的方法和VHDL語(yǔ)言在 EP2S90F1508C3芯片中(算法2)實(shí)現(xiàn)。
在使用綜合工具Synplify Pro 9.6對(duì)經(jīng)典的點(diǎn)乘算法1和算法2進(jìn)行綜合后，在50 MHz的時(shí)鐘頻率下，兩種點(diǎn)乘算法分別在9.6 ms和10.1 ms內(nèi)完成一次點(diǎn)乘操作。可見(jiàn)，為了讓經(jīng)典橢圓曲線點(diǎn)乘算法獲得更好的抗功耗能力，而使用乘法器替代模平方算法的改進(jìn)措施對(duì)點(diǎn)乘算法的計(jì)算性能沒(méi)有明顯改變。
通過(guò)對(duì)實(shí)現(xiàn)基于混合結(jié)構(gòu)乘法器的點(diǎn)乘算法仿真驗(yàn)證，結(jié)果表明，基于混合結(jié)構(gòu)乘法器的點(diǎn)乘算法在運(yùn)算速度上較改進(jìn)前有一定的提高，和同類型的橢圓曲線點(diǎn)乘算法比較有顯著提高。與此同時(shí)，為提高算法的抗功耗分析能力，使用模乘運(yùn)算取代模平方運(yùn)算的改進(jìn)措施，對(duì)點(diǎn)乘算法的執(zhí)行時(shí)間影響較小。
參考文獻(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] 趙彥光，白國(guó)強(qiáng)，陳弘毅.一種針對(duì)特征2域橢圓曲線密碼芯片的差分功耗分析[J].微電子學(xué)與計(jì)算機(jī)，2006，23(12).
[11] 余榮威，陳建華.抗側(cè)信道攻擊的橢圓曲線點(diǎn)乘算法設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，2006.