第2章流密码技巧.pptVIP

第2章 流密码 2.1 流密码的基本概念 2.2 线性反馈移位寄存器 2.4 m序列的伪随机性 2.5 m序列密码的破译 2.6 非线性序列 2.1 流密码的基本概念 流密码的是利用密钥k产生一个密钥流z z0z1…，并使用如下规则对明文串x x0x1x2…加密： y y0y1y2… Ez0 x0 Ez1 x1 Ez2 x2 …。 密钥流的长度与明文长度相同。 密钥流由密钥流发生器f产生： zi f k,σi ，这里σi是加密器中的记忆元件（存储器）在时刻i的状态，f是由密钥k和σi产生的函数。 1.密钥流强度依赖： 随机性 不可预测性 2.核心问题： 密钥生成器的设计 3.实现可靠解密的关键技术： 同步 4.分组密码与流密码的区别：有无记忆性 2.1.1 同步流密码 根据加密器中记忆元件的存储状态σi是否依赖于输入的明文字符，流密码可进一步分成: 同步流密码:σi独立于明文字符;（目前使用） 自同步流密码:σi依赖于明文字符; 可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。 图2.2 同步流密码体制模型 同步流密码的加密变换Ezi可以有多种选择，只要保证变换是可逆的即可。 实际使用的数字必威体育官网网址通信系统一般都是二元系统，因而在有限域GF 2 上讨论的二元加法流密码（如图2.3）是目前最为常用的流密码体制，其加密变换可表示为: yi zi xi。 图2.3 加法流密码体制模型 密码设计者的最大愿望是设计一次一密的密码。 实际使用时，密钥流序列具有如下性质： 极大的周期 良好的统计特性 抗线性分析 抗统计分析 流密码的优点： 加密速度快、容易实现 2.1.2 有限状态自动机（FA,Finite state Automation） 有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成： ① 有限状态集S si|i 1,2,…,l 。 ② 有限输入字符集A1 A 1 j|j 1,2,…,m 有限输出字符集A2 A 2 k|k 1,2,…,n 。 ③ 转移函数A 2 k f1 si,A 1 j sh f2 si,A 1 j 即在状态为si，输入为A 1 j时，输出为A 2 k，而状态转移为sh。 表示方法： ①表 ② 状态图（转移图） 例2.1 S s1,s2,s3 ，A1 A 1 1,A 1 2,A 1 3 ，A2 A 2 1,A 2 2,A 2 3 ， 转移函数由表2.1给出。 表2.1 转移函数f1和f2 有限状态自动机可用有向图表示，称为转移图。转移图的顶点对应于自动机的状态，若状态si在输入A 1 i时转为状态sj，且输出一字符A 2 j，则在转移图中，从状态si到状态sj有一条标有 A 1 i,A 2 j 的弧线，见图2.4。 例：若输入序列为: A 1 1A 1 2A 1 1A 1 3A 1 3A 1 1， 初始状态为s1，则得到状态序列: s1 s2 s2 s3 s2 s1 s2 输出字符序列: A 2 1A 2 1A 2 2A 2 1A 2 3A 2 1 图2.4 有限状态自动机的转移图 2.1.3 密钥流产生器 同步流密码的关键是密钥流产生器。一般可将其看成一个参数为k的有限状态自动机，由一个输出符号集Z、一个状态集∑、两个函数φ和ψ以及一个初始状态σ0组成。 关键在于找出适当的状态转移函数φ和输出函数ψ。 使得输出序列z满足密钥流序列z应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用非线性函数。 由于具有非线性的φ的有限状态自动机理论很不完善，相应的密钥流产生器的分析工作受到极大的限制。 当采用线性的φ和非线性的ψ时，将能够进行深入的分析并可以得到好的生成器； 可将这类生成器分成驱动部分和非线性组合部分（如图2.6）； 驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列； 非线性组合部分要利用这些序列组合出满足要求的密钥流序列。 图2.6 密钥流生成器的分解 图2.7 常见的两种密钥流产生器 2.2 线性反馈移位寄存器 移位寄存器是流密码产生密钥流的一个主要组成部分。GF 2 上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f a1,a2,…,an 组成. 每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF 2 上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列 a1,a2,…,an 或n维向量 a1,a2,…,an 表示，其中ai是第i级存储器的内容。 初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并根据寄存器此时的状态a1,a