AVR单片机的RC5和RC6算法比较与改进

AVR单片机的RC5和RC6算法比较与改进（精选2篇）

AVR单片机的RC5和RC6算法比较与改进 篇1

AVR单片机的RC5和RC6算法比较与改进

摘要：RC5及RC6是两种新型的分组密码。AVR高速嵌入式单片机功能强大，在无线数据传输应用方面很有优势。本文基于Atmega128高速嵌入式单片机，实现RC5和RC6加密及解密算法，并对算法进行汇编语言的优化及改进。根据实验结果。对两种算法的优热点进行比较和分析。

关键词：Atmega128 RC5 RC6 分组密码 混合密钥 Flash

引言

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

AVR高速嵌入式单片机是8位RISC MCU，执行大多数指令只需一个时钟周期，速度快(8MHz AVR的运行速度约等于200MHz C51的运行速度);32个通用寄存器直接与ALU相连，消除和运算瓶颈。内嵌可串行下载或自我编程的Flash和EPPROM，功能繁多，具有多种运行模式。

依照IEEE发布的802.11无线局域网协议标准，采用Atmel公司的Atmega128高速嵌入式单片机，开发无线数据传输装置。为了实现无线数据传输时的安全性，同时尽可能节省成本，采用软件进行加密、解密。这就对算法的简法性、高速性及适应性提出了很高的要求。RC5和RC6两种新型的分组加密算法能够比较好地满足上述的要求。

1 RC5及RC6算法

1.1 RC5及RC6的参数

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

表1 RC5及RC6算法参数定义

参 数定 义常 用w以比特表示的字的尺寸16,32,64r加密轮数0～255b密钥的字节长度0～255

1.2 RC5及RC6字运算部件

RC5及RC6均由三部分组成，分别为混合密钥生成过程、加密过程和解密过程。在这两种算法中，共使用了六种基本运算：

①模2w加法运算，表示为“+”;

②模2w减法运算，表示为“-”;(本网网收集整理)

③逐位异或运算，表示为+;

④循环左移，字a循环左移b比特表示为“a<<

⑤循环右移，字a循环右移b比特表示为“a>>>b”;

⑥模2w乘法，表示为“×”。

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

1.3 RC5算法

(1)RC5算法混合密钥生成过程的伪代码表示

S[0]=Pw

for i=1 to t-1 do

S[i]=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[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]方括号表示上取整运算，t=2r+2，当w分别为16、32、64时，常数Pw、Qw分别如表2所列。

表2 常数Pw、Qw取值表

W163264Pw0xB7E10xB7E151630xB7E151628AED2A6BQw0x9E370x9E3779B90x9E3770B97F4A7C15

(2)RC5加密算法过程的伪代码表示

Input(A,B)

A=A+S(0)B=B+S[1]

for i=1 to r do

A=((A+B)<<

B=((B+A)<<

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))<<

u=(D×(2D+1))<<<1og2w

A=((A+t)<<

C=((C+u)<<

(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))<<

t=(B×(2B+1))<<

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的数据。

2 RC5和RC6算法的实现及改进

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

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

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

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

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

表3 RC5及RC6算法混合密钥过程效果比较

混合密钥生成过程周期计数停止观察/μs程序大小/字ctRC5算法15 2481270.67141826RC6算法15 2461270.50141828

表4 RC5及RC6算法加密过程效果比较

加密过程(不考虑生成混合密钥的时间)周期计数停止观察/μs程序大小/字共处理数据的位数效率/(位/s)RC5算法2511209.256632约为152 927RC6算法625295210.7517064约为12 282

表5 RC5及RC6算法解密过程效果比较

解密过程(不考虑生成混合密钥的时间)周期计数停止观察/μs程序大小/字共处理数据的位数效率/(位/s)RC5 算法2509209.086832约为153 051RC6 算法625275210.5817664约为12 283

表6 RC5及RC6算法总体过程效果比较

总体算法过程(考虑生成混合密钥的时间，不考虑数据传输所用的)周期计数停止观察/μs程序大小/字共处理数据的位数效率/(位/s)RC5算法20 2601688.3326732约为18 594RC6算法140 27411 689.5045564约为5475

由表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算法。

结语

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

AVR单片机的RC5和RC6算法比较与改进 篇2

关键词：元件贴装顺序优化,贴片机,遗传算法,交叉算子

0引言

随着电子产品装配技术日新月异的发展, 表面组装技术 (SMT) , 这一集电子元器件、组装装备和焊接技术为一体的综合性技术得到了越来越广泛的应用[1]。表面组装生产线的使用, 加快了电子产品的生产效益, 增强了产品的可靠性, 与此同时大大降低了生产成本, 使得电子产品装配较之手工装配发生了质的飞跃。为进一步地提高贴片机的性能, 其关键因素之一就是提高贴片机的效率:即贴片机送料器的位置分配优化和元器件的贴装优化。

这里假设送料器位置固定, 来解决元器件的贴装优化问题。对于单台贴片机而言, 这个问题都属于NP Hard问题, 一般被规划为旅行商问题 ( Traveling Sales man Problem, TSP) [2], 已有一些学者成功地用传统的遗传算法 (GA) 解决。但是, 由于贴片机的发展, 它的结构已经变得更为复杂, 其头数已多达12头, 甚至更多, 解决贴装顺序优化问题的方法近年来主要有:遗传算法、蚁群算法、伞布搜索法以及差分算法。遗传算法是进化算法, 主要通过选择变异和交叉算子完成;蚁群算法是基于图论的算法, 通过信息素选择交换信息;伞布搜索法属于比较新的应用于贴装顺序优化的算法, 目前国内的研究报道少之又少, 国外尚未有关此算法在贴装优化方面的研究应用;差分算法是在遗传算法的基础上增加了迁徙进化过程, 使算法拥有更好的全局性, 但较之遗传算法编程思想比较麻烦。所以本文只讨论遗传算法的应用, 并对其进行改进, 使贴装优化不仅编程简便且拥有较好的全局性和收敛性。

1遗传算法的基本原理

20世纪50—60年代, 一些科学家独立开展了旨在可以成为工程问题优化工具的进化系统的研究。80年代以后, 经过相关领域专家学者的交流和共同努力, 遗传算法、ES、EP走向融合, 构成了进化计算的思想和主要算法形式[3]。由于其不受搜索空间的限制性假设的约束, 不必要求诸如连续性、倒数存在和单峰等假设, 以及其固有的并行性, 遗传算法在最优化、机器学习和并行处理领域得到了越来越广泛的应用。遗传算法GA把问题的解表示成“染色体”, 在执行遗传算法之前, 给出一群“染色体”, 即假设解。然后把这些假设解放置于问题的“环境”中, 按照适者生存的原则, 较适应环境的“染色体”被挑选出来进行复制, 再通过交叉, 变异过程产生更适应环境的新一代“染色体”群。这样, 一代一代地进化, 最后就会收敛到最适应环境的一个“染色体”上, 它就是问题的最优解。

2贴片机的工作过程及数学模型

无论是全自动贴片机还是手动贴片机, 无论是高速贴片机还是中低速贴片机, 它的总体结构均有类似之处。图1是一种通用贴片机的内部结构示意图, 所示为12个吸嘴, 其工作过程:PCB由传送带入口送入, 传送带将PCB送到工作位置停板, 定位针进行夹紧, 通过相机识别MARK点对PCB板完成定位后, PCB板固定, 贴装头吸取元件通过x/y轴及R轴和Z轴的移动以一定的压力把元件贴装在有粘性的已经印刷焊锡的焊盘上, 即吸取-位移-定位-放置功能[4], 贴装头不断地重复这样的贴装循环, 直到所有元件贴装完毕即完成贴装。贴片机贴装路径优化问题描述如下:已知印制板上各个元器件的装配位置, 寻求一个贴片机头遍历这些装配位置的路径, 寻求开销最小。

该问题与经典的TSP问题有相似之处, 即都是遍历整个集合, 求最小值问题。不同的是, 贴片机贴装要分批进行, 如一个4吸嘴的贴片头一个贴装循环内只能贴装4个元器件, 一次循环结束后贴片头要返回工料站进行取料再开始下一个循环。所以整体来说, 贴片机的贴装优化并不属于TSP问题。贴片机贴装时间需包括:取料时间、贴装时间、循环间吸取原料的时间及弃料抛料时间等。整个贴片机的贴装过程是一个比较复杂的过程, 为使模型的建立稍微简单些, 必须牺牲掉一些不必要的环节, 故参照文献[5]做以下假设:

(1) 假设供料器位置为原点;

(2) 将整个贴装过程中只做一次的动作例如PCB MARK点的定位省略;

(3) 假设每次贴片式贴装头在x, y方向运动的时间均大于其贴装头的旋转对中时间;

(4) 假设吸嘴吸片时间固定, 为90 ms;贴片时间固定, 为90 ms;

故类似文献[6], 一个完整的贴装时间可以表示为:

式中:T1i表示第i个循环内总共的贴片头移动时间;T2i表示贴片头从第i个循环的最后一个元件贴装完毕移动到下一个循环的第一个元件的贴装位置所需要的时间; ti表示第i个元件的贴片时间, 如上文所假设, 一般每个元件的贴片时间一定;s表示总循环次数;n表示总元件个数。按距离远近x, y方向的运动有加速-减速 (短距离) 、加速-恒速-减速 (长距离) 两种形式。按给定运动距离S、加速度a、恒速度v可得到对应的运动时间t的计算公式:

短距离:t =4aS ;长距离:t =vS+av

式中v, a都是设定值。故求上式的最小值可简化为的最小值, d1表示贴装循环内贴片头要移动的距离, d2表示循环间贴片头要移动的距离。

3算法

3.1遗传算法

遗传算法在群体进化过程中发生繁殖、杂交和突变现象, 不断发现重要基因[7]。寻找较好模式的过程中, 高适应度的个体被选择的概率大于低适应度的个体, 则好的基因得以遗传下来, 不好的基因被剔除, 随着迭代次数的增加逐渐创造出更好的个体, 同时也渐渐趋近于全局最优解。

主要包括3部分:多样性初始解集的产生;解集的改良更新, 其中的算子包括复制算子、交叉算子和变异算子;最优解的出现。

3.2初始解集的产生

初始解集的特性对计算结果和计算效率有重要的影响, 要实现全局最优, 初始解集在解空间上应尽量分散, 若按照随机方法产生一组原始解集, 可能会导致初始解集在解空间的分布不均进而影响算法的性能。在遗传算法中初始种群的各个个体间应保持一定的距离, 这样的分布能使解在解空间上含有较丰富的模式, 进而增加搜索收敛全局最优的可能性[8]。

3.3复制算子

遗传算法中通过个体的适应值反映群体中个体的好坏程度, 复制算子把当前群体中的个体按照与适应值成比例的概率复制到新的群体中。一般选用赌盘选择的方法完成复制。

3.4交叉算子

交叉算子是对整个染色体操作的, 所以在遗传算法中起核心作用, 遗传算法的收敛性主要取决于交叉算子的收敛性[9]。经典的交叉算子包括:单点交叉、两点交叉、多点交叉、融合交叉、均匀交叉等。

3.5变异算子

按概率对染色体的某一基因位 (自变量的某一维) 进行一个微扰动或是取反。

4算法的比较和改进

以一个PCB板子上的20个元器件为例, 其各个元件坐标如下表所示, 假设贴片头上有4个吸嘴。这里初始染色体中有10个体, 迭代次数为200, 交叉概率为定值0.8, 变异概率为定值0.2, 采用多种遗传算法的贴装距离分别如表1所示。

mm

如图2所示, 其中 (a) 结果收敛性和全局优化性都差; (b) 虽然收敛速度快, 但全局性不好; (c) 虽然获得了好的全局性, 但收敛速度慢;相比之下 (d) 的收敛速度和全局性都比较优秀。

图2 (d) 是在前3种遗传算法上的改进, 算法步骤为:

(1) 初始化染色体, 这里取染色体的个体为10;2

(2) 按照赌盘选择和适应值的大小进行复制。即将染色体中前5个适应值高的个体直接复制给新的群体, 剩下的5个解则按照赌盘选择的方法进行选择, 这样不仅提高了群体的平均适应值, 也加快了算法的整体收敛速度;

(3) 对染色体按适应度大小进行排列, 适应度大的排在前面, 小的排在后面;

(4) 从第一个染色体开始选取概率为Pc个染色体, 每两个进行组合形成一对父代双亲, 随机产生一个交叉点k, 并随机产生一个小于从交叉点到最后节点个数的随机数r, 进行交叉。

如假设P1=[1, 4, 3, 7, 2, 5, 6], P2=[2, 4, 7, 3, 6, 5, 1];

若随机产生k=2, r=3;则P1′=[7, 3, 6, 1, 4, 3, 7, 2, 5, 6], P2′=[3, 7, 2, 2, 4, 7, 3, 6, 5, 1];依次删去重复的数得到新的子代个体:p1=[7, 3, 6, 1, 4, 2, 5], p2=[3, 7, 2, 4, 6, 5, 1];

(5) 分别比较2个父代和子代的适应值, 选择适应值最大的遗传下来, 作为最终的子代个体。这样保证了每次都遗传最好的基因, 加快了最优解出现的速度。

5结论

本文提出的遗传算法, 是在传统遗传算法基础上的完善, 通过改善复制算子和交叉算子并加入最后选择算子, 使新的交叉算子有更大的全局优化性和更快的收敛性。相比于文献[2], 文献[2]是改进过交叉算子的应用, 但迭代结果仍然上下波动, 收敛效果不好;相比于文献[10]虽然效果相似, 但却比其有着更简便的编程思想。 该方法得到最优解更具有全局性, 且速度也比较快。

参考文献

[1]SRIHARI K, RAGHAVAN Sundarraman.A process planning system for PCB assembly using TAB and SMT[J].Advanced Manufacturing Technology, 1994, 9:311-318.

[2]曾又姣, 金烨.基于遗传算法的贴片机贴装顺序优化[J].计算机集成制造系统, 2004, 10 (2) :205-208.

[3]韩瑞锋.遗传算法原理与应用实例[M].北京:兵器工业出版社, 2009.

[4]王燕.水平旋转式贴片机贴装过程优化研究[D].西安:西安电子科技大学, 2010.

[5]袁鹏, 刘海明, 胡跃明.高速高精度多功能贴片机及产业化关键技术研究[D].广州:华南理工大学, 2005.

[6]朱光宇, 罗哲, 陈志锦.基于差分算法的贴装顺序优化问题求解[J].中国工程机械学报, 2012, 10 (4) :391-397.

[7]俞国燕, 郑时雄, 刘桂雄, 等.复杂工程问题全局优化算法研究[J].华南理工大学学报, 2000, 28 (8) :104-110.

[8]袁鹏, 刘海明, 胡跃明.基于伞布搜索法的贴片机贴装顺序优化算法[J].电子工艺技术, 2007, 28 (6) :316-320.

[9]翟梅梅.基于交叉算子改进的遗传算法求解TSP问题[J].淮南师范学院学报, 2009, 11 (5) :114-119.