第3章 基于混沌的流加密算法

序列密码是将消息分成连续的符号或比特串作为密钥流，然后和对应明文流分别进行加密。由于各种消息（报文、语音、图像和数据等）都可以经过量化编码等技术转化为二进制数字序列，因此假设序列中的明文空间M、密文空间C和序列空间K都是由二进制数字序列组成的集合。那么一个序列密码系统可用(M,C,K,Ek,Dk,Z)的六元组来描述。对于每一个k∈K，由算法Z确定一个二进制密钥序列z(k)=z0,z1,z2,…，当明文m=m0,m1,…,mn-1时，在密钥k下的加密过程为：对i=0,1,2,…,n-1，计算ci =mi⊕zi，密文为c=Ek(m)=c0,c1,c2,…,cn-1，其中⊕表示模2加；解密过程为：i=0,1,2,…,n-1，计算mi =ci⊕zi，由此恢复明文m=Dk(c)= m 0,m1,m2,…,mn-1。

序列密码的安全性主要依赖于密钥序列z(k)=z0,z1,z2…，因此序列密码系统设计的关键是如何设计出具有良好特性的随机密钥序列。传统密码学中常见的是基于线性反馈移位寄存器（LFSR）的密钥序列产生器。如前所述，混沌是确定性非线性系统产生的类似随机性的现象，它产生于确定性系统却又难于预测。混沌系统对初值和系统参数极端敏感，相同的混沌系统在具有微小差别的初始条件下，将会发生完全不同的长期行为，而且混沌系统的长期行为是不可预测。然而，只要系统参数和初始条件给定，混沌现象本身是可以重复再生的。利用混沌系统，可以产生数量众多、非相关、类似噪声、又可以再生的混沌序列，这种序列难于重构和预测，从而使密码分析者难以破译。所以，只要加以正确的利用，就完全可以实现将混沌理论用于序列密码的设计中。

以混沌系统为基础设计伪随机数发生器是混沌流密码研究中的一个主要的方面。目前，由于混沌密码理论还不够成熟，在考评混沌伪随机序列时还没有统一的标准和完备的理论指导，因此常借鉴传统随机序列的检测标准来对混沌随机序列进行评测。在本章中，我们将首先介绍NIST（美国国家标准与技术委员会）发布的考评随机和伪随机序列的16个指标。然后介绍基于混沌设计伪随机数发生器的主要方法，以及一类特殊的基于混沌的流加密算法和对该算法的攻击与改进。

3.1 随机序列与伪随机序列的检测标准[11, 90]

鉴别一个序列是否为随机序列，NIST给出了16项检测指标，如果序列能够通过此16项检测，则认为序列具有随机性，反之则认为序列的随机性存在缺陷。为了便于用户对随机序列进行检测，NIST提供了相应的测试软件，在计算各检测指标的过程中，使用了归一化处理，归一化后的检测结果被称之为P-Value，最终通过判断序列各项指标的P-Value值来决定其是否具有随机性。NIST发布的16项检测指标以及它们的计算方法如下所述。

3.1.1 频率测试（FT）

频率测试的目的是检测整个序列中0和1的比例，即测试序列中0和1的比例是否近似相等，约为50%。具体测试的方法如下：

步骤1，将由0，1组成的序列转换为由-1，1组成的序列，转换方式为xi =2ε-1。其中，ε，xi为转换前后的比特值。计算转换后的序列的和Sn，即Sn =x1+x2+…+xn，

步骤2，计算统计值sobs，即

步骤3，计算判断标准P-Value的值∶，其中erfc（）为互补误差函数，即

若P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.2 块内频率测试（FTB）

块内频率测试的目的是检测在长度为M比特的块中0和1的比例，即测试在块内部0和1的比例是否近似相等，约为50%。具体测试的方法如下：

步骤1，将需要检测的序列划分为个块；

步骤2，对每个块，计算其中比特值1在块中的比例，即

式中，πi为序列中第i个块内比特值1所占的比例；M为块的长度；εx为序列中第x个比特上的值。

步骤3，计算统计值

步骤4，计算判断标准P-Value的值：P-Value=igamc(N/2, (obs)/2)，其中χ2 igamc( )为Incomplete Gramma函数，其表达式为：

并且满足Q(a,0) = 1和Q(a,∞) = 0；函数Γ(a)为：

若P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.3 游程测试（RT）

所谓游程是指序列中由相同比特所构成的不间断的子序列。游程测试的目的是计算序列中游程的个数，并判断0和1的游程个数是否与随机序列一致。同时，该项测试还可以用于判断序列在0和1之间的振荡快慢。具体测试方法如下：

步骤1，对需要检测的序列进行预处理，计算1在序列中的比例，即

式中，n为序列长度，εj为比特值。

步骤2，判断预处理结果是否达到要求。如果，则认为序列不为随机序列，不再进行下面的处理。数值τ为预先设定的值，在NIST的测试代码中将它设定为。在时，转步骤3。

步骤3，计算统计值，式中r（k）的取值为：若εk =εk+1，则r（k）=1；反之r（k）=0。

步骤4，计算判断标准P-Value的值：，式中：π通过步骤1计算得到；函数erfc( )如式（3.1）所示。

若P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.4 块内比特1的最长游程测试（LROBT）

此项测试的目的是检测在长度为 M比特的块中比特1的最长游程，并比较在测试序列内比特1的最长游程的长度是否与随机序列一致。具体计算步骤如下所述。

步骤1，将序列划分为长度为M比特的块。M的取值如表3.1所示。

步骤2，按照表3.2中的规则，统计每个块中的最长游程出现的频率vi。

步骤3，计算统计值

式中，参数K和N的值由块的长度M确定，如表3.3所示。参数πi的取值如表3.4所示。

步骤4，计算判断标准P-Value的值：P-Value=igamc(K/2, (obs)/2)，函数igamc( )χ2如式（3.2）所示。

若P-Value的值小于0.01，则认为测试的序列不是随机序列，反之则认为序列是随机序列。

3.1.5 二进制矩阵阶测试（BMRT）

二进制矩阵阶测试的目的是计算序列中不相交子矩阵的阶，并据此判断原始序列中固定长度的子序列之间的线性依赖关系。具体计算步骤如下：

步骤1，将序列划分为M×Q比特的不相交的块；序列中块的数目为。序列在划分为 N个块后，若还有的多余的比特，则丢弃不用。将每个块转换为 M行Q列的矩阵。

步骤2，计算每个矩阵的阶Rl, l=1,2, …, N。

步骤3，定义变量FM，FM-1为阶是M和M-1的矩阵个数；N-FM-FM-1为其余矩阵的个数。

步骤4，计算统计值

步骤5，计算判断标准P-Value的值：。

若P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

同时注意对于此项测试要求序列的长度必须满足n≥38MQ。

3.1.6 离散傅里叶变换（谱）测试（DFTT）

此项测试的目的是计算序列在进行离散傅里叶变换时尖峰的高度，并据此判断测试序列的周期特性。具体计算步骤如下：

步骤1，将由0，1组成的序列转换为由-1，1组成的序列，转换方式为xi =2ε-1。其中，ε，xi为转换前后的比特值。

步骤2，对转换后的序列X进行离散傅里叶变换（DFT），得到序列S = DFT(X)。设Sj为S中第j个元素，则

式中，exp(2πikj/n)=cos(2πkj/n)+i sin(2πkj/n),j=0,1,…,n-1且。

步骤3，计算M =modulus(S′)，其中S′是由S的前n/2个元素组成的子序列，求模函数modulus用于产生尖峰高度序列。

步骤4，计算，作为尖峰高度的95%的阈值。

步骤5，计算N0 =0.95n/2, 表示值小于T的尖峰的期望的理论数量。

步骤6，计算N1，它表示M中实际的观察到的值小于T的尖峰数量。

步骤7，计算，然后计算判断标准P-Value的值：

若P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.7 非重叠模板匹配测试（NTMT）

此项测试的目的是计算预先定义的模板在检测序列中的发生次数，即测试序列中是否有过多的预先给定的非周期模板。具体计算步骤如下：

步骤1，将测试序列分成N个独立的块，每个块长为M比特。

步骤2，Wj(j=1,…,N)表示模板B出现在第j个块中的个数。设模板B的比特长度为m。在查找B的过程中，通过在序列上产生一个长度为m比特的窗口来进行搜索，比较窗口中的比特与模板B是否匹配。如果不匹配，窗口向后滑一位；如果匹配，窗口向后滑动m比特。

步骤3，按照式（3.5）计算均值（μ）和方差（σ2）

步骤4，计算统计值

步骤5，计算统计标准P-Value的值：

P-Value=igmc(N/2, (obs)/2)χ2

注意，对于每个模板都需要计算一个P-Value值，故需要计算多个P-Value值。igamc( )如式（3.2）所示。若计算出的P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.8 重叠模板匹配测试（OTMT）

此项测试的目的同样是计算预先定义的模板在检测序列中的发生次数，即测试序列中是否有过多地预先给定的非周期模板。此项测试与非重叠模板匹配测试类似，在测试过程中也需要使用一个窗口，只是不管窗口中的数据是否与模板匹配，在比较完成后窗口都只向后滑动1比特。具体计算步骤如下：

步骤1，将序列分成N个独立的块，每个块长为M比特。

步骤2，计算N个块中的模板B的出现次数。设模板B的比特长度为m。在查找B的过程中，通过在序列上产生一个长度为m比特的窗口来进行搜索，每次比较之后，窗口都向后滑动1比特。记录模板B在每个块中的出现次数，并根据B出现次数，将数组v中的元素vi（i = 0,…,5）的值增加1，即B的出现次数为0，1，2，3，4时分别将v0，v1，v2，v3，v4的值增加1；B出现的次数为5次及其以上时，将v5的值增加1。

步骤3，根据式（3.7）计算λ和η的值：

步骤4，计算

式中，π0 = 0.367879, π 1= 0.183940, π 2 = 0.142670, π 3 =0.106645, π 4 =0.077147, π5=0.166269。

步骤5，计算统计标准P-Value的值：

P-Value=igamc(5/2, (obs)/2)χ2

式中，igamc( )如式（3.2）所示。若计算出的P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.9 Maurer通用统计测试（MUST）

此项测试主要集中于考察匹配模式中的比特数目（与压缩序列长度相关的测度），测试的目的是为了检测序列是否可以在不丢失信息的情况下进行显著压缩。如果能，则说明序列不是随机序列。具体计算步骤如下所述。

步骤1，将n比特序列分两个部分：初始部分和测试部分。初始部分为Q个L比特的非重叠模块；测试部分为K个L比特的非重叠模块，剩余的不足L比特的数据忽略不计。即将序列前Q个块用做初始化，剩余的K个块用于测试（K=[n/L]-Q）。

步骤2，处理初始部分，对其中每个可能的L比特的值创建一个表格，表格中的值为对应的L比特块在初始部分最后出现时的块的编号。即i依次取从1到Q值，并设置Tj=i，其中j为第i个L比特块对应的十进制数。

步骤3，依次对测试部分的K个块进行处理（即i依次取Q + 1至Q + K），用当前测试块的编号替换表中对应的记录值，即设置Tj=i（j为第i个L比特块对应的十进制数）。同时，计算相同的 L比特数据重新出现的距离，并且对该距离值取log2的对数，然后计算此K个数的平均值，即

式中，Tj同样为第i个块中L比特对应的十进制数值。

步骤4，计算统计标准P-Value的值：

式中，函数erfc( )如式（3.1）所示。L为块的长度，expectedValue（L），δ可从事先计算出的表3.5中取值。在假设序列为随机序列的条件下，expecetdValue( )表示期望值，且参数δ可按照下式计算：

若计算出的P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

另外，对于需要检测的长度为n的序列，L，Q的取值可参照表3.6。

3.1.10 LZ压缩测试（LZCT）

此项测试需要对序列中不同的单词进行计数，测试目的是检测序列可以被压缩的程度。具体计算步骤如下所述。

步骤1，将序列分成连续，独立的且不相同的单词，用于形成序列的单词“字典”。产生字典中单词的过程为：依次从序列中抽出比特组成子字串，如果该子字串不在字典中存在则将此子字串加入字典中，如果已经存在则将序列中下一个比特加入到子字串中组成一个新的单词。比如序列0101110010，形成的字典中单词为0，1，01，10，010。定义Wobs表示字典中的单词总数。

步骤2，计算统计标准P-Value的值：

式中，μ=69586.25,,n=106。对于不同的n值,μ和δ的值需要重新计算。由于当前没有理论指导如何计算μ和δ，测试中需要的μ和δ值是借助于SHA-1产生的序列进行计算产生的。函数erfc( )如式（3.1）所示。

若计算出的P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.11 线性复杂度测试（LCT）

此项测试集中于计算反馈移位寄存器的长度，其目的是判定序列是否具有足够高的线性复杂度。通常认为随机序列具有比移位寄存器更高的线性复杂度，如果线性复杂度不够高，通常可认为序列不具有随机性。具体计算步骤如下所述。

步骤1，将长度为 n比特的序列分成 N个独立的块，块的长度为 M比特，即n=MN。

步骤2，使用B-M算法，确定N个块的线性复杂度Li(i=1,2,…,N)。

步骤3，假设序列随机，计算理论均值μ∶

步骤4，对每个块，计算其对应的Ti值：

Ti = (-1)M ·(Li-μ)+2/9

步骤5，根据Ti的值和表3.7中的规则，设置v0,…,v6的值。

步骤6，计算，式中π0=0.03125，π1=0.125，π2=0.5，π3=0.25，π4=0.0625，π5=0.02078；K为自由度，NIST在其测试代码中将其值默认设置为6。

步骤7，计算统计标准P-Value的值：

P-Value=igamc(K/2,χ 2(obs)/2)

式中，igamc( )如式（3.7）所示。若计算出的P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.12 串行测试（ST）

此项测试计算在整个序列中所有可能的重叠模板（模板长度为m比特）的频率，其目的是判断2m个 m比特的重叠模板在序列中出现的频率是否与随机序列中模板的出现频率大致相同。注意当 m=1的时，串行测试就退化为频率测试。具体测试步骤如下所述。

步骤1，对测试序列ε进行扩展，将初始的m-1个比特附加在序列的最后，形成一个新的序列，记为ε′。

步骤2，计算所有可能的重叠长度为m，m-1和m-2比特块的出现频率。令表示长度为m比特的块i1…im的出现频率；令表示长度为m-1比特的块i1…im-1的出现频率；令表示长度为m-2比特的块i1…im-2的出现频率。

步骤3，计算对应的变量值∶

步骤4，计算，即,。

步骤5，计算判断标准的值

其中，igamc( )如式（3.2）所示。若计算出的P-Value1和P-Value2的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.13 近似熵测试（AET）

此项测试需要计算整个序列中所有长度为m的可重叠块的频率，其目的是比较两个长度连续（即长度为m和m+1）的可重复模块的出现频率是否大致与随机序列相同。具体计算步骤如下所述。

步骤1，设测试序列ε的初始长度为n，对其进行扩展，将初始的m-1个比特附加在序列的最后，形成一个新的序列，记为ε′。

步骤2，对n个可重叠块统计其频率，记为，i表示长度为m比特的二进制串对应的数值。即，其中#i表示数值为 i的块出现的次数，n为序列的初始长度，也是所有长度为m的块的个数。

步骤3，计算∶，其中,j=log2 i。

步骤4，将m更改为m+1，然后重复步骤1至步骤4。

步骤5，计算统计值∶

χ2= 2n[log 2-ApEn(m)]

式中，ApEn(m)=φ(m-φ(m+1)。

步骤6，计算统计标准P-Value的值：

式中igamc()如式（3.2）所示。若计算出的P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.14 累积和测试（CST）

此项测试在将序列调整为±1序列后，计算每个随机通路中最大的偏差，其目的是确定在测试序列中是否存在部分序列的累计和相对于随机序列的累积和，显得过大或者过小。对随机序列而言偏差应该接近于0。具体计算步骤如下所述。

步骤1，将由0，1组成的序列转换为由-1，1组成的序列，转换方式为，其中εi，xi为转换前后的比特值。

步骤2，计算部分和Si，如果mode为0表示从第一个比特X 1开始计算部分和1，如果mode为1表示从最后一个比特Xn开始计算部分和，具体如表3.8所示。

即mode=0时, Sk =Sk-1+X k；mode=1时，Sk =Sk-1+Xn-k+1。

步骤3，计算部分和绝对值的最大值z，即

步骤4，计算统计标准P-Value的值：

式中，函数Φ(x)的定义为：

若计算出的P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.15 随机偏离测试（RET）

此项测试需要计算在累积和随机通路中恰好观察到K次的循环数目。累积和随机通路从转变为±1的序列中产生，每个循环由起始为0结束也为0的子序列构成。此项测试的目的是判断在循环内观察到某个特定状态的次数是否于随机序列一致。具体计算步骤如下：

步骤1，将由0，1组成的序列转换为由-1，1组成的序列，转换方式为Xi =2εi-1，其中εi，xi为转换前后的比特值。

步骤2，计算部分和，即

S 1=X1, S 2=X1+X2, …, Sk =X 1+X2+X3+…+Xk, …,

Sn =X 1+X2+X3+…+Xk +…+Xn

步骤3，在所有部分和前后分别加上0，组成一个新的序列S′，即

步骤4，定义J为序列S 中被0分割的子序列个数也就是循环的个数，所谓循环是指起点为0，终点也为0，中间为任一数字的子序列。

步骤5，对每个循环，计算其中非零值x(-1和1≤x≤4)的出现频率。4≤x≤-

步骤6，对x的8个状态，计算vk(x)的值。vk(x)表示状态x在所有循环中，出现恰好为k次的总数目，其中k的取值为0, 1, 2, …, 5（对于出现次数超过5的情况，其出现次数算做v5(x)）。

步骤7，对x的8个状态，分别按照下式计算统计值：

式中，πk(x)为随机分布中状态x出现k次的概率，其取值如表3.9所示。

步骤8，对每个状态值x，计算判断标准P-Value的值，即

P-Value=igamc(5/2,χ 2(obs)/2)

式中，igamc()如式（3.2）所示。若计算出的P-Value的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。

3.1.16 随机偏离变量测试（REVT）

此项测试主要是计算在累积和随机通路中某个特定状态出现的次数的总数目，其目的是检测观察到的数目与随机通路中的各种状态之间偏离情况。具体计算步骤如下所述。

步骤1，将由0，1组成的序列转换为由-1，1组成的序列，转换方式为，其中εi，Xi为转换前后的比特值。

步骤2，计算部分和，即

S 1=X1, S 2=X1+X2, …, Sk =X 1+X2+X3+…+Xk, …,

Sn =X 1+X2+X3+…+Xk +…+Xn

步骤3，在所有部分和前后分别加上0，组成一个新的序列S，即

步骤4，定义J为序列S 中被0分割的子序列个数也就是循环的个数，所谓循环是指起点为0，终点也为0，中间为任一数字的子序列。对x的18个非零状态值，计算ξk(x)的值。ξk(x)为状态x出现在所有J个循环中次数的总和。

步骤5，对每个ξk(x)，计算判断标准P-Value的值，即

式中erfc( )如式（3.1）所示。若计算出的P-Vvalue的值小于0.01，则认为测试的序列不为随机序列，反之则认为序列是随机序列。