1混沌序列加密算法由于混沌映射所具有的许多类似随机的性质和密码学中的混淆和扩散等性质相似，所以出现了很多混沌加密算法，本文分析的混沌序列密码算法使用的是Logistic［1］映射.
f(x)=μx(1-x),x∈［0,1］,μ∈［3.5699456,4］
(1)当x∈［0,1］,μ∈［3.5699456,4］时，Logistic映射具有混沌效应.然而由于实数在计算机中以有限的精度实现，对于每次迭代产生的x可以表示如下：x(n)=∑n-1i=0xi2i
其中n表示精度.明文分组长度是64 bit,密钥是混沌的初始控制参数x0和μ.该加密算法如下四步：a. 初始化，以初态x0和控制参数μ迭代N0次，得到ω.即ω=fN0μ(x0).b. 以ω为初态迭代70次，并取出每次迭代得到的二进制数xni的第k位,得到一个70位的二进制随机序列{xni(k)}70i=1,将此随机序列分为两部分.
Aj={xni(k)}64i=1，Dj=∑5i=025-ixni(k)
其中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的等效密钥，只要完成了对{ω,μ}的攻击就完成了对加密系统的攻击.在选择明文攻击条件下，选取第一个64 bit明文分组为全零分组，即M1=(0,0,0,…,0),C1为对应的密文分组，则由Cj=(MjDj)Aj知C1=A1.即当第一个64 bit明文分组为全零时，其对应的密文分组就是随机序列的前64 bit值{xni(k)}64i=1.下面分析由{xni(k)}64i=1恢复等效密钥{ω,μ}.定理1［4］设x0,x1,x2,…是利用混沌变换f(x)=μx(1-x),0＜x＜1由m精度的初值x0产生的m精度小数序列，xi′是xi的n精度小数，则在xi′给定时，xi+1′至多有5种变化，且2nxi+1′的可能取值范围是仅与xi′有关的连续的整数.定理2［5］设函数f(x)=μx(1-x),μ,μ+δ∈(3.5699456,4］,x,x+ε∈［0,1］，则:
|fμ(x)-fμ+δ(x+ε)|≤4|ε|+14|σ|.证明：由于函数f(x)在［0,1］是连续可导的，则由拉格朗日中值定理知，存在
ξμ∈［x,x+ε］,ηx+δ∈［μ,μ+δ］
使得
fμ(x)-fμ(x+ε)=xfμ(x)|x=ξμ·|ε|(2)
fμ(x+ε)-fμ+δ(x+ε)=μfμ(x)|μ=ηx+δ·|δ|(3)
将(2)、(3)两式相加得到
|fμ（x)-fμ+δ(x+ε)|=xfμ(x)|x=ξμ·|ε|+μfμ(x)|μ=ηx+δ·|δ|再由xfμ(x)=|μ(1-2x)|＜4μfμ(x)=|x(1-x)|=14-1-122＜14得到：fμ(x)-fμ+δ(x+ε)≤4|ε|+14|δ|定理1、2说明，Logistic混沌映射具有如下性质：输入的低位变化对输出的高位影响不大，而上述加密系统中的实际用来加密的二进制流，是由混沌映射反复迭代产生的，这就导致了混沌序列具有前几个值对混沌初态和参数的低位比特变化不够敏感的性质；由随机序列的产生方式知，当输入发生轻微变化时，输出几乎不变.从为了定量刻画这种性质，引入吻合度的概念.定义［5］设k和k′分别是某密码算法的正确密钥和试验密钥，{bi}∞i=1和{bi′}∞i=1分别是它们产生的随机序列，则称max{t:i,1≤i≤t,bi=bi′}为k′的吻合度.将{ωn,μn}的吻合度记为tn,要从理论上精确分析tn的分布规律是困难的.文献［4］用模拟分析方法给出了密钥为64 bit，算法的吻合度分布的统计规律.

表1T16的分布规律
Table 1Regularities of distribution of T16
T16<=8910111213141516171819202122232425>=26个数98721161933143984595595896265835985695174903983493012771第6期蔡琼，等：一种混沌序列加密算法的密码分析
武汉工程大学学报第33卷
一般地有: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.设{ω,μ}为正确的密钥，若同时穷举密钥中两个数的高n bit，则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］的产生方式.算法中，以初态xt和参数μ迭代100次，并取出每次迭代得到的二进制数xni的第k位，得到二进制序列{xni(k)}100i=1，将此序列排列成一个10×10的矩阵M10×10,并取二进制序列最后的16bit序列{xni(k)}100i=85，表示为一个整数Ni,最后计算MNi, 将迭代之后的矩阵按行排列为二进制比特串:
M10×10=
B1B2…B64Aj1B65B66…B70Aj2B71B72…B100Aj3,Bi∈{0,1}如果上式将100位比特串划分为Aj1、Aj2、Aj3.其中将Aj2表示为对64取模的整数Dj.将明文块Pj循环右移Dj,获得一个新的块Pj′,对新的块Pj′通过与Aj1异或得到密文C，然后执行下述操作：Cj=Pj′Aj1,f1=(f(Aj1)+f(Aj3))mod64Cj′=s(Cj,f1)Aj3,f2=(f(Aj1)+3f(Aj3))mod64Cj″=s(Cj′,f2)Aj1
其中，s(c,n)表示把c循环左移n位.
f(A)=∑7i=0Ai如果所有的明文块加密完毕则结束，否则执行下述操作，然后转至步骤(b).D*=Dj+f(Cj″)mod64ω=fD*+70(ω)4改进后的安全性分析改进之后随机序列的产生方式改为在之前的随机序列基础上增加矩阵［7］的取模幂乘.然而增加矩阵幂乘运算会减慢加密的速度，采用以下算法，其法时间复杂度为O(logn2）(n为矩阵迭代指数):由于矩阵乘法具有结合律，如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的值的变化情况，计算相应的序列位变化率.位变化率的定义如下：
T=n′n其中n为序列长度，n′为初始条件进行微小改变后生成的二值序列与原序列比较，相应位变化的个数.取μ=3.659 6，比较随机序列的前70位得到的结果表2所示.表2序列变化率
Table 2Sequence rate
混沌系统
初始条件0.30.40.50.60.7变化后的
初始条件0.300 0010.400 0010.500 0010.600 0010.700 001原混沌系统位变化率0.485 70.50.442 90.500 10.485 6改进后位
变化率0.571 40.628 60.600 30.514 30.582 3改进后相对于原随机序列的变化率0.557 10.50.601 20.314 30.552 7由表2可知，改进后的混沌系统比原系统有更好的初值敏感性，对于第一个全零的明文分组有：C1=(MD1)A1，知C1=A1，但是从上表得知改进后的系统使得随机序列有了平均50%以上的变化率，需要穷举至少C3570≈270次才能恢复随机序列，对密钥的分割攻击的计算复杂度为C3570·260≈2130,有效地抵抗了密钥分割攻击.4.2密钥吻合度分析取μ=3.659 6，密钥为64 bit，随机选取10 000个密钥统计得到如图1~4所示的吻合度分布图，其中虚曲线代表改进之后的吻合度分布，实线代表之前的吻合度分布.改进之后的吻合度分布趋向于随机化，即p(tm≥t趋向于2-t,故改进之后使得基于密钥的分割攻击变得无效.图1T8的分布规律
Fig.1Regularities of distribution of T8图2T16的分布规律
Fig.2Regularities of distribution of T16图3T24的分布规律
Fig.3Regularities of distribution of T24图4T32的分布规律
Fig.4Regularities of distribution of T324.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结语针对一个基于混沌设计的分组密码算法所产生的混沌序列具有前几个值对混沌初态的低位比特变化不敏感，无法抵抗在选择明文攻击条件下对密钥的分割攻击，提出了增加矩阵取模幂乘运算，并改进算法中参数的控制，由密钥吻合度分布实验可知，可基本确保任意两个不同的试验密钥产生的乱数序列相互独立，并且对初始值的变化有更好的敏感性，使得改进之后的算法，能抵抗对密钥的分割攻击和选择明文攻击.