序列密码
序列密码
本讲主要内容 。序列密码的介绍 。线性反馈移位寄存器 。非线性序列 。序列密码的算法举例(A5、RC4) CNR@HEU http://machunguang.hrbeu.edu.cn
本讲主要内容 序列密码的介绍 线性反馈移位寄存器 非线性序列 序列密码的算法举例(A5、RC4) 3
序列密码的简介 序列密码通常认为起源于20世纪20年代的维尔姆(ernam) 密码，Vernam密码中的密钥序列要求是随机的序列，由于随机 的密钥序列的产生、存储以及分配等方面存在一定的困难， Vernam体制在当时并没有得到广泛的应用。随着微电子技术和 数学理论的发展和完善，基于伪随机序列的序列密码得到了长 足的发展和应用，其产生有比较成熟的数学理论工具。如果密 钥序列是随机的序列，则序列密码就是“一次一密”密码体制。 商农已经证明“一次一密”密码体制在理论上是不可破译的。 目前，序列密码是世界各国的军事和外交等重要领域中使用的 主要密码体制之一。 在序列密码中，加密和解密所用的密钥序列都是伪随机序 列，序列密码是对称密码体制中的一类，又称为流密码。 CNR@HEU http://machunguang.hrbeu.edu.cn
序列密码的简介 序列密码通常认为起源于 序列密码通常认为起源于20世纪20年代的维尔姆(Vernam) 密码，Vernam密码中的密钥序列要求是随机的序列，由于 密码中的密钥序列要求是随机的序列，由于随机 的密钥序列的产生、存储以及分配等方面存在一定的困难， Vernam体制在当时并没有得到广泛的应用。随着微电子技术和 体制在当时并没有得到广泛的应用。随着微电子技术和 数学理论的发展和完善，基于伪随机序列的序列密码得到了长 足的发展和应用，其产生有比较成熟的数学理论工具。如果密 钥序列是随机的序列，则序列密码就是“一次一密”密码体制。 商农已经证明“一次一密”密码体制在理论上是不可破译的。 目前，序列密码是世界各国的军事和外交等重要领域中使用的 主要密码体制之一。 在序列密码中，加密和解密所用的密钥序列都是伪随机序 列，序列密码是对称密码体制中的一类，又称为流密码。 4 列，序列密码是对称密码体制中的一类，又称为流密码
序列密码的描述 在序列密码中，将明文消息按一定长度（长度较小）分 组，然后对各组用相关但不同的密钥进行加密，产生相应的 密文，相同的明文分组会因在明文序列中的位置不同而对应 于不同的密文分组。解密用相同的密钥序列对密文序列进行 分组解密以恢复出明文序列。 >设明文为p=poPP2… P,∈GF(2,20 >设密钥为k=k,kk2… k,∈GF2),20 >设密文为C=CoC1C2… y,∈GF2),20 >则加密变换为c,=EkP) ≥0 >则解密变换为p,=Dkc) 20 CNR@HEU http://machunguang.hrbeu.edu.cn
序列密码的描述 在序列密码中，将明文消息按一定长度 将明文消息按一定长度 将明文消息按一定长度 将明文消息按一定长度（长度较小）分 组，然后对各组用相关但不同的密钥进行加密，产生相应的 密文，相同的明文分组会因在明文序列中的位置不同而对应 于不同的密文分组。解密用相同的密钥序列对密文序列进行 分组解密以恢复出明文序列。 ¾设明文为p=p0p1p2… … pi∈GF(2), i≥0 ¾设密钥为k=k0k1k2… … ki∈GF(2), i≥0 ¾设密文为c c= 0c1c2… yi∈GF(2), i≥0 ¾则加密变换为ci＝Eki(pi) i≥0 ¾则解密变换为p D (c ) i≥0 5 ¾则解密变换为pi＝Dki(ci) i≥0
序列密码的原理 种子密钥K 密钥序列 产生器 密钥序列k: 明文序列P +密文序列C 特点： >加解密运算只是简单的模二加运算。 >密码安全强度主要依赖密钥流的安全性。 6 CNR@HEU http://machunguang.hrbeu.edu.cn
序列密码的原理 种子密钥K 密钥序列 产生器 明文序列P 密文序列C 密钥序列ki 明文序列Pi 密文序列Ci 特点： ¾ 加解密运算只是简单的模二加运算。 ¾ 密码安全强度主要依赖密钥流的安全性。 特点： 6 ¾ 密码安全强度主要依赖密钥流的安全性
序列密码体制的示意图 同步方式是指密钥流的产生需 要收发双方进行同步，密钥流 完全独立于消息流。 明文序列 密文序列 密文序列 明文序列 Pm-1…PPo. Cn-1...C1Co Cn-1...C1Co Pm-1…PPo 公共信道 密钥序列 密钥序列 a-1k ka-1 密钥序列产生器 密钥序列产生器 种子密钥K 秘密信道 种子密钥K 自同步方式是指收发双方中 的任何一方，其密钥流的产 生依赖于密文流。 CNR@HEU http://machunguang.hrbeu.edu.cn
序列密码体制的示意图 同步方式是指密钥流的产生需 明文序列 密文序列 要收发双方进行同步，密钥流 完全独立于消息流。 明文序列 密文序列 c n-1 … c1c 0 公共信道 密文序列 c n-1 … c1c 0 明文序列 p n-1 … p1p 0 p n-1 … p1p 0 密钥 序列 密钥 序列 密钥序列产生器 kn-1 … k1k0 密钥序列产生器 kn-1 … k1k0 种子密钥 K 种子密钥 K 自同步方式是指收发双方中 的任何一方，其密钥流的产 7 生依赖于密文流
密钥序列产生器(KG)基本要求 >种子密钥K的长度足够大，一般应在128位以上； >KG生成的密钥序列仫}具极大周期； >{k}具有均匀的-元分布，即在一个周期环上，某特定形式的 n-长bit串与其求反，两者出现的频数大抵相当（例如，均匀 的游程分布)； >利用统计方法由：}提取关于KG结构或K的信息在计算上不可 行； >雪崩效应。即K任一位的改变要引起k}在全貌上的变化。 >密钥流k}不可预测的。密文及相应的明文的部分信息，不能 确定整个k}。 8 CNR@HEU http://machunguang.hrbeu.edu.cn
密钥序列产生器 密钥序列产生器(KG)基本要求 ¾ 种子密钥K的长度足够大，一般应在128位以上； ¾KG生成的密钥序列 生成的密钥序列{ki}具极大周期； ¾{ki}具有均匀的n-元分布，即在一个周期环上 即在一个周期环上，某特定形式的 n-长bit串与其求反，两者出现的频数大抵相当 串与其求反，两者出现的频数大抵相当(例如，均匀 的游程分布)； ¾ 利用统计方法由{ki}提取关于KG结构或K的信息在计算上不可 的信息在计算上不可 行； ¾ 雪崩效应。即K任一位的改变要引起{ki}在全貌上的变化。 ¾ 密钥流{ki}不可预测的。密文及相应的明文的部分信息，不能 确定整个{k } 。 8 确定整个{ki}
密钥序列产生器的分解 把产生的多条驱动序列综合 般由m-序列生成器构 在一起的一些非线性编码手 成，提供若干周期大、 段，目的是有效地破坏和掩 分布特性好的序列。 盖多条驱动序列中存在的规 种子密钥K 律或关系，提高复杂度。 驱动子系统 非线性组合 子系统 密钥序列K LFRS2 密钥序列K FRSn 常用的密钥序列产生器 9 CNR@HEU http://machunguang.hrbeu.edu.cn
密钥序列产生器的分解 一般由 m-序列生成器构 成，提供若干周期大 、 把产生的多条驱动序列综合 在一起的一些非线性编码手 段，目的是有效地破坏和掩 种子密钥 K 成，提供若干周期大 、 分布特性好的序列。 段，目的是有效地破坏和掩 盖多条驱动序列中存在的规 律或关系，提高复杂度 律或关系，提高复杂度。 驱动子系统 非线性组合 子系统 密钥序列 K 驱动子系统 。 i 。 . LFRS1 。 。 LFRS2 F 密钥序列 Ki 常用的密钥序列产生器 。 . LFRSn 9 常用的密钥序列产生器
线性反馈移位奇存器理论的简介 序列密码的关键是设计一个随机性好的密钥流发生 器，为了研究密钥流发生器，挪威政府的首席密码学家 Ernst Selmer于1965年提出了移位寄存器理论，它是 序列密码中研究随机密钥流的主要数学工具。 尤其，线性反馈移位寄存器因其实现简单、速度快、 有较为成熟的理论等优点而成为构造密码流生成器的最 重要的部件之一。 10 CNR@HEU http://machunguang.hrbeu.edu.cn
线性反馈移位奇存器理论的简介 序列密码的关键是设计一个随机性好的密钥流发生 器 ，为了研究密钥流发生器 ，挪威政府的首席密码学家 Ernst Selmer 于1965年提出了移位寄存器理论，它是 序列密码中研究随机密钥流的主要数学工具。 尤其，线性反馈移位寄存器因其实现简单、速度快、 有较为成熟的理论等优点而成为构造密码流生成器的最 重要的部件之一。 10
反馈移位寄存器 反馈移位寄存器(feedback shift register,FSR)是由n位 的寄存器和反馈函数feedback function)组成，如下图所示， 位的寄存器中的初始值称为移位寄存器的初态。 In In-1· b b-...b2 bi →输出位0 反馈函数f 工作原理：移位寄存器中所有位的值右移1位，最右边的一个 寄存器移出的值是输出位，最左边一个寄存器的值由反馈函 数的输出值填充，此过程称为进动1拍。反馈函数f是个变元 (b1,b2,,b)的布尔函数。移位寄存器根据需要不断地进动m 拍，便有m位的输出，形成输出序列01,02,0m。 CNR@HEU http://machunguang.hrbeu.edu.cn
反馈移位寄存器 反馈移位寄存器 反馈移位寄存器(feedback shift register,FSR) (feedback shift register,FSR)是由n位 的寄存器和反馈函数(feedback function)组成，如下图所示， n位的寄存器中的初始值称为移位寄存器的初态。 bn bn-1 … b2 b1 rn rn-1 … r2 r1 输出位Oi 反馈函数f 工作原理：移位寄存器中所有位的值右移1位，最右边的一个 寄存器移出的值是输出位，最左边一个寄存器的值由反馈函 反馈函数 寄存器移出的值是输出位，最左边 个寄存器的值由反馈函 数的输出值填充，此过程称为进动1拍。反馈函数f是n个变元 (b1,b2,…,bn)的布尔函数。移位寄存器根据需要不断地进动m 11 ( 1, 2, , n) 布尔函数 移位寄存 根据需要 断 动 拍，便有m位的输出，形成输出序列o1,o2,…,om