遗传算法生成密钥的图像加密技术

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

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

　　1 遗传算法

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

　　1. 1 选择

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

　　1. 2 交叉

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

　　1. 3 变异

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

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

　　2 适应函数构造

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

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

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

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

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

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

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

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

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

　　通过以上步骤，具有最大适应值的个体在每次迭代时被记录下来，在满足停止条件后，最大适应值的个体被选中作为密钥进行加密。图 4 为密钥生成过程中使用的遗传算法。用密钥进行加密参照高级加密标准（ AES） ,遗传算法生成的密钥过程属于对称密钥算法，由于其计算速度快、密钥管理开销小而被广泛使用。

　　3 Matlab 仿真实验

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

　　实验使用密钥生成混沌序列算法进行加密和解密，共加密了十余幅图像，只选取其中一幅图像，其原始图与加密图如图 6 所示。从图 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,也可加密和解密，但在解密时一些数据会丢失。下一步的研究工作，可对算法加以改进，以实现无数据丢失的加密。