基于橢圓曲線的RFID電子標(biāo)簽加密算法研究

張藝與，趙海軍**，賀春林，陳毅紅

(1. 西華師范大學(xué) 計(jì)算機(jī)學(xué)院，四川 南充 637009；2. 物聯(lián)網(wǎng)感知與大數(shù)據(jù)分析南充市重點(diǎn)實(shí)驗(yàn)室，四川 南充 637009)

物聯(lián)網(wǎng)作為新一代信息技術(shù)的重要組成部分，已經(jīng)廣泛應(yīng)用于各個(gè)領(lǐng)域. 它是基于互聯(lián)網(wǎng)、各類傳感器以及射頻識(shí)別 (Radio Frequency Identification,RFID)等技術(shù)的新興技術(shù)，旨在將物與物、人與物連接起來，實(shí)現(xiàn)萬物互聯(lián). RFID是物聯(lián)網(wǎng)的核心技術(shù)，其應(yīng)用已經(jīng)遍及各個(gè)領(lǐng)域，典型應(yīng)用如智能交通、現(xiàn)代醫(yī)療、身份識(shí)別、物流、倉儲(chǔ)管理、車輛道路交通自動(dòng)收費(fèi)管理、智能家居、產(chǎn)品防偽檢測(cè)和智能卡等領(lǐng)域.

一方面，與傳統(tǒng)的條碼技術(shù)相比，RFID具有非接觸式識(shí)別、抗污染性強(qiáng)、使用便捷、低成本和自主識(shí)別等優(yōu)點(diǎn)，所以RFID取代傳統(tǒng)條碼技術(shù)是必然的；另一方面，由于RFID系統(tǒng)對(duì)應(yīng)用完全開放的設(shè)計(jì)思想，使其安全與隱私難以保障，阻礙著它大規(guī)模應(yīng)用. 典型的RFID系統(tǒng)主要由電子標(biāo)簽(Tag)、閱讀器、RFID中間件和應(yīng)用軟件4部分構(gòu)成. 其中電子標(biāo)簽按供電方式分為有源標(biāo)簽、無源標(biāo)簽以及半有源標(biāo)簽. 與傳統(tǒng)的硬件資源相比，電子標(biāo)簽因其自身硬件資源極端受限，計(jì)算能力和存儲(chǔ)能力較弱，難以實(shí)現(xiàn)安全性強(qiáng)的公鑰加密算法.但基于簡單異或等邏輯運(yùn)算的輕量級(jí)加密算法又難以保證標(biāo)簽數(shù)據(jù)的安全性，所以對(duì)于公鑰加密算法的輕量化成為解決這個(gè)問題的關(guān)鍵.

國內(nèi)外學(xué)者為了平衡RFID系統(tǒng)中硬件實(shí)現(xiàn)效率和算法安全性，做了大量研究，提出了許多輕量級(jí)加密方案. 文獻(xiàn)[1]提出的輕量級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn) (Data Encryption Standard Lightweight, DESL)分組密碼算法，將數(shù)據(jù)加密標(biāo)準(zhǔn)(Data Encryption Standard, DES)算法的密鑰減少為 56 bit，從而實(shí)現(xiàn)輕量化，這種算法保密性好、結(jié)構(gòu)緊湊、效率更高.文獻(xiàn)[2]提出了A2U2序列密碼算法，該算法是針對(duì)RFID標(biāo)簽所專門設(shè)計(jì)的一種輕量級(jí)加密算法，硬件實(shí)現(xiàn)成本低. 文獻(xiàn)[3]提出了ITUbee算法，通過減少加密輪次，降低能耗以達(dá)到輕量化. 由于單向散列(Hash)函數(shù)計(jì)算簡單，故在RFID系統(tǒng)中得以廣泛應(yīng)用，比較典型的有文獻(xiàn)[4]提出的散列鎖(Hash-Lock)協(xié)議. 在非對(duì)稱密碼算法的輕量化研究中，橢圓曲線密碼 (Elliptic Curve Cryptography,ECC)體制相比于其他公鑰加密算法，具有密鑰長度短、占用內(nèi)存資源低以及加密強(qiáng)度大等技術(shù)優(yōu)勢(shì)，因此許多學(xué)者致力于ECC的輕量化研究. 文獻(xiàn)[5]提出了一種基于改進(jìn)ECC算法的RFID系統(tǒng)安全認(rèn)證協(xié)議；文獻(xiàn)[6-8]通過優(yōu)化ECC算法運(yùn)算過程中的標(biāo)量乘運(yùn)算，以達(dá)到降低運(yùn)算量的目的.

以上輕量加密方案可以概括為：基于對(duì)稱密碼體制的輕量化和基于非對(duì)稱密碼體制的輕量化. 對(duì)稱密碼體制輕量化主要通過減少密鑰長度和減少加密輪次來實(shí)現(xiàn)，此類方法均是通過犧牲一定安全性來降低算法計(jì)算量，非對(duì)稱密碼體制中橢圓曲線密碼體制的輕量化主要通過減少密鑰長度和優(yōu)化底層運(yùn)算來實(shí)現(xiàn)輕量化. 同樣的，減少密鑰長度會(huì)犧牲一定的安全性，而優(yōu)化底層運(yùn)算來降低算法計(jì)算量可以在不改變安全性的基礎(chǔ)上提高計(jì)算速度，是目前橢圓曲線密碼體制研究的熱點(diǎn)問題.

本文考慮到ECC算法占用內(nèi)存小、計(jì)算速度快、帶寬要求低、加密強(qiáng)度大等優(yōu)勢(shì)，選擇ECC算法作為RFID系統(tǒng)電子標(biāo)簽的加密算法，并對(duì)原有算法進(jìn)行改進(jìn)以提高算法的計(jì)算速度. 標(biāo)量乘法是橢圓曲線加密體制最耗時(shí)的運(yùn)算，本文主要研究通過改進(jìn)橢圓曲線標(biāo)量乘運(yùn)算來實(shí)現(xiàn)橢圓曲線密碼體制的輕量化.

1 RFID 系統(tǒng)數(shù)據(jù)加密問題

1.1 RFID 系統(tǒng)中的數(shù)據(jù)特點(diǎn)RFID 作為物聯(lián)網(wǎng)感知層的核心技術(shù)，系統(tǒng)中產(chǎn)生和存儲(chǔ)的數(shù)據(jù)具有如下特點(diǎn)[9]：

（1）時(shí)效性 指從數(shù)據(jù)產(chǎn)生到其被清除的時(shí)間，數(shù)據(jù)時(shí)效性是由系統(tǒng)的實(shí)施部署所決定. 物聯(lián)網(wǎng)對(duì)實(shí)時(shí)性要求較高，需要做到能夠及時(shí)發(fā)送、交互性強(qiáng)、數(shù)據(jù)轉(zhuǎn)發(fā)性能高.

（2）海量性 物聯(lián)網(wǎng)是由若干無線識(shí)別的物體彼此連接和結(jié)合形成的動(dòng)態(tài)網(wǎng)絡(luò)，在這個(gè)動(dòng)態(tài)網(wǎng)絡(luò)中所采集、產(chǎn)生的數(shù)據(jù)量都是巨大的，如何處理這些海量的數(shù)據(jù)，是物聯(lián)網(wǎng)數(shù)據(jù)處理需要特別考慮的問題.

（3）多態(tài)性與異構(gòu)性 在物聯(lián)網(wǎng)中通過無線傳感器網(wǎng)絡(luò)、RFID系統(tǒng)以及M2M系統(tǒng)來采集數(shù)據(jù)，這些底層設(shè)備在不同應(yīng)用系統(tǒng)中又有不同用途，并且這些設(shè)備結(jié)構(gòu)不同、性能各異，其采集的數(shù)據(jù)結(jié)構(gòu)也各不相同，也就導(dǎo)致了物聯(lián)網(wǎng)中數(shù)據(jù)的多態(tài)和異構(gòu).

根據(jù)RFID系統(tǒng)中數(shù)據(jù)的以上特點(diǎn)，需要針對(duì)該類數(shù)據(jù)的特點(diǎn)選取合適的數(shù)據(jù)加密方法.

1.2 RFID 系統(tǒng)中的數(shù)據(jù)加密機(jī)制作為數(shù)據(jù)保護(hù)的核心技術(shù)，數(shù)據(jù)加密可保障數(shù)據(jù)機(jī)密性、完整性、認(rèn)證性、不可抵賴性以及可用性[10]. 因此，物聯(lián)網(wǎng)下的數(shù)據(jù)加密機(jī)制成為了物聯(lián)網(wǎng)安全的重要研究內(nèi)容之一. 在當(dāng)前RFID系統(tǒng)的數(shù)據(jù)加密機(jī)制的研究領(lǐng)域，根據(jù)算法的安全性和實(shí)現(xiàn)復(fù)雜度分為輕量級(jí)加密算法、中量級(jí)加密算法和重量級(jí)加密算法[11]. RFID系統(tǒng)中主要的輕量級(jí)數(shù)據(jù)加密方法有：基于簡單異或等邏輯運(yùn)算的輕量級(jí)互認(rèn)證協(xié)議(Lightweight Mutual Authentication Protocol,LMAP)[12]、DESL 算法[1]、A2U2算法[2]和 Present-80算法[13]等；中量級(jí)數(shù)據(jù)加密方法有：基于散列(Hash)函數(shù)的Hash-lock加密算法[4]、隨機(jī)Hashlock加密算法[14]等；重量級(jí)數(shù)據(jù)數(shù)據(jù)加密方法有：基于公鑰加密的RSA[15]、橢圓曲線密碼體制[16]和超橢圓曲線密碼體制 (Hyperelliptic Curve Cryptography, HECC)[17]等. 輕量級(jí)加密算法計(jì)算量相對(duì)較少，對(duì)硬件資源要求低，但相應(yīng)的安全性不高. 重量級(jí)加密算法安全性高，但對(duì)于硬件資源極端受限的情況下不適用，其中橢圓曲線加密體制與其他公鑰密碼體制相比密鑰短、加密強(qiáng)度高，占用存儲(chǔ)資源少，其輕量化能夠?qū)崿F(xiàn)硬件資源受限和安全性之間很好的平衡，因此許多學(xué)者致力于輕量化ECC以適應(yīng)于RFID系統(tǒng)的電子標(biāo)簽數(shù)據(jù)加密.

2 橢圓曲線密碼體制概述

2.1 橢 圓 曲 線 的 定 義橢 圓 曲 線 加 密 體 制 由Kobilitz和Miller[16]提出. 橢圓曲線是指由韋爾斯特拉(Weierstrass)方程

所確定的平面曲線，通常用E表示，表示虧格為1的代數(shù)曲線. 其中a、b、c、d和e屬于域F，F(xiàn)可以是有理數(shù)域、復(fù)數(shù)域或有限域F(p). 橢圓曲線是其上所有點(diǎn)(x，y)的集合，再加一個(gè)無窮遠(yuǎn)點(diǎn)O. 無窮遠(yuǎn)點(diǎn)是指橢圓曲線上一個(gè)特殊的點(diǎn)，為仿射平面無窮遠(yuǎn)處的點(diǎn).

2.2 有限域F(p)上的橢圓曲線用于密碼學(xué)的橢圓曲線分為以素?cái)?shù)為模的整數(shù)域F(p)(適合于軟件實(shí)現(xiàn))和特征為2的伽羅華域F(2m)(適合于硬件實(shí)現(xiàn))兩大類. 本文主要研究有限域F(p)上的曲線，這類橢圓曲線最簡單的表示式為

其中，p為一個(gè)大素?cái)?shù)，a、b、x和y均在有限域F(p)中，即從{0, 1, ·· · ,p?1}上取值，且滿足 4a3+27b2(modp)≠0，這類橢圓曲線通常用Ep(a,b)表示. 該橢圓曲線上只有有限個(gè)離散點(diǎn)，設(shè)為N個(gè)，則N稱為橢圓曲線的階，N越大，安全性越高.

設(shè)點(diǎn)P=(x1,y1)和點(diǎn)Q=(x2,y2)在F(p)的橢圓曲線上. 另外，設(shè)O為無窮遠(yuǎn)處的點(diǎn).

橢圓曲線（Elliptic Curve，EC）的加法運(yùn)算規(guī)則如下：

對(duì)于給定點(diǎn)P和Q，如果x1=x2y2=?y1，則

一般情況下，R=Q+P，其中R=(x3,y3)的結(jié)果定義如下：

2.3 橢圓曲線離散對(duì)數(shù)問題橢圓曲線加密體制的安全性基于橢圓曲線上離散對(duì)數(shù)問題的難度，目前還不存在多項(xiàng)式時(shí)間算法求解橢圓曲線上的離散對(duì)數(shù)問題[18]. 其中Q為P的倍點(diǎn)，則存在正整數(shù)k，由k和P容易計(jì)算Q. 由P、Q求k稱為橢圓曲線上的離散對(duì)數(shù)問題 (Ecliptic Curve Discrete Logarithm Problem，ECDLP).

3 橢圓曲線加密算法的輕量化

3.1 橢圓曲線上的標(biāo)量乘橢圓曲線密碼體制中最核心的問題是在給定大整數(shù)k以及點(diǎn)P∈E后有效地計(jì)算出kP，即

該運(yùn)算稱為標(biāo)量乘，其中k稱為標(biāo)量. 標(biāo)量乘的計(jì)算主要由點(diǎn)加與倍點(diǎn)兩部分組成，是ECC的主要運(yùn)算之一，占用的執(zhí)行時(shí)間最多，因此決定了橢圓曲線密碼體制的效率. 因此本文提出對(duì)標(biāo)量乘運(yùn)算進(jìn)行優(yōu)化來實(shí)現(xiàn)橢圓曲線加密算法的輕量化.

3.2 提出的 PECC-NAF 并行標(biāo)量乘計(jì)算方法

3.2.1 二進(jìn)制方法 二進(jìn)制方法是計(jì)算ECC標(biāo)量乘的傳統(tǒng)算法，基于點(diǎn)運(yùn)算，即點(diǎn)加和點(diǎn)乘運(yùn)算，是一種用于求冪運(yùn)算的加法表示. 設(shè)F(p)是有限域，橢圓曲線Ep(a,b)的基點(diǎn)為P，P的階為n，標(biāo)量k隨機(jī)地從區(qū)間 [1, 2, ··· ,n?1]選取，k的二進(jìn)制表示為 (kn?1, ··· ,k2,k1,k0)2,ki∈{0, 1}，則

算法1具體步驟如下：

步驟 1將結(jié)果集Q置為0.

步驟 2從右到左掃描每一位二進(jìn)制位ki，當(dāng)ki=1時(shí)執(zhí)行一次點(diǎn)加操作Q=Q+P，并將計(jì)算結(jié)果存入結(jié)果集中.

步驟 3執(zhí)行一次點(diǎn)乘操作P=2P. 返回步驟2，直至所有二進(jìn)制位掃描結(jié)束.

步驟 4返回結(jié)果集Q.

對(duì)于標(biāo)量k，二進(jìn)制算法需要執(zhí)行l(wèi)?1次倍點(diǎn)運(yùn)算和h?1次點(diǎn)加運(yùn)算，其中h是k的二進(jìn)制表示中漢明重量(即非零比特的個(gè)數(shù))，因此標(biāo)量乘的運(yùn)算量取決于標(biāo)量k二進(jìn)制表示的長度l和漢明重量h. 因?yàn)殚L度為l位的標(biāo)量k的平均漢明重量期望值是l/2，所以，算法1的計(jì)算量可以近似表示為(l?1)/2A+(l?1)D，其中D表示倍點(diǎn)運(yùn)算，A表示點(diǎn)加運(yùn)算[19]. 圖1給出了標(biāo)量k為119時(shí)的二進(jìn)制標(biāo)量乘kP的計(jì)算過程.

圖 1 二進(jìn)制標(biāo)量乘計(jì)算過程Fig. 1 The calculation process of Binary scalar

3.2.2 高效的非鄰接形式方法 從二進(jìn)制算法可以看到，標(biāo)量乘kP運(yùn)算中標(biāo)量k的二進(jìn)制表示長度以及其非零元的個(gè)數(shù)(即漢明重量)決定了該運(yùn)算的計(jì)算效率. 為了減少運(yùn)算量，提高運(yùn)算效率，可以通過構(gòu)建原二進(jìn)制表示的等價(jià)序列表示，目的是縮短標(biāo)量原二進(jìn)制表示中的長度或減少原二進(jìn)制表示中漢明重量. 根據(jù)這一思想，提出了一種稀疏的使用帶符號(hào)數(shù)位集的表示即非鄰接形式(Non-Adjacent Form, NAF)[19]的高效計(jì)算方法.

一個(gè)正整數(shù)k的NAF表達(dá)式為其中ki∈{?1, 0, 1}，kl?1≠0，并且沒有兩個(gè)連續(xù)的數(shù)字ki是非零的，也就是說若ki=0，則ki+1≠0；若ki≠0，則ki+1=0，其中NAF的長度是l. 整數(shù)k的非鄰接形式記作NAF(k). 算法2具體步驟如下：

步驟 1將結(jié)果集Q置為0.

步驟 2從左到右掃描每一位ki，執(zhí)行倍乘運(yùn)算Q=2Q.

步驟 3當(dāng)ki=1時(shí)執(zhí)行一次點(diǎn)加操作Q=Q+P，并將計(jì)算結(jié)果存入結(jié)果集中. 當(dāng)ki=?1時(shí)執(zhí)行一次點(diǎn)減操作Q=Q?P，并將計(jì)算結(jié)果存入結(jié)果集中. 返回步驟2，直至所有位掃描結(jié)束.

步驟 4返回結(jié)果集Q.

在以上算法運(yùn)算過程中，有l(wèi)?1次倍點(diǎn)運(yùn)算和平均(l?1)/3次點(diǎn)加運(yùn)算. 因此算法2的運(yùn)算量可以表示為 (l?1)/3A+(l?1)D[19]. 圖 2 給出了標(biāo)量k為119時(shí)的NAF標(biāo)量乘kP的計(jì)算過程.

圖 2 NAF 標(biāo)量乘計(jì)算過程Fig. 2 The calculation process of NAF scalar multiplication

3.2.3 PECC-NAF 并行標(biāo)量乘算法 為了進(jìn)一步減少標(biāo)量乘法的執(zhí)行時(shí)間，本文在基于NAF標(biāo)量乘算法的基礎(chǔ)上，提出了一種并行計(jì)算ECC標(biāo)量乘法的方法 (Parallel ECC-NAF，PECC-NAF)來實(shí)現(xiàn)加密. 算法3具體步驟如下：

步驟 1執(zhí)行倍乘運(yùn)算.

（1） 將結(jié)果集R置為P.

（2） 從右到左掃描每一位ki，每次循環(huán)均執(zhí)行倍乘運(yùn)算R=2R，并將結(jié)果集R存入共享數(shù)組Ai.

步驟 2轉(zhuǎn)換標(biāo)量表示為NAF(k)，再執(zhí)行點(diǎn)加運(yùn)算.

（1） 執(zhí)行 NAF 標(biāo)量轉(zhuǎn)換.

（2） 從右到左掃描每一位ki，并從共享數(shù)組中Ai中取出當(dāng)前倍乘運(yùn)算結(jié)果存入臨時(shí)數(shù)組T中. 取出當(dāng)前位的值ki存入臨時(shí)變量m中.

（3） 判斷當(dāng)前位m的值，當(dāng)m=1時(shí)執(zhí)行一次點(diǎn)加操作Q=Q+T，并將計(jì)算結(jié)果存入結(jié)果集中. 當(dāng)m=?1時(shí)執(zhí)行一次點(diǎn)減操作Q=Q?T，并將計(jì)算結(jié)果存入結(jié)果集中. 返回步驟2，直至所有位掃描結(jié)束.

（4） 返回結(jié)果集Q.

在以上算法運(yùn)算過程中，有l(wèi)?1次倍點(diǎn)運(yùn)算和平均(l?1)/3次點(diǎn)加運(yùn)算，點(diǎn)加運(yùn)算次數(shù)明顯小于倍點(diǎn)運(yùn)算次數(shù). 由于并行執(zhí)行點(diǎn)加和倍點(diǎn)運(yùn)算，因此標(biāo)量乘的計(jì)算時(shí)間取決于(l?1)次倍點(diǎn)運(yùn)算. 與算法1和算法2對(duì)比，運(yùn)算效率有明顯的改善和提升. 圖3給出了標(biāo)量k為119時(shí)的PECC-NAF標(biāo)量乘kP的計(jì)算過程.

圖 3 PECC-NAF 標(biāo)量乘計(jì)算過程Fig. 3 The calculation process of PECC-NAF scalar multiplication

從圖1和圖2對(duì)比可以看出，二進(jìn)制標(biāo)量乘每一次點(diǎn)加操作都要等待倍點(diǎn)運(yùn)算的結(jié)果與上一次結(jié)果相加，其中倍點(diǎn)運(yùn)算較點(diǎn)加操作更復(fù)雜，因此點(diǎn)加操作會(huì)產(chǎn)生較長的等待時(shí)間. 而NAF標(biāo)量乘用NAF表示標(biāo)量，降低了標(biāo)量的漢明重量，從而減少了點(diǎn)加操作的次數(shù)，但點(diǎn)加操作仍然需要等待倍點(diǎn)運(yùn)算；從圖3可以看出，PECC-NAF標(biāo)量乘運(yùn)算，在NAF標(biāo)量乘基礎(chǔ)上將運(yùn)算量更大的倍點(diǎn)運(yùn)算與點(diǎn)加運(yùn)算并行執(zhí)行，改變了原算法的執(zhí)行過程. 改進(jìn)算法的點(diǎn)加操作不再需要在每一步都等待倍點(diǎn)運(yùn)算結(jié)果，只需在非零位將點(diǎn)加和倍點(diǎn)運(yùn)算的結(jié)果相加，提高了算法的執(zhí)行效率. 改進(jìn)算法利用了并行化思想，將點(diǎn)加和倍點(diǎn)運(yùn)算并行執(zhí)行，雖然不能實(shí)現(xiàn)兩種運(yùn)算完全互不影響，但倍點(diǎn)運(yùn)算可以看做是完全獨(dú)立的進(jìn)程，極大地減少了點(diǎn)加運(yùn)算的等待時(shí)間，因此認(rèn)為該算法改進(jìn)方案是可取的.

該并行算法策略是在基于NAF算法基礎(chǔ)上，將標(biāo)量乘中倍乘和點(diǎn)加操作并行化. 采用任務(wù)分解策略，將NAF標(biāo)量乘法算法分解為兩部分進(jìn)行并行計(jì)算.

第1部分由進(jìn)程1處理，進(jìn)程1計(jì)算l?1次倍乘操作，并將結(jié)果保存到共享數(shù)組A中. 可以看出，{?1, 0, 1}和倍乘操作之間沒有依賴關(guān)系. 進(jìn)程 1 必須根據(jù)密鑰l?1的長度執(zhí)行倍乘操作. 在本方案中，如果密鑰大小為160 bit，則進(jìn)程1必須執(zhí)行重復(fù)操作159次. 此外，進(jìn)程1必須保存共享數(shù)組A中的點(diǎn)乘結(jié)果，數(shù)組A的大小與n的大小相同.

進(jìn)程2中要做兩步操作. 首先求出NAF表示，然后執(zhí)行加法操作. 加法操作的次數(shù)等于密鑰的漢明重量. 進(jìn)程2必須在執(zhí)行加法操作之前得到NAF表示. 根據(jù)NAF表示中的位(1或?1)的類型，執(zhí)行加法或減法操作.

如果NAF表示中的位是‘1’，進(jìn)程2執(zhí)行加法運(yùn)算并將結(jié)果保存在累加器Q中；如果位是‘?1’，執(zhí)行減法運(yùn)算并將結(jié)果保存在Q中；如果位是‘0’，進(jìn)程2不執(zhí)行任何運(yùn)算.

進(jìn)程2通過讀取共享數(shù)組A中保存的點(diǎn)(2P、4P、…、2n?1P)來執(zhí)行加減操作，兩個(gè)進(jìn)程都能夠訪問位于共享內(nèi)存中的共享數(shù)組A. 進(jìn)程1在數(shù)組A中執(zhí)行寫操作，而進(jìn)程2在數(shù)組A中執(zhí)行讀操作.

對(duì)共享數(shù)組的訪問需要謹(jǐn)慎處理. 進(jìn)程1應(yīng)該只允許寫入，而進(jìn)程2應(yīng)該只允許讀出. 共享數(shù)組A的讀寫方式為：進(jìn)程1在開始執(zhí)行第i+1次倍點(diǎn)操作時(shí)為A[i]添加同步鎖，在寫入結(jié)果之后釋放同步鎖，能夠保證進(jìn)程2在讀取A[i]時(shí)的數(shù)據(jù)一致性.

4 算法實(shí)驗(yàn)結(jié)果及分析

本文將提出的PECC-NAF標(biāo)量乘法從算法運(yùn)行效率、內(nèi)存開銷和密鑰長度3個(gè)維度與二進(jìn)制標(biāo)量乘法和NAF標(biāo)量乘法進(jìn)行比較，綜合比較證明PECC-NAF標(biāo)量乘法的可行性.

圖4中給出了算法的執(zhí)行過程，3種算法的執(zhí)行過程相同，其中標(biāo)量轉(zhuǎn)換和標(biāo)量乘步驟的核心算法各有差異，這決定了3種算法不同的運(yùn)行效率和內(nèi)存開銷. 并將基于PECC-NAF標(biāo)量乘的橢圓曲線加密算法與現(xiàn)有的其他能夠應(yīng)用到RFID標(biāo)簽的加密算法進(jìn)行安全性比較，更加全面地證明本文改進(jìn)算法的可行性.

4.1 算法運(yùn)行效率分析實(shí)驗(yàn)選擇比特幣采用的secp256k1標(biāo)準(zhǔn)定義的橢圓曲線，使用IDEA編程工具和JAVA編寫了順序代碼和并行代碼. 在具體的實(shí)現(xiàn)過程中使用隨機(jī)生成的一個(gè)大整數(shù)作為密鑰，在并行和順序形式中密鑰的每個(gè)二進(jìn)制位用來確定加法和減法操作的數(shù)目. 根據(jù)一個(gè)隨機(jī)密鑰生成執(zhí)行標(biāo)量乘法，對(duì)于每類不同大小的密鑰，在并行和串行形式中都采用相同的密鑰執(zhí)行標(biāo)量乘法的計(jì)算. 非零位數(shù)在計(jì)算ECC標(biāo)量乘法中的作用非常關(guān)鍵，由于使用了NAF表示，密鑰中的非零位的平均數(shù)量約為50%或者更少，因此能夠有效提高運(yùn)算速度.

在實(shí)現(xiàn)過程中，測(cè)試了并行和串行兩種算法的兩種不同的密鑰大小：255、160 bit. 為兩種密鑰大小隨機(jī)生成一個(gè)大整數(shù)作為私鑰，將私鑰與基點(diǎn)相乘做標(biāo)量乘運(yùn)算. 分別測(cè)試了標(biāo)量乘運(yùn)算在二進(jìn)制算法、NAF算法下的串行和并行執(zhí)行情況(其中NAF算法的并行算法即為PECC-NAF算法)，對(duì)每種情況執(zhí)行10次，取平均執(zhí)行時(shí)間進(jìn)行比較. 表1給出了二進(jìn)制算法和NAF算法串行和并行形式各自的執(zhí)行時(shí)間.

圖 4 算法比較流程圖Fig. 4 Flow chart of different algorithms

表 1 二進(jìn)制算法與 NAF 算法串/并行速率比較Tab. 1 Comparison of serial/parallel rate between Binary algorithm and NAF algorithm

由實(shí)驗(yàn)結(jié)果可以看出，在算法的運(yùn)行效率上PECC-NAF算法要優(yōu)于傳統(tǒng)二進(jìn)制算法以及NAF算法本身. 這是因?yàn)樵谟?jì)算標(biāo)量乘運(yùn)算過程時(shí)，PECC-NAF算法將倍點(diǎn)運(yùn)算與點(diǎn)加運(yùn)算同時(shí)進(jìn)行，點(diǎn)加運(yùn)算不再需要每次等待倍點(diǎn)運(yùn)算結(jié)果，只需在標(biāo)量的NAF表示中遇到非零位時(shí)再取倍點(diǎn)運(yùn)算結(jié)果進(jìn)行計(jì)算，因此極大地提高了標(biāo)量乘的運(yùn)算效率.

同時(shí)，本文將PECC-NAF標(biāo)量乘算法與文獻(xiàn)[7]中提出的改進(jìn)標(biāo)量乘算法的運(yùn)行時(shí)間進(jìn)行比較. 通過Java編程，在程序中隨機(jī)生成5個(gè)整數(shù)和橢圓曲線上面的點(diǎn)P，計(jì)算kP所生成的時(shí)間，比較結(jié)果由表2給出.

表 2 兩種算法的運(yùn)算時(shí)間的比較 (單位：ms)Tab. 2 Comparison of operation time of two algorithms(unit: ms)

由表2可以看出，針對(duì)不同的標(biāo)量k，PECCNAF算法的運(yùn)算時(shí)間要比文獻(xiàn)[7]中的改進(jìn)算法更短. 這是因?yàn)槲墨I(xiàn)[7]中改進(jìn)算法是基于多基標(biāo)量乘，標(biāo)量轉(zhuǎn)換算法和標(biāo)量乘算法復(fù)雜度高. 本文提出的PECC-NAF算法與之相比，標(biāo)量轉(zhuǎn)換更為簡單，且利用并行化思想優(yōu)化了標(biāo)量乘計(jì)算過程，有效提高了算法計(jì)算效率.

4.2 算法內(nèi)存開銷分析在內(nèi)存開銷損失不大的前提下提高了標(biāo)量乘運(yùn)算的運(yùn)行效率，表3給出了二進(jìn)制算法和NAF算法串行和并行形式各自需要的內(nèi)存大小.

由表3可以看出，在算法內(nèi)存開銷上，改進(jìn)的算法與二進(jìn)制算法相比有較為明顯的提升，但與NAF算法相比，優(yōu)化并不明顯，有一定的內(nèi)存開銷損失，但相對(duì)于算法整體內(nèi)存開銷可以忽略不計(jì).綜合考慮算法運(yùn)行效率的提升以及算法內(nèi)存開銷，改進(jìn)的算法具有一定的應(yīng)用價(jià)值，對(duì)后續(xù)研究橢圓曲線密碼體制具有一定的啟示作用.

表 3 二進(jìn)制算法與 NAF 算法串/并行內(nèi)存開銷比較Tab. 3 Comparison of serial/parallel memory overhead between Binary algorithm and NAF algorithm

4.3 算法安全性分析改進(jìn)算法 PECC-NAF 主要是對(duì)標(biāo)量乘運(yùn)算運(yùn)行效率的影響，沒有改變橢圓曲線加密體制的加解密過程. 因此，將PECC-NAF算法運(yùn)用到橢圓曲線加密體制中代替原標(biāo)量乘運(yùn)算，能夠在提高算法運(yùn)行效率的同時(shí)，保證算法的安全性. 表4給出了在相同加密強(qiáng)度下，公鑰加密算法ECC和RSA 的安全性比較. 其中MI/S(Million Instruction Per Second)表示單字長定點(diǎn)指令平均執(zhí)行速度，每秒處理百萬級(jí)的機(jī)器語言指令數(shù). MI/S-年表示以每秒執(zhí)行100萬條指令的計(jì)算機(jī)運(yùn)行1年，一般認(rèn)為破譯時(shí)間為1012MI/S-年表示安全.

表 4 ECC、RSA 的安全性比較Tab. 4 Security comparison of ECC and RSA

由表4可以看出，在相同加密強(qiáng)度下，ECC密鑰長度始終比RSA密鑰長度短. 并且隨密鑰長度不斷增加，ECC的安全性比RSA增長更快.

表5比較了基于改進(jìn)標(biāo)量乘PECC-NAF算法的橢圓曲線加密算法與文獻(xiàn)[11]中的4種密碼體制的算法性能.

對(duì)表5的數(shù)據(jù)分析可知，ECC與其他密碼體制相比雖然具有高安全性，但由于其算法復(fù)雜度較高，算法執(zhí)行效率低. 本文通過改進(jìn)標(biāo)量乘來優(yōu)化ECC，在保證算法安全性的基礎(chǔ)上，降低運(yùn)算量，提高算法執(zhí)行效率.

表 5 ECC 與其他密碼體制算法性能比較Tab. 5 Comparison of performance between ECC and other encryption algorithms

5 結(jié)束語

RFID系統(tǒng)自身硬件資源非常受限，難以實(shí)現(xiàn)安全性強(qiáng)的公鑰加密算法. 要實(shí)現(xiàn)適用性和安全性的平衡，需要選擇合適的加密算法. 本文提出采用公鑰加密算法中的橢圓曲線密碼體制作為RFID系統(tǒng)的加密機(jī)制；與減少密鑰長度的橢圓曲線輕量化方案相比，本文在保證算法安全性的基礎(chǔ)上降低算法運(yùn)算量. 為了減少標(biāo)量乘法的執(zhí)行時(shí)間，提出了一種新方法即PECC-NAF并行執(zhí)行標(biāo)量乘運(yùn)算.PECC-NAF算法改變了傳統(tǒng)標(biāo)量乘算法的執(zhí)行過程，在二進(jìn)制標(biāo)量乘算法和NAF標(biāo)量乘算法基礎(chǔ)上進(jìn)行了顯著的過程優(yōu)化，計(jì)算速度更快，計(jì)算量更低，從而使得橢圓曲線加密體制整體上達(dá)到了安全、有效以及輕量化的要求. 下一步可以將該算法應(yīng)用到物聯(lián)網(wǎng)射頻識(shí)別認(rèn)證協(xié)議的設(shè)計(jì)中，繼續(xù)利用橢圓曲線加密體制的優(yōu)勢(shì)設(shè)計(jì)輕量級(jí)的認(rèn)證協(xié)議，使其既能保障RFID系統(tǒng)的安全性和隱私，也能適應(yīng)RFID系統(tǒng)資源極端受限的情況.