周華，黃廷磊

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

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

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

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

1 遺傳算法

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

1.1 選擇

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

1.2 交叉

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

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

1.3 變異

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

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

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

2 適應(yīng)函數(shù)構(gòu)造

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

1)初始種群。初始種群的染色體以二進(jìn)制數(shù)的形式標(biāo)記。

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

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

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

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

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

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

8)交叉和變異。交叉和變異過程反復(fù)進(jìn)行，選擇最接近最大適應(yīng)值的染色體種群。

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

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

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

3 Matlab仿真實(shí)驗(yàn)

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

圖5 均值和標(biāo)準(zhǔn)差圖Fig.5 Mean and standard difference

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

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

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

仿真步驟及參數(shù)分析在Matlab中進(jìn)行，加密、解密的算法代碼如下:

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 結(jié)束語

采用遺傳算法生成密鑰，實(shí)現(xiàn)了對(duì)圖像的加密。通過對(duì)數(shù)百個(gè)樣例進(jìn)行實(shí)驗(yàn)表明，各群體間差異很大，每次試驗(yàn)的密鑰長度為128位，更長的密鑰序列也可工作。用10個(gè)種群進(jìn)行10次交叉和變異操作，生成300次迭代的密鑰生成時(shí)間為75.382 s，也可加密和解密，但在解密時(shí)一些數(shù)據(jù)會(huì)丟失。下一步的研究工作，可對(duì)算法加以改進(jìn)，以實(shí)現(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］李昌剛，韓正之.圖像加密技術(shù)綜述［J］.計(jì)算機(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.