密钥流产生技术

1,第4章,密钥流产生技术,2,本章内容概要,概述密钥流产生原理、技术和实例。,3,本章目录,4.1 流密码体制概述4.2 流密码设计方法4.3线性反馈移位寄存器4.4 流密码安全性分析4.5密钥流产生器的构造,4,4.1 流密码体制概述,4.1.1 一次一密密带体制的工作原理4.1.2 一次一密密带体制的安全性4.1.3 同步序列密码原理4.1.4 真随机序列的三大特征,5,4.1.1 一次一密密带体制的原理,一次一密密带体制也称为Vernam密码。它是在1917年由Major Joseph Mauborgne和AT&T的Gilber Vernam发明的。在这种密码体制中，密文是由明文消息与相同长度的非重复随机序列按比特异或生成的。因为在GF(2)中，加法和减法是相同的，所以第二次施行异或，就能完成解密。图4-1给出一次一密密带体制的原理图。,6,一次一密密带体制的原理,一次一密密带体制的基本原理是通过使用真随机的密钥序列,使密文和明文在统计上无关.产生这种随机序列(即序列中的每一比特都独立于其前面的各比特,并且其等概率地取0或1的序列)的设备叫作二进制对称源(BSS).简而言之,BSS输出一种相当好的硬币抛掷序列.,7,一次一密密带体制的原始形式,一次一密密带体制的原始形式是用于电传打字机。发送者使用密带上每一个密钥字母严密地加密一个明文字母。加密是明文字母和一次一密密带上的密钥字母的mod26加法，解密是密文字母和一次一密密带上的密钥字母的mod26减法。对于一次消息，每一个密钥字母严格地使用一次。发送者加密消息，然后毁坏使用过的密带上的记录或者使用过的磁带介质。接收者具有和发送者相同的密带，并且依次使用密带上的每一个密钥字母解密密文中的每一个字母。在解密消息后，接收者毁坏使用过的密带上的记录或者磁带介质。为了能够再次进行安全通信，接收端保存的密带上记录或者磁带介质应与发送端完全相同。,8,电传打字机的加密与解密,例4-1 如果消息是：ONETIMEPAD； 密钥字母序列是：TBFRGFARFM，完成电传打字机的加密。解：假定我们按正常序列中字母的位置数给每一个字母标一个数来表示它则可以得到下面的对应关系：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26因为电传打字机的加密是明文字母和密钥字母的mod26加法所以有 (OT)mod 26(1520)mod 269mod 26I；同理(NB)mod 26P；(DM)mod 26Q，得到密文为IPKLPSFHGQ。例4-2 如果密文消息是：IPKLPSFHGQ； 密钥字母序列是: TBFRGFARFM,完成电传打字机的解密。因为电传打字机的解密是密文字母和密钥字母的mod26减法所以有(IT)mod26(920)mod 26(1126)mod 2615mod 26O；(PB)mod 26(162) mod 2614 mod26N；(QM)mod26(1713)mod 264mod26D，得到明文为ONETIMEPAD。从例4-1和例4-2可知，mod26运算有一个重要性质，如果密文和使用相同的密钥字母流进行减法，则恢复成明文。,9,4.1.2 一次一密密带体制的安全性,1一次一密密带体制的安全性来自于真随机密钥序列 关于一次一密密带体制，值得注意是：如果一个窃听者不能得到加密消息的一次一密密带，那么这个密码体制是完全安全的。因为一次一密密带体制使用的密钥序列是真随机产生的；一个真随机密钥序列加到一个非随机的明文消息上，会产生一个完全随机的密文消息，并且没有一种计算方法能改变这种情况，所以从一次一密密带体制得到的密文消息具有下列特点：密文和明文在统计上是无关的； 每一个密文消息都是完全随机的，与等长的任意可能的明文消息之间不存在某种关系；在进行密码分析时，任意一个明文消息都有等概率出现的可能，这样对于密码分析者来说，没有一种方法能够确定哪一个明文消息是正确的。 因为每一个密钥序列公正地相似(记住，密钥序列是真随机产生的)，密码分析者没有可用于分析密文的信息，所以一次一密密带体制是完全安全的。,10,伪随机序列存在局部的非随机特征,1使用一个伪随机序列代替真随机序列是有漏洞的告诫：这是一个重要的告诫，密钥序列必须随机产生。如果密钥序列具有局部的非随机特征，那么容易遭到攻击。使用一个伪随机序列代替真随机序列在安全上是有漏洞的，因为伪随机序列存在局部的非随机特征。如果使用一个真随机源，那么攻击是困难的。2相同的密钥序列不能重复使用如果一个密码分析者已经掌握有密钥交叠的多重密文，则他能够重构明文。因为异或操作有一个特性：如果密文和使用相同的密钥流进行异或，则恢复成明文(模运算也有类似特性，如例4-1和例4-2所示)。因此，从不使用相同的密钥序列。,11,4一次一密密带体制的实现问题,1）密钥的分配和存储问题因为在一次一密密带体制中，密钥比特必须是随机的，并且从不再次使用，密钥的长度要等于消息的长度，所以在这3个约束条件下，要求密钥产生速度快、密钥分配及时，因而一次一密密带体制不适合长消息加密，只适合一些短的消息加密。当然能够把650兆字节的随机比特存储在一个CD-ROM上，但是也存在一些问题。首先，需要两个精确的随机比特复制品，但是，CD-ROM仅仅在大量使用时才是经济的。其次，必须毁坏已经使用过的比特。除非在物理层面破坏整个CD-ROM，它是不容易被局部毁坏的设备。在这些存储介质的挑选中，数字磁带是更好的介质。2）密钥的同步问题即使解决了密钥的分配和存储问题，也必须确信发送者和接收者使用的密钥是完全同步的。如果接收者使用的密钥相对于发送者偏移1比特(或者如果在传输期间停止传输一些比特)，则会引起收发双方密钥失步，导致无法解密。另一方面，如果在传输期间一些比特发生改变(比如由于随机噪声影响而发生)，那么仅仅这些比特解密不正确。3）目前主要用于超安全低带宽信道一次一密密带体制已经得到实用，主要用于超安全低带宽信道。在那种场合下，完全保密是头等重要的。但是因为对密钥产生的时间和密钥分配要求过高，目前还只能在低速情况下应用。,12,4.1.3 同步序列密码原理,图中的密钥流产生器，它在真正密钥（K）的控制下，产生一随机序列，其被用来对明文加密。这样的同步序列密码体制的安全性取决于密钥序列的“随机性”。假定采用已知明文攻击，密码分析者完全可以获得部分密钥流。关键在于密码设计者如何设计，使得即使密码分析者获得部分密钥流（ ki ），也不能预测后继的密钥流或通过反演绎工作获得产生密钥流（ki）的真正密钥（K）。,一次一密密带体制的基本原理是通过使用真随机的密钥序列,使密文和明文在统计上无关.产生这种随机序列(即序列中的每一比特都独立于其前面的各比特,并且其等概率地取0或1的序列)的设备叫作二进制对称源(BSS).简而言之,BSS输出一种相当好的硬币抛掷序列,13,流密码工作模型,14, 流密码的安全性,密钥流产生器输出愈接近随机,安全性能愈好如果密钥流产生器输出无穷个零，那么密文将等于明文，并且整个工作变得毫无价值。如果密钥流产生器的输出比特流周期太小，如周期为16比特，那么算法将是一个简单的异或电路组成的，可以忽略其安全性。如果密钥流产生器输出无穷个随机比特流(不是伪随机，而是真随机)，那么密钥流产生器的安全性能达到一次一密密带的效果，并具有完美的保密性。实际的流密码的安全性位于简单的异或电路与一次一密密带之间。密钥流产生器产生的比特流看上去是随机的，但是实际上是确定性的比特流，而且在解密时能够无错误地重复产生。密钥流产生器的输出愈接近随机，密码分析者破译它就愈困难。密钥流产生器起始状态不变带来的弊端如果每次打开密钥流产生器都产生相同的比特流，那么密钥流很容易被破译。窃听者可以采取以下办法破译密钥流，如表10-2所示。密钥流产生器必须由密钥来驱动如果密钥流产生器由密钥来驱动，那么其输出是密钥的函数，只要密钥改变就不会产生相同的比特流。这就是为什么密钥流产生器必须由密钥来驱动的原因。现在，如果窃听者得到一个明文/密文对，那么他只能读懂由相同密钥加密的消息；只要密钥改变，窃听者就不能读懂其他密文。,15,密钥流产生器起始状态不变带来的弊端,16,4.1.4 真随机序列的三大特征,1统计的随机性如果一个序列具备统计的随机性，则把它称为伪随机序列，这意味着它能够通过所有的统计试验。例如，它们之中1和0数目应该是相等的，大约各占长度的一半，0和1游程长度的分布也应该是一样的。在实际使用中，要求伪随机序列的周期比实际使用的长度(不是周期)足够长。因此要求伪随机序列的局部随机性也要与随机序列的整体随机性难以区分。2不可预测性尽管给出产生序列的算法或者硬件完整的知识及前面产生的比特流，也不可能通过计算机预测出下一个随机比特是什么。3不可再生性不可再生性是指，即使使用精确的相同输入，随机序列产生器两次分别产生的随机序列也是不相同的。,17,不可预测性：要求下一个比特值与前面无关,充分条件硬币抛掷序列呈现出的线性复杂性,典型地随着所考察的序列的数目n增大而增长,如图所示。于是,当密钥流具有这种线性复杂性曲线时,就好像它也呈现出均匀的统计特性。相反.在一个周期序列中的均匀分布的统计特性,并非意味着大的线性复杂性。例如,有着良好分布特性的最大长度序列相对于周期长度而言,其线性复杂性最小。周期为 的二元最长序列仅仅需要知道2n位的值就能完全确定,必要条件 密钥流必须具有长的周期：因为如果知道周期的值和第一周期的密钥流,就能完全确定密钥流的其他部分。 大的线性复杂性：线性复杂性指能够产生该密钥流的最短的线性反馈移位寄存器的级数.如果线性复杂性愈大,那么密钥流的周期愈长。,18,4.3线性反馈移位寄存器,4.3.1 反馈移位寄存器4.3.2 线性反馈移位寄存器4.3.3 线性反馈移位寄存器的特点,19,4.3.1反馈移位寄存器,20,4.3.2 (4比特)线性反馈移位寄存器,21,4.3.3 线性反馈移位寄存器的特点,线性反馈移位寄存器有以下特点。(1)如果LFSR的初始值全为0，则会导致输出一直为0，这在实际中是不能使用的，所以全0初始值(有时称为零态)不允许存在。(2)n比特的LFSR可能(2n-1)有个状态。这就意味着在重复前能产生长度为(2n-1)比特的伪随机序列。仅仅使用某些抽头序列的LFSR才能循环通过个内部状态，这是LFSR的最长周期。具有最长周期的线性反馈移位寄存器序列称为m序列。产生m序列的条件是抽头序列（或称抽头接法）要满足本原多项式。,22,(3)当谈论多项式时，术语“素数”由“不可约的”取代。如果一个多项式不能表示为两个其他多项式的乘积(除了1和自身外)，那么它是不可约的多项式。多项式x2+1在整数域是不可约的而多项式x3+2x2+x是可约的，因为它能够表示为x(x+1)(x+1)。 (4)当一个多项式在给定的域中能成为一个最长周期的产生器时，这个多项式称为原始的多项式或本原多项式，且它们的所有系数互为素数。(5)为了使一个特殊的LFSR成为具有最大周期的LFSR，抽头序列必须加一个常数项1(即加x0=1)，以便构成本原多项式。多项式阶次等于移位寄存器的长度。,23,(6)一般来说，在给定阶次(也就是说给定移位寄存器的长度)的情况下，没有一种容易的方法产生mod2 本原多项式。最容易的方法是选择一个随机多项式，试验它是否是本原的。(7)表4-2列出一些不同阶次的本原多项式。例如，表中列出(32，7，5，3，2，1，0)，这意味着它是一个32级线性反馈移位寄存器，其mod2本原多项式为： x32+x7+x5+x3+x2+x+1,24,线性反馈移位寄存器表示,本原多项式对于(32，7，5，3，2，1，0)，它意味着当采用一个长度为32比特的移位寄存器时，产生的新比特由第32、第7、第5、第3和第2比特一起异或,25,4.4 流密码安全性分析,线性复杂性和相关免疫是衡量基于LFSR流密码安全强度的一种主要标志。4.4.1 线性复杂性 通常，分析流密码比分析分组密码更容易。例如，基于线性移位寄存器的产生器，其重要特性之一是线性复杂性(linear complexity)或线性跨度(linear span)，其定义为，模拟产生器输出的最短线性移位寄存器的长度n。有限状态机产生的任何序列具有有限的线性复杂性。线性复杂度的概念是重要的，因为一个简单的算法，如Berlekamp-Massey算法,在仅仅经过2n比特位检验后，就能掌握相关线性移位寄存器的结构。也就是说已经破译了流密码。为了理解Berlekamp-Massey算法的原理，下面举例说明。,26,本原多项式的获得过程,已知m序列的周期为15，接收到信号为10011010，求该m序列的特征多项式(亦称连接多项式). 联立方程的获得过程如下：把接收到的前n比特作为初态(目前n=4),第n+1比特作为线性移位寄存器输出(一般输出位靠近连接系数的低次项),所以得到式(4-8).把接收到的前n+1位2位作为第二状态,第n+2比特作为线性移位寄存器输出,所以得式(4-9).以此类推,可得式(4-10)和(4-11),27,4.4.2 相关免疫 (1),为了获得高强度的密码序列，最常用的办法之一是从一组较简单的原始序列出发，经过某种非线性方法组合，得到一个新的序列。这里存在的危险是，一个或更多内部原始序列经常由线性移位寄存器产生，它们可能分别与输出的组合密钥流相关。 相关攻击的基本思想是，检验输出的组合密钥流与它的一个内部原始序列之间的相关性，然后，借助于观测组合密钥流的输出序列，获得一个内部原始序列的信息。再通过使用这些信息和其他信息的相关性，收集关于其他内部原始序列的信息，直到破译整个产生器。,28,4.4.2 相关免疫 (2),可以把上述相关分析或称为相关攻击的思想用数学形式来表示，即在由多个子序列,可以把上述相关分析或称为相关攻击的思想用数学形式来表示，即在由多个子序列 驱动的密钥流k中,对k与子序列的符合率进行分析,如果 与 中0比特的符合率为 ，且 ，则 与k之间存在相关性，当 值愈大，k与 之间的互信息就愈大。相关免疫(correlation immunity)是指 ，n个随机变量统计独立或互信息为 =0 。,29,相关法破译,Geffe产生器把三个线性移位寄存器用非线性方法组合起来。两个线性移位寄存器输入到一个多路选择器，第3个线性移位寄存器控制多路选择器的输出。,为了获得高强度的密码序列,最常用的办法之一是从一组较简单的原始序列出发,经过某种非线性方法的组合,得到一个新的序列.这里存在的危险是,一个或更多内部原始序列可能分别与输出的组合密钥流相关.相关攻击的基本思想是:检验输出的组合密钥流与它的一个内部原始序列之间的相关性,借助于观测组合密钥流输出序列,来获得一个内部原始序列的信息.通过使用这些信息和其他的相关性,收集关于其他内部原始序列的信息,直到破译整个产生器,30,相关法破译,31,相关法破译实例,例 已知Geffe产生器输出序列B为10100 10111 00100 01101 10010 01010 10010 10110 11100 01110 11010 01000 11110100 10111 00111 01101 10010 00111 10011 10110 11111 00101 11010 00011 101连接多项式分别是,试破译各原始序列 的初始态,也就是破译序列产生器的密钥,32,33,破译步骤1,第1步，寻找序列A2的初始态。使用序列A2的连接多项式校验序列B的工作状态，结果如下表所示。由表可知，由状态值“101”产生的校验值“001”与输出序列B的“001”完全一致，所以“101”是序列A2的正确的工作状态。由于“101”是第一个工作状态，所以它是初始态。 使用序列A2连接多项式校验序列B的工作状态 状态序号 B输出 10100 10111 00100 01101 10010 01010 10010 10110 11100 A2校验位 00 11 用初始态“101”重构序列 A2B输出 10100 10111 00100 01101 10010 01010 10010 10110 11100 01110 11010 01000 111 A2输出10100 11101 00111 01001 11010 01110 10011 10100 11101 00111 01001 11010 011 A2与B的符合率为(6318)/6310.2860.714，符合理论分析，说明初始态的选择是正确的。,34,破译步骤2(a),第2步，寻找序列A3的初始态。一开始可以认为，既然“101”是序列的初始态，那么“1010”会不会是序列A3的初始态，所以把“1010”设置到A3连接多项式中，重构序列A3。 用初始态“1010”重构序列 A3B输出 10100 10111 00100 01101 10010 01010 10010 10110 11100 01110 11010 01000 111 A3输出10101 10010 00111 10101 10010 00111 10101 10010 00111 10101 10010 00111 101 A3与B的符合率为(6328)/6310.450.55，不符合理论分析，说明初始态的选择是不正确的。,35,破译步骤2(b),状态 序号 01234567890123456789012345678901234567890123456789012B输出 10100101110010001101100100101010010101101110001110110100A3校验位 10001011100010100001 00000111100011100001111111100101 状态 序号 3456789012345B输出 1000111101001 A3校验位 0000111101010 使用序列A3连接多项式校验序列B的工作状态。由状态序号055，没有一个状态值与其校验值一致，只有状态序号56表示的状态值“0001”产生的校验值“1111”与输出序列B的“1111”完全一致，所以“0001”是序列A3正确的工作状态。由“0001”的状态序号(56号)可以推算出序列B的初始态为“1111”。使用初始态“1111”重构序列 A3B输出 10100 10111 00100 01101 10010 01010 10010 10110 11100 01110 11010 01000 111 A3输出11110 10110 01000 11110 10110 01000 11110 10110 01000 11110 10110 01000 111A3与B的符合率为(6317)/6310.270.73，符合理论分析，说明初始态选择是正确的。,36,破译步骤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个工作状态，所以它是初始态。,37,寻找A1初态,A2输出10100 11101 00111010011101 001110 1001A3输出11110 10110 01000111101011 001000 1111B输出 10100 10111 00100011011001 001010 1001A1输出X1X11X0X01X110011011X01XXXX01XX11XA1输出 1111110101 01100110111011 00101 0111 1A1校验位 0101 01100110111 011011110 0101 0A2输出 110 1001 1101001 11010A3输出 010 1100 1000111 10101B输出 010 1101 1100011 10110A1输出 0XXX0X1X1X010XX0011A1输出 01 010 011 10010110011A1校验位 000110010 00010101101,38,由重构序列控制和产生的B序列,A2输出 10100 11101 00111 010011101 001110 1001A3输出 11110 10110 01000 111101011 001000 1111A1输出 11111 10101 01100 110111011 010010 0111重构B输出 10100 10111 00100 011011001 001010 1001B输出 10100 10111 00100 011011001 001010 1001A2输出 110 1001 1101001 11010A3输出 010 1100 1000111 10101A1输出 0 0 0101 1110010 10001重构B输出 010 1101 1100011 10110B输出 010 1101 1100011 10110,39,一般的Geffe产生器,一般的Geffe产生器是选择n个线性移位寄存器代替两个线性移位寄存器，这里n等于2的幂。共有n+1个线性移位寄存器，其中第一个线性移位寄存器的时钟速度比其他n个线性移位寄存器快 倍,尽管这个线路比Geffe产生器更加复杂，但是同样会遭受同类的相关攻击，所以不推荐采用这种产生器。,40,4.5密钥流产生器的构造,本节主要讲述三种安全可靠的密钥流产生器。4.5.1 基于线性移位寄存器设计密钥流产生器 1.设计方法概述 2. 多路选择密钥流