密码学02－流密码课件.ppt

第二章 流密码 本章提要 流密码概况 2.1 流密码的基本概念 布尔函数简介 2.2 线性反馈移位寄存器 2.3 线性移位寄存器的一元多项式表示 2.4 m序列的伪随机性 2.5 m序列密码的破译 2.6 非线性序列 流密码概况 流密码(stream cipher)是一种重要的密码体制 明文消息按字符或比特逐位加密 流密码也称为序列密码(Sequence Cipher) 流密码在手工和机械密码时代是主流技术 流密码在50年代得到飞跃式发展 密钥流可以用移位寄存器电路来产生，也促进了线性和非线性移位寄存器发展 主要用于专用和机密机构：军方，银行等 由于互联网是分组传输的，流密码的使用较少 流密码具有有效的数学分析工具 代数(如布尔代数)、有限域理论和谱分析理论等等 流密码在现代密码学阶段的主要成果来自于密码分析 很多密码学家因流密码研究而成名 肖国镇，Massey，Berlikamp等。 在IEEE Transaction on Information Theory上能够发表的密码成果多数都是来自于流密码的相关研究 流密码基于硬件实现优势更明显，目前也有些算法是针对软件设计的 如Ecrypt计划中的算法，RC4等 参考资料：《伪随机序列及其应用》，《流密码学及其应用》，肖国镇著 2.1 流密码的基本概念 流密码的基本思想 利用密钥k产生一个密钥流z=z0z1z2…，并使用如下规则对明文串x=x0x1x2…加密： y=y0y1y2…＝Ez0(x0)Ez1(x1) Ez2(x2)…， 密钥流 由密钥流发生器 f 产生：zi＝f(k,σi) σi是加密器中的记忆元件在时刻 i 的状态 f 是由k, σi 产生的函数 流密码 分组密码 内部记忆元件由一组移位寄存器构成 流密码与分组密码的区别：在于有无记忆性 流密码的滚动密钥由函数f、密钥k和指定的初态σ0完全确定 此后由于输入加密器的明文可能影响加密器中的内部记忆元件的存储状态，因而σi (i0)可能依赖于k，σ0，x0，x1，…，xi－1，前 i 个明文和密钥及初态 分组密码中，一组一组的加密，一般等长 在分组内明文和密钥充分混淆，分组间一般互不影响，与分组连接模式有关 2.1.1同步流密码 流密码可按记忆元件存储状态分类 按照加密器中记忆元件的存储状态σi 是否依赖于输入的明文字符流，流密码可进一步分成同步和自同步流密码两种 σi 独立于明文字符流的叫做同步流密码，否则叫做自同步流密码 由于自同步流密码的密钥流的产生与明文有关，所以理论上难于分析。 好的密码算法应该在理论上或基于实践检验能够证明其是安全的或至少是没有明显漏洞的。 如果算法难于分析，则无法保证其安全性，也就无法放心使用，因此自同步流密码研究很少，很少采用。 目前大多数研究成果都是关于同步流密码的 由于zi＝f(k,σi)与明文无关，此刻的密文字符yi=Ezi(xi)也不依赖于此前的明文字符，这样可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。 设解密变换为xi=Dzi(yi)。同步流密码体制模型如下图 加密变换Ezi可有多种选择，保证变换可逆性即可 比如明文流和密钥流对应位异或 实际数字必威体育官网网址通信系统一般都是二元的{0,1},在有限域GF(2)上讨论二元加法流密码是目前最常用的流密码体制 加密变换可表示为yi＝zi?xi，加法流密码体制模型 一次一密密码(One Time Padding 一次一密乱码本)是加法流密码的原型 其中密钥的长度至少和明文的长度一样长，是无条件安全的，但实用性较差，因而不能广泛应用。 如果加法流密码中，zi＝ki，即直接将密钥k(k至少和明文一样长)用作滚动的密钥流，则加法流密码就是一次一密密码。 流密码体制中如果密钥有限，则安全性一般低于一次一密 从信息论意义上讲，对k比特长的串进行任何固定变换，其信息量至多为k比特，即密钥流再长，其安全性最大也就是密钥长度，而一次一密的密钥长度至少和明文一样。 同步流密码算法的设计主要是密钥流产生器的设计 密钥产生器目标是：使得密钥k经其扩展成的密钥流序列z具有如下性质： 极大的周期，良好的统计特性，抗差分分析，抗线性分析等 2.1.2 有限状态自动机 流密码中任意时刻密钥流和密文的输出与状态密切相关。可以用有限状态自动机这一数学模型来表述 有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由3部分组成： 有限状态集S={si|i=1,2,…,l} 共有l个可能状态 有限输入字符集A1={Aj(1)| j=1,2,…,m}和有限输出字符集A2={Ak(2)| k=1,2,…,n}。 转移函数: Ak(2)=