第二章流密码 内容提要 1.流密码的基本概念 2线性反馈移位寄存器 3非线性序列 4.流密码算法 历忠毛孑技*字
内容提要 1. 流密码的基本概念 2. 线性反馈移位寄存器 3. 非线性序列 4. 流密码算法 2/ 第二章 流密码
第二章流密码 21流密码的基本概念 ●流密码( stream cipher),也称为序列密码( Sequence Cipher),是一种重要的密码体制 明文消息按字符或比特还位加密 ●流密码的基本思想 利用密钥k产生一个密钥流乙=x1z1z2, 内部记忆元件 并使用如下规则对明文串x=xx}2…加密: =yy1y2…,=Ex0)E1(x1)Ez2(x2) 流密码示意图 ●流密码与分组密码的区别:在于有无记忆性 流密码的密钥流是由已知记忆状态导出 当前状态与记忆元件初始状态、密钥k、 无记忆元件 y 输入的明文和状态转换函数导出 yE(x) 分组密码对明文一组一组的加密,组间一般没有关系分组密码示意图 团岑毛孑彳
2.1 流密码的基本概念 流密码(stream cipher)，也称为序列密码(Sequence Cipher)，是一种重要的密码体制 ⚫ 明文消息按字符或比特逐位加密 流密码的基本思想 ⚫ 利用密钥k产生一个密钥流z=z0z1z2…， ⚫ 并使用如下规则对明文串x=x0x1x2…加密： y=y0 y1 y2…＝Ez0 (x0 ) Ez1 (x1 ) Ez2 (x2 )… 流密码与分组密码的区别：在于有无记忆性 ⚫ 流密码的密钥流是由已知记忆状态导出 当前状态与记忆元件初始状态、密钥k、 输入的明文和状态转换函数导出 ⚫ 分组密码对明文一组一组的加密，组间一般没有关系 3/ 第二章 流密码 内部记忆元件 … … … k xi yi yi=Ezi(xi) 无记忆元件 k x1 yl y=Ek(x) ... xm y1 流密码示意图 分组密码示意图
第二章流密码 21流密码的基本概念 ●流密码在50年代得到飞跃式发展 密钥流可以用移位寄存器电路来产生,因此基于硬件实现优势更明显 也有些算法是针对软件设计的,如 Ecrypt计划中的算法,Rc4等 ●主要用于专用和机密机构:军方,外交,银行等 ●资源受限环境(如RFD标签)、伪随机数生成器、链路加密等环境 加密速度快,实现简单,同步流密码不存在错误扩散问题,对一些有 扰信道而言是良好的选择 ≥流密码具有有效的数学分析工具 代数(如布尔代数)、有限域理论和谱分析理论、概率论等等 ≥很多密码学家因流密码研究而成名:肖国镇, Massey, Berlekamp等。 ●参考资料: 肖国镇著《伪随机序列及其应用》,《流密码学及其应用》 历毛孑拌技大字
2.1 流密码的基本概念 流密码在50年代得到飞跃式发展 ⚫ 密钥流可以用移位寄存器电路来产生，因此基于硬件实现优势更明显 ⚫ 也有些算法是针对软件设计的，如Ecrypt计划中的算法，RC4等 主要用于专用和机密机构：军方，外交，银行等 ⚫ 资源受限环境(如RFID标签)、伪随机数生成器、链路加密等环境 ⚫ 加密速度快，实现简单，同步流密码不存在错误扩散问题，对一些有 扰信道而言是良好的选择 流密码具有有效的数学分析工具 ⚫ 代数(如布尔代数)、有限域理论和谱分析理论、概率论等等 很多密码学家因流密码研究而成名：肖国镇，Massey，Berlikamp等。 参考资料： ⚫ 肖国镇著《伪随机序列及其应用》，《流密码学及其应用》 4/ 第二章 流密码
第二章流密码:21流密码的基本概念 211同步流密码 ●流密码的滚动密钥流 由密钥流发生器产生:z=k, ●内部记忆元件由一组移位寄存器构成,这里假设有m个移位寄存器 m-1 a1 Feedback shift Register, fsr =(a1 ●0是加密器中的记忆元件在时刻i的状态,可表示为 r=(an,n1,…,a1) ∫是由k,G产生的函数 流密码的滚动密钥由函数密钥k和指定的初态完全确定 此后由于输入加密器的明文可能影响加密器中的内部记忆元件的存储 状态,因而σ(>0)可能依赖于k,0,x0,x1,…,x;-1,即前i个明文 和密钥及初态 历忠毛孑技*字
2.1.1 同步流密码 流密码的滚动密钥流 ⚫ 由密钥流发生器f 产生：zi＝f(k,σi ) ⚫ 内部记忆元件由一组移位寄存器构成，这里假设有n个移位寄存器 ⚫ σi是加密器中的记忆元件在时刻i 的状态，可表示为 ⚫ σi=(an , an-1 , … , a1 ) ⚫ f 是由k, σi产生的函数 ⚫ 流密码的滚动密钥由函数f、密钥k和指定的初态σ0完全确定 ⚫ 此后由于输入加密器的明文可能影响加密器中的内部记忆元件的存储 状态，因而σi (i>0)可能依赖于k，σ0，x0，x1，…，xi－1，即前 i 个明文 和密钥及初态 5/ 第二章 流密码：2.1 流密码的基本概念 an σi=(a1,a2,…,an) an-1 ... a1 Feedback Shift Register, FSR
第二章流密码:21流密码的基本概念 211同步流密码 ●流密码可按记忆元件存储状态分类 按照加密器中记忆元件的存储状态G是否依赖于输入的 明文字符流,流密码可进一步分成同步和自同步流密码 两种 ●G;独立于明文字符流的叫做同步流密码,否则叫做自同 步流密码 由于自同步流密码的密钥流产生与明文有关,所以理论上难于 分析。 ●好的密码算法应该在理论上或基于实践检验能够证明其是安全 的或至少是没有明显漏洞的。 如果算法难于分析,则无法保证其安全性,也就无法放心使用 ,因此自同步流密码研究很少,很少采用。 历忠毛孑技*字
2.1.1 同步流密码 流密码可按记忆元件存储状态分类 ⚫ 按照加密器中记忆元件的存储状态σi是否依赖于输入的 明文字符流，流密码可进一步分成同步和自同步流密码 两种 ⚫ σi 独立于明文字符流的叫做同步流密码，否则叫做自同 步流密码 ⚫ 由于自同步流密码的密钥流产生与明文有关，所以理论上难于 分析。 ⚫ 好的密码算法应该在理论上或基于实践检验能够证明其是安全 的或至少是没有明显漏洞的。 ⚫ 如果算法难于分析，则无法保证其安全性，也就无法放心使用 ，因此自同步流密码研究很少，很少采用。 6/ 第二章 流密码：2.1 流密码的基本概念
第二章流密码:21流密码的基本概念 211同步流密码 ●目前大多数研究成果都是关于同步流密码的 由于=fk,o与明文无关,此刻的密文字符y=E(x)也 不依赖于此前的明文字符,这样可将同步流密码的加密 器分成密钥流产生器和加密变换器两个部分。 设解密变换为x=Dz)。同步流密码体制模型如下图 k4Z→k 安全信道 滚动密钥生成器 滚动密钥生成器 Ezi(xi) Dzivi 历忠毛孑技*字
2.1.1 同步流密码 目前大多数研究成果都是关于同步流密码的 ⚫ 由于zi＝f(k,σi )与明文无关，此刻的密文字符yi=Ezi (xi )也 不依赖于此前的明文字符，这样可将同步流密码的加密 器分成密钥流产生器和加密变换器两个部分。 ⚫ 设解密变换为xi=Dzi (yi )。同步流密码体制模型如下图 7/ 第二章 流密码：2.1 流密码的基本概念 安全信道 k k 滚动密钥生成器 … … … 滚动密钥生成器 … … … zi zi xi yi Ezi(xi) … … … yi xi Dzi(yi)
第二章流密码:21流密码的基本概念 211同步流密码 加密变换E可有多种选择,保证变换可逆性即可 比如明文流和密钥流对应位异或 实际数字保密通信系统一般都是二元的0,1}在有限域GF(2)上讨论 二元加法流密码是目前最常用的流密码体制 加密变换可表示为y1=zA,加法流密码体制模型 ●同步流密码算法的设计主要是密钥流产生器的设计 密钥产生器目标是:使密钥k经其扩展成的密钥流序列有:极大 的周期,良好的统计特性,抗差分分析,抗线性分析等性质 k4Zx→k 安全信道 滚动密钥生成器 滚动密钥生成器 4 可 历忠毛孑技*字
2.1.1 同步流密码 加密变换Ezi可有多种选择，保证变换可逆性即可 ⚫ 比如明文流和密钥流对应位异或 ⚫ 实际数字保密通信系统一般都是二元的{0,1},在有限域GF(2)上讨论 二元加法流密码是目前最常用的流密码体制 ⚫ 加密变换可表示为yi＝zixi，加法流密码体制模型 同步流密码算法的设计主要是密钥流产生器的设计 ⚫ 密钥产生器目标是：使密钥k经其扩展成的密钥流序列z具有：极大 的周期，良好的统计特性，抗差分分析，抗线性分析等性质 8/ 第二章 流密码：2.1 流密码的基本概念 安全信道 k k 滚动密钥生成器 … … … 滚动密钥生成器 … … … zi zi xi yi … … … yi xi
第二章流密码:21流密码的基本概念 212有限状态自动机 ●流密码中任意时刻密钥流和密文的输出与状态密切相关。 可以用有限状态自动机这一数学模型来表述 ●有限状态自动机是具有离散输入和输出(输入集和输出集 均有限)的一种数学模型,由3部分组成: 有限状态集S={s=1,2,共有个可能状态 有限输入字符集41={4=1,2…,m和有限输出字符集 A2={42k=1,2…,n 转移函数 输出转移函数:A42f(S,A4/),状态转移函数:s≠,4y①) 即在状态为s,输入为4①时,输出为42),而状态转移为h 历忠毛孑技*字
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)=f1 (si ,Aj (1))，状态转移函数：sh=f2 (si ,Aj (1)) ⚫ 即在状态为si，输入为Aj (1)时，输出为Ak (2)，而状态转移为sh。 9/ 第二章 流密码：2.1 流密码的基本概念
第二章流密码:21流密码的基本概念 212有限状态自动机 ●【例2-1】 Sas 19 A1={41(,A2,43},A2={412,42,432},转移函数由 表2-1给出。f为输出转移函数,f2为状态转移函数 A1(1) S A1(2) 2) (2) A2 A,(2 (2) (2) (2 A,(1) 历忠毛孑技*字 10
2.1.2 有限状态自动机 【例2－1】 ⚫ S={s1 ,s2 ,s3 }， ⚫ A1={A1 (1) ,A2 (1) ,A3 (1) }，A2={A1 (2) ,A2 (2) ,A3 (2) }，转移函数由 表2－1给出。f1为输出转移函数，f2为状态转移函数 10/ 第二章 流密码：2.1 流密码的基本概念 f 1 A1 (1) A2 (1) A3 (1) s1 A1 (2) A3 (2) A2 (2) s2 A2 (2) A1 (2) A3 (2) s3 A3 (2) A2 (2) A1 (2) f 2 A1 (1) A2 (1) A3 (1) s1 s2 s1 s3 s2 s3 s2 s1 s3 s1 s3 s2
第二章流密码:21流密码的基本概念 212有限状态自动机 有限状态自动机可用有向图表示,称为转移图 转移图的顶点对应于自动机的状态 若状态S在输入4时转为状态s,且输出一字符42),则在转移图 中,从状态到状态有一条标有(4(,42)的有向弧线,如图 ●在例2-1中,若 输入序列为412A41①433A1") (42),A2) 初始状态为s1, 则得到状态序列为: (43,A3 S1S,S,S3S2SIS (43,A2) 4),:e2,A 输出字符序列为: A/2A2A2A12A2A124,A9((52)44吗3))4949 (4,A12) 历忠毛孑技*字
2.1.2 有限状态自动机 有限状态自动机可用有向图表示，称为转移图 ⚫ 转移图的顶点对应于自动机的状态 ⚫ 若状态 si在输入Ai (1)时转为状态sj，且输出一字符Aj (2)，则在转移图 中，从状态si到状态sj有一条标有(Ai (1) ,Aj (2) )的有向弧线，如图 在例2-1中，若 ⚫ 输入序列为A1 (1)A2 (1)A1 (1)A3 (1)A3 (1)A1 (1) ⚫ 初始状态为s1， ⚫ 则得到状态序列为： ⚫ 输出字符序列为： 11/ 第二章 流密码：2.1 流密码的基本概念 s1 (A2 (1) , A3 (2) ) s3 (A2 (1) , A2 (2) s ) (A2 2 (1) , A1 (2) ) (A3 (1) , A3 (2) ) (A1 (1) , A1 (2) ) (A1 (1) , A3 (2) ) (A3 (1) , A2 (2) ) (A1 (1) , A2 (2) ) (A3 (1) , A1 (2) ) s1 s2 s2 s3 s2 s1 s2 A1 (2)A1 (2)A2 (2)A1 (2)A3 (2)A1 (2)