一個迭代函數系統的分形混沌特性及其應用

摘" 要" 介紹迭代函數系統生成分形的原理以及分形位移動力系統的混沌特性. 構造了一個迭代函數系統，用于生成充滿整個單位正方形的填充曲線，理論上證明該迭代函數系統的分形位移動力系統的Devaney混沌特性. 將該迭代函數系統的分形位移動力系統參數化，數值上驗證該分形位移動力系統的混沌性能，并使用該混沌系統設計了一個基于DNA運算的混沌圖像加密算法，詳細分析了該加密算法的安全性.

關鍵詞" 迭代函數系統，分形，填充曲線，混沌，動力系統，圖像加密

中圖分類號" TP309.7" " 文獻標識碼" A

1" 引" 言

混沌和分形作為非線性科學中兩個非常重要的研究分支，經過數十年的發展，現在已經深入到各個學科的諸多研究領域，其重要性不言而喻. 混沌系統經常以分形的形態演繹其混沌性質，可以說是時間上的分形；分形實際上也來自混沌系統的演化，可以說是空間上的混沌. 分形和混沌就像一對孿生姐妹，相隨誕生自動力系統這樣一個母體. 從其誕生之日起，兩者互相促進，共同成長. 混沌理論研究動力系統對初始條件高度敏感的動力學行為，試圖解釋這樣一個事實，復雜和不可預測的結果可能會發生在對初始條件敏感的動力系統中. 這種敏感性通常有一個優雅的稱呼：蝴蝶效應. 一個通俗的例子就是，中國北京的一只蝴蝶扇動一下翅膀，可以影響到美國紐約幾天之后的天氣模式，可能造成一場災難式的龍卷風. 換言之，很小的事件可能會引發一系列越來越重要的事件，從而產生不可預測的、有時甚至是極端的結果. 初始條件的微小差異（如數值計算中舍入誤差引起的差異）會極大地改變系統的長期行為，從而使長期預測在一般情況下變得艱難甚至不可能. 我們身邊的許多例子很生動地刻畫了混沌特性，例如水龍頭滴水、云層形成、天氣變化、人類心臟顫動以及單擺在磁鐵影響下的運動，等等. 混沌系統的長期行為看起來像是隨機，但實際上是確定性的，這意味著它們未來的動力學完全由其初始條件決定，不涉及隨機因素. 這些系統對初始條件非常敏感，使系統在有限精度的計算中變得不可預測，但系統具有秩序感和模式感. 由于計算機技術的快速發展，混沌理論已經發展成為科學、數學、藝術和計算世界中非常重要的組成部分[1-4].

分形和混沌之間有著緊密的天然聯系，大多數分形從幾何角度描述了自然界中存在的混沌系統. 分形集合是一種粗糙或零碎的幾何形狀，可以分割成多個部分，每個部分是整體（至少近似）的縮小副本，這一特性稱為自相似性. 數學家Mandelbrot在20世紀70年代創立了分形幾何學，其中分形的英文詞匯fractal來源于拉丁語fractus，意為“破碎”或“斷裂”. 分形幾何是更適合描述自然界中混沌系統的一種新型幾何學. 自然界的大多數物理現象和結構都無法用歐氏集合中標準規則的幾何形狀來刻畫. 盡管歐氏幾何可以很容易地定義比較平滑的幾何對象，但如果你想對河流、山脈、云朵、樹林、閃電等復雜對象建模，歐氏幾何變得很吃力甚至無能為力，因為這些自然界的對象是一些非常不平滑、高度結構化的幾何對象. 分形幾何為描述、測量和預測這些自然現象提供了方便簡潔的方法，是許多自然形態的最佳數學描述. 不僅如此，分形還呈現了其奇特的藝術氣質和魅力，許多人因為迷戀分形的美麗圖案，因而投入更多的時間到分形的娛樂、學習和研究中. 分形幾何超越了數學作為復雜、枯燥的公式的典型認知，將藝術與數學相結合，證明了數學不僅僅是一組組冰冷的數字和令人畏懼的符號[4-6].

分形幾何和混沌理論之間的聯系需要得到深入的研究，其中的應用更是值得開發. 在本文中，我們將從迭代函數系統的角度入手，從理論上研究了如何生成其對應的分形圖像及其伴隨的位移動力系統的混沌特性. 結合分形混沌系統的研究結論，我們提供了一個圖像信息安全方面的置亂加密應用方案，顯示分形混沌理論的應用價值. 首先介紹迭代函數系統（簡稱IFS），并探討與IFS相關的位移動力系統. IFS是生成分形的常用技術之一[7-8]. IFS在分形幾何中扮演非常重要的角色，對分形理論的發展起了非常關鍵的作用. IFS在物理學、工程技術、生物學、地質學、金融學等不同領域中具有很多應用的背景；它在計算機圖形和圖像處理，特別是在自然景觀模擬，動漫場景快速生成和數字圖像壓縮等研究領域更是一種難得的方法和工具[9-10]. 本文從理論和數值上分析了一個IFS及其伴隨的分形位移動力系統的混沌動力學性質. 將所構造的IFS所對應的伴隨位移動力系統用于生成偽隨機性優良的密鑰流，控制圖像加密算法的置亂和擴散過程，開發了分形混沌動力系統的新應用領域[11].

隨著過去幾十年數字圖像處理技術、多媒體應用和網絡通信的快速發展，電子出版和數字多媒體數據通過互聯網絡、智能手機等無線網絡廣泛傳播共享. 如何防止網上分享傳播的私密信息數據泄漏已成為當務之急. 例如軍事圖像數據庫、機密視頻會議，醫學成像系統、在線私人相冊等需要可靠、快速和穩健的安全系統來存儲和傳輸數字圖像. 滿足數字圖像安全的需求促進了有效圖像加密算法的研究和開發. 數字圖像具有一些固有特征，例如數據海量、數據冗余、相鄰像素的強相關性、與文本數據相比不那么敏感等等. 傳統的加密算法（如DES、RSA等）由于在加密圖像時效率低的弱點，不再適合于具有實時要求的數字圖像加密實際應用[12]. 幸運的是，混沌系統具有遍歷性、不可預測性、偽隨機性等優良性能，基于混沌系統所設計的圖像加密算法因此備受關注，混沌圖像加密算法也不斷展現出其優越的性能和應用潛力. 眾所周知，性能優異的密碼系統要求對密鑰和明文極端敏感，并且這是密碼學的混淆和擴散基本要求. 混沌系統正好擁有和這些基本要求高度一致的混沌特性，這使得混沌系統成為圖像加密算法設計中非常具有競爭力的選項[13-20].

自從1998年Fridrich在文獻[13]首次使用混沌映射設計圖像加密算法以來，許多基于混沌的圖像加密算法陸續涌現. 混沌系統以確定性方式很好地模擬隨機行為，特別地，混沌映射很容易在計算機中模擬實現. 因此，混沌密碼系統通常具有高速度和低成本的優勢，這使得它們比許多傳統密碼更適合用于圖像數據的加密. 在基于混沌的經典加密方案中，一維和二維混沌系統，如Logistic映射[20]，Arnold映射[17，21]，斜帳篷映射[22-23]，面包師映射[14]，標準映射[15-16，24]和Henon映射[25]，由于實現簡單的優點而被廣泛應用. 但是，一維混沌系統一般存在密鑰空間小、安全性薄弱的嚴重缺陷. 基于低維混沌系統的圖像加密算法容易遭遇密碼分析學者或黑客的破解[26-29]. 密碼學要求一個好的加密方案應該對密碼系統的密鑰高度敏感，使得密鑰空間足夠大，可以有效抵御蠻力攻擊；密碼學也要求混淆和擴散過程應具有優良的作用機制，使得密文圖像具有優良的統計性能，可以有效挫敗差分攻擊、已知明文和選擇明文攻擊等密碼學分析. 因此，許多密碼學專家致力于開發改進的基于混沌的密碼系統，一方面使其具有巨大的密鑰空間，另一方面使加密算法中的擴散機制更加可靠. 雖然構造高維超混沌系統，可以生成復雜的偽隨機混沌序列，并且高維超混沌系統具有多個維度的初始值和系統參數可以作為密鑰選擇，使得密鑰空間得到很大的提高，但是其計算效率明顯不如低維混沌系統[30-32]. 綜合考慮計算復雜度和加密安全性兩者的平衡，二維混沌動力系統是一種較合適的選擇，其中的初始值和參數可以作為密鑰使用，取得較好的安全性能和計算效率[33-34].

近年來，由于DNA運算具有大規模并行性、巨大存儲等良好特性，研究密碼的學者提出了基于混沌系統和DNA編碼運算相結合的圖像加密算法，取得了很好的加密性能和安全性. 文獻[35]利用正弦映射和分段線性映射的復合構造了一個具有更好混沌特性的混沌系統，并基于該混沌系統和DNA編碼設計了一個新的圖像加密算法. 數值實驗表明，所提出的加密算法具有良好的安全性能. 文獻[36]基于DNA運算和混沌系統提出了一種新的彩色圖像加密算法. 通過DNA編碼明文圖像獲得DNA矩陣，計算DNA矩陣的漢明距離和圓距離，并通過混沌系統生成控制加密和解密過程的密鑰流，利用DNA異或、加法和減法運算實現加密，獲取密文圖像. 模擬和安全分析表明，所提出的算法具有很高的安全性和很好的抵御選擇明文攻擊、已知明文攻擊、差分攻擊和統計分析攻擊等能力.

本文在應用部分提出了一種基于分形位移動力系統和DNA運算相結合的圖像加密算法. 利用一個迭代函數系統誘導得到一個分形上的混沌動力系統，并對該動力系統進行軌跡、分叉圖、李雅普諾夫指數等的性能分析，結果表明該分形位移動力系統具有優良的混沌特性. 為了保證加密圖像的安全性，加密算法采用置亂和擴散兩種過程實現加密操作. 在置亂過程，加密算法構造了一種新的填充曲線，用來對圖像進行掃描置亂，另外采用分形位移動力系統所生成的混沌序列進行排序得到的位置索引進一步對明文圖像置亂，從而很大程度上打亂了像素的位置，破壞相鄰像素的相關性. 為了改變像素的亮度值，利用分形位移動力系統生成偽隨機數序列，量化生成加密算法的密鑰流，對圖像進行動態的DNA編碼、運算與解碼，實現圖像的像素亮度值擴散操作. 生成的灰度值密鑰流敏感依賴分形位移動力系統的參數以及初始條件，同時也強烈依賴于所處理的明文圖像，因此所提出的加密方案可以很好地抵抗暴力攻擊、統計分析攻擊、差分攻擊、已知明文攻擊以及選擇明文攻擊等. 仿真實驗進行了密鑰敏感性、統計特性、差分攻擊、噪聲攻擊和剪切攻擊等的分析，結果均顯示本文所提出的加密算法具有優良的加密效果和安全性，可用于圖像和視頻通信的安全應用領域.

本文的主要貢獻表現為如下的幾個方面. （1）利用迭代函數系統生成單位正方形上的混沌動力系統，理論上證明該混沌系統具有Devaney混沌特性，并從數值上驗證了系統具有優良的混沌特性. （2）利用迭代函數系統設計一種新型的圖像像素掃描置亂算法. （3）擴散過程采用動態的DNA編碼和運算實現，提高了加密算法的安全性. （4）通過Hash函數獲取圖像的摘要信息，進一步改變分形位移動力系統的初值和系統參數，導致生成的混沌序列與明文高度相關. 這意味著即使使用相同的密鑰，加密不同的明文圖像時密鑰流也會產生巨大的不同，攻擊者無法通過已知/選擇明文攻擊獲取任何有用的信息. 因此，本文提出的圖像加密算法具有自適應的特性，可以達到一次一密的加密效果.

本文的其余部分組織如下. 第2節將介紹迭代函數系統及其分形位移動力系統的一些預備知識和結論. 第3節將對參數化迭代函數系統所生成的分形做仿真實驗，演繹單位正方形上的填充曲線的生成；對伴隨于IFS的分形位移動力系統的混沌特性做理論上的證明，并從數值上仿真驗證其優良的混沌特性. 第4節研究分形位移動力系統在圖像信息安全領域中的應用，提供了兩種方面的應用. 其一是以分形填充曲線為工具，設計一種置亂圖像像素位置的方法；其二是利用分形位移動力系統生成混沌序列密鑰流，控制圖像加密算法中的擴散過程. 將置亂和擴散綜合構成一個新的圖像加密算法. 第5節對圖像加密算法進行詳細的性能分析，評估了所構造的圖像加密算法的安全性和加密性能. 第6節對全文的內容做總結.

2" 預備知識

設（X，d）為一個度量空間，（H（X），h）為（X，d）的所有非空緊子集所組成的Hausdorff度量空間，其度量記為h.

定義1. 一個壓縮的迭代函數系統由一個完備的度量空間（X，d）和一個有限的壓縮映射集Wn ： X→X，n＝1，2，？噎，N及其相應的壓縮因子0≤sn＜1所組成，記為{X ; Wn ： n＝1，2，…，N}，壓縮因子為s＝max{s1，？噎，sn}.

分形幾何理論確保了下面的定理1成立.

定理1[6]. 設{X ; Wn ： n＝1，2，？噎，N}是擁有壓縮因子s的壓縮迭代函數系統，則定義如W（B）＝■Wn（B），B∈H（X）的變換W ： H（X）→H（X）是完備度量空間（H（X），h）上具有壓縮因子s的壓縮映射，即h（W（A），W（B））≤sh（A，B），■A，B∈H（X），其唯一不動點P∈H（X）滿足

P＝W（P）＝■Wn（P），P＝■Wn（B），■B∈H（X）.

不動點P也稱為IFS的吸引子（分形）.

生成分形的確定性算法. 定理1是生成分形的確定性算法的理論基礎. 任選一個初始緊集E0，然后迭代計算En＝Wn（E0），當n較大時，En將給出迭代函數系統的分形吸引子P的良好逼近圖像.

生成分形的另一種算法是基于遍歷理論的隨機算法，分形圖像是由隨機迭代算法給出的，這種算法在原來的IFS中增加一組概率，稱為帶概率的迭代函數系統（簡記為IFSP）.

定義2. 一個帶概率的壓縮迭代函數系統IFSP由一個IFS{X ; Wn ： n＝1，2，？噎，N}與一組概率{ pn}N" " n＝1組成，其中■pn＝1，pn＞0，n＝1，2，？噎，N，而每個概率pn對應于變換Wn，將一個IFSP記為{X ; Wn，pn ： n＝1，2，？噎，N}. 在X＝R2的情況下，映射通常采用仿射變換的形式

Wn x y＝ an" " "bb cn" " "dn x y＋ en" fn，pn＝■＝■.

若對某個An＝0，則pn可取一小數，如0.001，然后適當調整概率集.

生成分形的隨機迭代算法. 令{X ; Wn，pn ： n＝1，2，？噎，N}是一個壓縮IFSP，任取x0∈X進行隨機迭代. 在第k次迭代時，根據概率集{ p1，？噎，pN}產生隨機數ik∈{1，2，？噎，N}，選取仿射變換Wi■進行迭代生成點序列xk＝Wi■（xk－1），k＝1，2，？噎. 去掉序列前面的若干過渡點，剩余的點列將逼近IFS的分形.

確定性算法在生成分形時將花費更多的時間，但是其生成過程中得到的緊集序列清晰演繹了分形的逼近圖形序列. 隨機迭代算法生成分形會更省時，但是由于生成過程所產生的點序列是隨機迭代得到的，所以沒有明確的規律可言，無法像確定性算法那樣生成一些預期的序列圖像.

定義3. 設（X，d）為度量空間，f ： X→X是從X到自身的映射. 對任意x0∈X，在f的迭代作用下，生成xk＋1＝f（xk）＝f k（x0），k＝0，1，？噎，稱為x0的前向軌道，記為O＋f（x0）＝{xk＝f k（x0），k＝0，1，？噎}. xk＋1＝f（xk），k＝0，1，？噎確定了一個離散動力系統，記為{X； f }.

定義4[3]. 度量空間（X，d）上連續自映射動力系統f ： X→X稱為Devaney混沌，如果滿足下面三個條件：

（a） f具有拓撲傳遞性，即存在x0∈X，使得x0的軌道在X稠密；

（b） f具有初值敏感依賴性，即存在ε＞0，使得對任意x∈X及？啄＞0，在x的？啄－鄰域（x，？啄）中總存在y以及n≥0，使得d（f n（x），f n（y））＞ε；

（c） f的周期點集合在X上稠密.

利用動力系統可以演繹混沌和分形現象，本文將研究壓縮IFS中蘊涵的分形與混沌現象. 我們將介紹一種特殊類型的動力系統，稱之為分形位移動力系統，該類動力系統由IFS誘導得到. 通過研究分形位移動力系統的軌道，我們將跨越分形圖形，挖掘到更多關于分形位移動力系統的混沌特性，闡釋了為什么混沌和分形通常會一起出現的現象.

定義5. 設{X ; Wn ： n＝1，2，？噎，N}是一個壓縮的IFS，伴隨于該IFS的碼空間（■，dc）定義為N符號的符號空間，其度量為

dc（■，σ）＝■■，■■，σ∈■，■＝■1■2…，σ＝σ1σ2？噎.

伴隨于IFS的碼空間和IFS的吸引子之間存在密切的關系. 這種關系可以通過一個連續變換？準來實現. 定理2陳述了？準的構造細節.

定理2[37]. 設（X，d）為一個完備的度量空間，{X ; Wn ： n＝1，2，？噎，N}是擁有壓縮因子s的IFS，其對應的分形為A；（■，dc）為伴隨于該IFS的碼空間. 對每個σ∈■，k∈Z＋，x∈X，Z＋是正整數集合，定義？準（σ，k，x）＝Wσ■Wσ■？噎Wσ■（x）. 則？準（σ）＝■？準（σ，k，x）存在且屬于A，并且與A無關；？準" ：" ■→A為連續映上的映射.

定義6給出IFS的分類，可以根據IFS的分類對迭代函數系統相關的分形位移動力系統做理論分析.

定義6. 設（X，d）為一個完備的度量空間，{X ; Wn ： n＝1，2，？噎，N}是擁有壓縮因子s的IFS，其對應的分形為A；（∑，dc）為伴隨于該IFS的碼空間. ？準" ：" ■→A為定理2中的連續映上的映射. a∈A的地址定義為？準－1（a）＝{ω∈■ ： ？準（ω）＝a}中的任意一個元素. ？準－1（a）稱為a∈A的地址集.

（i）若吸引子A中的每個點a均擁有唯一的地址，則稱該IFS為全非連通.

（ii）若IFS不是全非連通，但是存在一個開集Θ？奐A，滿足開集條件：

wi（Θ）∩wj（Θ）＝■，■i，j∈{1，2，…，N}，i≠j；■wi（Θ）？奐Θ.

則稱該IFS為恰好接觸.

（iii）既不是全非連通，也不是恰好接觸的IFS稱為交疊IFS.

對于全非連通的IFS，其分形吸引子A和伴隨該IFS的碼空間之間滿足一一對應的關系，也就是說， ？準" ：" ■→A具有逆映射，？準是■，A之間的一個同胚. 我們可以著手建立分形上的動力系統了.

引理1[37]. 設{X ; Wn ： n＝1，2，？噎，N}是一個壓縮IFS，其分形吸引子為A，IFS為全非連通，則對每個n＝1，2，？噎，N，映射Wn ： A→A是單射.

由引理1可知，定義7是適定的.

定義7. 設{X ; Wn ： n＝1，2，？噎，N}是具有吸引子A的全非連通IFS. 在A上定義一個伴隨于IFS的變換S ： A→A：S（a）＝W－1n" " （a），a∈Wn（A），動力系統{A；S }稱為伴隨于IFS的分形位移動力系統.

眾所周知，N符號的碼空間∑有一個平凡但是很有用的移位動力系統{■；T }：

T ： ■→■，T（σ1σ2σ3…）＝σ2σ3？噎，■σ＝σ1σ2σ3 ？噎 ■ ■.

下面的定理3刻畫了移位動力系統{■；T }和分形位移動力系統{A；S }之間的深刻聯系. 這個聯系使得研究分形位移動力系統的動力學性質變得十分簡單，因為兩個動力系統是拓撲共軛的，也就是等價的，其動力學性質完全一致. 詳細地說，即是{■；T }若有K－周期點σ0，σ1，？噎，σK－1，則{A；S }有K－周期點？準（σ0），？準（σ1），？噎，？準（σK－1），且兩者的吸引或排斥性是一致的，反之也對. {∑；T }具有Devaney混沌性，當且僅當{A；S }具有Devaney混沌性. 因此我們將通過符號空間的移位動力系統{■；T }的動力學性質這一個便捷的途徑來刻畫分形位移動力系統的性質.

定理3. 設{X ; Wn ： n＝1，2，？噎，N}是具有吸引子A的全非連通壓縮IFS；{A；S }為伴隨于該IFS的分形位移動力系統；{■；T }為N符號的碼空間∑上的移位動力系統. 則{A；S }和{■；T }拓撲共軛，即滿足等價關系：？準T（σ）＝S？準（σ），■σ∈■，其中？準 ： ■→A為一一映上的連續映射，因此為■，A之間的一個同胚映射.

證明. 對于全非連通壓縮IFS來說，？準" ：" ■→A是一個同胚. 假設對任意的σ＝σ1σ2 ？噎 ■ ■，滿足？準（σ）＝a，則W－1σ1" " " （a）＝W－1σ1" " " （■Wσ1Wσ2？噎Wσn（x））＝■Wσ2？噎Wσn（x）＝？準（σ2σ3？噎）＝？準T（σ），其中x∈X可任意選取. 所以S？準（σ）＝S（a）＝W－1σ1" " " （a）＝？準T（σ），即{A；S }和{■；T } 拓撲共軛.

利用定理3以及定理4的結論便可以得到定理5.

定理4[37]. N符號的碼空間■上的移位動力系統{■；T }具有Devaney混沌性.

定理5[37]. 設{X ; Wn ： n＝1，2，？噎，N}是具有吸引子A的全非連通壓縮IFS，則伴隨于該IFS的分形位移動力系統{A；S }具有Devaney混沌性.

混沌特性使得分形位移動力系統{A；S } 可以用來生成混沌序列，并加以量化，便可以在設計密碼系統中作為隨機密鑰流加以使用. 一個混沌系統的混沌特性優良，可以生成具有優良偽隨機性的密鑰流，使之符合密碼學的要求. 我們將在第3節對一個參數化的IFS相關的分形位移動力系統的混沌特性進行數值仿真，從遍歷性，時間序列的自相關系數，李雅普諾夫指數以及對序列的SP800-22統計檢測等方面展示其優良的混沌性質. 在應用中，我們會碰到一些恰好接觸的壓縮迭代函數系統. 對全非連通的IFS的伴隨位移動力系統的結論稍微修改，同樣適用于恰好接觸的類型. 實際上只要將定理3中的結論改為{A；S }和{■；T }半拓撲共軛，即滿足等價關系：？準T（σ）＝S？準（σ），■σ∈■，其中？準 ： ■→A是一個映上的連續映射. 由于在恰好接觸的IFS中，分形A上的點a有可能存在多個地址與之對應，只要限制其中一個地址作為其地址，即可實現逆映射，使得動力系統{A；S }適定，比如，若a∈W1（A）∩W2（A），取S（a）＝W－11" " " " （a）便可以定義S（a）的函數值，從而定義了動力系統{A；S }. 由所有A中的點所對應的單地址所構成的空間記為■＋＝{σ∈∑： ■a∈A，σ限制為？準－1（a）中的一個}，則同理可以證明定理3的修正定理6.

定理6. 設{X ; Wn ： n＝1，2，…，N}是具有吸引子A的恰好接觸壓縮IFS；則{A；S }和{■＋；T }拓撲共軛，即滿足等價關系：？準T（σ）＝S？準（σ），■σ∈■＋，其中？準" ：" ■＋ → A是■＋ ， A之間的一個同胚.

本文將在第3節中構造單位正方形上的一個參數化的恰好接觸的壓縮IFS. 該IFS表現雖然簡單，但是其伴隨的分形位移動力系統卻不簡單，具有優良的混沌特性，非常適合用于設計圖像加密算法.

3" 一個單位正方形上的迭代函數系統及其分形位移動力系統

3.1" 一個迭代函數系統

考慮壓縮IFS{[0，1]2；W1，W2，W3，W4}，其中0＜a，b＜1為系統的參數.

W1（x，y）＝（ay，bx），W2（x，y）＝（ax，（1－b）y＋b），

W3（x，y）＝（（1－a）x＋a，（1－b）y＋b），W4（x，y）＝（－（1－a）y＋1，－bx＋b）.（1）

由于0＜a，b＜1，IFS（1）是一個壓縮IFS，因此在R2中具有唯一的吸引子分形. 由于單位正方形A＝[0，1]2滿足W（A）＝■Wi（A）＝A. 因此，IFS（1）的分形為單位正方形A. 由第2節的分形理論知道，IFS（1）的分形A上有一個伴隨的分形位移動力系統{A；S}. {A；S}可以表示為公式（2）.

S（x，y）＝W－11" " （x，y），（x，y）∈W1（A） ＼ {（a，y） ： 0≤y≤b}，W－12" " （x，y），（x，y）∈W2（A） ＼ {（x，b） ： 0≤x≤a}，W－13" "（x，y），（x，y）∈W3（A） ＼ {（a，y） ： b≤y≤1}，W－14" " （x，y），（x，y）∈W4（A） ＼ {（x，b） ： a＜x≤1}.（2）

分形幾何理論表明S（A）＝A，A是S的排斥吸引子，分形A上的動力系統{A；S}具有混沌特性. 推導得到定義在A上的動力系統S（x，y）的具體形式如（3）所示.

S（x，y）＝" " " " " " " " " " （y/b，x /a），（x，y）∈[0，a）×[0，b]" " " " " "（x /a，（y－b）/（1－b）），（x，y）∈[0，a]×（b，1]" "（（x－a）/（1－a），（y－b）/（1－b）），（x，y）∈（a，1]×[b，1]（（b－y）/b，（1－x）/（1－a）），（x，y）∈ {[a，1] ×[0，b），（a，b）}（3）

S（x，y）即是本文所構造的分形位移動力系統. 由于IFS（1）的吸引子分形是單位正方形，所以可以用（1）來生成填充單位正方形的分形曲線. 如圖1所示，當a＝0.5，b＝0.5時迭代函數系統在單位正方形A中所生成的迭代1到6次的填充曲線，可以看出當迭代次數足夠多時，該填充曲線可以填滿整個單位正方形.

顯然，W1（A），W2（A），W3（A），W4（A）之間在邊界部分接觸了，這是一個恰好接觸的壓縮迭代函數系統. 在定理7，我們給出該IFS的分形位移動力系統具有Devaney混沌特性的直接證明.

定理7. 設{A ; Wn ： n＝1，2，3，4}如（1）所示，其吸引子恰好為A. {■＋；T }為定理6中所定義，則在■＋上的移位動力系統 {■＋；T }具有Devaney混沌性，因此分形位移動力系統{A；S} 同樣具有混沌特性.

證明. 由（3）所定義的位移動力系統{A；S} 可知，單位正方形上的四部分重疊的邊界部分的點，其對應的碼地址限制為其中之一，令σi，i＝2，3，？噎，則具體如下：

（a） {（a，y） ： 0≤y≤b}上的點歸屬W4（A），不歸屬W1（A），所對應的碼地址為σ＝4σ2σ3？噎，即以4開始，后面的σi∈{1，2}；而不是σi＝1σ2σ3？噎，σi∈{3，4}的形式.

（b） {（x，b） ： 0≤x＜a}上的點歸屬W1（A），不歸屬W2（A），所對應的碼地址為σ＝1σ2σ3？噎，即以1開始，后面的σi∈{2，3}；而不是σ＝2σ2σ3？噎，σi∈{1，4}的形式.

（c） {（a，y） ： b＜y≤1}上的點歸屬W2（A），不歸屬W3（A），所對應的碼地址為σ＝2σ2σ3？噎，即以2開始，后面的σi∈{3，4}；而不是σ＝3σ2σ3？噎，σi∈{1，2}的形式.

（d） {（x，b） ： a＜x≤1}上的點歸屬W3（A），不歸屬W4（A），所對應的碼地址為σ＝3σ2σ3？噎，即以3開始，后面的σi∈{1，4}；而不是σ＝4σ2σ3？噎，σi∈{2，3}的形式.

對上述四部分的定義明確之后，便可以得到A上任何一點a的唯一一個地址σ，所有構成σ構成的空間為■＋. 實際上A上的點a若存在多個地址，則通過上述定義之后，a的地址一定是（a）－（d）之一的形式結尾，該結尾為兩個符號組成的序列. 則■＋為■去掉某些以兩個符號組成的序列作為結尾的元素后得到.

（i） 證明T對初值的敏感性. 對■σ＝σ1σ2σ3 ？噎 ■" ■＋及■＋中的球B（σ，ε），可設■＜ε≤■，對■■＝■1■2■3 ？噎 ■ B（σ，ε），■≠σ，存在充分大的正整數m＞n，使得σk＝■k，k＝1，2，？噎，m－1，且σm≠■m. 則對0＜δ＜■，

dc（T m－1（σ），T m－1（■））＝dc（σm？噎，■m？噎）≥■＞δ.

所以T對初值具有敏感性.

（ii） 證明T具有拓撲傳遞性. 構造■＋的一個點σ*＝σ1σ2σ3 ？噎，其中長度為k（k＝1，2，？噎）的由四個符號{1，2，3，4}組成的4k個序列按照字典順序排序組成，而長度短的序列排在長度長的序列前面，這樣構成的無窮長的序列記為σ*：

σ*＝■■？噎

顯然σ*不可能以兩個符號組成的序列作為結尾，所以σ*∈■＋. 對■＋中的任意點■＝■1■2■3 ？噎和任意正整數q，可以找到一個正整數k（q），使得■i＝σk（ q ）＋i，i＝1，2，？噎，q，且

T k（ q ）（σ*）＝σk（ q ）＋1σk（ q ）＋2 ？噎 σk（ q ）＋q ？噎＝■1■2 ？噎■q？噎，

dc（T k（ q ）（σ*），■）＝dc（σk（ q ）＋1σk（ q ）＋2 ？噎 σk（ q ）＋q ？噎，■1■2 ？噎■q？噎）≤■" " " " " ".

所以σ*的軌道在■＋中稠密.

（iii） 證明T的周期點在■＋中稠密. 在（ii）所構造的σ*中取σk（ q ）＋1σk（ q ）＋2 ？噎 σk（ q ）＋q，然后構造q周期點

σ＝σk（ q ）＋1σk（ q ）＋2 ？噎 σk（ q ）＋q σk（ q ）＋1σk（ q ）＋2 ？噎 σk（ q ）＋q？噎，

由■＝■1■2■3 ？噎 ■ ■＋知道■1■2 ？噎■q ■1■2 ？噎■q ？噎不可能在某個符號之后由兩個其他的符號組成的無窮序列作為結尾，即■1■2 ？噎■q ■1■2 ？噎■q ？噎 ■ ■＋，則類似（ii）可證明

dc（σ，■）＝dc（σk（ q ）＋1σk（ q ）＋2 ？噎 σk（ q ）＋q ？噎，■1■2 ？噎■q？噎）≤■" " " " .

所以T的周期點在■＋中稠密.

至此，證明了移位動力系統{■＋；T }具有Devaney混沌性. 由于分形位移動力系統{A；S}與{■＋；T }拓撲共軛，所以{A；S}同樣具有混沌特性. 證明完畢.

3.2" 性能分析

為了說明構造的分形位移動力系統（3）生成的序列的復雜性、不可預測性和其他混沌特性，下面將對其進行系列測試來分析它的混沌行為，包括軌跡遍歷分析、關于兩個參數的分叉圖分析、李雅普諾夫指數分析、以及生成比特序列的統計測試分析等.

選定初始值x0＝0.312，y0＝0.519，控制參數為a＝0.313，b＝0.718，迭代10 000次，得到兩個長度為10 000的混沌序列X，Y，并對其進行性能分析.

3.2.1" 軌跡分析

用于描述混沌系統特性的分形位移動力系統（3）的軌跡圖以及序列X，Y的時序圖如圖2所示，可以看出該系統的軌跡覆蓋整個相空間且分布均勻，因此，本文構造的單位矩陣上的分形位移動力系統所生成的序列在相空間中具有很好的遍歷性.

3.2.2" 分叉圖

動力系統的分叉圖描述動力系統輸出狀態隨系統參數變化而變化的狀況. 性能優良的混沌系統應該具備較大的混沌參數空間，對混沌參數空間中的參數所對應的動力系統具備混沌特性. 對初值的迭代所生成的狀態值軌道具有很好的偽隨機性和遍歷性. 保持初始值不變，當a＝0.313固定，可以刻畫系統隨b∈（0.1）變化的動力學性質，混沌序列X，Y關于參數b的分叉圖分別如圖3（a）和圖3（b）所示；當b＝0.718時，系統隨a∈（0.1）變化時序列X，Y的分叉圖如圖3（c）和圖3（d）所示. 可以看出該分形位移動力系統關于a，b的混沌區域均是整個單位區間（0.1），該2D分形位移動力系統具有優良的混沌行為.

3.2.3" 李雅普諾夫指數

混沌系統對初始值高度敏感，一個性能優良的混沌系統對于初始值的任何微小變化都會產生差別巨大的輸出序列. 李雅普諾夫指數是衡量一個系統因為微小的初始值誤差，隨系統迭代后狀態值產生分離的程度. 李雅普諾夫指數可以作為動力系統具備混沌行為的判斷依據，若系統的最大李雅普諾夫指數大于0，則認為系統具有混沌特性.

一個二維動力系統，可以計算得到兩個李雅普諾夫指數. 假設f （x，y）是二維動力系統， （xi，yi）＝f i（x0，y0）是動力系統f迭代（x0，y0）第i次的狀態值，i＝1，2，？噎，m，m為適當選取的迭代次數，時刻為i時系統的雅可比矩陣記為Ji. 為了得到二維動力系統的兩個李雅普諾夫指數，需要對矩陣Jm，Jm－1，？噎，J1進行如（4）所示的QR分解，其中Q0＝I，

qr[Jm，Jm－1，？噎，J1]＝qr[Jm，Jm－1，？噎，J2（J1Q0）]＝qr[Jm，Jm－1，？噎，J3（J2Q1）][R1]

＝qr[Jm，Jm－1，？噎，J4（J3Q2）][R2R1]＝？噎＝qr[Jm，Jm－1，？噎，Ji＋1（JiQi－1）][Ri－1Ri－2？噎R2R1]（4）

＝？噎＝Qm [Rm？噎R2R1]＝QmR，

其中qr[·]代表QR分解. 從J1開始，在第i 步中，用Ji左乘Qi－1得到Bi＝JiQi－1，再作QR分解Bi＝QiRi，i＝1，2，？噎，m. 矩陣R＝Rm？噎R2R1，其對角線上每個元素是所有二階矩陣Ri對角線上對應元素的乘積，動力系統f （x，y）的兩個李雅普諾夫指數的近似值可以通過式（5）計算得到.

LE1＝■■lnRi（1，1）；LE2＝■■lnRi（2，2）.（5）

當a＝0.313，b∈（0，1）和b＝0.718，a∈（0，1）時，計算對應的李雅普諾夫指數曲線，結果分別如圖4（a）和圖4（b）所示. 兩個參數變化時，所有參數所對應的動力系統的兩個李雅普諾夫指數均大于0，該分形位移動力系統具有優良的超混沌特性.

3.2.4" 自相關分析

一個時間序列X＝{x1，？噎，xn}的延遲k期的自相關系數ρk的定義如式（6）所示. 自相關系數是描述同一個序列在某一時刻與其延遲k期時刻的狀態值之間的相關程度. 自相關系數曲線可以刻畫序列的噪聲性質，如果自相關系數函數近似δ函數，說明序列中兩個時刻的狀態值之間相關性接近0，序列類似白噪聲，具有很好的偽隨機性.

ρk＝■（6）

其中n表示序列的長度，k是延遲期數，xi表示時間序列在時刻i的值，mean（X）表示X的均值.

圖5（a）和圖5（b）分別是序列X和序列Y延遲0-200期所得到的自相關系數圖. 在一個理想的混沌系統中，自相關系數函數應該很類似于δ函數. 由圖5可以說明本文所構造的分形位移動力系統所生成的序列具有很好的偽隨機性.

3.2.5" 信息熵分析

信息熵也叫香農熵，是描述信息源各事件的不確定性，可以描述序列的無序性，反映混沌系統生成的混沌序列的混沌程度，信息熵的公式如式（7）所示，信息熵越接近理論值，生成的序列越無序.

找出混沌序列的最小值和最大值，在最小值和最大值之間平均分成50份后得到50個不同的區間，分別求出序列中的偽隨機數落在這50個區間的概率pi，（i＝1，2，？噎，50），代入到式（7）中即可得到序列的信息熵. 計算理論值時，假設序列中的隨機數落入到這50個區間的概率都相等，p1＝p2＝？噎＝p50＝■，由式（7）得到信息熵最大理論值Emax＝log2 50≈5.643 9.

E ＝ －■pi log2 pi（7）

當a＝0.313，b∈（0，1）時，混沌序列X，Y的信息熵分別如圖6（a）和圖6（b）所示，可以看出隨著b值的改變，得到的信息熵都接近于理論值；當b＝0.718，a∈（0，1）時，混沌序列X，Y的信息熵分別如圖6（c）和圖6（d）所示，隨著a值的改變，得到的信息熵也都接近于理論值，所以本文提出的分形位移動力系統（3）所生成的混沌序列各個數值之間提供的信息熵足夠大，系統的混沌性能好.

3.2.6" 統計測試分析

先對分形位移動力系統（3）迭代1 000 000次生成的混沌序列X，Y根據公式（8）進行預處理生成0-1比特流，再對比特流序列進行NIST SP800-22測試[38]，測試結果如表1所示. 選擇顯著性水平為0.01，可以看到測試的結果P值都大于0.01，則該序列通過SP800-22測試，具有優良的統計特性.

X＝mod（floor（X×109），2）；Y＝mod（floor（Y×1011），2）.（8）

4" 圖像加密算法

本文所提出的圖像加密方法包括置亂和擴散兩個階段，下面先介紹加密時要用到的一些算法.

4.1" DNA編碼和運算

生物學中DNA有四種堿基，分別是A（腺嘌呤）、T（胸腺嘧啶）、G（鳥嘌呤）和C（胞嘧啶）. 本文的DNA編碼方式將二進制數與四種堿基聯系起來，分別用00、11、10和01編碼對應堿基A、T、G和C. 根據Watson-Crick互補規則，DNA堿基有產生8種等可能的編碼、解碼規則，如表2所示[39]. 表3 -表6是DNA的四種運算法則，分別是加法、減法、異或和同或運算. 對DNA編碼后得到的堿基序列可以進行加、減、異或和同或運算，在加密算法中DNA運算的符號記為Δa，根據a的值選擇對應的運算，定義如（9）所示.

Δa＝＋，a＝1－，a＝2？堠，a＝3⊙，a＝4（9）

4.2" Zigzag變換

Zigzag變換是一種掃描置亂方法，對大小為M×N的矩陣從第一個元素開始進行Z字形掃描，掃描后得到的一維向量重新排成大小為M×N的矩陣，便得到置亂的矩陣. 例如，如圖7所示，給定一個大小為3×5的矩陣，從第一個像素點便開始對矩陣進行Zigzag變換，得到一個置亂后的3×5的矩陣.

4.3" 風車型填充曲線

本文構造了基于迭代函數系統所生成的風車型填充曲線. 利用迭代函數系統生成分形的確定性算法，生成所需要的填充曲線. 給定一個IFS（1）的變型IFS{R2；W1'，W2'，W3'，W4'}，定義如公式（10）所示. 在圖8（a），當n＝1時，給定4個初始點集合B0＝{（■，■），（■，■），（■，■），（■，■）}，對這四個點首尾相連后是一個Z字型的形狀. 當n＝2時，根據IFS（10）對B0進行迭代，便可以生成B1＝■W1'（B0），將其中的點按次序連接，便得到圖8（b）. 其中圖8（b）中的位置I是由圖8（a）的一個相似縮小1/2的版本，位置II、III、IV是分別由位置I順時針旋轉90°、180°、270°的結果，再增加3條直線首尾相連，便得到一個類似風車形狀的曲線，此時的折線曲線經過42個點. 類似地，根據IFS（10）對圖8（b）迭代一次后得到圖8（c）的曲線，此時的曲線經過82個點.

利用上述所構造的風車型填充曲線對圖像進行掃描，對于大小為M×M的灰度圖像（其中M＝2K，K∈Z＋且行列大小一致，否則需要補0處理）實行風車掃描置亂，此時風車掃描曲線需迭代n＝log2（M）次，生成的風車型曲線能掃描大小是M×M的圖像中的每一個像素點.

圖9是一個風車型填充曲線掃描圖像像素的例子. 由圖9（a）所示，給定一個大小為8×8的原始圖像矩陣，對它連續執行兩次的風車掃描，根據IFS（10），對初始值點集合B0迭代n＝log2（8）＝3次，生成82個點. 為了使這些點能一一對應于原始圖像矩陣中每個像素的位置，需要將這些點進行量化預處理，如公式（11）所示. 該風車型曲線掃描原始圖像矩陣后會得到一個一維向量，對一維向量重新排列成如圖9（b）所示的大小為8×8的矩陣. 同理，對圖9（b）用同樣的方法掃描后得到圖9（c）所示的矩陣，可以看出經過兩次風車掃描后的原始矩陣具有較好的置亂效果.

W1'（x，y）＝（0.5x，0.5y），

W2'（x，y）＝（0.5y，－0.5x＋1），

W3'（x，y）＝（－0.5x＋1，－0.5y＋1），

W4'（x，y）＝（－0.5y＋1，0.5x）.

（x，y）＝（2n（x＋1/2n＋1），2n（y＋1/2n＋1））.（11）

4.4" 圖像加密算法

本文將對一個大小為M×N的明文圖像I進行加密，加密的流程圖如圖10所示，用風車型填充曲線和基于混沌序列排序對明文圖像的像素位置進行置亂，在改變像素點的位置后運用DNA運算實施擴散來改變其像素值.

1. 生成密鑰.首先給定外部密鑰，作為分形位移動力系統（3）的初始值和系統參數.

x1＝0.153 8，x2＝0.876 3，y1＝0.961 8，y2＝0.126 6，

a1＝0.876 3，a2＝0.925 4，b1＝0.488 6，b2＝0.005 6，

將明文圖像輸入SHA-256散列函數中得到長度為256bit的散列序列H，生成64個4-bit的Hash值，記為K1，K2，？噎，K64，通過公式（12）生成與明文相關的初始值K1，K2，？噎，K8，再利用公式（13）對外部密鑰流進行修正，使得密鑰流與明文相關. 通過SHA-256算法獲得與明文相關的初始值和系統參數，可以增強加密算法抵御差分攻擊、選擇明文攻擊和已知明文攻擊的性能.

ki＝（K8×（ i－1 ）＋1＋K8×（ i－1 ）＋2＋？噎＋K8× i＋mean（K1 ： K64））/100.（12）

x1＝mod（x1＋k1，1），y1＝mod（y1＋k2，1），a1＝mod（a1＋k3，1），b1＝mod（b1＋k4，1），

x2＝mod（x2＋k5，1），y2＝mod（y2＋k6，1），a2＝mod（a2＋k7，1），b2＝mod（b2＋k8，1）.

其中mod（x，y）為求余數函數，返回x除y以后的余數，mean（K1 ： K64）表示K1到K64所有值的均值.

2. 生成偽隨機數

Step 2.1. 利用構造的分形位移動力系統（3），給定初始值和參數x1，y1，a1，b1，迭代t＋M×N次，其中t＝500，去掉前t次，得到長度為M×N的2個偽隨機序列X，Y. 根據公式（14）對序列X，Y進行預處理得到新的序列X，Y，其中序列X是DNA編碼規則，序列Y是DNA解碼規則，其中函數“floor（x）”返回一個不大于x的最大整數.

X＝mod（floor（X×109），8）＋1，Y＝mod（floor（Y×1011），8）＋1.（14）

Step2.2. 利用分形位移動力系統（3），給定初始值和參數x2，y2，a2，b2，迭代t＋4×M×N次，其中t＝500，去掉前t次，得到長度為4×M×N的2個偽隨機序列X1，Y1. 根據公式（15）對序列X1，Y1進行預處理得到新的序列Z，R，其中序列Z是DNA運算規則，R為偽隨機灰度值序列，用于控制擴散過程.

Z＝mod（floor（X1×109），4）＋1，R＝mod（floor（Y1（1 ： M×N）×1011），256）.（15）

3. 置亂階段

Step 3.1. 風車掃描置亂. 對明文圖像進行兩次風車曲線掃描，得到像素位置改變后的圖像I1.

Step 3.2. 基于排序的置亂. 對圖像I1展開成一維向量V1，由公式（16），用sort函數將序列X1的前MN個隨機數升序排序得到位置索引id，即滿足Vtemp（i）＝V1（id（i）），i＝1，2，？噎，MN. 用id對向量V1進行置亂，再將向量V2用公式（17）轉化為M行M列的矩陣I2，reshape（V2，M，N）表示將V2按列優先重排為一個M行M列的二維矩陣.

[Vtemp，id ]＝sort（X1（1 ： MN）），V2（1 ： MN）＝V1（id（1 ： MN）），（16）

I2＝reshape（V2，M，N）.（17）

4. 擴散階段

Step 4.1. DNA編碼

對置亂操作后的矩陣進行擴散處理，將矩陣I2展開成MN行1列的向量D，每個像素轉化成8位的二進制形式，那么得到MN行8列的二進制數矩陣D1. 將向量X作為DNA編碼規則，根據表2用向量X的第m個數作為矩陣D1第m行的DNA編碼規則，m＝1，2，？噎，MN. 矩陣D1經過編碼得到MN行4列的堿基矩陣P，再根據公式（18）將堿基矩陣P重新排列成4M行N列的堿基矩陣P1.

P1＝reshape（P，4M，N）.（18）

Step 4.2. DNA運算和擴散

對序列R的每一個元素值按照表2的規則1進行DNA編碼，得到MN行4列的堿基序列R1，將堿基矩陣R1重新排列成4M行N列的矩陣. 將向量Z作為DNA的運算規則實施DNA運算. 首先將向量Z重新排列成4M行N列的矩陣X2. 由DNA運算規則和公式（19）對堿基序列P1和R1進行DNA運算，得到堿基序列Q，再對該堿基序列進行基于堿基的Zigzag變換得到置亂后的堿基序列Q1.

Q（1，1）＝P1（1，1）ΔX2（ 1，1 ）R1（1，1），" " Q（1，j）＝P1（1，j）ΔX2（ 1，j" ）R1（1，j）ΔX2（ 1，j ）Q（1，j－1），j＝2 ： N；" " " "Q（i，1）＝P1（i，1）ΔX2（" i，1 ）R1（i，1）ΔX2（" i，1 ）Q（i－1，N），Q（i，j）＝P1（i，j）ΔX2（" i，j" ）R1（i，j）ΔX2（" i，j" ）Q（i，j－1），j＝2 ： N，i＝2 ： 4M.（19）

Step 4.3. DNA解碼

將堿基序列Q1重新排列成MN列4行的堿基矩陣Q2，并將向量Y作為DNA解碼規則進行解碼. 用向量Y的第m個數作為矩陣Q2第m行的DNA解碼規則，m＝1，2，？噎，MN. Q2經過解碼得到MN行8列的二進制矩陣Q3，最后轉化成十進制形式得到MN列1行的向量Q4，重新排列成M行N列的密文圖像C.

本文的解密過程是加密的逆過程，不再詳述.

5" 安全性分析

5.1" 加密及解密測試

為驗證圖像加密及解密算法的正確性，使用不同明文圖像測試加密過程和解密過程. 以尺寸為256×256的Lena圖像和bird圖像，尺寸為512×512的cameraman圖像和woman圖像為例，其中Lena圖像的加密及解密結果如圖11所示. 測試結果顯示，四幅密文圖像內容都呈噪聲樣式分布，無任何有用可視信息，表明此加密算法能有效保護明文圖像內容的私密性；而解密圖像與明文圖像相同，表明算法能正確解密恢復原始圖像信息.

5.2" 密鑰安全性分析

5.2.1" 密鑰敏感性

密鑰包括外部密鑰和內部密鑰，其中外部密鑰通過特定的算法生成內部密鑰時，密鑰敏感性是指如果外部密鑰發生微小的變化，使得加密同一個明文圖像得到兩個有顯著差異的密文圖像，那么就可以說該加密方法的密鑰敏感性強. 以大小256×256的Lena為例，對本文的加密方法進行密鑰敏感性的分析. 對已知的外部密鑰x1，y1，a1，b1，x2，y2，a2，b2分別改變10－15，加密4幅測試明文圖像，分別得到8個不同的密文圖像，用于計算密鑰敏感性.

像素改變率（NPCR）和歸一亮度改變強度（UACI）是衡量兩幅圖像的差異程度的指標，也是評價圖像加密算法抵抗差分攻擊的重要指標，其計算公式如（20）-（21）所示. 可以通過計算原始密文圖像和改變密鑰后的密文圖像的NPCR和UACI值，分析它們之間的差異程度，其中NPCR和UACI的理論值分別是99.609 4%和33.463 5%[40]. 結果如表7所示，顯示明文圖像Lena、bird、cameraman和woman所得到的NPCR和UACI值均接近理論值，說明本文提出的算法有優良的密鑰敏感性.

NPCR（P1，P2）＝■■■sign（P1（i，j）－P2（i，j））×100%，sign（x）＝0，x＝0，1，x≠0.（20）

UACI（P1，P2）＝■■■■×100%.（21）

5.2.2" 密鑰空間

密鑰空間是指所有可能密鑰的數量，當密鑰空間大于2100時，該加密算法能抵抗暴力攻擊[41]. 本文所提出的加密算法的密鑰包括x1，y1，x2，y2，a1，b1，a2，b2，它們都是0到1的實數值，從密鑰的敏感性分析可以看出，每個密鑰的個數均可以達到1015，加密算法的密鑰空間的大小為L＝log2 （1015）8 bit≈399bit ＞＞ 100bit，所以本文提出的加密算法能有效地抵抗暴力攻擊.

5.3" 統計分析

5.3.1" 直方圖分析

直方圖分析是圖像加密最常見的分析方法. 如果加密后密文圖像的直方圖呈現均勻分布，那么不能從中獲取有用的統計信息，說明加密算法能有效抵抗統計分析的攻擊. Lena的明文圖像及密文圖像的直方圖如圖12所示. 可以看出，明文圖像的直方圖統計特征明顯，而密文圖像的直方圖明顯不同于明文圖像的直方圖，統計分布均勻，攻擊者難以獲取有效統計特征信息，這表明該算法能有效抵抗直方圖統計攻擊.

5.3.2" 相鄰像素相關性分析

通常明文圖像在垂直、水平和對角方向上的相鄰像素具有較強的相關性，而密文圖像相鄰像素則幾乎沒有相關性. 從考察的圖像中任意選取T＝6 000對相鄰的像素點，記它們的灰度值為（ui，vi），i＝1，2，？噎，T，則向量u＝{ui}和向量v＝{vi}間的相關系數ruv可通過公式（22）-（23）計算. 根據計算所得的不同圖像的明文和密文相關系數見表8，密文圖像相關系數接近于0，說明本文所出的加密算法可以很好地消除明文圖像相鄰像素的相關性.

ruv＝■，cov（u，v）＝■×■（ui－E（u））×（vi－E（v）），（22）

D（u）＝■×■（ui－E（u））2，E（u）＝■×■ui，（23）

5.3.3" 信息熵分析

香農用信息熵的概念來描述信息的不確定度，信息熵越高，不確定性就越大，可見信息越少. 信息熵計算公式如（24）.

H ＝ －■P（i）log2" P（i）（24）

式中P（i）表示灰度值i出現的概率，L表示圖像灰度等級.

對于8 bit的灰度圖，信息熵的最大理論值為log2 256＝8. 明文圖像及其密文圖像的信息熵如表9所示，可以看出密文圖像的信息熵非常接近最大熵，信息泄露的風險可以忽略不計，加密算法可以有效抵御信息熵分析的攻擊.

5.4" 差分攻擊分析

對明文的敏感性越強，算法抵抗差分攻擊的能力越強. 差分攻擊是指對明文圖像做細微的改變后，使用相同密鑰加密兩幅圖像，得到兩個相應的密文圖像，并通過比較兩個密文圖像的差別來尋找破譯的線索. 如果兩個密文圖像的差別迥異，則稱該圖像密碼系統具有優良的明文敏感性；如果這兩個密文圖像的差別較小，則稱該圖像密碼系統具有較弱的明文敏感性. NPCR和UACI也是評價圖像加密算法抵抗差分攻擊的重要指標. 本文對Lena等明文圖像隨機選取100個像素，在每一次實驗中只改變一個像素的灰度值1個灰度級，用相同的密鑰進行加密，得到新的密文圖像，計算原始圖像和改變圖像對應密文圖像的NPCR和UACI值，計算其平均值，測試結果如表10所示，可以看出NPCR和UACI的測試值均接近理論期望值，表明本文提出的算法具有良好的抵抗差分攻擊的能力.

5.5" 抗損壞攻擊分析

真實應用環境中，信道噪聲及剪切攻擊不可避免. 一種好的圖像加密算法要能抵抗一定的噪聲攻擊及剪切攻擊.

5.5.1" 抗噪聲分析

抗噪聲攻擊實驗中，對Lena密文圖像添加椒鹽噪聲，噪聲密度分別為5%、10%、15%和20%，然后解密添加噪音的密文，如圖13所示，仍可恢復明文圖像的主要信息.

峰值信噪比（PSNR）可以用來評價兩幅圖像之間的像素差異程度，它表示圖像的失真程度，當PSNR值越大，圖像與原始圖像越接近，所以當測試明文圖像和加了噪聲的解密圖像時，PSNR值越大說明越好，PSNR的定義如公式（25）所示，MSE是均方差，如公式（26）所示.

PSNR＝10×log10■（25）

MSE＝■■■P（i，j）－C（i，j）2（26）

其中P（i，j）是明文像素灰度值，C（i，j）是受過噪聲攻擊的解密明文圖像像素灰度值.

我們將測試明文圖像和加了噪聲的解密圖像的PSNR值，用來觀察加了噪聲后的解密圖像的失真程度，測試結果如表11所示，當噪聲攻擊越強時，得到的PSNR值越小，說明失真程度與噪聲攻擊強度成正比. 在與文獻[42]的對比中，可以看出相同的噪聲攻擊下，本文提出算法得到的PSNR值更大，說明失真程度相比更小，本文提出算法的密文圖像抗噪聲攻擊能力較好.

5.5.2" 抗剪切分析

抗剪切攻擊實驗中，對Lena密文圖像分別剪切圖像的1/16、1/4和1/2的像素，然后解密被剪切的密文圖像，實驗結果如圖14所示. 對密文圖像添加噪音或進行部分剪切后，解密圖像質量有受影響，與明文圖像所對比，仍可恢復明文圖像的主要信息，這說明算法能有效抵抗噪聲攻擊和剪切攻擊. 如表11所示，我們用大小為256×256的Lena圖，測試遭到不同程度剪切攻擊的密文的解密圖像與明文圖像的PSNR值，可以看出圖像失真程度與剪切攻擊強度成正比. 與文獻[42]相比，在同等的剪切攻擊下，本文的PSNR值要更大一些，說明本文提出算法的密文圖像抗剪切攻擊能力較好.

5.6" 加密及解密速度

實驗使用一臺配置AMD銳龍5-5600U、16G內存的筆記本電腦，算法基于MATLAB2018b語言實現. 加密及解密速度測試使用尺寸為256×256的圖像. 加密速度測試中，對同一圖像加密100次，記錄每次加密耗時，取計算平均值，解密速度測試也采取相同的方式. 測試結果，算法加密平均速度為2.000 265 s，解密平均速度為2.350 252 s. 這說明算法具有有效的加密及解密速度，可適用于實際通信環境.

6" 結語

本文通過迭代函數系統誘導構造了一個分形位移動力系統，從理論上證明了該動力系統的Devaney混沌特性，并從數值上分析驗證了該動力系統的混沌特性. 利用該分形位移動力系統所生成的混沌序列，設計了一個新的基于混沌的圖像加密算法. 加密算法包括置亂和擴散兩個階段. 置亂階段首先采用另一個迭代函數系統生成的填充曲線實現圖像像素位置的掃描，達到像素位置的初步置亂；接著利用分形位移動力系統所生成的混沌序列的排序得到的位置索引實現像素位置的再次置亂. 擴散階段采用動態的DNA編碼運算和Zigzag掃描實現，動態DNA編碼和運算使得算法的安全性能更高. 實驗結果表明，該算法能有效抵抗暴力破解、統計攻擊、差分攻擊，也能抵抗一定強度的噪聲攻擊和剪切攻擊，具有優良的安全性能，而且計算速度較快.

參考文獻

[1]" GLEICK J. Chaos：making a new science[M]. New York：Pengiun Books，1987.

[2]" STEWART I. Does god play dice？ the mathematics of chaos[M]. Cambridge M A：Blackwell，1989.

[3]" DEVANEY R. An introduction to chaotic dynamical systems[M]. New York：Addison-Weslay，1989.

[4]" PEITGEN H O，J？譈RGENS H，SAUPE D. Chaos and fractals，new frontiers of science[M]. 2nd ed.New York：Springer-Verlag，2004.

[5]" MANDELBROT B. The fractal geometry of nature[M]. San Francisco：W H Freeman and Company，1982.

[6]" BARNSLEY M F. Fractals everywhere[M]. Boston M A：Academic Press，1993.

[7]" DEMKO S，HODGES L，NAYLOR B. Construction of fractal objects with iterated function systems[C].SIGGRAPH 3，1985：271-276.

[8]" BARNSLEY M F，DEMKO S. Iterated function systems and the global construction of fractals[J].Proceedings of the Royal Society A，1985，399（1817）：243-275.

[9]" JACQUIN A E. Image coding based on a fractal theory of iterated contractive image transformations[J].IEEE Trans Image Processing，1992（1）：18-30.

[10]" FISHER Y. Fractal image compression-theory and application[M]. New Yok：Springer-Verlag，1994.

[11]" LI C，WU Y，YE R. Recent advances in applied nonlinear dynamics with numerical analysis-fractionaldynamics，network dynamics，classical dynamics and fractal dynamics with their numerical simulations[M]. Interdisciplinary Mathematical Sciences Vol 15. Singapore：World Scientific，2013.

[12]" SCHNEIER B. Cryptography：theory and practice[M]. Boca Raton：CRC Press，1995.

[13]" FRIDRICH J. Symmetric ciphers based on two-dimensional chaotic maps[J]. International Journal ofBifurcation and Chaos，1998（8）：1259-1284.

[14]" MAO Y B，CHEN G，LIAN S G. A novel fast image encryption scheme based on the 3D chaotic baker map[J]. International Journal of Bifurcation and Chaos，2004，14（10）：3613-3624.

[15]" WONG K W，KWOK B，LAW W S. A fast image encryption scheme based on chaotic standard map[J].Physics Letters A，2008，372：2645-2652.

[16]" PATIDAR V，PAREEK N K，SUD K. K. A new substitution-diffusion based image cipher using chaoticstandard and logistic maps[J]. Commun Nonlinear Sci Numer Simulat，2009（14）：3056-3075.

[17]" YE R. A novel chaos-based image encryption scheme with an efficient permutation-diffusion mechanism[J]. Optics Communications，2011，284：5290-5298.

[18]" 黎椏娟，葉瑞松. 基于一種新的二維混沌映射的自適應圖像加密算法[J]. 汕頭大學學報（自然科學版），2019，34（2）：23-36.

[19]" YE R. A novel image encryption scheme based on generalized multi-sawtooth maps [J]. FundamentaInformaticae，2014，133：87-104.

[20]" PAREEK N K，PATIDAR V，SUD K K. Image encryption using chaotic Logistic map[J]. Image andVision Computing，2006，24：926-934.

[21]" 楊鳳霞.基于二維Arnold映射的彩色圖像加密算法[J]. 小型微型計算機系統，2014，35（8）：1922-1925.

[22]" ZHANG G J，LIU Q. A novel image encryption method based on total shuffling scheme[J]. OpticsCommunications，2011，284：2775-2780.

[23]" 蘇杰彬，朱子怡，鐘幸賢，等. 基于二維斜帳篷映射和中國剩余定理的彩色圖像加密算法[J]. 圖像與信號處理，2022，11（2）：54-67.

[24]" YE R，HUANG H. Application of the chaotic ergodicity of standard map in image encryption andwatermarking[J]. I J Image，Graphics and Signal Processing，2010，2（1）：19-29.

[25]" 陳錦彬，葉瑞松. 基于改進Henon映射的混沌圖像加密算法[J]. 計算機科學與應用，2022，12（2）：422-435.

[26]" ALVAREZ G，LI S. Breaking an encryption scheme based on chaotic baker map[J]，Physics Letters A，2006，352：78-82.

[27]" XIAO D，LIAO X，WEI P. Analysis and improvement of a chaos-based image encryption algorithm[J].Chaos，Solitons and Fractals，2009（40）：2191-2199.

[28]" LIU J M，QU Q. Cryptanalysis of a substitution-diffusion based on cipher using chaotic standard andlogistic map[C]. Third International Symposium on Information Processing，2010：67-69.

[29]" RHOUMA R，SOLAK E，BELGHITH S. Cryptanalysis of a new substitution-diffusion based imagecipher[J]. Commun. Nonlinear Sci Numer Simulat，2010（15）：1887-1892.

[30]" ZHU C. A novel image encryption scheme based on improved hyperchaotic sequences[J]. OpticsCommunications，2012，285：29-37.

[31]" NI J，TANG Y，YE Y. An image encryption scheme based on 4D chaotic system and permutation-

diffusion operations[C]. Proceedings of 8th Annual International Conference on Network and Information Systems for Computers，2022：354-360.

[32]" WANG S， PENG Q， DU B. Chaotic color image encryption based on 4D chaotic maps and DNAsequence[J]. Optics amp; Laser Technology，2022，148：107753.

[33]" YE R，LI Y. A novel adaptive image encryption scheme based on iterated function system[C]. Proceeding of 2019 IEEE International Conference on Computer and Communication Engineering Technology，2019：1-5.

[34]" YE R，HUANG H. An adaptive image encryption scheme using fractal dynamical system and DNAoperation[C]. Proceeding of 2021 IEEE International Conference on Electronic Technology，Communicationamp; Information，2021：284-289.

[35]" ZHANG S，LIU L. A novel image encryption algorithm based on SPWLCM and DNA coding[J].Mathematics and Computers in Simulation，2021，190：723-744.

[36]" ZHANG X，YE R. A novel RGB image encryption algorithm based on DNA sequences and chaos[J].Multimedia Tools and Applications，2021，80（6）：8809-8833.

[37]" 李水根，吳紀桃. 分形與小波[M]. 北京：科學出版社，2002.

[38]" RUKHIN A，SOTO J，NECHVATAL J. et al. A statistical test suite for random and pseudorandom"number generators for cryptographic applications[R]. Special Publication 800-22 Revision 1a. National Institute of Standards and Technology（NIST）. 2010.

[39]" WATSON J，CRICK F. Molecular structure of nucleic acids：a structure for deoxyribose nucleic acid[J].Nature，1953，171：737-738.

[40]" 張勇. 混沌數字圖像加密[M]. 北京：清華大學出版社，2016.

[41]" 牛瑩，張勛才. 基于填充曲線和相鄰像素比特置亂的圖像加密方法[J]. 電子與信息學報，2022，44（3）：1137-1146.

[42]" WANG X，CHEN X. An image encryption algorithm based on dynamic row scrambling and Zigzag transformation[J]. Chaos，Solitons amp; Fractals，2021，147：110962.

The Fractal and Chaotic Natures of an Iterated Function System and Its Application

YE Ruisong， CHEN Yueming

（Department of mathematics， Shantou University， Shantou 515063， Guangdong，" China）

Abstract" The principle of generating fractal by iterated function system and the chaotic characteristics of fractal shifting dynamical system are introduced. An iterated function system is constructed to generate the filling curve on the unit square. The Devaney chaotic nature of the fractal shifting dynamical system is proved. The fractal shifting dynamical system is parameterized， and its chaotic natures are verified numerically. Based on the fractal shifting dynamical system， a chaotic image encryption algorithm is designed by combining DNA operations. The security and performance analysis of the cryptosystem are carried out as well.

Keywords" iterated function system; fractal; filling curve; chaos; dynamical system; image encryption