幾種輕量級加密算法的比較研究

路安平等

摘 要： 隨著無線射頻識別（RFID）技術在各個應用領域的迅猛發(fā)展，輕量級（lightweight）加密算法日益受到人們的關注。在RFID中硬件資源是極端受限制的，為了在算法加密性能與硬件資源開銷間得到一個好的權衡，把橢圓曲線加密算法（ECC）與流密碼加密算法中RC4算法，分組加密算法中的PRESENT算法，進行分析比較。并選取Atmega?32微處理器在AVR Studio仿真平臺上進行分析比較。實驗獲得了這三種算法在算法運行效率、密碼安全強度和硬件資源開銷間的比較結果。得出，在硬件資源同樣極端受限的環(huán)境下，ECC所表現(xiàn)出的運行效率和密碼安全強度是其他兩種算法所不能比擬的，證明了非對稱加密算法也可以做到輕量化。

關鍵詞： 輕量級加密； RFID； 橢圓曲線加密； 流密碼； PRESENT加密算法

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2014）12?0037?05

Abstract： With the rapid development of radio frequency identification （RFID） technology， the lightweight encryption algorithm attracts increasing attention. In RFID system， the hardware resources are extremely limited. In order to get a better trade?off between the algorithm's encryption performance and the hardware resource requirements， the elliptic curve cryptography（ECC）is compared with RC4 algorithm in the stream cipher algorithm and PRESENT algorithm in the grouping encryption algorithm. Through the Atmega?32 microprocessor in the AVR Studio simulation platform， the comparison results between the three algorithms′ efficiency and the hardware requirements are obtained. The ECC algorithm ， under the condition of the same restricted hardware resources， is better in the operation efficiency and the password security than the other two algorithms. It proves that the non?symmetric encryption algorithm can also be lightweight.

Key words： lightweight encryption； RFID； ECC； stream cipher； PRESENT encryption algorithm

0 引 言

無線識別射頻技術（RFID）具有非接觸掃描，體積小型化，抗污染能力強，可重復使用，穿透性強，識別距離遠等優(yōu)點，在物流監(jiān)管，門禁系統(tǒng)，電子自動收費等領域得到了迅猛地發(fā)展[1]。它的信息安全問題也越來越受到人們的關注[2]。以往經(jīng)典的加密算法如高級加密標準（AES），側重的是提供高級別加密性能，而沒有過多的考慮硬件資源開銷問題[3]。顯然，在RFID這種硬件資源極端受限的環(huán)境下，采用高性能的加密算法是不明智的選擇。

輕量級（lightweight）加密算法在密鑰長度，加密輪數(shù)等方面作了改進，使之對處理器計算能力的要求和對硬件資源的開銷均有不同程度上的降低，卻足以提供所要求的加密性能[4]。在很多RFID低成本無源電子標簽（如RFID門票）中，所進行的加密算法只是為了換取一個時間代價，即只要能夠保證標簽內的信息在所要求的一個時間段內安全即可。

流密碼中的RC4算法和分組密碼中的PRESENT算法，都屬于對稱加密算法即加密和解密使用相同的密鑰，故能較容易做到算法的輕量化，而橢圓曲線加密算法是不對稱加密算法[5?7]。本文利用ATmaga?32單片機在AVR Studio.4仿真平臺上，對這三種算法的運行效率和密碼破譯時間進行分析比較。得出在硬件資源同樣極端受限的環(huán)境下，橢圓曲線加密算法的運行效率要高于另外兩種，所生成的密碼最難被破譯，證明了非對稱加密算法同樣可以做到輕量化。

1 算法介紹

1.1 橢圓曲線加密算法

1.1.1 橢圓曲線概述

橢圓曲線加密算法屬于公開密鑰加密算法，加密和解密使用不同的密鑰。橢圓曲線定義：橢圓曲線是指在射影平面上滿足Weierstrass方程的一條光滑曲線和一個無窮遠點0∞的集合[8]。本文所選取的這條光滑曲線可以表示為E：Y2=X3+aX+b，此時方程的特征值為大于3的素數(shù)。點加運算是橢圓曲線上一條很重要的運算規(guī)則，具體規(guī)則如下：任意選取橢圓曲線上兩點P，Q（若P，Q兩點重合，則做P點的切線）做直線交于橢圓曲線的另一點R′，過R′做y軸的平行線交于R，則有P+Q=R。圖1給出了橢圓曲線的加法運算法則。根據(jù)這個法則，可以知道橢圓曲線內無窮遠點0∞與曲線上任一點P有：0∞+P=P，故把無窮遠點0∞稱為零元。同時可以得出如下結論：如果橢圓曲線上的三個點A，B，C，處于同一條直線上，那么他們的和等于零元，即A+B+C=0∞。k個相同的點P相加，記作kP。如，P+P+P=2P+P=3P。

1.1.2 橢圓曲線加密流程

首先確定一個有限域Fp，這個域只有p（p為素數(shù)）個元素，在這取p=79。

（1） 用戶A在這個有限域中選定一條橢圓曲線Ep（a，b），并取橢圓曲線上一點，作為基點G。

（2） 用戶A在1～p-1之間隨機選擇一個素數(shù)作為私有密鑰k，并根據(jù)加法則，生成公開密鑰K=kG。

（3） 用戶A將Ep（a，b）和點K，G傳給用戶B。

（4） 用戶B接到信息后 ，將待傳輸?shù)拿魑木幋a到Ep（a，b）上一點M，并產(chǎn)生一個隨機整數(shù)r（r

（5） 用戶B計算點C1=M+rK；C2=rG。

（6） 用戶B將C1，C2傳給用戶A。

（7） 用戶A接到信息后，計算C1～kC2，結果就是點M，再對點M進行解碼就可以得到明文。在這個通信過程，偷窺者只能看到Ep（a，b），K，G，C1，C2，而通過K，G 求k或通過C2，G求r都是十分困難的。這正是橢圓曲線加密所基于的數(shù)學難題，因此偷窺者無法得到用戶A，B間傳送的明文信息。本文選用密鑰為79 b的橢圓曲線加密算法。圖2給出橢圓曲線算法的加解密流程。

1.2 流密碼加密算法

1.2.1 流密碼概述

流密碼（stream cipher）也稱為序列密碼，按位或字節(jié)對數(shù)據(jù)流進行處理，加密和解密使用相同的密鑰，是對稱密碼算法的一種。本文選取的是流密碼中的RC4算法。RC4算法是一個面向字節(jié)操作、密鑰長度可變的流密碼（stream cipher）。算法的基本原理可描述為：對于n位長的數(shù)據(jù)，有共N=2n個可能的內部置換狀態(tài)矢量S=S[0]，S[1]，…，S[N-1]，這些狀態(tài)是保密的。密鑰流K由S中的2n個元素按一定方式選出一個元素而生成，每生成一個密鑰值，S中的元素就重新置換一次，置換后的S自始至終都包含從0～N-1的所有n位比特數(shù)，這體現(xiàn)了“一次一密”的加密體制[9]。

1.2.2 流密碼加密流程

內部狀態(tài)矢量S的初始化： 把S中的元素按升序從0～N-1賦值，即S[0]=0，S[1]=1，S[N-1]=N-1。同時建立一個臨時矢量T，如果密鑰K的長度為N字節(jié)，則將K賦給T否則，若密鑰長度為keylen字節(jié)則將K的值賦給T的前keylen個元素，并循環(huán)重復用K的值賦給T剩下的元素，直到T的所有元素都被賦值。

用類C偽代碼可表示如下：

for i=0 to N?1 do

S[i]=i；

T[i]=K[i mod keylen]

j=0

for i=O to N?1 do

j=（j+s[i]+T[i]）mod N

swap（s[i]，s[j]）；

密鑰流的生成：矢量S一旦完成初始化，輸人密鑰就不再被使用。密鑰流的生成是從S[0]～S[N-1]，對每個S[i]，根據(jù)當前S的值，將S[i]與S中的另一字節(jié)置換。當S[N?1]完成置換后，再從S[0]開始繼續(xù)重復操作。用類C偽代碼可表示如下：

i，j=0

while（true）

i=（i+1）mod N

j=（j+S[i]）mod N

swap（sEi]，s[j]）

t=（sEi]+s[j]）mod N；

k=S[t]

加密時，將k的值與下一明文字節(jié)異或；解密時，將k的值與下一密文字節(jié)異或。

1.3 PRESENT算法

1.3.1 PRESENT算法概述

PRESENT是分組密碼，分組大小是64位，根據(jù)密鑰的大小可分為PRESENT?80和PRESENT?128兩種參數(shù)版本，密鑰長度分別為80位和128位，因此，在這里選用PRESENT?80。

1.3.2 PRESENT算法流程

圖3為PRESENT?80的算法流程圖。

PRESENT?80算法要經(jīng)過31輪加密，每一輪都經(jīng)過一個SP結構，每個SP結構都是由addRoundKey、sBoxLayer和pLayer三步操作組成[10]。addRoundKey操作是將PRESENT?80的分組數(shù)據(jù)與輪密鑰Ki按位進行異或操作；sBoxLayer是一個非線性置換操作，在PRESENT?80中由一個4位到4位的S盒（S?box）實現(xiàn)。表1給出了S?box的16進制表示；

pLayer操作是一個位變換操作，用于改變PRESENT當前分組數(shù)據(jù)的順序，把第i位變?yōu)榈赑（i）位，表2給出了pLayer具體操作。

密鑰調度：PRESENT?80的初始密鑰存放在一個80位的密鑰寄存器（Key Register）里，表示為K79K78…K0，然后取其高64位的值作為輪密鑰Ki=k63k62…k0 （1≤i≤32）。在第i輪加密中，輪密鑰Ki=k63k62…k0=K79K78…K16該輪加密完成后，密鑰寄存器更新，產(chǎn)生新的輪密鑰如此完成31輪的PRESENT?80加密。

2 實驗與分析

2.1 實驗設計和實現(xiàn)

在微處理器平臺的選擇上，希望微處理器既能夠適用于低功耗的RFID系統(tǒng)中，又能夠很好地對上述三種算法進行實現(xiàn)。ATmega32單片機是Atmel公司推出的一款高性能、低功耗AVR高檔微處理器。芯片內部集成了較大容量的存儲器和豐富強大的硬件接口電路，但由于采用了小引腳封裝（為DIP28和TQFP/MLF32），所以其價格相對比較便宜，非常適用于成本較低的RFID系統(tǒng)[11]。另外，ATmega32含有32 KB的內存容量，能夠完全滿足這三種加密算法的內存需要。所以可以把ATmega32單片機作為目標平臺。

開發(fā)工具選擇方面，仿真工具選用AVR Studio4，編譯工具選用Win AVR（GCC），并把后者添加前者內，這樣就可以在同一個界面下完成對算法編譯和仿真。為了數(shù)據(jù)的準確性，所有仿真都執(zhí)行多次，取其平均值。

2.2 算法性能評估與比較

本文從三個方面對這三種算法進行評估和比較：一是評估它們運行時的內存開銷，來比較它們各自對硬件資源的需求；二是評估執(zhí)行這三種算法所需要的機器周期，來比較這三種算法的運行效率；三是評估三種算法各自的密碼破譯時間，來比較它們的密碼安全強度。

2.2.1 內存開銷比較

算法的內存開銷，主要是指算法在完成一次加密和解密的過程中所需要的內存大小[12]。表3給出了這三種算法在完成一次加密和解密的過程中所需要的內存大小，單位為字節(jié)。為了更直觀的比較，在圖4中以三維柱狀圖的形式給出。

從表3可以看出，三種算法的代碼開銷都沒有超過總內存的[110]，佐證了這三種算法的輕量級性，而流密碼中的RC4算法的代碼開銷尤為突出，這與其密鑰短小有莫大的關系。RRESENT的代碼稍大，主要是因為算法過程中的位置換運算消耗內存大。

2.2.2 算法的運行效率

算法的運行效率，是指算法完成一次加密和解密所需要的機器周期，它反應了算法對能量的運用效率。在能量及其有限的RFID系統(tǒng)中，算法的運行效率顯得尤其的關鍵。在此我們把CPU工作頻率設定在8 MHz下，并且為了能夠完全覆蓋這三種算法，選取一個256位的測試向量進行。表4給出了這三種算法各自的執(zhí)行時間，單位是機器周期。

表4 算法的執(zhí)行時間

為了更直觀，圖5給出了三種算法完成一次加密和解密所需要的機器周期的比較。

可以明顯的看出，在算法的運行效率上橢圓曲線算法要優(yōu)于另外兩種算法，這與在仿真過程中，軟件只運行橢圓曲線加密算法的低計算開銷部分有關。而在運行RC4算法和PRESENT?80時，都要進行位置換和位賦值的操作，這在硬件上實現(xiàn)可能沒有任何性能開銷，所做的只是將電路的對應位置相連，但是在軟件上實現(xiàn)就顯得困難多。

2.2.3 算法安全強度比較

算法的破譯，稱為密碼分析，針對這三種加密算法選用各自最有效的密碼分析方法分別對其進行密碼分析，用破譯算法所耗時間和所占的空間，來衡量這三種算法的密碼安全強度。

橢圓曲線加密算法，加密和解密所用密鑰是不同的，對此采用密鑰窮盡搜索方式[13]。在一個有3 000臺計算機的網(wǎng)絡中進行密鑰窮盡搜索的計算，使用粗略的時間估算原理可以得出破解橢圓曲線密鑰需要幾小時到幾天的時間，盡管如此，這種加密強度對于低成本的RFID系統(tǒng)來說還是綽綽有余的，因為召集這樣多的人力和計算機資源來破解這種低成本的電子標簽是得不償失的。

流密碼中的RC4算法，是對稱加密算法中的一種，采用暴力攻擊方式對其進行破解[14]。暴力攻擊RC4算法，必須知道密文某幾個字節(jié)對應的明文，使之成為已知明文攻擊，知道明文后，通過逐一假設密鑰嘗試解密密文與已知明文進行比較，若解密結果與明文匹配，那么正確的密鑰就已經(jīng)找到。找到了加密密鑰，剩余的密文就可以完全解密。用暴力攻擊中的全查表法，破譯RC4算法所需空間為10 TB，所需時間幾乎為0。可以看出雖然RC4算法的代碼所占內存小但是安全性卻是比較低的。

對于分組密碼中的PRESENT算法，采用代數(shù)分析對其進行攻擊[15]。所謂代數(shù)分析就是將一個密碼算法的計算過程構造成一組代數(shù)方程，通過求解這組方程中的未知元來獲取該密碼算法中的密鑰信息。在PRESENT算法的代數(shù)分析中，所需的空間可以由單臺個人計算機提供，所需要的時間代價是幾天，這些時間代價主要用在求解方程組上。為了便于比較，表5給出這三種算法的破譯代價。

表5 算法破譯代價

盡管在衡量破譯時間上使用的是粗略估算時間原理，但這并不妨礙對這三種算法安全強度的分析，因為RFID系統(tǒng)本身成本就很低，在其中進行加密運算，很大程度上就是為了換取一個安全的時間代價。從表4可以看出：流密碼中的RC4算法是最好破譯的，這與它的算法簡單、密鑰短小、算法按位操作有關；橢圓曲線算法和PRESENT?80算法所換取的時間代價是相似的，但是在破譯所需空間上，橢圓曲線算法卻要比PRESENT?80算法大很多，可以這樣說，橢圓曲線加密算法的安全強度勝過PRESENT?80算法。

3 結 語

對于RFID這種硬件資源極端受限的系統(tǒng)中，就如何在算法的加密性能與硬件資源消耗之間取得一個最佳的權衡。本文選取了不對稱加密算法中的橢圓曲線加密算法，并選取對稱加密算法中RC4加密算法和PRESENT?80算法與之進行比較。對它們在微處理器平臺上進行仿真分析，并比較它們各自的內存消耗，運行效率和密碼破譯難度。從最后的實驗數(shù)據(jù)可以看出，運行這三種加密算法所耗用的內存都沒有超過微處理器內存的10%，證實了這三種算法都屬于輕量級的加密算法；在算法的運行效率上，橢圓曲線加密算法所需要的機器周期要比另外兩種算法少。

在加密強度上，橢圓曲線加密算法作為不對稱加密算法所表現(xiàn)出的密碼強度更是兩外兩種算法不能企及的。在硬件資源極端受限的環(huán)境下，橢圓曲線加密算法在內存開銷、運行效率和密碼的安全強度之間做到了較好的兼顧，不對稱加密算法同樣也可以做到算法的輕量化。

參考文獻

[1] XOLE P H， TURNER L H， HU Zhong?hao， et al. The next generation of RFID technology [C]// Proceedings of Unique Radio Innovation for the 21st Century： Building Scalable and Global RFID Networks. Berlin： [s.n.]， 2010， 3?24.

[2] 張忠，徐秋亮.物聯(lián)網(wǎng)環(huán)境下UC安全的組證明RFID協(xié)議[J].計算機學報，2011，34（7）：1188?1194.

[3] MOJTABA Alizadeh， WAN Haslina Hassan， MAZDAK Zamani， et al. Implementation and evaluation of lightweight encryption algorithms suitable for RFID [J]. Journal of Next Generation Information Technology， 2013， 01（4）： 65?77.

[4] FINKENZELLER K. Fundamentals and applications in iontactless smart card， radio frequency identification and near?field communication [M]. 3rd ed. Chichester： Wiley， 2010.

[5] KOBLIT Zneal. The stateof elliptic curve cryptography [J]. Designs Codes and Cryptography， 2000， 19： 173?193.

[6] COUTURE N， KENT K.B. The effectiveness of brute force attacks on RC4 [C]// Proceedings of Second Annual Conference on Communication Networks and Services Research. [S.l.]： [s.n.]， 2004： 333?336.

[7] BODGANOV A， KUNDSEN L R， LEANDER G， et al. PRESENT： an ultra?lightweight block cipher [C]// Workshop on Cryptographic Hardware and Embedded Systems. Berlin： [s.n.]， 2007： 450?466.

[8] 李俊芳，崔建雙.橢圓曲線加密算法及實例分析[J].網(wǎng)絡安全技術與應用，2004（11）：55?57.

[9] 黃道林，楊軍.RC4加密算法FPGA設計與實現(xiàn)[J].云南大學學報：自然科學版，2009，31（z1）：80?83.

[10] GUANG Gong. Lightweight cryptography for RFID systems [D]. Canana： University of Waterloo， 2010.

[11] 許鳴，黃健.面向嵌入式應用的加密算法開銷與性能分析[J].計算機工程與設計，2009（23）：5365?5368.

[12] 茅岑微.適用于RFID的幾種小型加密算法比較[J].射頻世界，2008（6）：21?24.

[13] CERTICOM. ECC challenge [EB/OL]. [2009?11?16]. http：//www.certicom.com /inde.

[14] MANTIN Itsik， SHAMIR Adi. A practical attack on broadcast RC4 [C]//Fast Software Encryption. Germany： Springer?verlag， 2002： 87?104.

[15] BIHAM Eli， DUNKELMAN Orr， KELLER Nathan. Linear cryptanalysis of reduced?round serpent [J]. Lecture Notes in Computer Science， 2002， 2355： 16?27.

[2] 張忠，徐秋亮.物聯(lián)網(wǎng)環(huán)境下UC安全的組證明RFID協(xié)議[J].計算機學報，2011，34（7）：1188?1194.

[3] MOJTABA Alizadeh， WAN Haslina Hassan， MAZDAK Zamani， et al. Implementation and evaluation of lightweight encryption algorithms suitable for RFID [J]. Journal of Next Generation Information Technology， 2013， 01（4）： 65?77.

[4] FINKENZELLER K. Fundamentals and applications in iontactless smart card， radio frequency identification and near?field communication [M]. 3rd ed. Chichester： Wiley， 2010.

[5] KOBLIT Zneal. The stateof elliptic curve cryptography [J]. Designs Codes and Cryptography， 2000， 19： 173?193.

[6] COUTURE N， KENT K.B. The effectiveness of brute force attacks on RC4 [C]// Proceedings of Second Annual Conference on Communication Networks and Services Research. [S.l.]： [s.n.]， 2004： 333?336.

[7] BODGANOV A， KUNDSEN L R， LEANDER G， et al. PRESENT： an ultra?lightweight block cipher [C]// Workshop on Cryptographic Hardware and Embedded Systems. Berlin： [s.n.]， 2007： 450?466.

[8] 李俊芳，崔建雙.橢圓曲線加密算法及實例分析[J].網(wǎng)絡安全技術與應用，2004（11）：55?57.

[9] 黃道林，楊軍.RC4加密算法FPGA設計與實現(xiàn)[J].云南大學學報：自然科學版，2009，31（z1）：80?83.

[10] GUANG Gong. Lightweight cryptography for RFID systems [D]. Canana： University of Waterloo， 2010.

[11] 許鳴，黃健.面向嵌入式應用的加密算法開銷與性能分析[J].計算機工程與設計，2009（23）：5365?5368.

[12] 茅岑微.適用于RFID的幾種小型加密算法比較[J].射頻世界，2008（6）：21?24.

[13] CERTICOM. ECC challenge [EB/OL]. [2009?11?16]. http：//www.certicom.com /inde.

[14] MANTIN Itsik， SHAMIR Adi. A practical attack on broadcast RC4 [C]//Fast Software Encryption. Germany： Springer?verlag， 2002： 87?104.

[15] BIHAM Eli， DUNKELMAN Orr， KELLER Nathan. Linear cryptanalysis of reduced?round serpent [J]. Lecture Notes in Computer Science， 2002， 2355： 16?27.

[2] 張忠，徐秋亮.物聯(lián)網(wǎng)環(huán)境下UC安全的組證明RFID協(xié)議[J].計算機學報，2011，34（7）：1188?1194.

[3] MOJTABA Alizadeh， WAN Haslina Hassan， MAZDAK Zamani， et al. Implementation and evaluation of lightweight encryption algorithms suitable for RFID [J]. Journal of Next Generation Information Technology， 2013， 01（4）： 65?77.

[4] FINKENZELLER K. Fundamentals and applications in iontactless smart card， radio frequency identification and near?field communication [M]. 3rd ed. Chichester： Wiley， 2010.

[5] KOBLIT Zneal. The stateof elliptic curve cryptography [J]. Designs Codes and Cryptography， 2000， 19： 173?193.

[6] COUTURE N， KENT K.B. The effectiveness of brute force attacks on RC4 [C]// Proceedings of Second Annual Conference on Communication Networks and Services Research. [S.l.]： [s.n.]， 2004： 333?336.

[7] BODGANOV A， KUNDSEN L R， LEANDER G， et al. PRESENT： an ultra?lightweight block cipher [C]// Workshop on Cryptographic Hardware and Embedded Systems. Berlin： [s.n.]， 2007： 450?466.

[8] 李俊芳，崔建雙.橢圓曲線加密算法及實例分析[J].網(wǎng)絡安全技術與應用，2004（11）：55?57.

[9] 黃道林，楊軍.RC4加密算法FPGA設計與實現(xiàn)[J].云南大學學報：自然科學版，2009，31（z1）：80?83.

[10] GUANG Gong. Lightweight cryptography for RFID systems [D]. Canana： University of Waterloo， 2010.

[11] 許鳴，黃健.面向嵌入式應用的加密算法開銷與性能分析[J].計算機工程與設計，2009（23）：5365?5368.

[12] 茅岑微.適用于RFID的幾種小型加密算法比較[J].射頻世界，2008（6）：21?24.

[13] CERTICOM. ECC challenge [EB/OL]. [2009?11?16]. http：//www.certicom.com /inde.

[14] MANTIN Itsik， SHAMIR Adi. A practical attack on broadcast RC4 [C]//Fast Software Encryption. Germany： Springer?verlag， 2002： 87?104.

[15] BIHAM Eli， DUNKELMAN Orr， KELLER Nathan. Linear cryptanalysis of reduced?round serpent [J]. Lecture Notes in Computer Science， 2002， 2355： 16?27.