周華，黃廷磊

(桂林電子科技大學 計算機科學與工程學院，廣西 桂林541004)

近年來，遺傳算法基本上是一種探索性研究，最優(yōu)化和機器學習研究在達爾文適者生存的進化論基礎上得到發(fā)展。密碼學是在通信中除了接收者外別人無法破解的一門科學，它是一種研究發(fā)送偽裝消息僅僅讓接收者消除偽裝的技術。密碼學為個人隱私、互聯(lián)網(wǎng)、外交和軍事安全提供了高度保護機密信息的解決方法。由加解密過程可知，加密系統(tǒng)是利用密鑰序列的一套加密、解密程序算法。香農(nóng)提出的第一個密鑰系統(tǒng)模型如圖1所示。

圖1 香農(nóng)模式的保密通信模型Fig.1 Shannon model of secret communication

決定密鑰強弱的一項重要特征不是量化矩陣而是加密算法的性能，如對稱與非對稱、適應函數(shù)、密鑰的長短和算法的復雜度。由于目前加密算法的加密依賴于置亂矩陣的復雜性，容易被黑客等用枚舉算法攻克，無法確保網(wǎng)絡安全。密碼攻擊可測試算法的健壯性，參數(shù)攻擊可評估基于密鑰生成的長度和復雜性的算法效果。密鑰復雜度可在生成過程中加工，這使得密碼專家很難將其攻破。隨機數(shù)生成器用來生成密鑰，遺傳算法會使得密鑰更加復雜，密鑰的選擇完全依賴于由隨機數(shù)產(chǎn)生的不同字符串的適應值。為此，在遺傳算法的建模思想上，提出一種基于遺傳算法生成圖像加密密鑰序列的加密技術，對圖像矩陣做一系列混沌變換，從而達到加密的目的。

1 遺傳算法

遺傳算法是以自然選擇為原則的隨機搜索與最優(yōu)化算法，使用選擇、交叉和變異3種基本運算。遺傳算法經(jīng)選擇、交叉、變異的不斷循環(huán)直至滿足約束條件即停止。選擇與交叉使遺傳算法成為一種具有很強搜索能力的算法。

1.1 選擇

選擇是遺傳群體中染色體適應性被選擇復制的一種定量方法，也就是將一個很龐大的群體隨機抽樣出一個比較合適的樣本，以便做抽樣分析，其目的是為設置適應函數(shù)的規(guī)模算法做準備。

1.2 交叉

在交叉操作中，2條染色體相互作用產(chǎn)生2條新的染色體，并帶有原染色體的某些特征，如字符串1010010和1110001，可越過第3個位置產(chǎn)生2個后代1010001和1110010。交叉操作有單點交叉、雙點交叉、均勻交叉3種類型。本研究的交叉操作為單點交叉，其操作過程如圖2所示。

圖2 交叉操作過程Fig.2 Crossover operation

1.3 變異

變異用來維持種群一代到下一代的遺傳多樣性，這類似于生物的基因突變。遺傳算法旨在修改候選位上的突變基因作為解決方案，這些變異包括字符串的位逆轉。位逆轉運算包括隨機互換2位或者逆轉一個染色體上的位，如字符串00000111可能在其從左到右第5個位置上發(fā)生突變成為00001111。圖3為遺傳算法的周期模型。

圖3 遺傳算法的周期模型Fig.3 Basic model of genetic algorithm

用圖3中的各種進程作用于初始種群。從初始種群中選擇具有最大適應值的個體作進一步處理，適應值的計算通過相應的適應函數(shù)實現(xiàn)。被選擇的種群通過交叉、變異等操作產(chǎn)生新的最適應個體。

2 適應函數(shù)構造

染色體的初始種群利用一個隨機函數(shù)產(chǎn)生一連串十六進制數(shù)，初始種群字節(jié)長度為128位，適應函數(shù)是一個極大值函數(shù)，表示具有單個后代最大適應值的個體將被選擇，可評估所有的后代個體。在適應函數(shù)作用后，選擇最好的2個個體進行單點交叉并產(chǎn)生所選擇的后代個體。交叉后得到所選擇的子代，然后再對子代進行適應函數(shù)評估，若其評估值比父代好，則子代取代父代。前一個步驟輸出的新后代作為變異操作的輸入，經(jīng)過最后的變異，獲得用于加密的最終密鑰。密鑰生成過程的遺傳算法步驟如下:

1)初始種群。初始種群的染色體以二進制數(shù)的形式標記。

2)評估。將每一個二進制格式的染色體轉換成十進制數(shù)，對所產(chǎn)生的數(shù)值進行隨機性測試。

3)臨界值檢查。這些值被選擇后，其中大于該臨界值的被選中。

4)交叉。對種群進行單點交叉，交叉后產(chǎn)生新種群，不符合最大適應需求的將被淘汰。

5)變異。在步驟4)后，選擇一些染色體的隨機位并作改變，根據(jù)突變率產(chǎn)生一部分新的染色體，形成一個新的種群。

6)適應函數(shù)計算。突變產(chǎn)生的新種群可能不符合最大適應函數(shù)的要求，需再次進行臨界值檢查。在這個程序運行到最后找到最終的種群。這個種群被存儲在一個文件中，整個過程重復n次，上述步驟導致n套種群的隨機性測試，最好的個體樣品選擇和每個染色體的偏差設置為自相關系數(shù)，&Φ為價值樣本計算值，每個染色體的最大適應值函數(shù)為:

7)迭代選擇。通過迭代選擇，具有最大適應值的那些個體將替代之前被選擇的個體。

8)交叉和變異。交叉和變異過程反復進行，選擇最接近最大適應值的染色體種群。

通過以上步驟，具有最大適應值的個體在每次迭代時被記錄下來，在滿足停止條件后，最大適應值的個體被選中作為密鑰進行加密。圖4為密鑰生成過程中使用的遺傳算法。

圖4 密鑰生成過程中使用的遺傳算法Fig.4 Genetic algorithm using for key generation

用密鑰進行加密參照高級加密標準(AES)，遺傳算法生成的密鑰過程屬于對稱密鑰算法，由于其計算速度快、密鑰管理開銷小而被廣泛使用。

3 Matlab仿真實驗

仿真實驗采用加密算法，即利用遺傳算法生成密鑰進行加密。根據(jù)整個種群適應函數(shù)的改造以及生成密鑰的流程圖，利用Matlab平臺進行仿真，最后用遺傳算法對加密圖像進行直方圖分析，并做各種測試，彌補了圖像矩陣加密密鑰空間有限的缺陷。通過用10個種群，每個種群50次迭代，共500次迭代算法，測試并計算不同運行情況收集的最大適應值的均值和標準差。根據(jù)均值和標準差繪制的圖像如圖5所示。從圖5可看出，隨著迭代次數(shù)的增加，迭代效率呈緩慢上升趨勢。

圖5 均值和標準差圖Fig.5 Mean and standard difference

實驗使用密鑰生成混沌序列算法進行加密和解密，共加密了十余幅圖像，只選取其中一幅圖像，其原始圖與加密圖如圖6所示。

圖6 原始圖與加密圖Fig.6 Original image and encrypted image

從圖6可看出，原始圖像經(jīng)加密之后是不可預見的，達到了加密的目的。

仿真步驟及參數(shù)分析在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)//產(chǎn)生密鑰混沌序列

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

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

end

4 結束語

采用遺傳算法生成密鑰，實現(xiàn)了對圖像的加密。通過對數(shù)百個樣例進行實驗表明，各群體間差異很大，每次試驗的密鑰長度為128位，更長的密鑰序列也可工作。用10個種群進行10次交叉和變異操作，生成300次迭代的密鑰生成時間為75.382 s，也可加密和解密，但在解密時一些數(shù)據(jù)會丟失。下一步的研究工作，可對算法加以改進，以實現(xiàn)無數(shù)據(jù)丟失的加密。

［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，F(xiàn)leming P J.An overview of evolutionary algorithms in multiobjective optimization［J］.Evolutionary Computation，2012，3(1):1-16.

［3］李昌剛，韓正之.圖像加密技術綜述［J］.計算機研究與發(fā)展，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.