序列密码讲解及事例

《序列密码讲解及事例》由会员分享，可在线阅读，更多相关《序列密码讲解及事例（67页珍藏版）》请在金锄头文库上搜索。

1、第五讲：序列密码1人们试图用序列密码方式仿效”一次一密”密码. 从而促成了序列密码的研究和发展. 序列密码是世 界军事, 外交等领域应用的主流密码体制. 在通常 的序列密码中, 加解密用的密钥序列是伪随机序列, 它的产生容易且有较成熟的理论工具, 所以序列密 码是当前通用的密码系统.序列密码的安全性主要依赖于密钥序列, 因而 什么样的伪随机序列是安全可靠的密钥序列, 以及 如何实现这种序列就成了序列密码中研究的一个主 要方面.25.1 5.1 密码学中的随机数密码学中的随机数 在密码学都要涉及到随机数？因为许多密码系统的安全性都依 赖于随机数的生成，例如DES加密算法中的密钥，RSA加密和数字

2、 签名中的素数。 5.1.1 随机数的使用 序列密码的保密性完全取决于密钥的随机性。如果密钥是真正 的随机数，则这种体制在理论上就是不可破译的。但这种方式所需 的密钥量大得惊人，在实际中是不可行的。目前一般采用伪随机序列来代替随机序列作为密钥序列，也就 是序列存在着一定的循环周期。这样序列周期的长短就成为保密性 的关键。如果周期足够长，就会有比较好的保密性。现在周期小于 1010的序列很少被采用，周期长达1050的序列也并不少见。 3何谓伪随机数生成器（PRNG）？假定需要生成介于1和 10 之间的随机数，每一个数出现的几率都是一样的。理想情况下，应生 成0到1之间的一个值，不考虑以前值，这个

3、范围中的每一个值出现 的几率都是一样的，然后再将该值乘以 10。由任何伪随机数生成器返回的数目会受到 0 到 N 之间整数数目的限制。因为常见情况下，伪随机数生成器生成 0 到 N 之间的一个 整数，返回的整数再除以 N。可以得出的数字总是处于 0 和 1 之 间。对生成器随后的调用采用第一次运行产生的整数，并将它传给 一个函数，以生成 0 到 N 之间的一个新整数，然后再将新整数除 以 N 返回。 5.1.2 伪随机数产生器4目前，常见随机数发生器中N 是2321 （大约等于 40 亿），对于 32 位数字来说，这是最大的值。但在密码学领域， 40 亿个数根本 不算大！伪随机数生成器将作为“

4、种子”的数当作初始整数传给函数。由 伪随机数生成器返回的每一个值完全由它返回的前一个值所决定。 因此，最初的种子决定了这个随机数序列。如果知道用于计算任何 一个值的那个整数，那么就可以算出从这个生成器返回的下一个值 。伪随机数生成器是一个生成完全可预料的数列（称为流）的确定 性程序。一个编写得很好的的PRNG可以创建一个序列，而这个序列 的属性与许多真正随机数的序列的属性是一样的。例如：（1）PRNG可以以相同几率在一个范围内生成任何数字； （2）PRNG 可以生成带任何统计分布的流；（3）由PRNG生成的数 字流不具备可辨别的模。55.1.3 基于密码算法的随机数产生器 1使用软件方法的随机

5、数产生器 一个常用的随机数产生器是属于线形拟合生成器一类的。这 类生成器相当普遍，它们采用很具体的数学公式：Xn+1 = (aXn + b) mod c 即第 n+1 个数等于第 n 个数乘以某个常数 a，再加上常数 b。 如果结果大于或等于某个常数 c，那么通过除以 c，并取它的余数来 将这个值限制在一定范围内。注意：a、b 和 c 通常是质数。 2使用硬件方法的随机数产生器 目前生成随机数的几种硬件设备都是用于商业用途。得到广泛使 用的设备是 ComScire QNG，它是使用并行端口连接到 PC 的外部设备， 它可以在每秒钟生成 20,000 位，这对于大多数注重安全性的应用程序来 说已

6、经足够了。另外Intel 公司宣布他们将开始在其芯片组中添加基于热能的硬件 随机数发生器，而且基本上不会增加客户的成本。迄今为止，已经交付了 一些带有硬件 PRNG 的 CPU。 65.1.4 伪随机数的评价标准 （1）看起来是随机的，表明它可以通过所有随机性统计检验。现在的许多统计测试。它们采用了各种形式，但共同思路是它们 全都以统计方式检查来自发生器的数据流，尝试发现数据是否是随 机的。确保数据流随机性的最广为人知的测试套件就是 George Marsaglia 的 DIEHARD 软件包（请参阅http:/www.stat.fsu.edu/ pub/diehard/）。另一个适合此类测试

7、的合理软件包是 pLab（请参 阅http:/random.mat.sbg.ac.at/tests/）。（2）它是不可预测的。即使给出产生序列的算法或硬件和所有以 前产生的比特流的全部知识，也不可能通过计算来预测下一个随机 比特应是什么。（3）它不能可靠地重复产生。如果用完全同样的输入对序列产生 器操作两次将得到两个不相关的随机序列。 75.2 序列密码的概念及模型 序列密码算法将明文逐位转换成密文，如下图所示。m密钥流发生器（也称为滚动密钥发生器）输出一系列比特流：K1 ，K2，K3，Ki 。密钥流（也称为滚动密钥）跟明文比特流，m1，m2 ，m3，mi ，进行异或运算产生密文比特流。加密：

8、 C i =miK i在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。 解密： m i =C iK i显然，miK iK i =m i8事实上，序列密码算法其安全性依赖于简单的异或运算和一次 一密乱码本。密钥流发生器生成的看似随机的密钥流实际上是确定 的，在解密的时候能很好的将其再现。密钥流发生器输出的密钥越 接近随机，对密码分析者来说就越困难。 如果密钥流发生器每次都生成同样的密钥流的话，对攻击来说， 破译该算法就容易了。假的Alice得到一份密文和相应的明文，她就可以将两者异或 恢复出密钥流。或者，如果她有两个用同一个密钥流加密的密文， 她就可以让两者异或得到两个明文互相异或而成的

9、消息。这是很容 易破译的，接着她就可以用明文跟密文异或得出密钥流。现在，无论她再拦截到什么密文消息，她都可以用她所拥有的 密钥流进行解密。另外，她还可以解密，并阅读以前截获到的消息 。一旦Alice得到一明文/密文对，她就可以读懂任何东西了。9这就是为什么所有序列密码也有密钥的原因。密钥流发生器的 输出是密钥的函数。这样，Alice有一个明文/密文对，但她只能读到用特定密钥加 密的消息。更换密钥，攻击者就不得不重新分析。流密码是将明文划分成字符流密码是将明文划分成字符( (如单个字母如单个字母) )，或其编码的基本单，或其编码的基本单元元( (如如0, 10, 1数字数字) )，字符分别与密钥

10、流作用进行加密，解密时以同步，字符分别与密钥流作用进行加密，解密时以同步 产生的同样的密钥流实现。产生的同样的密钥流实现。 流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)。 核心问题是密钥流生成器的设计。 保持收发两端密钥流的精确同步是实现可靠解密的关键技术。10流密码的分类:1.自同步序列密码 自同步序列密码就是密钥流的每一位是前面固定数量密文位的 函数，下图和下页图描述了其工作原理。其中，内部状态是前面n 比特密文的函数。该算法的密码复杂性在于输出函数，它收到内部 状态后生成密钥序列位。11自同步流密码SSSC(Self-Syn

11、chronous Stream Cipher)内部状态i依赖于(kI,i-1,mi)，使密文ci不仅与当前输入mi有 关，而且由于ki对i的关系而与以前的输入m1, m2 ,mi-1有关。 一般在有限的n级存储下将与mi-1,mi-n有关。12特点: 密钥流不仅依赖于种子密钥和密钥流产生器的结构，还 与密文流（或明文流）有关。初始向量IV在这里相当 于初始密文的作用，要求收、发双方必须相同。 自同步。解密只取决于先前特定数量的密文字符，因此 ，即使出现删除、插入等非法攻击，收方最终都能够自 动重建同步解密，因而收、发双方不再需要外部同步。 有差错传播。因为密钥流与密文流有关，所以一个密文 的传

12、输错误会影响下面有限个密文的解密。 13自同步序列密码举例例 假设种子密钥为k=h，之后的密钥是上一个密文。采用移位密 码，明文为cryptography，列表给出它的加密和解密过程。一个字符的差错传播 不需要同步142同步序列密码在同步序列密码中，密钥流的产生独立于明文和密文。分组加密的OFB模 式就是一个同步序列加密的例子。 1）同步要求。在一个同步序列密码中，发送方和接收方必须是同步的， 用同样的密钥且该秘钥操作在同样的位置，才能保证解密。如果在传输过 程中密文字符有插入或删除导致同步丢失，则解密失败，且只能通过重新 同步来实现恢复。 2）无错误传输。在传输期间，一个密文字符被改变只影响

13、该字符的恢复 ，不会对后继字符产生影响。152同步序列密码同步流密码SSC(Synchronous Stream Cipher)：内部状态i与明文消息无关，密钥流将独立于明文。特点： 对于明文而言，这类加密变换是无记忆的。但它是时变的。 只有保持两端精确同步才能正常工作。 对主动攻击时异常敏感而有利于检测 无差错传播(Error Propagation)16同步序列密码同样可防止密文中的插入和删除，因为它们会使系统失去同步而立即被发现。然而，却不能避免单个位被窜改。优点：具有自同步能力，强化了其抗统计分析的能力缺点：有n位长的差错传播。密钥流序列的性质密钥流序列的性质密码设计者的最大愿望是设计

14、出一个滚动密钥生成器，使得 密钥经其扩展成的密钥流序列具有如下性质： 极大的周期 良好的统计特性 抗线性分析 抗统计分析。17实际上实际上, ,序列密码不可能做到序列密码不可能做到“ “一次一密一次一密” ”但若密钥流生成器生成的密钥周期足够长，且随机性好，其安但若密钥流生成器生成的密钥周期足够长，且随机性好，其安全强度可以得到保证！全强度可以得到保证！因此，序列密码的设计核心在于密钥流生成器的设计，序列密因此，序列密码的设计核心在于密钥流生成器的设计，序列密码的安全强度取决于密钥流生成器生成的密钥周期、复杂度、随机码的安全强度取决于密钥流生成器生成的密钥周期、复杂度、随机（伪随机）特性等。（

15、伪随机）特性等。185.3 线性反馈移位寄存器(linear feedback shift register，LFSR) 异或表达式-线性反馈如果n级线性反 馈移位寄存器产 生的输出序列的 周期为2n-1，则 称为m序列产生器 。m序列不仅周期 长，而且伪随机 特性好，这正是 序列密码的密钥 流所需要的特性 。 195.3 线性反馈移位寄存器 产生密钥序列的最重要部件是线性反馈移位寄存器(LFSR), 是因为:(1) LFSR非常适合于硬件实现;(2) 能产生大的周期序列;(3) 能产生较好统计特性的序列;(4) 其结构能应用代数方法进行很好的分析.移位寄存器是流密码产生密钥流的一个主要组成部

16、分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,an)组成，如下页图所示。 20每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容 构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维 向量，共有2n种可能的状态。每一时刻的状态可用n长序列“a1,a2,an ”n维向量“(a1,a2,an)” 来表示，其中ai是第i级存储器的内容。初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储 器ai都将其内容向下一级ai-1传递，并计算f(a1,a2,an)作为下一时刻 的an。21反馈函数f(a1,a2,an)是n元布尔函数，即n个变元a1,a2,an 可以 独立地取0和1两个可能的值，函数中的运算有逻辑与、逻辑或、逻 辑补等运算，最后的函数值也为0或1。例：下图是一个3级反馈移位寄存器