AVR单片机的RC5和RC6算法比较与改进 - 软件编程/OS - 电子工程

2dmin

<strong>引言</strong>

在无线局域网中，传输的介质主要是无线电波和红外线，任何具有接收能力的窍听者都有可能拦截无线信道中的数据，掌握传输的内容，造成数据泄密。因此，对于无线局域网来说，数据的加密是关键技术之一。

AVR高速嵌入式单片机是8位RISC MCU，执行大多数指令只需一个时钟周期，速度快（8MHz AVR的运行速度约等于200MHz C51的运行速度）；32个通用寄存器直接与ALU相连，消除和运算瓶颈。内嵌可串行下载或自我编程的Flash和EPPROM，功能繁多，具有多种运行模式。
依照IEEE1999年发布的802.11无线局域网协议标准，采用Atmel公司的Atmega128高速嵌入式单片机，开发无线数据传输装置。为了实现无线数据传输时的安全性，同时尽可能节省成本，采用软件进行加密、解密。这就对算法的简法性、高速性及适应性提出了很高的要求。RC5和 RC6两种新型的分组加密算法能够比较好地满足上述的要求。

<strong>1 RC5及RC6算法</strong>

1.1 RC5及RC6的参数

RC5及RC6是参数变量的分组算法，实际上是由三个参数确定的一个加密算法族。一个特定的RC5或者RC6可以表示为RC5-w/r/b或者 RC6-w/r/b。其中这三个参数w、f和b分别按照表1所列定义。

<strong>表1 RC5及RC6算法参数定义</strong>
参数定义常用w以比特表示的字的尺寸16,32,64r加密轮数0～255b密钥的字节长度0～255
1.2 RC5及RC6字运算部件

RC5及RC6均由三部分组成，分别为混合密钥生成过程、加密过程和解密过程。在这两种算法中，共使用了六种基本运算：
①模2w加法运算，表示为“+”；
②模2w减法运算，表示为“-”；
③逐位异或运算，表示为+；
④循环左移，字a循环左移b比特表示为“a<<<b”；
⑤循环右移，字a循环右移b比特表示为“a>>>b”；
⑥模2w乘法，表示为“×”。

RC5算法运用了上述的①～⑤运算部分，RC6算法使用了上述所有的运算部件。

1.3 RC5算法

（1）RC5算法混合密钥生成过程的伪代码表示
S[0]=Pw
for i=1 to t-1 do
[sup]S=S[i-1]+Qw
输入比特数大小为8，密钥长度为b的用户密钥K[0]至K[b-1]
转换K[0]至K[b-1]为数组长度为c，比特数为w的L[]数组
i=j=0 x=y=0
do 3×max(t,c)times：
S=(S+x+y)<<<3;X=S;i=(i+1)mod t
L[j]=(L[j]+x+y)<<<(x,y);X=L[j];j=(j+1)modC
其中c=[b×8/w]方括号表示上取整运算，t=2r+2，当w分别为16、32、64时，常数Pw、Qw分别如表2所列。

表 2 常数Pw、Qw取值表[/sup]<i><i></i></i>W163264Pw0xB7E10xB7E151630xB7E151628AED2A6BQw0x9E370x9E3779B90x9E3770B97F4A7C15<i><i></i></i>（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分别为要加密的两个比特数为w的数据，最终的A、B分别为加密好的两个比特数为w的数据。

（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中的数据就是已经加密了的比特数为w的数据，最终的A、B中的数据为解密后的比特数为w的数据。

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分别为要加密的四个比特数为w的数据，最终的A、B、C、D分别为加密好的四个比特数为w的数据。

(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分别为已经被加密的四个比特数为w的数据，最终的A、B、C、D分别为解密后的四个比特数为w的数据。

<strong>2 RC5和RC6算法的实现及改进</strong>

2.1 AVR单片机的RC5和RC6算法流程

RC5及RC6算法加密过程实现流程图如图1所示，解密过程实现流程图如图2所示，总体过程流程图如图3所示。<i><i><i><i>


<ignore_js_op>





2010-3-17 21:59:52 上传
<strong>下载附件</strong> (15.47 KB)




</ignore_js_op>



<ignore_js_op>





2010-3-17 21:59:51 上传
<strong>下载附件</strong> (17.9 KB)




</ignore_js_op>



<ignore_js_op>





2010-3-17 21:59:50 上传
<strong>下载附件</strong> (21.22 KB)




</ignore_js_op>


</i></i></i></i>2.2 AVR单片机RC5和RC6算法的改进

①在进行算法流程的安排时，考虑到AVR高速嵌入式单片机只有32个8位寄存器，为了节省寄存器的使用，应该在混合密钥生成过程执行后，再把待加密的数据赋予寄存器。这样在混合密钥生成过程以前的寄存器都可以被使用，而不会对整个算法的执行结果造成影响。
②在进行RC5及RC6算法参数的选择时，考虑到AVR高速嵌入式单片机指令最多只支持16位数据相加以及程序的简洁化，所以在本程序中选择w 为16而没有选择w为32，r和b的值依据Rivest的建议分别取为12和16。
③在执行算法中的左循环或者右循环运算时，考虑到循环移位的效果，实际循环移位的位数应该为要执行移位次数的低1log2w位。在本程序中为要执行移位次数的后四位。
④在执行算法中的模2w加法运算、模2w减法运算、模2w乘法运算时，由于2w的取值为65536,而2个8位寄存器（0～15位）最高可以表示数据的值为65535，数据再大就要向高位进位，所以在本程序执行上述的算法只需要考虑到2个8位寄存器所表达的值就得到了上述运算的最终结果，而不用再进行模2w运算。
⑤为了提高数据加密及解密的速率，可以把混合密钥生成过程提前执行，以使之生成一张混合密钥表。把这个表装入发送数据端Atmega128高速嵌入式单片机和接收数据端Atmega128高速嵌入式单片机的Flash中，从而在以后的加密与解密过程中直接使用混合密钥。值得注意的是，每当用户输入的用户密钥发生改变时，必须重新执行混合密钥生成过程，并且重新给Flash装载重新生成后的混合密钥表。在本程序中，RC5混合密钥表共占据52个8 位寄存单元，RC6混合密钥表共占据56个8位存储单元。
⑥在本程序中运用加法运算以及移位运算实现了16位二进制数乘以16位二进制数的无符号运算。该运算的子程序如下：
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

<strong>3 RC5及RC6算法实验结果及其比较与分析</strong>

RC5及RC6算法实验的混合密钥过程、加密过程、解密过程和总体过程的效果比较如表3、4、5、6所列。

<strong>表3 RC5及RC6算法混合密钥过程效果比较</strong><i><i></i></i>混合密钥生成过程周期计数停止观察/μs程序大小/字ctRC5算法15 2481270.67141826RC6算法15 2461270.50141828<i><i></i></i><strong>表4 RC5及RC6算法加密过程效果比较</strong><i><i></i></i>加密过程（不考虑生成混合密钥的时间）周期计数停止观察/μs程序大小/字共处理数据的位数效率/（位/s)RC5算法2511209.256632约为152 927RC6算法625295210.7517064约为12 282<i><i></i></i><strong>表5 RC5及RC6算法解密过程效果比较</strong><i><i></i></i>解密过程（不考虑生成混合密钥的时间）周期计数停止观察/μs程序大小/字共处理数据的位数效率/（位/s）RC5 算法2509209.086832约为153 051RC6 算法625275210.5817664约为12 283<i><i></i></i><strong>表6 RC5及RC6算法总体过程效果比较</strong><i><i></i></i>总体算法过程（考虑生成混合密钥的时间，不考虑数据传输所用的）周期计数停止观察/μs程序大小/字共处理数据的位数效率/(位/s)RC5算法20 2601688.3326732约为18 594RC6算法140 27411 689.5045564约为5475<i><i></i></i>由表3可以发现，RC6算法和RC5算法在混合密钥生成时程序的大小相同，但量RC6算法却比RC5算法省时。这是因为根据混合密钥生在方法在执行循环，最终生成混合密钥时要执行比较操作。当超出了比较范围t时，要对指针地址重新复位。RC6算法t的取值大于RC5算法中t的取值，因此RC6算法执行了较少的复位操作。从而节省了运行周期，故RC6算法比RC5算法在生成混合密钥时省时。

以上所有实验结果均是在AVR Studio4.07仿真软件上选用Atmel公司的Atmega128高速嵌入式单片机为实验设备平台。选取参数w=16、r=12、b=16，并根据计算公式求得c=8，t=26(RC5算法)或者t=28（RC6算法）在12MHz运行速度下模拟所得。

从实验结果所得的表3、表4、表5、表6可以明确得出以下结论。
①从程序的执行效率来看，无论在加密还是在解密过程中，RC5算法都要比RC6算法执行效率高。
因此，在一些非常注重程序执行效率，而对数据安全性要求不是非常高的情况下，应该采用RC5算法。
②从程序的执行时间来看，无论在加密过程不是在解密过程中，RC5算法都要比RC6算法省时。因此，在一些对程序执行时间长短要求很高，对数据安全性要求不是非常高的情况下，可以采用RC5算法。
③从程序的大小来看，无论在加密过程中还是在解密过程中，RC5算法都要比RC6算法更简洁。因此，在一些对程序所用空间大小要求很高，对数据安全性要求不是非常高的情况下，可以采用RC5算法。
④从安全性角度考虑，RC6算法是在RC5算法基础之上针对RC5算法中的漏洞，主要是循环移位的位移量并不取决于要移动次数的所有比特，通过采用引入乘法运算来决定循环移位次数的方法，对RC5算法进行了改进，从而大大提高了RC6算法的安全性。因此，在一些对数据安全性要求很高的情况下，应该采用RC6算法。

<strong>结语</strong>

RC5及RC6算法是两种新型的分组密码，它们都具有可变的字长，可变的加密轮数，可变的密钥长度；同时，它们又只使用了常见的初等运算操作，这使它们有很好的适应性，很高的运算速度，并且非常适合于硬件和软件实现。两种算法各有其优缺点，在工程应用中应该根据实际需要选择最适合的方法，以得到最优的效果。

<strong>参考文献</strong>

1. Rivest Ronald L The RC6TM Block Cipher 1999
2. 宋震 密码学 2002
3. 杨义先 现代密码新理论 2002
4. 李勋.耿德根 AVR 单片机应用技术 2002
5. 耿德根 AVR 高速嵌入式单片机原理与应用 2001

作 者：西安交通大学 王泉 齐春 罗新民 黄伟 郑州大学 马旭东
来 源：单片机与嵌入式系统应用 2003（10）