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

蔡 瓊，彭 濤，葉 楊

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

1 混沌序列加密算法

由于混沌映射所具有的許多類似隨機(jī)的性質(zhì)和密碼學(xué)中的混淆和擴(kuò)散等性質(zhì)相似，所以出現(xiàn)了很多混沌加密算法，本文分析的混沌序列密碼算法使用的是Logistic[1]映射.

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

(1)

當(dāng)x∈[0,1],μ∈[3.5699456,4]時，Logistic映射具有混沌效應(yīng).然而由于實(shí)數(shù)在計算機(jī)中以有限的精度實(shí)現(xiàn)，對于每次迭代產(chǎn)生的x可以表示如下：

其中n表示精度.

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

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

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

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

2 加密系統(tǒng)的信息泄露規(guī)律以及攻擊

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

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

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

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

使得

(2)

(3)

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

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

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

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

表1 T16的分布規(guī)律

一般地有: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.

設(shè){ω,μ}為正確的密鑰，若同時窮舉密鑰中兩個數(shù)的高nbit，則tn≥t吻合度的試驗(yàn)密鑰的個數(shù)期望為22n-1,且吻合度tn≥t的試驗(yàn)密鑰中包含{ωn,μn}的概率為p(tn≥t).當(dāng)試驗(yàn)密鑰{ω′n,μ′n}與{ωn,μn}不相等時，可認(rèn)為由{ω′n,μ′n}產(chǎn)生的的序列與亂數(shù)序列相互獨(dú)立，因而{ω′n,μ′n}產(chǎn)生的序列的吻合度tn≥t的概率近似為2-t,而由模擬試驗(yàn)知，{ωn,μn}的吻合度tn≥t的概率相對于2-t要大得多.據(jù)此就可將隨機(jī)試驗(yàn)密鑰{ω′n,μ′n}和{ωn,μn}區(qū)分開.由上述模擬實(shí)驗(yàn)結(jié)果可知，利用已知明文采取先攻擊高位密鑰再攻擊低位密鑰的方法對這兩個密碼算法進(jì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

即該加密系統(tǒng)是不安全可破的.

3 改進(jìn)辦法

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

M10×10=

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

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

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

D*=Dj+f(Cj″)mod64

ω=fD*+70(ω)

4 改進(jìn)后的安全性分析

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

4.1 初值敏感性分析

對混沌系統(tǒng)的初始條件進(jìn)行微小變化，通過統(tǒng)計產(chǎn)生的二值序列中相應(yīng)位置上的1和0的值的變化情況，計算相應(yīng)的序列位變化率.位變化率的定義如下：

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

表2 序列變化率

4.2 密鑰吻合度分析

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

圖1 T8的分布規(guī)律

圖2 T16的分布規(guī)律

圖3 T24的分布規(guī)律

圖4 T32的分布規(guī)律

4.3 對于選擇明文攻擊

假設(shè)Pz與明文塊長度相同(64位),且全為0，相應(yīng)的密文為Cz，則有下式(a);假設(shè)Ps與明文塊長度相同(64位),且第一位為0，其他全為1,相應(yīng)的密文為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)無法推導(dǎo)出Aj1,Aj3,窮舉264·264·64·64=2140次方可列舉全部的組合.

5 結(jié) 語

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

參考文獻(xiàn)：

[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].計算機(jī)應(yīng)用研究,2010,27(6)：2294-2296.

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

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

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

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