基于混沌序列加權抽樣和排序變換的圖像置亂

曹光輝 胡 凱

(北京航空航天大學 計算機學院，北京100191)

隨著互聯網和多媒體技術的飛速發展，當今社會已經進入了一個全新的網絡化和數字化時代.通過網絡傳輸的多媒體信息防御主動和被動攻擊的重要性越來越引起人們的關注.圖像作為通過網絡傳輸的主要內容之一，其安全性位列其中.目前，信息加密是保護圖像信息的主要手段，但傳統的加密技術適用于具有類似單鏈表結構的普通數據流，圖像是一種八連通結構，像素間具有很強的相關性，這種結構的差異，使置亂成為對圖像加密預處理的一種重要技術.當然，圖像置亂除用于數字圖像加密方法預處理外，也常用于更復雜的隱藏與數字水印的預處理或后處理，以增加隱藏和抗攻擊能力.目前，已經有多種置亂算法可供選擇，例如Baker映射方法［1］、高維Arnold變換和 Fibonacci-Q 變換［2］、Hilbert方法、元胞自動機方法、仿射變換、幻方變換、騎士巡游變換、混沌二叉樹遍歷方法、混沌位置交換方法［3］、混沌排序方法［4］等，而且新的數字圖像置亂算法可能被不斷的提出.在這些方法中，混沌排序方法因充分利用混沌非周期、初值敏感等特性，并且算法對混沌數據一次性處理，使用簡單，安全性高，被廣泛使用，但存在密鑰空間不足，置亂度低，易受重構攻擊等缺點.為了克服這些不足，本文以一類典型的混沌排序方法——Ye算法［4］為例給予研究.

1 Ye算法流程概述

1)讀入圖像并且以十進制矩陣A的形式表示，A矩陣大小為M×N;

2)把A矩陣所有元素，都轉化為二進制數，形成二進制矩陣B，大小為M×8N;

3)利用Logistic方程:生成合適長度的混沌序列X，對該混沌序列進行排序，得到新的序列X1，找到新序列X1中每一個元素在原序列中的位置，生成位置向量，記為T;

4)依據向量T重新排列矩陣B的所有行，生成矩陣B1;

5)類似于步驟 3)，生成位置向量 Vi，i∈［1，M］，每一個Vi，元素個數為8N;

6)依據對應的位置向量Vi，對矩陣B1的每一行元素置亂，得到矩陣C;

7)把二進制表示的C矩陣，以8 bit為一組，轉換為十進制表示的矩陣D，置亂過程結束.

2 Ye算法置亂強度分析

為了研究Ye算法置亂強度，首先對如下置亂實例進行實驗:生成矩陣A，取Logistic控制參數r=3.65，初值x0=0.55，應用Ye算法，對原始矩陣A以矩陣元素為單位置亂，得到B矩陣.可以看到，B矩陣第2、第3行對應列位置僅有3個元素不同，第4、第5行置亂結果完全相同.結果表明:相鄰兩行整體模式匹配度高，B矩陣每一列并不是均勻分布，新模式出現的隨機性有待改進.為了進一步揭示Ye算法置亂的水平，下面首先設計置亂強度測試算法，然后應用該算法分析Ye算法置亂強度.

目前，置亂強度測試算法很多［5］，主要基于置亂后像素值的某種表現，這些算法不能避免不同位置的相同像素值對置亂強度測試產生的影響.本文為避免置亂強度測試與具體像素值相關，提出如下的設計規則和相應算法.

2.1 設計置亂測試算法原則

1)因為置亂是數據位置的改變，與實際置亂內容值無關，應該致力于衡量被置亂對象相對位置改變的程度;

2)評估應能反映置亂方案的特征.

2.2 置亂測試算法

依據這個原則，設計了針對基于混沌排序置亂算法的均勻隨機置亂測試算法，步驟如下:

1)生成大小為m×n的原始測試矩陣A=［ai，j］，其中 A(:，i)=i，i∈［1，n］;

2)應用Ye算法，對矩陣的每一行置亂;

3)統計矩陣每一列包含數字1的數目，2的數目，…，n的數目;

5)計算所有列通過卡方測試比率:η=n0/n×100%，n0為卡方檢驗接受的次數.

2.3 實驗結果

為了與常見256×256圖像數據量一致，實驗數據量取m=256，n=256×8.應用置亂測試算法，對Ye算法進行測試，實驗結果如表1所示.

表1 Ye算法置亂強度測試通過率

從表1可見，Ye算法置亂強度主要受混沌控制參數影響.當控制參數一定時，初值對置亂強度造成小范圍波動.這些控制參數，有的能使Ye算法具有很好的整體置亂水平，如 r1，r4，r5，有的則使Ye算法置亂水平很低，如r0，r2，r3.如何使基于混沌排序置亂算法的置亂水平不受或少受控制參數影響，成為本文探究的目標.

3 等間隔混沌序列圖像置亂

3.1 等間隔混沌序列置亂算法強度分析

Ye算法關鍵思想是首先產生混沌序列，然后對混沌序列排序，生成位置向量，驅動數據置亂.混沌序列的生成模式決定了數據置亂強度.本文嘗試使用基于某種規則，對混沌原始序列抽樣，形成新的混沌序列，那么，基于什么樣的規則成為本文探究的對象.本文分別探究基于1次、2次、3次間隔抽樣的方法生成新的混沌序列，進行排序和置亂，置亂強度測試結果見表2.

表2 等間隔混沌序列置亂算法置亂強度

從實驗結果可見:

1)總體而言，在抽樣間隔確定的條件下，Logistic映射參數控制卡方測試通過率的幅度，但不排除個別奇異點(如參數為4.0情況);初值變化對卡方測試通過率幅度造成一定波動.其他m×n×8形狀的數據矩陣，也給予實驗，得到類似的結果.

2)奇數次間隔抽樣產生的混沌序列對原始Ye算法置亂強度測試通過率達到90%的系統，效果不顯著，對強度測試通過率低于90%的系統，效果顯著提高.對于偶數次間隔抽樣形成的置亂系統，強度測試通過率與使用混沌原始序列效果相當.

3)在基于抽樣混沌序列排序的圖像置亂算法中，影響系統置亂程度的因素從強到弱排序:抽樣間隔大小＞系統控制參數＞系統初值.因此，本文建議置亂系統密鑰組成為(抽樣間隔大小，控制參數，系統初值).

3.2 混沌間隔抽樣提高置亂強度的機理

下面采用近似熵方法對混沌序列間隔抽樣提高圖像置亂強度的原因進行分析.

3.2.1 近似熵理論

近似熵(ApEn)由Pincus于1991年提出，并在度量混沌時間序列復雜性方面得到廣泛應用，其主要思想是基于一維序列進行多維相空間的重構，描述維數由m增加至m+1時產生新模式的概率，即表示前一數據對后一數據的可預測性，定量描述時間序列的可重復性、系統運動的復雜性和無序程度，是時間序列結構相似性的度量方法.ApEn值越大，表明時間序列越具有隨機性或不規則性，其非周期性越強，復雜度越高;ApEn值越小，表明數據周期性越強，確定性越大，復雜度越小.基于此原理，本文采用近似熵測量混沌序列間隔抽樣熵值走勢，找出置亂強度增加的內在動力.

3.2.2 實驗結果及分析

本文采用經典近似熵算法，分別對基于1次、2次、3次間隔抽樣生成的混沌序列，進行近似熵值計算，計算結果見表3.

表3 單一間隔混沌序列近似熵分析

近似熵維數m=2，閾值等于0.2倍標準差，抽樣得到序列長度1000.

從表3中的實驗數據可見，混沌序列間隔抽樣能夠一定程度提高序列近似熵，在一定范圍內，抽樣間隔間距越大，近似熵越大.但值得一提的是，雖然偶數次抽樣混沌序列能提高近似熵值，但由于混沌序列特有的伸展收縮特性使得形成的二次混沌序列具有明顯的大數小數連接模式，這樣引入排序后，偶數次間隔抽樣混沌序列產生的模式與原始序列產生的模式效果相當.故在基于混沌排序置亂算法中，對圖像置亂產生的效果，表現很一般，使用中偶數次抽樣間隔產生序列給予忽略.

3.2.3 近似熵走勢分析

為了研究近似熵與抽樣間隔大小的關系，近似熵走勢實驗被設計.實驗參數如下:圖1中Logistic控制參數r=3.75，初值x0=0.85，抽樣間隔由0間隔抽樣到間隔100次取一次，每個種類間隔抽樣1000次;圖2中Logistic控制參數r=4，初值x0=0.55，抽樣間隔由0間隔到間隔100次抽樣一次，每個種類間隔抽樣1000次.

圖1 r=3.75近似熵走勢

圖2 r=4近似熵走勢

由圖1和圖2可見，隨著間隔抽樣次數的增加，信息熵會在一定范圍內波動，但不會一直增加下去.

3.2.4總結

上述實驗說明，采用間隔抽樣可以提高序列不規則模式出現的概率，進而能夠提高置亂強度，同時，近似熵增加到一定值后，隨抽樣間隔的增加上下波動.這可以解釋混沌序列間隔抽樣可以提高基于混沌排序置亂算法的置亂強度.

采用單一抽樣間隔盡管能夠提高置亂算法的置亂強度，但不能提高算法的密鑰空間，故本文進一步給出基于加權間隔抽樣的圖像置亂算法.

4 加權抽樣混沌圖像置亂

根據對Ye算法置亂強度的定量分析發現，由原始混沌序列抽樣后形成新的混沌序列用于置亂數據可以提高置亂強度，故本文設計的置亂系統引入抽樣間隔參數.考慮抽樣間隔次數的多樣性，引入抽樣加權機制，由用戶指定概率決定每個抽樣間隔出現的次數，其中隨機源由修正Logistic映射生成［3］.

4.1 加權系統思想

加權保密系統最早由Shannon［6］提出.假設2個保密系統T和R，常用不同的方式形成新的保密系統S.如果T和R具有相同的消息空間，可以形成一類加權和S=pT+qR，這里p+q=1.這個操作首先對概率p和q做出選擇，用以決定T和R哪一個被使用.這個選擇是系統S密鑰的一部分.選擇之后，T或R被用作原始的定義.系統S的整個密鑰必須指定T和R哪一個系統被使用，以及T或R的哪個密鑰被使用.這個加權系統的一般形式如下:

4.2 加權抽樣混沌排序圖像置亂算法

系統使用2個Logistic映射，一個用于確定混沌序列抽樣間隔數，叫修正Logistic映射［3］，方程如下:

一個用于生成混沌間隔抽樣序列，叫主Logistic映射，方程是式(1).

4.2.1 隨機抽樣間隔的選擇

本文使用的加權置亂系統如下:

其中，pi由用戶指定或系統設定;θi由公式(3)求出.

應用修正Logistic映射，生成隨機數ρ，如果ρ∈［θi-1，θi)，則進行與概率 pi對應的間隔抽樣.p1對應混沌序列1次間隔抽樣，p2對應混沌序列3次間隔抽樣，p3對應混沌序列5次間隔抽樣.R，U，T使用同一主Logistic映射，區別在于生成不同抽樣間隔的混沌序列.

4.2.2 加權抽樣混沌序列置亂算法

步驟如下:

1)應用修正Logistic映射生成隨機值ρ，根據該隨機值，按照4.2.1節確定抽樣間隔，使用主Logistic映射生成具有該抽樣間隔的混沌隨機序列;

2)依據基于混沌排序的數據集置亂算法，應用步驟1)生成的混沌序列對圖像進行行置亂;

3)應用修正Logistic映射生成新的隨機數，根據該隨機數，按照4.2.1節選擇抽樣間隔，使用主Logistic映射生成具有該抽樣間隔的混沌隨機序列;

4)依據基于混沌排序的數據集置亂算法，應用步驟3)生成的混沌序列對圖像每一行的所有像素比特進行列置亂;

5)重復步驟3)和步驟4)直到圖像的最后一行完成為止.

算法框圖如圖3所示.

圖3 建議算法框圖

5 實驗結果

為驗證本文的算法，對大量各類圖像進行了實驗，取得了很好的結果.圖4給出粗紋理圖像的實驗結果.

從圖像的置亂結果可見，本文設計的加權抽樣置亂算法能夠很好地打亂原始圖像的八連通結構;從置亂圖像空間直方圖可見，原始圖像的相關性被很好地去除，空間分布顯示出置亂像素分布的均勻性.這些實驗結果表明本文設計的算法達到了打亂原始圖像八連通結構，去除相關性的目的，為進一步圖像加密和數字水印奠定了很好的基礎.

圖4 粗紋理圖像置亂效果

6 加權抽樣置亂算法安全性分析

6.1 密鑰空間

本文建議的圖像置亂系統應用2個Logistic映射方程，一個是產生混沌均勻分布序列的修正Logistic映射，用于按用戶指定的概率選擇混沌抽樣間隔的大小，一個是依據選擇的抽樣間隔生成混沌序列用于置亂圖像.因此，密鑰空間為2個Logistic方程的初值，2個控制參數，以及概率pi的選擇.與Ye算法比較，密鑰空間是原來的2倍多.

6.2 抗重構攻擊

利用混沌進行圖像置亂存在重構攻擊的可能.相空間重構的基本思想是一個結構復雜的系統可以用相空間中的吸引子來描述.Takens從理論上給予證明，并提出了著名的嵌入定理.

從該定理可知，已知的觀測序列是等間隔采樣，如果是不等間隔采樣，定理不成立.結合本文用于置亂圖像的混沌序列，可分為2種情況討論:

1)當攻擊者獲得的觀測序列是非等間隔采樣序列時，依照嵌入定理恢復出的動力系統是錯誤的，無法進行相空間重構.

2)當攻擊者獲得的觀測序列是等間隔采樣序列時，合理選擇嵌入維數m和延遲時間τd，應用文獻［7］理論上可以恢復原非線性動力系統，但依照等間隔生成的混沌序列破解置亂圖像是失敗的，因為本文設計的是混沌非等間隔抽樣序列置亂圖像，混沌抽樣序列間隔依靠另一個系統產生的概率決定，并不是使用閉合混沌迭代序列驅動圖像置亂.另外，由于本文使用間隔抽樣混沌序列，當間隔長度使抽樣序列成為欠采樣序列時，依據文獻［8］可知，混沌序列預測能力大大降低，是否能夠進行相空間重構目前還沒有相關研究.

綜上所述，本文設計的圖像置亂系統具有抗重構攻擊的能力.

6.3 加權間隔抽樣置亂算法置亂強度分析

表4給出應用本文設計的置亂強度測試算法對加權抽樣混沌置亂圖像算法進行置亂強度測試的實驗結果.

比較表1和表4的實驗結果可見，本文建議的圖像置亂算法的置亂強度遠遠優于Ye算法的置亂強度，進一步證實了加權抽樣混沌序列能夠提高圖像置亂效果.

表4 建議算法置亂強度測試

7 結論

基于混沌的圖像置亂是當前信息安全領域的一類熱點話題.本文研究了一類典型的基于混沌排序圖像置亂算法——Ye算法.首先給出Ye算法的簡單描述，然后針對該算法，給出與置亂對象無關的置亂強度測試算法.探索發現間隔抽樣混沌序列可以提高Ye算法置亂度，并用近似熵給出其理論依據.為增加密鑰空間，設計了基于加權采樣混沌排序的圖像置亂算法，該方法密鑰空間大，置亂強度高，抗重構攻擊.本文僅針對基于混沌排序置亂算法給出基于位置的置亂強度測試方法，如何設計與置亂對象無關的適合任何圖像置亂算法的強度測試算法是作者努力的方向.

致謝感謝Michigan State University的佟維博士與作者的密切交流與合作.

References)

［1］ Fridrich J.Symmetric ciphers based on two-dimensional chaotic maps［J］.International Journal of Bifurcation and Chaos，1998，8(6):1259-1284

［2］ Sun Fuyan，Liu Shutang，Lü Zongwang.Image encryption using high-dimension chaotic system［J］.Chinese Physics，2007，16(12):3616-3623

［3］曹光輝，胡凱，佟維.基于Logistic均勻分布圖像置亂方法［J］.物理學報，2011，60(11):110508-8 Cao Guanghui，Hu Kai，Tong Wei.Logistic uniform distribution based image scrambling ［J］.Acta Physica Sinica，2011，60(11):110508-8(in Chinese)

［4］ Ye Gongdong.Scrambling encryption algorithm of pixel bit based on chaos map［J］.Pattern Recognition Letters，2010，31(5):347-354

［5］陳燕梅，張勝元.基于交叉熵的數字圖像置亂程度評價方法［J］.中國圖象圖形學報，2007，12(6):997-1001 Chen Yanmei，Zhang Shengyuan.Digital image scrambling degree evaluation method based on cross entropy［J］.Journal of Image and Graphics，2007，12(6):997-1001(in Chinese)

［6］ Shannon C E.Communication theory of secrecy systems［J］.Bell System Technical Journal，1949，28:656-715

［7］李鶴，楊周，張一民，等.基于徑向基神經網絡預測的混沌時間序列嵌入維數估計方法［J］.物理學報，2011，60(7):070502-6 Li He，Yang Zhou，Zhang Yimin，et al.Methodology of estimating the embedding dimension in chaos time series based on the prediction performance of radial basis function neural networks［J］.Acta Physica Sinica，2011，60(7):070502-6(in Chinese)

［8］ Barahona M，Poon G S.Detection of nonlinear dynamics in short noisy time series［J］.Nature，1996，381:215-217