楊恒歡，馮 濤，荊 銳

(1. 上海中新科技管理學(xué)院計(jì)算機(jī)系，上海 200023；2. 上海第二工業(yè)大學(xué)成人與繼續(xù)教育學(xué)院，上海 200041)

一種黑洞數(shù)和Logistic混沌序列的圖像加密應(yīng)用

楊恒歡1，馮 濤2，荊 銳1

(1. 上海中新科技管理學(xué)院計(jì)算機(jī)系，上海 200023；2. 上海第二工業(yè)大學(xué)成人與繼續(xù)教育學(xué)院，上海 200041)

圖像加密技術(shù)是數(shù)字信息保護(hù)的一種有效手段。在信息技術(shù)的發(fā)展下，人們對(duì)圖像信息安全性的要求越來(lái)越高。本文提出了一種基于黑洞數(shù)和Logistic混沌序列的圖像加密算法。本算法通過(guò)對(duì)黑洞數(shù)的研究，利用黑洞數(shù)發(fā)生器產(chǎn)生偽混沌序列，將該序列作為初始參數(shù)代入logistic算法，產(chǎn)生混沌密鑰流對(duì)圖像進(jìn)行加密。實(shí)驗(yàn)結(jié)果表明該方法運(yùn)算速度快，產(chǎn)生的置亂和加密序列的安全性很高。

黑洞數(shù)；logistic算法；圖像加密

0 引言

隨著互聯(lián)網(wǎng)技術(shù)與多媒體技術(shù)的飛速發(fā)展，越來(lái)越多的信息通過(guò)網(wǎng)絡(luò)來(lái)進(jìn)行傳輸。數(shù)字圖像已經(jīng)成為人們進(jìn)行信息交流的一種重要的信息載體。圖像加密技術(shù)是多媒體信息安全的核心技術(shù)，是數(shù)學(xué)、密碼學(xué)、計(jì)算機(jī)視覺(jué)等多學(xué)科交叉的研究課題。其中密碼學(xué)主要是研究通信安全保密的學(xué)科，是保護(hù)信息在信息的傳遞過(guò)程中不被敵手竊取、解讀和利用的主要方法。數(shù)學(xué)中有很多公式和方法被應(yīng)用于其中，凡是具有混沌特征的算法都可應(yīng)用在加密領(lǐng)域。

混沌現(xiàn)象最早由美國(guó)氣象學(xué)家Lorenz E T 發(fā)現(xiàn)。他在1963年進(jìn)行數(shù)值實(shí)驗(yàn)時(shí)，利用計(jì)算機(jī)模擬天氣變化，發(fā)現(xiàn)了系統(tǒng)變化的非周期性和不可預(yù)測(cè)性之間的關(guān)系，給出了一個(gè)三變量自治方程（Lorenz方程）來(lái)描述混沌現(xiàn)象，并提出了用蝴蝶效應(yīng)來(lái)表達(dá)系統(tǒng)長(zhǎng)期行為對(duì)初值的敏感依賴性。混沌系統(tǒng)還有遍歷性和內(nèi)隨機(jī)性[1]。初值的敏感依賴性體現(xiàn)為：混沌算法產(chǎn)生的序列，隨著初始值的微小變化，將具有非常大的差異性。遍歷性和內(nèi)隨機(jī)性體現(xiàn)為混沌系統(tǒng)生成的序列分布是離散的?；煦缦到y(tǒng)的性質(zhì)十分適合加密領(lǐng)域，并且具有很好的適用性和安全性。因此，現(xiàn)今的加密技術(shù)主要以混沌系統(tǒng)作為主要研究方向之一。目前數(shù)字圖像加密所用的混沌系統(tǒng)主要有：

(1) Logistic映射，是實(shí)際系統(tǒng)中存在的最簡(jiǎn)單的非線性差分方程之一。這是一個(gè)動(dòng)態(tài)系統(tǒng)，由于系統(tǒng)在運(yùn)行過(guò)程中表現(xiàn)出混沌行為，因此在許多領(lǐng)域中都被研究和應(yīng)用，其公式如下：

其中λ稱為分枝參數(shù)，當(dāng)λ=2.8時(shí)，系統(tǒng)表現(xiàn)出存在兩個(gè)周期點(diǎn)；當(dāng)，出現(xiàn)四個(gè)周期點(diǎn)。隨著λ的逐漸增大，存在的周期點(diǎn)數(shù)也越來(lái)越多，并且頻率越來(lái)越高，直到達(dá)到極限值3.569 945 6…。當(dāng)3.569 945 6…＜λ≤4時(shí)，映射處于混沌狀態(tài)，其產(chǎn)生的序列{xi}是非周期不收斂，隨著初始值的不同有著非常大的差異性。該系統(tǒng)初始狀態(tài)x1在(0, 1)中隨機(jī)取值作為迭代初值，通過(guò)公式(1)對(duì)這個(gè)初始值進(jìn)行迭代，當(dāng)λ＞3.569 945 672…時(shí)，系統(tǒng)進(jìn)入混沌狀態(tài)。Logistic映射所構(gòu)建的密鑰序列具有良好的隨機(jī)性和初值敏感性。

(2) Chebychev混沌序列，以K為映射基數(shù)的Chebychev公式如下：

當(dāng)K= 6時(shí)，方程處于混沌狀態(tài)，所產(chǎn)生的序列{xn}為混沌序列。系統(tǒng)在空間的相鄰軌道間收斂或發(fā)散的平均指數(shù)率（Lyapunov）為1.791 733…。文獻(xiàn)[2]通過(guò)Chebychev多項(xiàng)式的混沌映射構(gòu)建了加密質(zhì)量控制模型，并進(jìn)一步構(gòu)造了圖像小波域加密算法。該方法簡(jiǎn)單易行，兼容性高，但在透明性與運(yùn)算時(shí)間上難以取得較好的平衡點(diǎn)。

(3)正弦映射，Sin方程在某種條件下亦可生成混沌序列，公式如下：

當(dāng)λ= 0.99時(shí)，系統(tǒng)處于混沌狀態(tài)，將初始值x1帶入，可獲得序列{xn}。序列{xn}中的元素值呈混沌分布且離散。由于正弦方程較為簡(jiǎn)單，其運(yùn)算速度很快，但易被破解，往往需要與其他算法相結(jié)合才能達(dá)到一定的安全性。如文獻(xiàn)[3-4]都是利用正弦混沌映射和Logistic映射相結(jié)合對(duì)圖像進(jìn)行加密的方法，但在傳輸及還原過(guò)程中容易造成一定的圖像損失。

本文算法通過(guò)引入數(shù)論中的黑洞數(shù)，根據(jù)其數(shù)學(xué)特征產(chǎn)生具有一定混沌特性的短序列，結(jié)合Logistic映射將圖像進(jìn)行加密。實(shí)驗(yàn)結(jié)果表明該方法簡(jiǎn)單有效，加密后的圖像具有很好的混沌特征，而且計(jì)算速度快、安全性高。

2 黑洞數(shù)以及其性質(zhì)

黑洞數(shù)問(wèn)題是近幾十年內(nèi)出現(xiàn)的有趣數(shù)學(xué)問(wèn)題，引起了國(guó)內(nèi)外數(shù)學(xué)界的廣泛注意和研究[5-7]。數(shù)論中對(duì)于黑洞數(shù)定義為：在含有未知數(shù)變量x的代數(shù)式y(tǒng) = f (x)中，當(dāng)變量x任意取值時(shí)，其應(yīng)變量y都不改變，此時(shí)稱應(yīng)變量y為黑洞數(shù)（數(shù)組）。本文主要在重排求差黑洞數(shù)的基礎(chǔ)上介紹產(chǎn)生偽混沌序列的方法，并應(yīng)用于圖像加密。

重排求差方法：任意數(shù)字不完全重復(fù)的整數(shù)x（像33, 555, 777 7等都應(yīng)該排除），經(jīng)有限“重排求差”操作，總會(huì)得某一個(gè)或一組黑洞數(shù)y。重排x得到的最大數(shù)減去重排x得到的最小數(shù)，不斷循環(huán)此過(guò)程，直到落入循環(huán)，此循環(huán)內(nèi)的數(shù)稱為黑洞數(shù)（數(shù)組）。下表中列出部分?jǐn)?shù)字重排求差流程及結(jié)果。

表1 重排求差流程及結(jié)果Tab. 1 The Process and results for number with potentiometer

文獻(xiàn)[8]通過(guò)數(shù)學(xué)論證，證明了黑洞數(shù)具有3個(gè)性質(zhì)：1) 黑洞數(shù)一定能被9整除；2) 奇數(shù)黑洞數(shù)（位數(shù)≥3）定能被99整除，且中間位數(shù)字為9；3) 任意黑洞數(shù)，其首末位的數(shù)字和為10，或者和為9且中間的所有位數(shù)皆為9。

本文作者在此基礎(chǔ)上作了大量的數(shù)據(jù)分析研究，發(fā)現(xiàn)了更多的規(guī)律。

規(guī)律1

1) 任意位數(shù)為偶數(shù)（大于2）的黑洞數(shù)定能被9整除，首末位數(shù)字的和為10，如：表1中x =851 742和x=860 832的黑洞數(shù)組；

2) 任意位數(shù)為奇數(shù)（大于2）的黑洞數(shù)定能被99整除，且中間數(shù)字為9。如：表1中x =82 962和x =8 429 652黑洞數(shù)組；

3) 對(duì)于任意黑洞數(shù)必定首末位和為10或者9，和為9時(shí)所有中間位數(shù)必定都為9。如：黑洞數(shù)495。

為了敘述簡(jiǎn)便，本文加入了邊的概念：

定義 當(dāng)一個(gè)數(shù)滿足規(guī)律1中黑洞數(shù)性質(zhì)時(shí)，則認(rèn)為此數(shù)字在落入黑洞數(shù)的邊上或者黑洞數(shù)中。

規(guī)律2 當(dāng)一個(gè)數(shù)落入黑洞數(shù)的邊上或者黑洞數(shù)中，通過(guò)對(duì)此數(shù)字的重排求差運(yùn)算，很快能得到此數(shù)字產(chǎn)生的所有黑洞數(shù)。如：表中6 619 974為首末位為10的非黑洞數(shù)，符合規(guī)律1條件，只需2次重排求差計(jì)算就落入黑洞數(shù)。

規(guī)律3 對(duì)于任意數(shù)字x，在重排求差運(yùn)算至第二次落入黑洞數(shù)前，運(yùn)算過(guò)程中所得到的數(shù)字序列中所有數(shù)字都只出現(xiàn)一次。不同的數(shù)字間，在落入黑洞數(shù)的邊之前，所得數(shù)字集合必定不同。如：表1中的所有初始數(shù)字，其取落入黑洞數(shù)的邊之前的數(shù)字均不相同。

黑洞數(shù)的性質(zhì)與規(guī)律，表明了對(duì)任意數(shù)字，其重排求差運(yùn)算過(guò)程中直到第二次落入黑洞數(shù)前，得到的數(shù)字是無(wú)序、離散、無(wú)重復(fù)項(xiàng)的混沌序列。隨著不同的初始值，運(yùn)算所得的數(shù)據(jù)具有很大的差異性。對(duì)于位數(shù)較低的x，其黑洞數(shù)相對(duì)較少，長(zhǎng)度較短，無(wú)法取得足夠長(zhǎng)度的混沌序列，并且黑洞數(shù)邊上的數(shù)字具有快速落入黑洞數(shù)的特性。因此，本文算法為提高安全性，由隨機(jī)數(shù)發(fā)生器生成長(zhǎng)度超過(guò)10位的初始值x，然后將x代入黑洞數(shù)發(fā)生器取得偽混沌的運(yùn)算軌跡序列，最后將偽混沌序列遞入logistic算法產(chǎn)生足夠長(zhǎng)的混沌序列對(duì)圖像置亂加密。

3 基于黑洞數(shù)序列和Logistic的圖像加密算法

本文算法通過(guò)黑洞數(shù)發(fā)生器生成具有混沌性質(zhì)的短密鑰流，將其作為L(zhǎng)ogistic算法的初始值，生成混沌密鑰流，截取與圖像相同長(zhǎng)度的加密密鑰流。最后將歸一化的加密密鑰流與置亂后圖像做異或，得到混合加密圖像。算法包括3部分：1) 黑洞數(shù)發(fā)生器生成短混沌序列；2) Logistic混沌加密；3) 圖像解密。流程圖如圖1所示：

圖1 程序流程圖Fig.1 Program flow diagram

3.1 黑洞數(shù)發(fā)生器生成偽混沌序列

由于圖像信息的數(shù)據(jù)儲(chǔ)存格式與系統(tǒng)做運(yùn)算的格式不符，須先對(duì)圖像進(jìn)行歸一化操作才能再加密。將灰度圖像讀入后可得到一個(gè)M*N大小的二維矩陣I，其中各元素是范圍為0～255的整型數(shù)據(jù)。將I降維為一維圖像矩陣IM，其元素?cái)?shù)值是以1/256為階，范圍為[0, 1]的Double型數(shù)據(jù)。圖像歸一化使得圖像像素之間的差異性降低，對(duì)加密的要求降低。

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，對(duì)于初始值K，如果其位數(shù)越短，黑洞數(shù)發(fā)生器可計(jì)算的步驟越少，不足以產(chǎn)生足夠長(zhǎng)的密鑰流，并且K直接在黑洞數(shù)邊或黑洞數(shù)上的幾率較大；當(dāng)K超過(guò)8位，大多隨機(jī)數(shù)可產(chǎn)生足夠長(zhǎng)度的密鑰流，即使不同的K皆落在同一黑洞數(shù)（組）上，不同數(shù)字落入的黑洞數(shù)組的位置也極有可能不同，甚至落入不同的黑洞數(shù)（組）中。所以K的位數(shù)越高，安全性越高。本文認(rèn)為K位數(shù)超過(guò)10時(shí)最佳，在長(zhǎng)度超過(guò)10的情況下，只要不是黑洞數(shù)中的數(shù)值，即使K與某個(gè)黑洞數(shù)的邊相鄰，發(fā)生器產(chǎn)生的序列也是非常安全的。

由隨機(jī)數(shù)發(fā)生器產(chǎn)生一個(gè)位數(shù)大于10的初始數(shù)K，K中每個(gè)位的數(shù)字不能完全相同。為保證黑洞數(shù)發(fā)生器能取得盡可能長(zhǎng)的偽混沌序列，先檢測(cè)K是否在黑洞數(shù)和黑洞數(shù)邊上。對(duì)于不符合要求的K，則由隨機(jī)數(shù)發(fā)生器重新生成K。符合要求的K將作為提取密鑰反饋給用戶，然后將K作為黑洞數(shù)發(fā)生器的初始值代入，運(yùn)行黑洞數(shù)發(fā)生器并記錄每次運(yùn)算結(jié)果，直到運(yùn)算落入第二次循環(huán)時(shí)跳出。所記錄的數(shù)值即為偽混沌序列L，黑洞數(shù)發(fā)生器生成偽混沌序列操作完成。判斷黑洞數(shù)邊的公式流程如下：

步驟1 將密鑰K看作由n (n ≥10)個(gè)一位數(shù)組成的數(shù)組K ={a1, a2,…, an}。

步驟2 判斷K是否在黑洞數(shù)或者黑洞數(shù)邊上：

（1）將K的首末位a1, an代入公式（4），求首末位數(shù)字和，如果1dA值為0（1）則表示首末位和為10（9）；（2）當(dāng)n為偶數(shù)時(shí)，將{a1, a2,…, an}代入公式（5），判斷所得2dA是否為整數(shù)；

（3）當(dāng)n為奇數(shù)時(shí)，將{a1, a2,…, an}代入公式（6），判斷2'dA為是否為整數(shù)且Mi為0。

如果將K代入后并不滿足步驟2中的（1）和（2）或者（1）,（3）時(shí)，說(shuō)明K為遠(yuǎn)離黑洞數(shù)的數(shù)字。此時(shí)K代入黑洞數(shù)發(fā)生器中得到的偽混沌序列更長(zhǎng)，不同K得到的偽混沌序列間的差異性更大。

黑洞數(shù)發(fā)生器取得序列的程序段如下：

for j =1∶30 % 運(yùn)行黑洞數(shù)發(fā)生器30次

if length(K(j))～=length(K(1)) % 判斷位數(shù)，如果發(fā)生器前一次取得數(shù)值如098等，則變?yōu)?80后參與運(yùn)算

adkey(j)=adkey(j)*10^(length(adkey(j))-length(K(1)));

end

key(1)=K(j)； % 賦值給中間變量

for i=1∶len % 將變量中各位數(shù)分離，如Kn={a}轉(zhuǎn)換為K ={a1, a2,…, an}

A(i)=fix(key(i)*10^(i-len));

key(i+1)=key(i)-A(i)*10^(len-i);

end

B=sort(A,'descend'); % 重新排序 降序

B1(1)=0;

for i=1∶len % 重新轉(zhuǎn)換，如{a1, a2,…, an}-＞{a}

B1(1)=B1(1)+B(i)*10^(len-i)；

end

C=sort(A)； % 重新排序 升序

C1(1)=0；

for i=1∶len % 重新轉(zhuǎn)換

C1(1)=C1(1)+C(i)*10^(len-i)；

end

K(j+1)=B1-C1； % 將升序和降序排列做差，并記錄數(shù)值給下一級(jí)Kn+1

end

初值K1通過(guò)時(shí)鐘密鑰key控制的隨機(jī)數(shù)發(fā)生器取得，運(yùn)行黑洞數(shù)發(fā)生器，從記錄得到的K ={K1, K2,…, K30}中，去除循環(huán)數(shù)部分，得到的K ={K1, K2,…, Kn}即為所求的偽混沌序列。

3.2 Logistic混沌加密

本文將偽混沌序列L中元素進(jìn)行歸一化，使序列L中的每一個(gè)數(shù)據(jù)都符合logistic混沌算法的要求，然后將所有數(shù)據(jù)分別代入logistic公式，取得多組混沌序列，將其相連并根據(jù)圖像IM的大小截取相同長(zhǎng)度，得到加密序列XL，將圖像像素加密。此方法的實(shí)現(xiàn)較為簡(jiǎn)單，加密流程如下：

步驟1 將L = (L1, L2,…, Ln)中數(shù)據(jù)進(jìn)行歸一化操作，先全部轉(zhuǎn)為0 ～ 1之間的double型數(shù)據(jù)，取8位有效數(shù)字，如3 847 243 8370.384 724 4，得到L'= {L'1, L'2,…, L'n}。然后將L'n代入公式(7)變換，得到一組logistic參數(shù)λ，λ={λ1,λ2,…,λn}。

步驟2 將L'和λ的元素按組(如L'1和λ1)代入logistic公式（1）并做迭代。迭代次數(shù)i由公式（8）取得：ceil為截尾取整，如果有小數(shù)則在取整后加1。將公式（1）迭代i次，記錄每次結(jié)果，去除前30個(gè)數(shù)據(jù)。代入所有的L'和λ可得到n組混沌密鑰流，根據(jù)圖像大小截取相同長(zhǎng)度的密鑰流，合并為圖像加密矩陣XL。

步驟3 將混沌加密矩陣XL與圖像像素值做異或運(yùn)算生成加密圖像。異或公式見(jiàn)公式(9)：

步驟4 將所得的置亂圖像I 'M由一維矩陣轉(zhuǎn)換成二維矩陣，至此圖像IM經(jīng)過(guò)混合加密得到加密圖像I 'M，加密算法結(jié)束。

3.3 圖像解密

圖像解密的步驟與加密步驟類似，先將提取密鑰key帶入隨機(jī)數(shù)發(fā)生器取得K，將K和加密后的圖像I 'M代入加密逆過(guò)程，把K作為初始值代入黑洞數(shù)發(fā)生器，產(chǎn)生偽混沌序列L'，然后將偽混沌序列L'代入Logistic加密算法取得解密序列XL，將XL與圖像I 'M做異或，提取解密圖像。

4 試驗(yàn)結(jié)果與結(jié)論

本文系統(tǒng)測(cè)試選擇的圖像為“上海SSPU”，像素?cái)?shù)大小為256×256，硬件測(cè)試環(huán)境為CPU 2.6GHz；內(nèi)存512MB；軟件環(huán)境為WINDOWS-XP, MATLAB 7.9.0。測(cè)試結(jié)果見(jiàn)表2。

表2 測(cè)試結(jié)果Tab. 2 The results for test

選擇輸入的時(shí)鐘密鑰為20，分別對(duì)圖像進(jìn)行了加密及置亂，解密效果顯示：無(wú)論是先加密后置亂，還是先置亂后加密，加密后的圖像都有著較高的安全性。仿真結(jié)果表明，該算法運(yùn)算速度較快，具有較高的抗攻擊和抗干擾能力，有一定的實(shí)用性。

測(cè)試結(jié)果表明，黑洞數(shù)發(fā)生器足以產(chǎn)生一定長(zhǎng)度的密鑰流，結(jié)合Logistic進(jìn)行混沌加密的圖像能夠達(dá)到很好的加密效果，具有很高的安全性，隨機(jī)數(shù)發(fā)生器產(chǎn)生的隨機(jī)數(shù)x的位數(shù)對(duì)系統(tǒng)運(yùn)行時(shí)間的影響較小，總體的運(yùn)算時(shí)間極少。

[1] 唐巍, 李殿璞, 陳學(xué)允. 混沌理論及其應(yīng)用研究[J]. 電力系統(tǒng)自動(dòng)化, 2000, 24(7): 67-70.

[2] 何希平, 朱慶生. 基于混沌的圖像小波域加密算法[J]. 計(jì)算機(jī)應(yīng)用, 2007, 27(8): 1895-1897, 1900.

[3] 陸秋琴, 馬亮. 基于logistic映射和正弦混沌映射的交替混沌加密算法[J]. 科技信息: 學(xué)術(shù)版, 2008(12): 106-108.

[4] 許小勇, 樊繼秋, 熊思燦. 一種基于雙混沌序列的數(shù)字圖像加密算法[J]. 科學(xué)技術(shù)與工程, 2010, 10(29): 7307-7309, 7333.

[5] KRAUSE R M, MILLER N, TRIGG C W. Solutions of elemientary problems(Kaprekar's Constant)[J]. American Mathematical Monthly, 1971(78): 197-198.

[6] ELDRIDGE K E, SAGONG S. The determination of Kaprekar convergence and loop convergece of all three-digit numbers[J]. American Mathematical Monthly, 1988(95): 105-112.

[7] 楊之, 張忠輔. 角谷猜想和黑洞數(shù)問(wèn)題的圖論表示[J]. 自然雜志, 1988(6): 453-456, 480.

[8] 黃振國(guó). 黑洞數(shù)的性質(zhì)與它神奇的衍生法[J]. 廣西大學(xué)梧州分校學(xué)報(bào), 2004(1): 62-64.

An Application in Image Encryption Algorithm By Black-Hole Numbers and Logistic Chaos Sequence

YANG Heng-huan1, FENG Tao2, JING Rui1
(1. Department of Computer, Shanghai Science and Technology Management College, Shanghai 200233, P. R. China; 2. School of Adult and Continuing Education, Shanghai Second Polytechnic University, Shanghai 200041, P. R. China)

As the development of information technology, people need more security on image safety. Image encryption is an effective technology for the digital information protection. This thesis introduces a new image encryption algorithm based on Black-hole numbers and Logistic chaos sequence. By research the Black-hole number, it can have a chaos sequence and the chaos sequence which will be sent into Logistic algorithm as the initial parameters. Then the algorithm can generate chaotic key stream for image encryption. The result shows that the system runs fastly and security of the image encryption is very high.

Black-hole; Logistic algorithm; Image encryption

TP391.41

A

1001-4543(2011)04-0287-06

2011-04-06;

2011-10-08

楊恒歡（1988－），男，江蘇無(wú)錫人，學(xué)士，主要研究方向?yàn)閳D像圖形學(xué)應(yīng)用與信息系統(tǒng)安全，電子郵箱yanghenghuan@hotmail.com。