蔡 瓊，彭 濤，葉 楊

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

1 混沌序列加密算法

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

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

(1)

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

其中n表示精度.

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

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

c. 加密明文分組，明文分組Mj對應的密文分組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ī)律以及攻擊

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

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

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

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

使得

(2)

(3)

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

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

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

將{ωn,μn}的吻合度記為tn,要從理論上精確分析tn的分布規(guī)律是困難的.文獻[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ù)的高nbit，則tn≥t吻合度的試驗密鑰的個數(shù)期望為22n-1,且吻合度tn≥t的試驗密鑰中包含{ωn,μn}的概率為p(tn≥t).當試驗密鑰{ω′n,μ′n}與{ωn,μn}不相等時，可認為由{ω′n,μ′n}產(chǎn)生的的序列與亂數(shù)序列相互獨立，因而{ω′n,μ′n}產(chǎn)生的序列的吻合度tn≥t的概率近似為2-t,而由模擬試驗知，{ωn,μn}的吻合度tn≥t的概率相對于2-t要大得多.據(jù)此就可將隨機試驗密鑰{ω′n,μ′n}和{ωn,μn}區(qū)分開.由上述模擬實驗結(jié)果可知，利用已知明文采取先攻擊高位密鑰再攻擊低位密鑰的方法對這兩個密碼算法進行分割攻擊，即依次攻擊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 改進辦法

針對上述問題，若要確保吻合度分布的合理性才能避免上述分割攻擊，需引入比特矩陣.由于隨機序列任然具有前幾個比特對混沌初態(tài)和參數(shù)的低位比特變化不夠敏感的性質(zhì)，所以改變隨機序列[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 改進后的安全性分析

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

4.1 初值敏感性分析

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

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

表2 序列變化率

4.2 密鑰吻合度分析

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

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

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

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

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

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 結(jié) 語

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

參考文獻：

[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] 楊建華.數(shù)列組的廣義線性相關性[J].武漢工程大學學報,2009,31(12)：79-81.

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