楊恒歡，馮 濤，荊 銳

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

文獻[8]通過數(shù)學論證，證明了黑洞數(shù)具有3個性質(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) 對于任意黑洞數(shù)必定首末位和為10或者9，和為9時所有中間位數(shù)必定都為9。如：黑洞數(shù)495。

為了敘述簡便，本文加入了邊的概念：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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ù)值給下一級Kn+1

end

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

3.2 Logistic混沌加密

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

步驟1 將L = (L1, L2,…, Ln)中數(shù)據(jù)進行歸一化操作，先全部轉(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個數(shù)據(jù)。代入所有的L'和λ可得到n組混沌密鑰流，根據(jù)圖像大小截取相同長度的密鑰流，合并為圖像加密矩陣XL。

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

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

3.3 圖像解密

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

4 試驗結(jié)果與結(jié)論

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

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

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

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

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

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

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

[4] 許小勇, 樊繼秋, 熊思燦. 一種基于雙混沌序列的數(shù)字圖像加密算法[J]. 科學技術(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ù)問題的圖論表示[J]. 自然雜志, 1988(6): 453-456, 480.

[8] 黃振國. 黑洞數(shù)的性質(zhì)與它神奇的衍生法[J]. 廣西大學梧州分校學報, 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－），男，江蘇無錫人，學士，主要研究方向為圖像圖形學應(yīng)用與信息系統(tǒng)安全，電子郵箱yanghenghuan@hotmail.com。