摘 要： 點乘算法是橢圓曲線密碼體制中決定速度和硬件資源的關(guān)鍵部分。在深入分析混合結(jié)構(gòu)乘法器并在FPGA上實現(xiàn)經(jīng)典橢圓曲線點乘算法基礎上，設計與實現(xiàn)了一種基于NAF編碼混合結(jié)構(gòu)乘法器思想的橢圓曲線點乘算法。對實現(xiàn)的點乘算法進行仿真測試和性能評估表明，新設計實現(xiàn)的基于混合結(jié)構(gòu)乘法器的點乘算法在計算速度和資源使用上具有明顯優(yōu)勢。
關(guān)鍵詞： 有限域；FPGA；NAF；橢圓曲線點乘；算法安全
橢圓曲線密碼體制(ECC)作為新一代公鑰技術(shù)的典型代表，提供了更好的算法實現(xiàn)性能、更高的安全性和更低的實現(xiàn)代價[1]，同時能夠完成數(shù)據(jù)加密和數(shù)字簽名的功能。
現(xiàn)場可編程邏輯門陣列(FPGA)是一種基于4輸入查找表(LUT)、通過可編程互聯(lián)連接的可配置邏輯塊(CLB)矩陣的可編程半導體器件。與為特殊設計而定制的專用集成電路(ASIC)相對，F(xiàn)PGA可以針對所需的應用或功能要求進行編程。其邏輯資源遠比一般處理器多，而且具有編程方便、集成度高、速度快的特點。目前以硬件描述語言（VHDL或Verilog HDL）所完成的電路設計，可以經(jīng)過簡單的綜合與布局，快速下載至FPGA上進行測試，因而被稱作是現(xiàn)代IC設計驗證的主流技術(shù)。
目前，ECC的實現(xiàn)方案主要有軟件和硬件兩種，其中硬件實現(xiàn)方案因具有運算速度快、帶寬要求低等優(yōu)勢，被廣泛應用于硬件加密設備和無線網(wǎng)絡通信等領域。
FPGA芯片在執(zhí)行加密過程中，會有消耗能量的晶體管充放電過程。功耗分析時，依賴于硬件的各種加密操作與功耗具有相關(guān)性，其原理是通過監(jiān)測硬件在加密過程中產(chǎn)生的功耗曲線，利用統(tǒng)計學和攻擊者的經(jīng)驗對收集到的信息進行分析，從而獲得加密過程的相關(guān)數(shù)據(jù)[2]。
本文采用NIST定義在有限域GF(2m)上的Koblitz曲線：y2+xy=x3+x2+1。建立在該曲線上的橢圓曲線點乘運算可以快速實現(xiàn)，因此特別適合構(gòu)建高效的密碼系統(tǒng)。
ECC的安全性主要依賴于橢圓曲線離散對數(shù)問題（ECDLP）的難解性。ECDLP的定義如下：若P是橢圓曲線E上的一點(稱為基點)，P的階為素數(shù)n，k為一隨機選擇的正整數(shù)，已知Q=kP，無法求得或者很難求得k，把Q定義為公鑰，k為私鑰。
在橢圓曲線上建立公鑰密碼系統(tǒng)的過程中，其核心計算是點乘運算，因此對橢圓曲線點乘算法進行深入研究很有必要。
ECC的層次結(jié)構(gòu)由自上而下可分解為加解密層、群運算層、域運算層，如圖1所示。各個運算模塊通過狀態(tài)機的合理控制，實現(xiàn)FPGA上橢圓曲線點乘算法。
隨著計算資源的急劇膨脹，特別是邊信道攻擊等新型的密碼攻擊方式的出現(xiàn)[5]，給ECC的安全性帶來一定的挑戰(zhàn)。針對ECC邊信道分析攻擊，采取的防御手段既有在算法實現(xiàn)方法上改進的軟件手段，也有通過增加噪聲干擾和采用數(shù)?；旌想娐樊a(chǎn)生真隨機數(shù)來擾亂掩碼和時鐘的硬件手段[6]。
1.2 實現(xiàn)方案
在FPGA上實現(xiàn)各種密碼算法的過程中，應考慮到FPGA的既定芯片資源限制以及如何在更少的資源量和更快的時序中找到平衡點這兩個因素。
由于1個求解逆元的操作在計算時間上約和70個乘法器相近[7]，因此在實施ECC的點乘算法時，應盡量減少使用求逆運算。
在設計與實現(xiàn)橢圓曲線的點乘算法時，本文內(nèi)容主要將作如下安排。首先，從算法級別對乘法器運算單元進行改進，以提高乘法器的速度。然后，對乘法器模塊由混合結(jié)構(gòu)乘法器實現(xiàn)的點乘運算進行性能評估。最后，在經(jīng)典橢圓曲線點乘算法的實現(xiàn)過程中，通過使用乘法器代替模平方運算的方法來增加計算的隱蔽性，算法內(nèi)部實現(xiàn)邏輯的改善，達到提高算法安全性的目的。
2 乘法器模塊設計
有限域上的乘法器是點加運算和點乘運算所要涉及的核心運算。實現(xiàn)多項式乘法器最基本方法是移位相加，而移位操作在FPGA中實現(xiàn)非常方便，不需要使用任何邏輯單元。研究表明，根據(jù)FPGA的特點而設計的乘法器具有明顯的速度優(yōu)勢。
本文使用的StratixⅡ系列器件是ALTERA公司基于1.2 V工藝的現(xiàn)場可編程門陣列。選用擁有高達72 768個ALUTs、903個IO資源的EP2S90F1508C3芯片作為乘法器實現(xiàn)方案的硬件基礎，如圖2。
圖2中，A、B分別表示多項式乘法器的乘數(shù)與被乘數(shù)，F(xiàn)表示有限域GF(2m)的多項式基，CLK為主時鐘信號，reset為復位信號，start為使能信號，result和done分別表示乘法器的運算結(jié)果和運算結(jié)束標志。
將混合結(jié)構(gòu)乘法器[8]與目前點乘算法所使用的乘法器做包括資源占用和計算性能兩方面比較。乘法器1是使用文獻[8]中提到的乘法器實現(xiàn)的橢圓曲線點乘算法在EP2S90F1508C3芯片上的實現(xiàn)，乘法器2是目前點乘算法所使用的乘法器。
通過使用Synplify Pro 9.6對2種乘法器進行綜合以及ModelSim-Altera的前仿真，文獻[8]使用23個時鐘數(shù)、算法2使用107個時鐘周期所得到的資源和計算性能評估結(jié)果如表1和表2所示。
在200 MHz的時鐘頻率下，乘法器計算性能的評估結(jié)果如表2所示。
混合結(jié)構(gòu)乘法器的計算性能較目前使用的乘法器2的性能有顯著的提高。
為驗證乘法器計算正確性，以163 bit的乘法器為例，其仿真結(jié)果如圖3所示。
下面將在目標芯片上實現(xiàn)基于這兩種乘法器的點乘算法。
3 橢圓曲線點乘算法的FPGA實現(xiàn)
計算有限域GF(2m)點乘kP的最直接方法是使用倍點和點加相結(jié)合的double-and-add方法。如果ki=0，則僅執(zhí)行倍點計算；如果ki=1，則執(zhí)行倍點計算和點加計算。Double-and-add算法需要(m-1)次倍點運算和m/2次點加運算[12]，而使用非相鄰（NAF）編碼思想的二進制點乘算法可以將計算點加的平均次數(shù)減少至m/3[9]。
基于上述兩種乘法器模塊，本文實現(xiàn)的是使用NAF編碼的163 bit二進制域上的橢圓曲線點乘算法。
3.1 基于NAF思想的橢圓曲線點乘
使用NAF編碼思想計算橢圓曲線點乘是因為橢圓曲線上點的減法和點的加法一樣有效，NAF編碼可以在不使用橢圓曲線倍點計算的環(huán)境下實現(xiàn)點乘運算而僅使用點加和基本的域運算的狀態(tài)下來完成二進制域上的點乘操作。
在計算NAF編碼的二進制點乘算法時，首先需要知道如何計算給定數(shù)的NAF值，然后使用該算法的思想完成橢圓曲線的點乘kP計算。其算法描述如下：
其中，m表示運算比特位數(shù)，f(z)是有限域GF(2m)的多項式基，n是基點G的階，x和y分別表示的是基點G的橫坐標和縱坐標。
在使用工具Synplify Pro 9.6綜合后，混合結(jié)構(gòu)乘法器的點乘運算和基于原有乘法器的點乘算法相比，在計算性能和資源占用等性能上的評估結(jié)果如表4所示。
設計實現(xiàn)的基于混合結(jié)構(gòu)乘法器的點乘算法（點乘算法1）在完成一次點乘運算的時間上較原有的點乘算法有所提高，且在資源占用上較原有算法有所減少，與同類型的點乘算法相比在計算性能上有明顯提高。
4 算法安全性
基于Montgomery Ladder的橢圓曲線多倍點運算是不安全的[10]。為了增加算法的抗功耗分析能力，通常的做法是采用增加計算的隱蔽性等軟件手段或者引入噪聲干擾以及掩膜方式等硬件手段[6]。
本文通過改進橢圓曲線點乘算法中的內(nèi)部結(jié)構(gòu)可以做到提高算法的抗功耗分析能力，其中使用乘法器替代模平方算法能有效防范邊信道攻擊[11]。本文以經(jīng)典橢圓曲線點乘算法為例(算法1)，從計算安全的角度考慮，使用乘法器替代模平方算法的方法和VHDL語言在 EP2S90F1508C3芯片中(算法2)實現(xiàn)。
在使用綜合工具Synplify Pro 9.6對經(jīng)典的點乘算法1和算法2進行綜合后，在50 MHz的時鐘頻率下，兩種點乘算法分別在9.6 ms和10.1 ms內(nèi)完成一次點乘操作。可見，為了讓經(jīng)典橢圓曲線點乘算法獲得更好的抗功耗能力，而使用乘法器替代模平方算法的改進措施對點乘算法的計算性能沒有明顯改變。
通過對實現(xiàn)基于混合結(jié)構(gòu)乘法器的點乘算法仿真驗證，結(jié)果表明，基于混合結(jié)構(gòu)乘法器的點乘算法在運算速度上較改進前有一定的提高，和同類型的橢圓曲線點乘算法比較有顯著提高。與此同時，為提高算法的抗功耗分析能力，使用模乘運算取代模平方運算的改進措施，對點乘算法的執(zhí)行時間影響較小。
參考文獻
[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實現(xiàn)[J].北京大學學報，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].小型微型計算機系統(tǒng)，2009(4).
[7] 汪朝暉，陳建華.素域上橢圓曲線密碼的高效實現(xiàn)[J].武漢大學學報（理工版），2004，50(3).
[8] 高獻偉，靳濟方，方勇，等.GF（2m）域乘法器的快速設計及FPGA實現(xiàn)[J].計算機工程與應用，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] 趙彥光，白國強，陳弘毅.一種針對特征2域橢圓曲線密碼芯片的差分功耗分析[J].微電子學與計算機，2006，23(12).
[11] 余榮威，陳建華.抗側(cè)信道攻擊的橢圓曲線點乘算法設計[J].計算機工程與應用，2006.
下載文檔
