AVR單片機(jī)的RC5和RC6算法比較與改進(jìn)
摘要:RC5及RC6是兩種新型的分組密碼。AVR高速嵌入式單片機(jī)功能強(qiáng)大,在無線數(shù)據(jù)傳輸應(yīng)用方面很有優(yōu)勢。本文基于Atmega128高速嵌入式單片機(jī),實(shí)現(xiàn)RC5和RC6加密及解密算法,并對算法進(jìn)行匯編語言的優(yōu)化及改進(jìn)。根據(jù)實(shí)驗(yàn)結(jié)果。對兩種算法的優(yōu)熱點(diǎn)進(jìn)行比較和分析。 關(guān)鍵詞:Atmega128 RC5 RC6 分組密碼 混合密鑰 Flash 引言 在無線局域網(wǎng)中,傳輸?shù)慕橘|(zhì)主要是無線電波和紅外線,任何具有接收能力的竅聽者都有可能攔截?zé)o線信道中的數(shù)據(jù),掌握傳輸?shù)膬?nèi)容,造成數(shù)據(jù)泄密。因此,對于無線局域網(wǎng)來說,數(shù)據(jù)的加密是關(guān)鍵技術(shù)之一。 AVR高速嵌入式單片機(jī)是8位RISC MCU,執(zhí)行大多數(shù)指令只需一個(gè)時(shí)鐘周期,速度快(8MHz AVR的運(yùn)行速度約等于200MHz C51的運(yùn)行速度);32個(gè)通用寄存器直接與ALU相連,消除和運(yùn)算瓶頸。內(nèi)嵌可串行下載或自我編程的Flash和EPPROM,功能繁多,具有多種運(yùn)行模式。 依照IEEE1999年發(fā)布的802.11無線局域網(wǎng)協(xié)議標(biāo)準(zhǔn),采用Atmel公司的Atmega128高速嵌入式單片機(jī),開發(fā)無線數(shù)據(jù)傳輸裝置。為了實(shí)現(xiàn)無線數(shù)據(jù)傳輸時(shí)的安全性,同時(shí)盡可能節(jié)省成本,采用軟件進(jìn)行加密、解密。這就對算法的簡法性、高速性及適應(yīng)性提出了很高的要求。RC5和RC6兩種新型的分組加密算法能夠比較好地滿足上述的要求。 1 RC5及RC6算法 1.1 RC5及RC6的參數(shù) RC5及RC6是參數(shù)變量的分組算法,實(shí)際上是由三個(gè)參數(shù)確定的一個(gè)加密算法族。一個(gè)特定的RC5或者RC6可以表示為RC5-w/r/b或者RC6-w/r/b。其中這三個(gè)參數(shù)w、f和b分別按照表1所列定義。
1.2 RC5及RC6字運(yùn)算部件 RC5及RC6均由三部分組成,分別為混合密鑰生成過程、加密過程和解密過程。在這兩種算法中,共使用了六種基本運(yùn)算: ①模2w加法運(yùn)算,表示為“+”; ②模2w減法運(yùn)算,表示為“-”; ③逐位異或運(yùn)算,表示為+; ④循環(huán)左移,字a循環(huán)左移b比特表示為“a<<<b”; ⑤循環(huán)右移,字a循環(huán)右移b比特表示為“a>>>b”; ⑥模2w乘法,表示為“×”。 RC5算法運(yùn)用了上述的①~⑤運(yùn)算部分,RC6算法使用了上述所有的運(yùn)算部件。 1.3 RC5算法 (1)RC5算法混合密鑰生成過程的偽代碼表示 S[0]=Pw for i=1 to t-1 do S[i]=S[i-1]+Qw 輸入比特?cái)?shù)大小為8,密鑰長度為b的用戶密鑰K[0]至K[b-1] 轉(zhuǎn)換K[0]至K[b-1]為數(shù)組長度為c,比特?cái)?shù)為w的L[]數(shù)組 i=j=0 x=y=0 do 3×max(t,c)times: S[i]=(S[i]+x+y)<<<3;X=S[i];i=(i+1)mod t L[j]=(L[j]+x+y)<<<(x,y);X=L[j];j=(j+1)modC 其中c=[b×8/w]方括號(hào)表示上取整運(yùn)算,t=2r+2,當(dāng)w分別為16、32、64時(shí),常數(shù)Pw、Qw分別如表2所列。
(2)RC5加密算法過程的偽代碼表示 Input(A,B) A=A+S(0)B=B+S[1] for i=1 to r do A=((A+B)<<<B)+S[2i] B=((B+A)<<<A)+S[2i+1] Output(A,B) 其中初始的A、B分別為要加密的兩個(gè)比特?cái)?shù)為w的數(shù)據(jù),最終的A、B分別為加密好的兩個(gè)比特?cái)?shù)為w的數(shù)據(jù)。 (3)RC5解密算法過程的偽代碼表示 Input(A,B) for i=r down to 1 do B=((B-S[2i+1])>>>A)+A A=((A-S[2i])>>>B)+B A=A-S[0] B=B-S[1] Output (A,B) 其中初始A、B中的數(shù)據(jù)就是已經(jīng)加密了的比特?cái)?shù)為w的數(shù)據(jù),最終的A、B中的數(shù)據(jù)為解密后的比特?cái)?shù)為w的數(shù)據(jù)。 1.4 RC6算法 (1)RC6算法混合密鑰生成過程偽代碼表示 RC6混合密鑰生成過程與RC5相同,只是t的取值為2r+4。 (2)RC6加密算法過程偽代碼表示 Input(A,B,C,D) B=B+S[0]D=D+S[1] for i=1 to r do t=(B×(2B+1))<<<log2w u=(D×(2D+1))<<<1og2w A=((A+t)<<<t)+S[2i] C=((C+u)<<<u)+S[2i+1] (A,B,C,D)=(B,C,D,A) A=A+S[2i+2]C=C+S[2i+3] Output(A,B,C,D) 其中初始的A、B、C、D分別為要加密的四個(gè)比特?cái)?shù)為w的數(shù)據(jù),最終的A、B、C、D分別為加密好的四個(gè)比特?cái)?shù)為w的數(shù)據(jù)。 (3)RC6解密算法過程的偽代碼表示 Input(A,B,C,D) C=C-S[2i+3]A=A-S[2i+2] for i=1 to r do (A,B,C,D)=(D,A,B,C) u=(D×(2D+1))<<<log2w t=(B×(2B+1))<<<log2w C=((C-S[2(r-i)+3])>>>t)+u A=((A-S[2(r-i)+2])>>>u)+t D=D-S[1] B=B-S[0] Output(A,B,C,D) 其中初始的A、B、C、D分別為已經(jīng)被加密的四個(gè)比特?cái)?shù)為w的數(shù)據(jù),最終的A、B、C、D分別為解密后的四個(gè)比特?cái)?shù)為w的數(shù)據(jù)。 2 RC5和RC6算法的實(shí)現(xiàn)及改進(jìn) 2.1 AVR單片機(jī)的RC5和RC6算法流程 RC5及RC6算法加密過程實(shí)現(xiàn)流程圖如圖1所示,解密過程實(shí)現(xiàn)流程圖如圖2所示,總體過程流程圖如圖3所示。 2.2 AVR單片機(jī)RC5和RC6算法的改進(jìn) ①在進(jìn)行算法流程的安排時(shí),考慮到AVR高速嵌入式單片機(jī)只有32個(gè)8位寄存器,為了節(jié)省寄存器的使用,應(yīng)該在混合密鑰生成過程執(zhí)行后,再把待加密的數(shù)據(jù)賦予寄存器。這樣在混合密鑰生成過程以前的寄存器都可以被使用,而不會(huì)對整個(gè)算法的執(zhí)行結(jié)果造成影響。 ②在進(jìn)行RC5及RC6算法參數(shù)的選擇時(shí),考慮到AVR高速嵌入式單片機(jī)指令最多只支持16位數(shù)據(jù)相加以及程序的簡潔化,所以在本程序中選擇w為16而沒有選擇w為32,r和b的值依據(jù)Rivest的建議分別取為12和16。 ③在執(zhí)行算法中的左循環(huán)或者右循環(huán)運(yùn)算時(shí),考慮到循環(huán)移位的效果,實(shí)際循環(huán)移位的位數(shù)應(yīng)該為要執(zhí)行移位次數(shù)的低1log2w位。在本程序中為要執(zhí)行移位次數(shù)的后四位。 ④在執(zhí)行算法中的模2w加法運(yùn)算、模2w減法運(yùn)算、模2w乘法運(yùn)算時(shí),由于2w的取值為65536,而2個(gè)8位寄存器(0~15位)最高可以表示數(shù)據(jù)的值為65535,數(shù)據(jù)再大就要向高位進(jìn)位,所以在本程序執(zhí)行上述的算法只需要考慮到2個(gè)8位寄存器所表達(dá)的值就得到了上述運(yùn)算的最終結(jié)果,而不用再進(jìn)行模2w運(yùn)算。 ⑤為了提高數(shù)據(jù)加密及解密的速率,可以把混合密鑰生成過程提前執(zhí)行,以使之生成一張混合密鑰表。把這個(gè)表裝入發(fā)送數(shù)據(jù)端Atmega128高速嵌入式單片機(jī)和接收數(shù)據(jù)端Atmega128高速嵌入式單片機(jī)的Flash中,從而在以后的加密與解密過程中直接使用混合密鑰。值得注意的是,每當(dāng)用戶輸入的用戶密鑰發(fā)生改變時(shí),必須重新執(zhí)行混合密鑰生成過程,并且重新給Flash裝載重新生成后的混合密鑰表。在本程序中,RC5混合密鑰表共占據(jù)52個(gè)8位寄存單元,RC6混合密鑰表共占據(jù)56個(gè)8位存儲(chǔ)單元。 ⑥在本程序中運(yùn)用加法運(yùn)算以及移位運(yùn)算實(shí)現(xiàn)了16位二進(jìn)制數(shù)乘以16位二進(jìn)制數(shù)的無符號(hào)運(yùn)算。該運(yùn)算的子程序如下: chengfa:clr result2 clr result3 ldi count1,16 lsr chengshu1 ror chengshu0 chengfa0: brcc chengfa1 add result2,beichengshu0 adc result3,beichengshu1 chengfa1: ror result3 ror result2 ror result1 ror result0 dec count1 brne chengfa0 ret 3 RC5及RC6算法實(shí)驗(yàn)結(jié)果及其比較與分析 RC5及RC6算法實(shí)驗(yàn)的混合密鑰過程、加密過程、解密過程和總體過程的效果比較如表3、4、5、6所列。
表4 RC5及RC6算法加密過程效果比較
表5 RC5及RC6算法解密過程效果比較
表6 RC5及RC6算法總體過程效果比較
由表3可以發(fā)現(xiàn),RC6算法和RC5算法在混合密鑰生成時(shí)程序的大小相同,但量RC6算法卻比RC5算法省時(shí)。這是因?yàn)楦鶕?jù)混合密鑰生在方法在執(zhí)行循環(huán),最終生成混合密鑰時(shí)要執(zhí)行比較操作。當(dāng)超出了比較范圍t時(shí),要對指針地址重新復(fù)位。RC6算法t的取值大于RC5算法中t的取值,因此RC6算法執(zhí)行了較少的復(fù)位操作。從而節(jié)省了運(yùn)行周期,故RC6算法比RC5算法在生成混合密鑰時(shí)省時(shí)。 以上所有實(shí)驗(yàn)結(jié)果均是在AVR Studio4.07仿真軟件上選用Atmel公司的Atmega128高速嵌入式單片機(jī)為實(shí)驗(yàn)設(shè)備平臺(tái)。選取參數(shù)w=16、r=12、b=16,并根據(jù)計(jì)算公式求得c=8,t=26(RC5算法)或者t=28(RC6算法)在12MHz運(yùn)行速度下模擬所得。 從實(shí)驗(yàn)結(jié)果所得的表3、表4、表5、表6可以明確得出以下結(jié)論。 ①從程序的執(zhí)行效率來看,無論在加密還是在解密過程中,RC5算法都要比RC6算法執(zhí)行效率高。 因此,在一些非常注重程序執(zhí)行效率,而對數(shù)據(jù)安全性要求不是非常高的情況下,應(yīng)該采用RC5算法。 ②從程序的執(zhí)行時(shí)間來看,無論在加密過程不是在解密過程中,RC5算法都要比RC6算法省時(shí)。因此,在一些對程序執(zhí)行時(shí)間長短要求很高,對數(shù)據(jù)安全性要求不是非常高的情況下,可以采用RC5算法。 ③從程序的大小來看,無論在加密過程中還是在解密過程中,RC5算法都要比RC6算法更簡潔。因此,在一些對程序所用空間大小要求很高,對數(shù)據(jù)安全性要求不是非常高的情況下,可以采用RC5算法。 ④從安全性角度考慮,RC6算法是在RC5算法基礎(chǔ)之上針對RC5算法中的漏洞,主要是循環(huán)移位的位移量并不取決于要移動(dòng)次數(shù)的所有比特,通過采用引入乘法運(yùn)算來決定循環(huán)移位次數(shù)的方法,對RC5算法進(jìn)行了改進(jìn),從而大大提高了RC6算法的安全性。因此,在一些對數(shù)據(jù)安全性要求很高的情況下,應(yīng)該采用RC6算法。 結(jié)語 RC5及RC6算法是兩種新型的分組密碼,它們都具有可變的字長,可變的加密輪數(shù),可變的密鑰長度;同時(shí),它們又只使用了常見的初等運(yùn)算操作,這使它們有很好的適應(yīng)性,很高的運(yùn)算速度,并且非常適合于硬件和軟件實(shí)現(xiàn)。兩種算法各有其優(yōu)缺點(diǎn),在工程應(yīng)用中應(yīng)該根據(jù)實(shí)際需要選擇最適合的方法,以得到最優(yōu)的效果。 |