应用密码学第4章序列密码体制

第4章序列密码体制4.1密码学中的随机数4.2序列密码的概念及模型4.3线性反响移位存放器4.4非线性序列简介4.5常用的序列密码算法 4.1密码学中的随机数

为什么在密码学中要讨论随机数的产生？因为许多密码系统的平安性都依赖于随机数的生成，例如DES加密算法中的密钥，RSA加密和数字签名中的素数。所有这些方案都需要足够长度并且要“随机〞的数，即使得任何特定值被选中的概率足够小，防止对方根据概率来优化搜索策略。例如DES密钥空间大小为256，如果密钥k是随机产生的，那么对方要尝试256个可能的密钥值。但是如果密钥k这样产生：选取一个16位随机秘钥s，然后利用一个复杂但是公开的函数f将其扩展为56位密钥k，这时对方只要尝试216个可能的密钥值就能找到真正密钥。随机数的使用

序列密码的保密性完全取决于密钥的随机性。如果密钥是真正的随机数，那么这种体制在理论上就是不可破译的。但这种方式所需的密钥量大得惊人，在实际中是不可行的。因此，目前一般采用伪随机序列来代替随机序列作为密钥序列，也就是序列存在着一定的循环周期。这样序列周期的长短就成为保密性的关键。如果周期足够长，就会有比较好的保密性。现在周期小于1010的序列很少被采用，周期长达1050的序列也并不少见。伪随机数产生器

计算机上的随机数产生器并不是随机的，因为计算机一直是具有完全确定性的机器，特别在行为随机性方面表现得不尽人意。所以当程序员需要一个或一组真正的随机数时，他们必须通过各种方式近似地生成随机数。

什么是伪随机数生成器〔PRNG〕？假定需要生成介于1和10之间的随机数，每一个数出现的几率都是一样的。理想情况下，应生成0到1之间的一个值，不考虑以前的值，这个范围中的每一个值出现的几率都是一样的，然后再将该值乘以10。因为在0和1之间有无穷多个值，计算机不能提供这样的精度。为了编写代码来实现类似于前面提到的算法，常见情况下，伪随机数生成器生成0到N之间的一个整数，返回的整数再除以N。得出的数字总是处于0和1之间。对生成器随后的调用采用第一次运行产生的整数，并将它传给一个函数，以生成0到N之间的一个新整数，然后再将新整数除以N返回。这意味着，由任何伪随机数生成器返回的数目会受到0到N之间整数数目的限制。

在大多数的常见随机数发生器中，N是232-1〔大约等于40亿〕，对于32位数字来说，这是最大的值。换句话说，我们经常碰到的这类生成器能够至多生成40亿个可能值，而40亿的个数根本不算大。伪随机数生成器将作为“种子〞的数当作初始整数传给函数。由伪随机数生成器返回的每一个值完全由它返回的前一个值所决定。因此，最初的种子决定了这个随机数序列。如果知道用于计算任何一个值的那个整数，那么就可以算出从这个生成器返回的下一个值。

伪随机数生成器是一个生成完全可预料的数列〔称为流〕确实定性程序。一个编写得很好的PRNG可以创立一个序列，而这个序列的属性与许多真正随机数的序列的属性是一样的。例如：〔1〕PRNG可以以相同几率在一个范围内生成任何数字；

〔2〕PRNG可以生成带任何统计分布的流；

〔3〕由PRNG生成的数字流不具备可区分的模。基于密码算法的随机数产生器

1．使用软件方法的随机数产生器

一个常用的随机数产生器是属于线性拟合生成器一类的。这类生成器相当普遍，它们采用很具体的数学公式：

Xn+1=(aXn+b)modc即第n+1个数等于第n个数乘以某个常数a，再加上常数b。如果结果大于或等于某个常数c，那么通过除以c，并取它的余数来将这个值限制在一定范围内。注意，a、b和c通常都是质数。DonaldKnuth在“TheArtofComputerProgramming〞一书中详细介绍了对于这些常数，如何挑选好的值。2．使用硬件方法的随机数产生器

真正的随机数发生器是非确定的，在计算机上执行非确定性事情的唯一方法是从一些自然的随机过程中收集数据。最好的一种方法涉及使用电子Geiger计数器，每次当它检测到放射性衰变时，它就会生成一个脉冲。衰变之间的时间是一个实足的、纯粹的随机局部。尤其是，没有人可以预测到下一次衰变的时间大于还是小于自上次衰变以来的时间。那就产生了一位随机信息。目前生成随机数的几种硬件设备都是用于商业用途。得到广泛使用的设备是ComScireQNG，它是使用并行端口连接到PC的外部设备，它可以在每秒钟生成20000位，这对于大多数注重平安性的应用程序来说已经足够了。

另外，Intel公司宣布他们将开始在其芯片组中添加基于热能的硬件随机数发生器，而且根本上不会增加客户的本钱。迄今为止，已经交付了一些带有硬件RNG的CPU。伪随机数的评价标准

如果一序列产生器是伪随机的，它应有下面的性质：

〔1〕看起来是随机的，说明它可以通过所有随机性统计检验。

现在有许多统计测试。它们采用了各种形式，但共同思路是它们全都以统计方式检查来自发生器的数据流，尝试发现数据是否是随机的。

确保数据流随机性的最广为人知的测试套件就是GeorgeMarsaglia的DIEHARD软件包〔请参阅〕。另一个适合此类测试的合理软件包是pLab〔请参阅〕。〔2〕它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。

〔3〕它不能可靠地重复产生。如果用完全同样的输入对序列产生器操作两次将得到两个不相关的随机序列。 4.2序列密码的概念及模型

序列密码算法将明文逐位转换成密文。该算法最简单的应用如图4－1所示。密钥流发生器〔也称为滚动密钥发生器〕输出一系列比特流：K1，K2，K3，…，Ki。密钥流〔也称为滚动密钥〕跟明文比特流P1，P2，P3，…，Pi，进行异或运算产生密文比特流，即Ci=Pi⊕Ki

〔4－1〕图4－1序列密码在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。Pi

=Ci⊕Ki

〔4-2〕系统的平安性完全依靠密钥流发生器的内部机制。如果它的输出是无穷无尽的“0〞序列，那么密文就是明文，系统没有加密功能。如果它产生的是一个重复性的16比特模式，那么该算法仅是一个可忽略平安性的异或运算。如果是一系列无尽的随机流，那就是一次一密乱码本和非常完美的平安。实际的序列密码算法其平安性依赖于简单的异或运算和一次一密乱码本。密钥流发生器生成的看似随机的密钥流实际上是确定的，在解密的时候能很好地将其再现。密钥流发生器输出的密钥越接近随机，对密码分析者来说就越困难。

如果密钥流发生器每次都生成同样的密钥流的话，对攻击来说，破译该算法就容易了。

假的Alice得到一份密文和相应的明文，他就可以将两者异或恢复出密钥流。或者，如果他有两个用同一个密钥流加密的密文，他就可以让两者异或得到两个明文互相异或而成的消息。这是很容易破译的，接着他就可以用明文跟密文异或得出密钥流。现在，无论他再拦截到什么密文消息，他都可以用她所拥有的密钥流进行解密。另外，他还可以解密，并阅读以前截获到的消息。一旦Alice得到一明文—密文对，他就可以读懂任何东西了。

这就是为什么所有序列密码也有密钥的原因。密钥流发生器的输出是密钥的函数。这样，Alice有一个明文—密文对，但他只能读到用特定密钥加密的消息。更换密钥，攻击者就不得不重新分析。序列密码算法对加密那些永不结束的通信数据流是特别有用的：如两台计算机之间的T1连接。1．自同步序列密码

自同步序列密码就是密钥流的每一位是前面固定数量密文位的函数，图4－2描述了其工作原理。其中，内部状态是前面n比特密文的函数。该算法的密码复杂性在于输出函数，它收到内部状态后生成密钥序列位。

因为内部状态完全依赖前面n个密文位，所以解密密钥流发生器在收到n个密文位后自动跟加密密钥流发生器同步。

在该模式的智能化应用中，每个消息都以随机的n位报头开始。这个报头被加密、传输、解密，在n位密文之前整个解密是不正确的，直到之后两个密钥流发生器同步。自同步密码的缺点是错误扩散。传输中每一个密文位被窜改，解密密钥流发生器就有n位密钥流位不能正确生成。因此，一位密文错误就会导致n位相应的明文错误，直到内部状态里面不再有该错误位。图4－2自同步密钥流发生器2．同步序列密码

在同步序列密码中密钥流是独立于消息流而产生的。加密端密钥流发生器一位接一位地产生密钥，在解密端另一个发生器产生出完全相同的密钥。两个密钥发生器同步以后，这种一致就开始了。如果其中一个发生器跳过一个周期或者一个密文位在传输过程中丧失了，那么错误后面的每一个密文字符都不能正确解密。

如果错误不幸发生了，发方和收方就必须在继续进行之前使两个密钥发生器重新同步。他们必须这样做以保证密钥流的任意局部不会重复，重新设置发生器回到前一个状态，然而这个简单的法子是不行的。这也有好的一面，同步密码并不扩散传输错误。如果有一位在传输中改变了，比丧失一位可能性大的多，那么只有该位不能正确解密。所有进程和结果都不会受影响。

由于在加解密两端密钥流发生器必须产生同样的输出，所以它必须是确定的。因为它是用有限状态机器实现的〔如计算机〕，密钥序列终会重复。这些密钥流发生器被称为是周期性的。除一次一密乱码本外，所有密钥流发生器都是周期性的。发生器的周期必须非常长，要比密钥更换之前发生器所能输出的位的长度还要长得多。如果其周期比明文还要短，那么明文的不同局部将用同样的加密——这是一个严重的弱点。如果密码分析者熟悉这样的一批明文，他就可以恢复出密钥流，然后恢复出更多的明文。即使分析者仅有密文，他也可以用同一密钥流加密的不同局部密文相异或得到明文跟明文的异或。这只是一个有非常长密钥的单一异或运算罢了。

周期需要多长取决于应用。用于加密连续T1连接通信的密钥发生器每天加密237比特。那么它的周期应该比这个数大几个数量级，尽管密钥每天都要更换。如果周期足够长，你仅仅需要每周甚至每月才更换密钥一次。同步序列密码同样可防止密文中的插入和删除，因为它们会使系统失去同步而立即被发现。然而，却不能防止单个位被窜改。就像CFB模式下的分组密码算法，Mallory更换数据流中的某个比特，如果他熟悉明文，他就可以使那些比特被解密成他想要的。后面的比特仍被正确地解密，所以在很多应用中Mallory仍可进行某些毁坏。 4.3线性反响移位存放器

移位存放器是流密码产生密钥流的一个主要组成局部。GF(2)上一个n级反响移位存放器由n个二元存储器与一个反响函数f(a1，a2，…，an)组成，如图4－3所示。图4－3GF(2)上的n级反响移位存放器每一存储器称为移位存放器的一级，在任一时刻，这些级的内容构成该反响移位存放器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。

每一时刻的状态可用n长序列“a1，a2，…，an〞的n维向量“(a1，a2，…，an)〞来表示，其中ai是第i级存储器的内容。

初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并计算f(a1，a2，…，an)作为下一时刻的an。

反响函数f(a1，a2，…，an)是n元布尔函数，即n个变元a1，a2，…，an可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。例4-1：图4-4是一个3级反响移位存放器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表4-1求出。

即输出序列为，周期为4。

如果f(a1,a2,…,an)是(a1,a2,…,an)的线性函数，那么称之为线性反响移位存放器LFSR〔linearfeedbackshiftregister〕，否那么称为非线性移位存放器。此时f可写为：f(a1,a2,…,an)=cna1

cn-1a2

…

c1an图4-4是一个3级反响移位存放器图4－5GF(2)上的n级线性反响移位存放器输出序列{at}满足an+k=cnat

cn-1at+1

…

c1an+t-1其中t为非负整数。线性反响移位存放器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。例4－2图4－6是一个5级线性反响移位存放器，其初始状态为〔a1，a2，a3，a4，a5〕=(1，0，0，1，1)，可求出输出序列为，周期为31。图4－6一个5级线性反响移位存放器在线性反响移位存放器中，总是假定c1，c2，…，cn中至少有一个不为0，否那么f(a1，a2，…，an)≡0，这样的话，在n个脉冲后状态必然是00…0，且这个状态必将一直持续下去。假设只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。一般对于n级线性反响移位存放器，总是假定cn=1。

n级线性反响移位存放器的状态周期小于等于2n-1。输出序列的周期与状态周期相等，也小于等于2n-1。只要选择适宜的反响函数便可使序列的周期到达最大值2n-1。定义4－1n级线性反响移位存放器产生的序列{ai}的周期到达最大值2n-1时，称{ai}为n级m序列。

根据密码学的需要，对于线性移位存放器，主要考虑下面两个问题：

〔1〕如何利用级数尽可能小的线性移位存放器产生周期长、统计性能好的序列；

〔2〕一个序列{ai}，如何构造一个尽可能短的线性移位存放器来产生它。我们首先需要介绍一些相关的代数学知识，因篇幅有限，局部定理不做证明。因为n级线性移位存放器的输出序列{ai}满足递推关系：an+k=c1an+k-1

c2a

n+k-2

…

cnak对任何k≥1均成立。这种递推关系可用一个一元高次多项式p(x)=1+c1x+…＋cn-1xn-1＋cnxn

表示，称这个多项式为LFSR的特征多项式。由于ai∈GF(2)(i=1,2,…,n)，所以共有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个，记2n-1个非零序列的全体为G(p(x))。

定义4－4仅能被非零常数或者本身的常数倍除尽，不能被其他多项式整除的多项式称为不可约多项式。

定理4－3n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约多项式。

该定理的逆不成立，即LFSR产生的特征多项式为不可约多项式，但其输出序列不一定是m序列。例如下面的例4－3证明存在特征多项式为不可约多项式，但其输出序列不一定是m序列。解得c3＝1，c2＝0，c1＝1从而得到特征多项式p(x)=x3+x+1 4.4非线性序列简介

1．Geffe序列生成器Geffe序列生成器由3个LFSR组成〔如图4－7〕，其中LFSR2作为控制生成器使用。当LFSR2输出1时，LFSR2与LFSR1相连接；当LFSR2输出0时，LFSR2与LFSR3相连接。假设设LFSRi的输出序列为{a(i)k}(i=1，2，3)，那么输出序列{bk}可以表示为：图4－7Geffe序列生成器图2．J－K触发器

J－K触发器如图4－8所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即其中x1和x2分别是J和K端的输入。图4－8J－K触发器在图4－9中，令驱动序列{ak}和{bk}分别为m级和n级m序列，那么有图4－9利用J－K触发器的非线性序列生成器如果令c-1=0，那么输出序列的最初3项为当m与n互素且a0+b0=1时，序列{ck}的周期为(2m-1)(2n-1)。3．Pless生成器

Pless生成器由8个LFSR、4个J－K触发器和1个循环计数器构成，由循环计数器进行选通控制，如图4－10所示。假定在时刻t输出第t(mod4)个单元，那么输出序列为：a0b1c2d3a4b5d6图4－10Pless生成器4．钟控发生器

钟控发生器是由控制序列〔由一个或多个移位存放器来控制生成〕的当前值决定被采样的序列存放器的移动次数〔即由控制序列的当前值确定采样序列存放器的时钟脉冲数目〕。控制序列和被采样序列可以是源于同一个LFSR〔称为自控〕，也可以源于不同的LFSR〔称为他控〕，还可以相互控制〔称为互控〕。钟控发生器示意图如图4－11所示。图4－11钟控发生器模型钟控发生器模型中典型的是(k，d)－钟控发生器。设控制序列为x，被采样的序列为y，那么输出序列z表示为：当控制序列当前值为1时，被采样序列生成器被时钟驱动k次后输出；当控制序列当前值为0时，被采样序列生成器被时钟驱动d次后输出。另外，停走式发生器也是一种钟控模型，它由两个LFSR组成。其中，LFSR1控制LFSR2的时钟输入。当且仅当LFSR1在时刻t-1的输出为1时，LFSR2在时刻t改变状态〔也即LFSR1输出时钟脉冲，使LFSR2进行输出并反响以改变移位存放器的状态〕。5．收缩和自收缩发生器

收缩发生器是由控制序列的当前值决定被采样序列移位存放器是否输出。该发生器由2个LFSR组成。LFSR1、LFSR2分别按各自的时钟运行，LFSR1在t-1时刻的输出为1时，LFSR2在t时刻输出为密钥流，否那么舍去。

自收缩发生器从一个LFSR中抽出2条序列，其中一条为控制序列，另一条为采样序列。当控制序列输出为1时，采样序列输出为密钥流，否那么舍去。

此外，还有多路复合序列，这类序列也归结为非线性组合序列。 4.5常用的序列密码算法

A5序列密码算法

A5序列密码算法是利用欧洲数字蜂窝移动〔GSM〕加密的序列密码算法，它用于从用户至基站的联接加密，GSM会话的每帧数据包含228比特，A5算法每次会话将产生228比特的密钥，算法的密钥长度为64比特，还包含有一个22比特的帧数。A5算法有两个版本：强A5/1和弱A5/2。

A5算法是一种典型的基于LFSR的序列密码算法，它由三个LFSR组成，是一种集控制与停走于一体的钟控模型，但是A5算法没有完全公开，因而各种资料的描述也不尽相同，重要的是第二个和第三个LFSR的联接多项式以及钟控的位置。A5算法的3个LFSR中LFSR1、LFSR2、LFSR3的级数分别为19、22和23。LFSR1的反响抽头是18、17、16、13，LFSR2的反响抽头是21、20、16、12，LFSR3的反响抽头是22、21、18、17〔如图4－12中的数字表示抽头的位置〕。因此，LFSR1、LFSR2、LFSR3的生成多项式分别为：三个线性反响移位存放器的生成多项式均为本原多项式。图4－12A5算法A5算法的密钥产生过程如下：

〔1〕先将64比特密钥注入LFSR；

〔2〕再将22比特的帧数与LFSR的反响值模2加注入LFSR〔以上LFSR正常驱动〕；

〔3〕LFSR开始停走钟控；

〔4〕舍去产生的100比特输出；

〔5〕产生114比特作为密钥输出；

〔6〕舍去产生的100比特输出；

〔7〕产生114比特作为密钥输出。SEAL序列密码算法

SEAL〔Software－OptimizedEncryptionAlgorithm〕序列密码算法是IBM公司的P.Rogaway和D.Coppersmith设计的易于软件实现的序列密码算法，它是面向32位处理器的，需要8个32位的存放器和约8MB的内存，它不是传统意义上基于LFSR的序列密码算法，而是一个伪随机函数簇〔PRF〕，它将明文的位置变成一个随机串。给定160比特长的密钥a和32比特的n，SEAL将扩展成L比特的函数与a(n)。设计第n个明文为xn，xn的长度为L比特，SEAL用密钥a将n加密成长度为L比特的SEAL(a,n,L)，那么位置n的明文xn的密文为〈n,xnSEAL(a,n,L)〉。下面描述SEAL算法的第3版〔SEAL3.0〕。运用SHA-1对整数进行杂凑就得到160比特的散列值：图4－13SEAL算法的内循环初始化局部是基于n、l的使用表T、R对A、B、C、D和n