密钥流产生技术课件

第4章

密钥流产生技术1本章内容概要概述密钥流产生原理、技术和实例。2本章目录4.1流密码体制概述4.2流密码设计方法4.3线性反馈移位寄存器4.4流密码安全性分析4.5密钥流产生器的构造34.1.1一次一密密带体制的原理一次一密密带体制也称为Vernam密码。它是在1917年由MajorJosephMauborgne和AT&T的GilberVernam发明的。在这种密码体制中，密文是由明文消息与相同长度的非重复随机序列按比特异或生成的。因为在GF(2)中，加法和减法是相同的，所以第二次施行异或，就能完成解密。图4-1给出一次一密密带体制的原理图。

5一次一密密带体制的原理一次一密密带体制的基本原理是通过使用真随机的密钥序列,使密文和明文在统计上无关.产生这种随机序列(即序列中的每一比特都独立于其前面的各比特,并且其等概率地取0或1的序列)的设备叫作二进制对称源(BSS).简而言之,BSS输出一种相当好的硬币抛掷序列.6一次一密密带体制的原始形式

一次一密密带体制的原始形式是用于电传打字机。发送者使用密带上每一个密钥字母严密地加密一个明文字母。加密是明文字母和一次一密密带上的密钥字母的mod26加法，解密是密文字母和一次一密密带上的密钥字母的mod26减法。对于一次消息，每一个密钥字母严格地使用一次。发送者加密消息，然后毁坏使用过的密带上的记录或者使用过的磁带介质。接收者具有和发送者相同的密带，并且依次使用密带上的每一个密钥字母解密密文中的每一个字母。在解密消息后，接收者毁坏使用过的密带上的记录或者磁带介质。为了能够再次进行安全通信，接收端保存的密带上记录或者磁带介质应与发送端完全相同。7电传打字机的加密与解密例4-1如果消息是：ONETIMEPAD；密钥字母序列是：TBFRGFARFM，完成电传打字机的加密。解：假定我们按正常序列中字母的位置数给每一个字母标一个数来表示它则可以得到下面的对应关系：ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567891011121314151617181920212223242526因为电传打字机的加密是明文字母和密钥字母的mod26加法所以有(O＋T)mod26＝(15＋20)mod26＝9mod26＝I；同理(N＋B)mod26＝P；…；(D＋M)mod26＝Q，得到密文为IPKLPSFHGQ。例4-2如果密文消息是：IPKLPSFHGQ；密钥字母序列是:TBFRGFARFM,完成电传打字机的解密。因为电传打字机的解密是密文字母和密钥字母的mod26减法所以有(I－T)mod26＝(9－20)mod26＝(－11＋26)mod26＝15mod26＝O；(P－B)mod26＝(16－2)mod26＝14mod26＝N；…；(Q－M)mod26＝(17－13)mod26＝4mod26＝D，得到明文为ONETIMEPAD。从例4-1和例4-2可知，mod26运算有一个重要性质，如果密文和使用相同的密钥字母流进行减法，则恢复成明文。8伪随机序列存在局部的非随机特征1．使用一个伪随机序列代替真随机序列是有漏洞的告诫：这是一个重要的告诫，密钥序列必须随机产生。如果密钥序列具有局部的非随机特征，那么容易遭到攻击。使用一个伪随机序列代替真随机序列在安全上是有漏洞的，因为伪随机序列存在局部的非随机特征。如果使用一个真随机源，那么攻击是困难的。2．相同的密钥序列不能重复使用如果一个密码分析者已经掌握有密钥交叠的多重密文，则他能够重构明文。因为异或操作有一个特性：如果密文和使用相同的密钥流进行异或，则恢复成明文(模运算也有类似特性，如例4-1和例4-2所示)。因此，从不使用相同的密钥序列。104.1.3同步序列密码原理图中的密钥流产生器，它在真正密钥（K）的控制下，产生一随机序列，其被用来对明文加密。这样的同步序列密码体制的安全性取决于密钥序列的“随机性”。假定采用已知明文攻击，密码分析者完全可以获得部分密钥流。关键在于密码设计者如何设计，使得即使密码分析者获得部分密钥流（ki），也不能预测后继的密钥流或通过反演绎工作获得产生密钥流（ki）的真正密钥（K）。

一次一密密带体制的基本原理是通过使用真随机的密钥序列,使密文和明文在统计上无关.产生这种随机序列(即序列中的每一比特都独立于其前面的各比特,并且其等概率地取0或1的序列)的设备叫作二进制对称源(BSS).简而言之,BSS输出一种相当好的硬币抛掷序列12⑵流密码的安全性①密钥流产生器输出愈接近随机,安全性能愈好如果密钥流产生器输出无穷个零，那么密文将等于明文，并且整个工作变得毫无价值。如果密钥流产生器的输出比特流周期太小，如周期为16比特，那么算法将是一个简单的异或电路组成的，可以忽略其安全性。如果密钥流产生器输出无穷个随机比特流(不是伪随机，而是真随机)，那么密钥流产生器的安全性能达到一次一密密带的效果，并具有完美的保密性。实际的流密码的安全性位于简单的异或电路与一次一密密带之间。密钥流产生器产生的比特流看上去是随机的，但是实际上是确定性的比特流，而且在解密时能够无错误地重复产生。密钥流产生器的输出愈接近随机，密码分析者破译它就愈困难。②密钥流产生器起始状态不变带来的弊端如果每次打开密钥流产生器都产生相同的比特流，那么密钥流很容易被破译。窃听者可以采取以下办法破译密钥流，如表10-2所示。③密钥流产生器必须由密钥来驱动如果密钥流产生器由密钥来驱动，那么其输出是密钥的函数，只要密钥改变就不会产生相同的比特流。这就是为什么密钥流产生器必须由密钥来驱动的原因。现在，如果窃听者得到一个明文/密文对，那么他只能读懂由相同密钥加密的消息；只要密钥改变，窃听者就不能读懂其他密文。14密钥流产生器起始状态不变带来的弊端

154.1.4真随机序列的三大特征1．统计的随机性如果一个序列具备统计的随机性，则把它称为伪随机序列，这意味着它能够通过所有的统计试验。例如，它们之中1和0数目应该是相等的，大约各占长度的一半，0和1游程长度的分布也应该是一样的。在实际使用中，要求伪随机序列的周期比实际使用的长度(不是周期)足够长。因此要求伪随机序列的局部随机性也要与随机序列的整体随机性难以区分。2．不可预测性尽管给出产生序列的算法或者硬件完整的知识及前面产生的比特流，也不可能通过计算机预测出下一个随机比特是什么。3．不可再生性不可再生性是指，即使使用精确的相同输入，随机序列产生器两次分别产生的随机序列也是不相同的。16不可预测性：要求下一个比特值与前面无关⑵充分条件硬币抛掷序列呈现出的线性复杂性,典型地随着所考察的序列的数目n增大而增长,如图所示。于是,当密钥流具有这种线性复杂性曲线时,就好像它也呈现出均匀的统计特性。相反.在一个周期序列中的均匀分布的统计特性,并非意味着大的线性复杂性。例如,有着良好分布特性的最大长度序列相对于周期长度而言,其线性复杂性最小。周期为的二元最长序列仅仅需要知道2n位的值就能完全确定⑴必要条件①密钥流必须具有长的周期：因为如果知道周期的值和第一周期的密钥流,就能完全确定密钥流的其他部分。②大的线性复杂性：线性复杂性指能够产生该密钥流的最短的线性反馈移位寄存器的级数.如果线性复杂性愈大,那么密钥流的周期愈长。174.3线性反馈移位寄存器4.3.1反馈移位寄存器4.3.2线性反馈移位寄存器4.3.3线性反馈移位寄存器的特点184.3.2(4比特)线性反馈移位寄存器204.3.3线性反馈移位寄存器的特点线性反馈移位寄存器有以下特点。(1)如果LFSR的初始值全为0，则会导致输出一直为0，这在实际中是不能使用的，所以全0初始值(有时称为零态)不允许存在。(2)n比特的LFSR可能(2n-1)有个状态。这就意味着在重复前能产生长度为(2n-1)比特的伪随机序列。仅仅使用某些抽头序列的LFSR才能循环通过个内部状态，这是LFSR的最长周期。具有最长周期的线性反馈移位寄存器序列称为m序列。产生m序列的条件是抽头序列（或称抽头接法）要满足本原多项式。21(6)一般来说，在给定阶次(也就是说给定移位寄存器的长度)的情况下，没有一种容易的方法产生mod2本原多项式。最容易的方法是选择一个随机多项式，试验它是否是本原的。(7)表4-2列出一些不同阶次的本原多项式。例如，表中列出(32，7，5，3，2，1，0)，这意味着它是一个32级线性反馈移位寄存器，其mod2本原多项式为：

x32+x7+x5+x3+x2+x+123线性反馈移位寄存器表示本原多项式对于(32，7，5，3，2，1，0)，它意味着当采用一个长度为32比特的移位寄存器时，产生的新比特由第32、第7、第5、第3和第2比特一起异或24本原多项式的获得过程

已知m序列的周期为15，接收到信号为10011010，求该m序列的特征多项式(亦称连接多项式).联立方程的获得过程如下：⑴把接收到的前n比特作为初态(目前n=4),第n+1比特作为线性移位寄存器输出(一般输出位靠近连接系数的低次项),所以得到式(4-8).⑵把接收到的前n+1位～2位作为第二状态,第n+2比特作为线性移位寄存器输出,所以得式(4-9).以此类推,可得式(4-10)和(4-11)264.4.2相关免疫(1)为了获得高强度的密码序列，最常用的办法之一是从一组较简单的原始序列出发，经过某种非线性方法组合，得到一个新的序列。这里存在的危险是，一个或更多内部原始序列经常由线性移位寄存器产生，它们可能分别与输出的组合密钥流相关。相关攻击的基本思想是，检验输出的组合密钥流与它的一个内部原始序列之间的相关性，然后，借助于观测组合密钥流的输出序列，获得一个内部原始序列的信息。再通过使用这些信息和其他信息的相关性，收集关于其他内部原始序列的信息，直到破译整个产生器。

274.4.2相关免疫(2)可以把上述相关分析或称为相关攻击的思想用数学形式来表示，即在由多个子序列

可以把上述相关分析或称为相关攻击的思想用数学形式来表示，即在由多个子序列驱动的密钥流k中,对k与子序列的符合率进行分析,如果与中0比特的符合率为，且，则与k之间存在相关性，当值愈大，k与之间的互信息就愈大。相关免疫(correlationimmunity)是指，n个随机变量统计独立或互信息为=0。

28相关法破译

30相关法破译实例例已知Geffe产生器输出序列B为101001011100100011011001001010100101011011100011101101001000111101001011100111011011001000111100111011011111001011101000011101连接多项式分别是试破译各原始序列的初始态,也就是破译序列产生器的密钥3132破译步骤1第1步，寻找序列A2的初始态。使用序列A2的连接多项式校验序列B的工作状态，结果如下表所示。由表可知，由状态值“101”产生的校验值“001”与输出序列B的“001”完全一致，所以“101”是序列A2的正确的工作状态。由于“101”是第一个工作状态，所以它是初始态。

使用序列A2连接多项式校验序列B的工作状态

状态序号

B输出101001011100100011011001001010100101011011100A2校验位0011

用初始态“101”重构序列A2B输出101001011100100011011001001010100101011011100011101101001000111A2输出101001110100111010011101001110100111010011101001110100111010011A2与B的符合率为(63－18)/63＝1－0.286＝0.714，符合理论分析，说明初始态的选择是正确的。

33破译步骤2(a)第2步，寻找序列A3的初始态。一开始可以认为，既然“101”是序列的初始态，那么“1010”会不会是序列A3的初始态，所以把“1010”设置到A3连接多项式中，重构序列A3。用初始态“1010”重构序列A3B输出101001011100100011011001001010100101011011100011101101001000111A3输出101011001000111101011001000111101011001000111101011001000111101A3与B的符合率为(63－28)/63＝1－0.45＝0.55，不符合理论分析，说明初始态的选择是不正确的。34破译步骤2(b)状态序号01234567890123456789012345678901234567890123456789012B输出10100101110010001101100100101010010101101110001110110100A3校验位1000101110001010000100000111100011100001111111100101状态序号3456789012345B输出

1000111101001A3校验位0000111101010使用序列A3连接多项式校验序列B的工作状态。由状态序号0～55，没有一个状态值与其校验值一致，只有状态序号56表示的状态值“0001”产生的校验值“1111”与输出序列B的“1111”完全一致，所以“0001”是序列A3正确的工作状态。由“0001”的状态序号(56 号)可以推算出序列B的初始态为“1111”。使用初始态“1111”重构序列A3B输出101001011100100011011001001010100101011011100011101101001000111A3输出111101011001000111101011001000111101011001000111101011001000111A3与B的符合率为(63－17)/63＝1－0.27＝0.73，符合理论分析，说明初始态选择是正确的。35破译步骤3第3步,寻找控制序列A1的初始态.把输出序列B分别与序列A2和A3比较,如果与A2符合,则A1记为“1”;如果与A3符合,则记A1为“0”;如果A2与A3和都符合记为“X”.这样可以得到部分比特,如果其长度超过寄存器的长度,那么就找到的一个正确的态,然后推算出初始态.这里介绍一种取巧的捷径:在A2和A3都符合记的情况下,如果在“1”上符合,记A1为“1”;如果在“0”上符合,则记A1为“0”,或者按照相反条件假设,主要看能否通过输出校验.从下表发现,经过这种处理,A1校验位与其输出的一致性迅速提高,并发现状态值“111111”产生的校验值“010101”与A1输出一致,所以““111111”是序列正确的工作状态。由于“111111”是第1个工作状态，所以它是初始态。36寻找A1初态A2输出1010011101001110100111010011101001A3输出1111010110010001111010110010001111B输出1010010111001000110110010010101001A1输出X1X11X0X01X110011011X01XXXX01XX11XA1输出1111110101011001101110110010101111A1校验位01010110011011101101111001010A2输出1101001110100111010A3输出0101100100011110101B输出0101101110001110110A1输出0XXX0X1X1X010XX0011A1输出0101001110010110011A1校验位0001100100001010110137由重构序列控制和产生的B序列A2输出1010011101001110100111010011101001A3输出1111010110010001111010110010001111A1输出1111110101011001101110110100100111重构B输出

1010010111001000110110010010101001B输出1010010111001000110110010010101001A2输出1101001110100111010A3输出0101100100011110101A1输出000101111001010001重构B输出0101101110001110110B输出010110111000111011038一般的Geffe产生器

一般的Geffe产生器是选择n个线性移位寄存器代替两个线性移位寄存器，这里n等于2的幂。共有n+1个线性移位寄存器，其中第一个线性移位寄存器的时钟速度比其他n个线性移位寄存器快倍尽管这个线路比Geffe产生器更加复杂，但是同样会遭受同类的相关攻击，所以不推荐采用这种产生器。394.5密钥流产生器的构造本节主要讲述三种安全可靠的密钥流产生器。4.5.1基于线性移位寄存器设计密钥流产生器

1.设计方法概述

2.多路选择密钥流产生器

3.钟控密钥流产生器

4.5.2基于置换盒设计密钥流产生器

404.5.1基于线性移位寄存器设计密钥流产生器

1.设计方法概述

⑴首先要获得一个或多个线性反馈移位寄存器(LFSR)，使用不同的反馈多项式产生不同的长度。密钥是各个线性移位寄存器的初态。输出比特是各个线性移位寄存器一些比特的函数，更适宜的是非线性函数，这个函数称为组合函数，整个产生器称作组合产生器。⑵为了增加