密码学基础与应用之序列密码分析（上）

      序列密码也称为流密码(Stream Cipher)，它是对称密码算法的一种,它利用密钥产生一个密钥Z=Z1Z2Z3…，然后利用此密钥流依次对明文X=X0X1X2...进行加密，是一个随时间变化的加密变换，转换速度快，传播错误率低。

　　序列密码是密码学的一个重要分支，由于人们对序列密码的研究比较充分，而且序列密码具有实现简单、便于硬件实施、效率高等特点，因此在实际应用中，特别是专用或机密机构中保持着优势，所以序列密码在许多重要应用领域中成为主流密码。

　　1 序列密码的概念

人们在"一次一密"密码在理论上是不可破译的这一事实中感觉到，如果想要得到保密性很高的密码，可以用某种方式仿效"一次一密"密码。人们一直以来都想要用序列密码的方式仿效"一次一密"密码，想要用这个方式来促进了序列密码的研究和发展。序列密码的理论到目前为止来讲已经是比较成熟的了，它在许多重要领域应用当中成为了主流的密码体制。

　　序列密码使用尽可能长的密钥可以使他的安全性提高，但是一般密钥长度长的对于其存储、分配都很困难。于是人们便想出采用一个短的种子密钥的办法来控制某种算法产生出长的密钥序列，用以提供加解密使用，这个种子密钥的长度较短，存储、分配起来都比较容易。

      序列密码的原理如图2-20所示。序列密码采用简单的模2加法器来作为它的加解密器，这样可以使序列密码的工程实现非常方便。所以，产生密钥序列的算法就是序列密码的关键。由密钥序列产生算法可以产生随机性和不可预测性好的密钥序列，而且目前己经有许多产生优质密钥序列的算法。序列密码实际应用中的关键技术是保持通信双方的精确同步。因为通信双方必须能够产生相同的密钥序列，所以这种密钥序列只能是伪随机序列而不可能是真随机序列，但是可以具有良好随机性和不可预测性的伪随机序列。

图2-20 序列密码的原理

　　密钥序列产生算法部采用带存储的时序算法可以产生出随机性好并且周期足够长的密钥序列，它的理论模型是有限自动机，时序电路是它的实现电路。

　　2 线性移位寄存器序列

　　(1)移位寄存器

      在数字电路中，用来存放二进制数据或代码的电路称为寄存器。寄存器是由具有存储功能的触发器组合起来构成的，其结构如图2-21。其中s₀，s_l,s_n-l组成左移移位寄存器，并且称每一时刻移位寄存器的具体取值做为它的一个状态。要通过函数f(s₀，s_l,…,s_n-l)计算产生移位寄存器的输出，与此同时还需要送入s_n-l。函数f(s₀，s_l,…,s_n-l)是移位寄存器的反馈函数。假如反馈函数f(s₀，s_l,…,s_n-l)是s₀，s_l,s_n-l的线性函数，那么便可以称移位寄存器为线性移位寄存器(LSR) ，否则称为非线性移位寄存器。

图2-21 移位寄存器

　　（2）反馈函数

　　设f(s₀，s_l,…,s_n-l)为线性函数，则f(s₀，s_l,…,s_n-l)可写成

　　f(s₀，s_l,…,s_n-l)=g₀s₀+g₁s_l+,…,+g_n-1s_n-l                      (2-34)

　　其中，g₀，g₁，…，g_n-1是反馈系数。在二进制的情况下，式(2-34)中的+就是模2加⊕，这个时候线性移位寄存器的结构如图2-22 所示。其中反馈系数giЄGF(2),如果g_i=O，则表示式(2-34)当中的g_is_i项不存在，表示均不连接。同理， g_i=1表示s_i连接。所以g_i就相当于一个开关的作用。

　　形式地，用xⁱ与s_i相对应，x的一个多项式可以根据式(2-34)的反馈函数导出:

　　g(x)=g_nxⁿ+g_n-1x^n-l+,…,+g₁x+g₀                        (2-35)

      g(x)可称为线性移位寄存器的连接多项式。和图2-22的对照可以得知， g_n=g₀=1。不然，如果g_n=0则输出反馈不到s_n-l  ，如果g₁=0那么s₀便不起作用，应该将其去掉。

图2-22 GF(2)上的线性移位寄存器

　　反馈函数完全可以决定线性移位寄存器的输出序列的性质，也就是完全由连接多项式所决定，具有了连接多项式的概念线，性移位寄存器的输出序列的性质就可以利用数学工具来深入研究。线性移位寄存器的输出序列的理论在现在来讲已经十分成熟。n级线性移位寄存器最多可以有7个不同的状态。如果其初始的状态为零，那么其后续的状态恒为零。如果其初始的状态不为零，那么其后续状态也不为零。由此可知，n级线性移位寄存器的状态周期≤2ⁿ-1，输出序列的周期≤2ⁿ-1。线性移位寄存器的只要选择合适的连接多项式便可使它的输出序列周期达到最大值2ⁿ-1，这时的输出序列便可以称为是最大长度线性移位寄存器输出序列，简称为m序列。

　　将序列当中连续的i个1称为长度等于i的1游程，把序列中连续的i个0称为长度等于i的0游程，我们便可以发现m序列具有以下的良好随机性:

　　①在一个周期内，0和l的出现次数接近相等，也就是0出现的次数为2^n-1-1， 而1的出现次数为2^n-1；

　　②在一个周期内，当游程总数为2^n-1时，它的中长度是i（1≤i≤n-2）的1游程和0游程的数目各均有2^n-i-2个，有1个长度为n-l的0游程，有1个长为n的1游程。

      ③自相关函数

                                （2-36）

　　m序列因为具有良好的随机性，使得它不管是在密码方面，还是在通信、雷达等方面都能得到广泛应用。

　　可以证明，当连接多项式g(x)仅为本原多项式时，它的线性移位寄存器的输出序列为m序列。假设f（x）是GF(2)上的一个多项式，将f（x）|x^p-l的最小正整数p 称为f（x）的周期。如果f（x）的次数为n，并且周期为2ⁿ-1，那么就称f（x）为本原多项式。已经证明，对于任意的正整数n ， 至少存在一个n 次本原多项式。这个可以表明，至少有一种连接方式可以使任意的n级线性移位寄存器输出为m序列的一个序列。

      例2-1 设g（x）=x⁴+x+1， g(x)为本原多项式，以其为连接多项式的线性移位寄存器如图2-23所示，它的输出序列为100110101111000...，它是一个周期为24-1=15的m序列。

图2-23 连接多项式为g（x）=x⁴+x+1的线性移位寄存器

　　尽管线性移位寄存器序列具有良好的随机性，但依然还是可以破译线性移位寄存器序列密码。一般来说，用每秒100万次的计算机一天之内便可以破译n=1000的线性移位寄存器序列密码。

　　移位寄存器可以用来寄存代码，还可以用来实现数据的串行—并行转换、数值的运算以及数据的处理等，它在序列密码当中是一个相当不错的一种。而序列密码当中还包括有RC4序列密码以及ZUC算法这两种，在这里小编就先不讲了，留在了序列密码分析下篇里面再详细地给大家分析讲解一下，大家喜欢的话也敬请关注哦。