一種混沌序列加密算法的密碼分析

蔡 瓊，彭 濤，葉 楊

(武漢工程大學 計算機科學與工程學院，湖北 武漢 430074)

1 混沌序列加密算法

由于混沌映射所具有的許多類似隨機的性質和密碼學中的混淆和擴散等性質相似，所以出現了很多混沌加密算法，本文分析的混沌序列密碼算法使用的是Logistic[1]映射.

f(x)=μx(1-x),x∈[0,1],μ∈[3.5699456,4]

(1)

當x∈[0,1],μ∈[3.5699456,4]時，Logistic映射具有混沌效應.然而由于實數在計算機中以有限的精度實現，對于每次迭代產生的x可以表示如下：

其中n表示精度.

明文分組長度是64 bit,密鑰是混沌的初始控制參數x0和μ.該加密算法如下四步：

其中Aj為64bit分組，Dj為小于64的整數.

c. 加密明文分組，明文分組Mj對應的密文分組Cj=(Mj?Dj)⊕Aj.然后把密文塊做一個映射，φ(Cj)=cj+cj+1+…+cj+7,D*=Dj+φ(Cj)mod64.

d. 如果所有的明文分組都被加密則加密結束，否則ω=fD*+70(ω)，然后轉到b繼續加密.

2 加密系統的信息泄露規律以及攻擊

雖然文獻[2]對該加密系統進行了改進，但文獻[3]指出了該加密算法對密鑰的分割攻擊存在安全隱患.加密算法步驟a實質上是為了掩蓋混沌初態，來增加系統的安全性，但是如果以迭代之后的ω為初態，以參數μ產生的混沌序列，與以x0為初態經過迭代之后產生的混沌序列是一致的.這樣就可以把ω視為x0的等效密鑰，只要完成了對{ω,μ}的攻擊就完成了對加密系統的攻擊.

定理2[5]設函數f(x)=μx(1-x),μ,μ+δ∈(3.5699456,4],x,x+ε∈[0,1]，則:

證明：由于函數f(x)在[0,1]是連續可導的，則由拉格朗日中值定理知，存在

ξμ∈[x,x+ε],ηx+δ∈[μ,μ+δ]

使得

(2)

(3)

將(2)、(3)兩式相加得到

|fμ(x)-fμ+δ(x+ε)|=

定理1、2說明，Logistic混沌映射具有如下性質：輸入的低位變化對輸出的高位影響不大，而上述加密系統中的實際用來加密的二進制流，是由混沌映射反復迭代產生的，這就導致了混沌序列具有前幾個值對混沌初態和參數的低位比特變化不夠敏感的性質；由隨機序列的產生方式知，當輸入發生輕微變化時，輸出幾乎不變.從為了定量刻畫這種性質，引入吻合度的概念.

將{ωn,μn}的吻合度記為tn,要從理論上精確分析tn的分布規律是困難的.文獻[4]用模擬分析方法給出了密鑰為64 bit，算法的吻合度分布的統計規律.

表1 T16的分布規律

一般地有:p(t8≥9)=0.992 4,p(t16≥9)=0.990 2,p(t24≥9)=0.989 3,p(t32≥29)=0.980 0,p(t40≥37)=0.988 3,p(t48≥46)=0.986 0.

設{ω,μ}為正確的密鑰，若同時窮舉密鑰中兩個數的高nbit，則tn≥t吻合度的試驗密鑰的個數期望為22n-1,且吻合度tn≥t的試驗密鑰中包含{ωn,μn}的概率為p(tn≥t).當試驗密鑰{ω′n,μ′n}與{ωn,μn}不相等時，可認為由{ω′n,μ′n}產生的的序列與亂數序列相互獨立，因而{ω′n,μ′n}產生的序列的吻合度tn≥t的概率近似為2-t,而由模擬試驗知，{ωn,μn}的吻合度tn≥t的概率相對于2-t要大得多.據此就可將隨機試驗密鑰{ω′n,μ′n}和{ωn,μn}區分開.由上述模擬實驗結果可知，利用已知明文采取先攻擊高位密鑰再攻擊低位密鑰的方法對這兩個密碼算法進行分割攻擊，即依次攻擊k8,k16,k24,k32,k40,k48，每次選取前者的候選密鑰，可最終獲得正確密鑰，而不漏掉正確密鑰的概率為:

p=p(t8≥1)p(t16≥9)p(t24≥19)p(t32≥29)p(t40≥37)p(t48≥46)=0.92 4×0.990 2×0.989 3×0.980 0×0.988 3×0.986 0≈0.928 4

即該加密系統是不安全可破的.

3 改進辦法

針對上述問題，若要確保吻合度分布的合理性才能避免上述分割攻擊，需引入比特矩陣.由于隨機序列任然具有前幾個比特對混沌初態和參數的低位比特變化不夠敏感的性質，所以改變隨機序列[6]的產生方式.

M10×10=

如果上式將100位比特串劃分為Aj1、Aj2、Aj3.其中將Aj2表示為對64取模的整數Dj.

其中，s(c,n)表示把c循環左移n位.

如果所有的明文塊加密完畢則結束，否則執行下述操作，然后轉至步驟(b).

D*=Dj+f(Cj″)mod64

ω=fD*+70(ω)

4 改進后的安全性分析

由于矩陣乘法具有結合律，如A4=A2·A2,因此有如下結論：當n為偶數時，An=A(n/2)·A(n/2)；當n為奇數時，An=A(n/2)·A(n/2)·A，(n/2取整)，依次遞歸計算，并在計算過程中不斷對2取模，避免高精度運算.

4.1 初值敏感性分析

對混沌系統的初始條件進行微小變化，通過統計產生的二值序列中相應位置上的1和0的值的變化情況，計算相應的序列位變化率.位變化率的定義如下：

其中n為序列長度，n′為初始條件進行微小改變后生成的二值序列與原序列比較，相應位變化的個數.取μ=3.659 6，比較隨機序列的前70位得到的結果表2所示.

表2 序列變化率

4.2 密鑰吻合度分析

取μ=3.659 6，密鑰為64 bit，隨機選取10 000個密鑰統計得到如圖1～4所示的吻合度分布圖，其中虛曲線代表改進之后的吻合度分布，實線代表之前的吻合度分布.改進之后的吻合度分布趨向于隨機化，即p(tm≥t趨向于2-t,故改進之后使得基于密鑰的分割攻擊變得無效.

圖1 T8的分布規律

圖2 T16的分布規律

圖3 T24的分布規律

圖4 T32的分布規律

4.3 對于選擇明文攻擊

假設Pz與明文塊長度相同(64位),且全為0，相應的密文為Cz，則有下式(a);假設Ps與明文塊長度相同(64位),且第一位為0，其他全為1,相應的密文為Cs,則有

s(s(s(Pz,Dj)⊕Aj1,f1)⊕Aj3,f2)⊕Aj1=Czs

(s(Aj1,f1)⊕Aj3,f2)⊕Aj1=Cz

(4)

s(s(s(Ps,Dj)⊕Aj1,f1)⊕Aj3,f2)⊕Aj1=Cs

(5)

由式(4)和式(5)無法推導出Aj1,Aj3,窮舉264·264·64·64=2140次方可列舉全部的組合.

5 結 語

針對一個基于混沌設計的分組密碼算法所產生的混沌序列具有前幾個值對混沌初態的低位比特變化不敏感，無法抵抗在選擇明文攻擊條件下對密鑰的分割攻擊，提出了增加矩陣取模冪乘運算，并改進算法中參數的控制，由密鑰吻合度分布實驗可知，可基本確保任意兩個不同的試驗密鑰產生的亂數序列相互獨立，并且對初始值的變化有更好的敏感性，使得改進之后的算法，能抵抗對密鑰的分割攻擊和選擇明文攻擊.

參考文獻：

[1] Xiang T,Liao X F,Tang G P, et al. A novel block cryptosystem based on iterating a chaotic map[J].Physics Letters A,2006(349):109-115.

[2] Wang King-yuan,Yu Cang hai.Cryptanalysis and improvement on a cryptosystem based on a chaotic map

[J]. Computers and Mathematics with Applications,2009(57):476-482．

[3] 張濤.一個混沌分組密碼算法的分析[J].計算機應用研究,2010,27(6)：2294-2296.

[4] 金晨輝.一個基于混沌的分組密碼算法的分析[J].中國工程科學，2001,3(6):75-80.

[5] 金晨輝，高海英．對兩個基于混沌的序列密碼算法的分析[J]．電子學報，2004，32(7)：1066-1070．

[6] 楊建華.數列組的廣義線性相關性[J].武漢工程大學學報,2009,31(12)：79-81.

[7] 胡端平，唐超.一致矩陣的特征性質[J].武漢工程大學學報，2009，31(5)：93-94.