基于遗传算法的图像加密技术及实现

周华，黄廷磊

(桂林电子科技大学 计算机科学与工程学院，广西 桂林541004)

近年来，遗传算法基本上是一种探索性研究，最优化和机器学习研究在达尔文适者生存的进化论基础上得到发展。密码学是在通信中除了接收者外别人无法破解的一门科学，它是一种研究发送伪装消息仅仅让接收者消除伪装的技术。密码学为个人隐私、互联网、外交和军事安全提供了高度保护机密信息的解决方法。由加解密过程可知，加密系统是利用密钥序列的一套加密、解密程序算法。香农提出的第一个密钥系统模型如图1所示。

图1 香农模式的保密通信模型Fig.1 Shannon model of secret communication

决定密钥强弱的一项重要特征不是量化矩阵而是加密算法的性能，如对称与非对称、适应函数、密钥的长短和算法的复杂度。由于目前加密算法的加密依赖于置乱矩阵的复杂性，容易被黑客等用枚举算法攻克，无法确保网络安全。密码攻击可测试算法的健壮性，参数攻击可评估基于密钥生成的长度和复杂性的算法效果。密钥复杂度可在生成过程中加工，这使得密码专家很难将其攻破。随机数生成器用来生成密钥，遗传算法会使得密钥更加复杂，密钥的选择完全依赖于由随机数产生的不同字符串的适应值。为此，在遗传算法的建模思想上，提出一种基于遗传算法生成图像加密密钥序列的加密技术，对图像矩阵做一系列混沌变换，从而达到加密的目的。

1 遗传算法

遗传算法是以自然选择为原则的随机搜索与最优化算法，使用选择、交叉和变异3种基本运算。遗传算法经选择、交叉、变异的不断循环直至满足约束条件即停止。选择与交叉使遗传算法成为一种具有很强搜索能力的算法。

1.1 选择

选择是遗传群体中染色体适应性被选择复制的一种定量方法，也就是将一个很庞大的群体随机抽样出一个比较合适的样本，以便做抽样分析，其目的是为设置适应函数的规模算法做准备。

1.2 交叉

在交叉操作中，2条染色体相互作用产生2条新的染色体，并带有原染色体的某些特征，如字符串1010010和1110001，可越过第3个位置产生2个后代1010001和1110010。交叉操作有单点交叉、双点交叉、均匀交叉3种类型。本研究的交叉操作为单点交叉，其操作过程如图2所示。

图2 交叉操作过程Fig.2 Crossover operation

1.3 变异

变异用来维持种群一代到下一代的遗传多样性，这类似于生物的基因突变。遗传算法旨在修改候选位上的突变基因作为解决方案，这些变异包括字符串的位逆转。位逆转运算包括随机互换2位或者逆转一个染色体上的位，如字符串00000111可能在其从左到右第5个位置上发生突变成为00001111。图3为遗传算法的周期模型。

图3 遗传算法的周期模型Fig.3 Basic model of genetic algorithm

用图3中的各种进程作用于初始种群。从初始种群中选择具有最大适应值的个体作进一步处理，适应值的计算通过相应的适应函数实现。被选择的种群通过交叉、变异等操作产生新的最适应个体。

2 适应函数构造

染色体的初始种群利用一个随机函数产生一连串十六进制数，初始种群字节长度为128位，适应函数是一个极大值函数，表示具有单个后代最大适应值的个体将被选择，可评估所有的后代个体。在适应函数作用后，选择最好的2个个体进行单点交叉并产生所选择的后代个体。交叉后得到所选择的子代，然后再对子代进行适应函数评估，若其评估值比父代好，则子代取代父代。前一个步骤输出的新后代作为变异操作的输入，经过最后的变异，获得用于加密的最终密钥。密钥生成过程的遗传算法步骤如下:

1)初始种群。初始种群的染色体以二进制数的形式标记。

2)评估。将每一个二进制格式的染色体转换成十进制数，对所产生的数值进行随机性测试。

3)临界值检查。这些值被选择后，其中大于该临界值的被选中。

4)交叉。对种群进行单点交叉，交叉后产生新种群，不符合最大适应需求的将被淘汰。

5)变异。在步骤4)后，选择一些染色体的随机位并作改变，根据突变率产生一部分新的染色体，形成一个新的种群。

6)适应函数计算。突变产生的新种群可能不符合最大适应函数的要求，需再次进行临界值检查。在这个程序运行到最后找到最终的种群。这个种群被存储在一个文件中，整个过程重复n次，上述步骤导致n套种群的随机性测试，最好的个体样品选择和每个染色体的偏差设置为自相关系数，&Φ为价值样本计算值，每个染色体的最大适应值函数为:

7)迭代选择。通过迭代选择，具有最大适应值的那些个体将替代之前被选择的个体。

8)交叉和变异。交叉和变异过程反复进行，选择最接近最大适应值的染色体种群。

通过以上步骤，具有最大适应值的个体在每次迭代时被记录下来，在满足停止条件后，最大适应值的个体被选中作为密钥进行加密。图4为密钥生成过程中使用的遗传算法。

图4 密钥生成过程中使用的遗传算法Fig.4 Genetic algorithm using for key generation

用密钥进行加密参照高级加密标准(AES)，遗传算法生成的密钥过程属于对称密钥算法，由于其计算速度快、密钥管理开销小而被广泛使用。

3 Matlab仿真实验

仿真实验采用加密算法，即利用遗传算法生成密钥进行加密。根据整个种群适应函数的改造以及生成密钥的流程图，利用Matlab平台进行仿真，最后用遗传算法对加密图像进行直方图分析，并做各种测试，弥补了图像矩阵加密密钥空间有限的缺陷。通过用10个种群，每个种群50次迭代，共500次迭代算法，测试并计算不同运行情况收集的最大适应值的均值和标准差。根据均值和标准差绘制的图像如图5所示。从图5可看出，随着迭代次数的增加，迭代效率呈缓慢上升趋势。

图5 均值和标准差图Fig.5 Mean and standard difference

实验使用密钥生成混沌序列算法进行加密和解密，共加密了十余幅图像，只选取其中一幅图像，其原始图与加密图如图6所示。

图6 原始图与加密图Fig.6 Original image and encrypted image

从图6可看出，原始图像经加密之后是不可预见的，达到了加密的目的。

仿真步骤及参数分析在Matlab中进行，加密、解密的算法代码如下:

begin

A=imread(‘rice.png’);

Imshow(A);

［M，N］=size(A);//原始图像A的尺寸

u1=4;u2=4;x1(1)=0.2;x2(1)=0.7;

sumA=sum(sum(A));

while(k＜255)do{

k=mod(sumA，256)*1.0/255;

x1(1)=(x1(1)+k)/2;

x2(1)=(x2(1)+k)/2;

y1(1)=(1/3.141 592 6)*asin(sqrt(x1(1)));

y2(1)=(1/3.141 592 6)*asin(sqrt(x2(1)));

for i=1∶1∶M*(N－1)//产生密钥混沌序列

x1(i+1)=u1*x1(i)*(1－x1(i));

x2(i+1)=u1*x1(i)*(1－x2(i));

end

4 结束语

采用遗传算法生成密钥，实现了对图像的加密。通过对数百个样例进行实验表明，各群体间差异很大，每次试验的密钥长度为128位，更长的密钥序列也可工作。用10个种群进行10次交叉和变异操作，生成300次迭代的密钥生成时间为75.382 s，也可加密和解密，但在解密时一些数据会丢失。下一步的研究工作，可对算法加以改进，以实现无数据丢失的加密。

［1］Kumar A，Rajpal N，Tayal A.New signal security system for multimedia data transmission using genetic algorithms［J］.International Conference on Hybrid Information Technology，2005，7(3):20-28.

［2］Fonseca C M，Fleming P J.An overview of evolutionary algorithms in multiobjective optimization［J］.Evolutionary Computation，2012，3(1):1-16.

［3］李昌刚，韩正之.图像加密技术综述［J］.计算机研究与发展，2002，39(10):1317-1324.

［4］Agarwal A.Secret key encryption algorithm using genetic algorithm［J］.International Journal of Advanced Research in Computer Science and Software Engineering，2012，2(4):33-37.

［5］Soni A，Agrawal S.Key generation using genetic algorithm for image encryption［J］.ACM Transactions on Graphics，2013，3(4):67-73.

［6］Goyat S.Genetic key generation for public key cryptography［J］.International Journal of Soft Computing and Engineering，2012，5(3):2231-2307.

［7］Ahmad F，Khalid S，Hussain M S.Encrypting data using the features of memetic algorithm and cryptography［J］.International Journal of Pattern Recognition and Artificial Intelligence，2011，9(3):109-110.