序列密码体制(续)解析

2020 4 8 1 应用密码学 张仕斌万武南张金全孙宣东编著 西安电子科技大学出版社 二00九年十二月 2020 4 8 2 第4章序列密码体制 2020 4 8 3 知识点 序列密码的概念 线性反馈移位寄存器 序列和周期 非线性序列简介 常用序列密码 2020 4 8 4 4 4非线性序列简介 线性移位寄存器序列密码在已知明文攻击下是可破译的这一事实促使人们向非线性领域探索 目前研究的比较充分的由非线性移位寄存器 对线性移位寄存器进行非线性组合等 为了使密钥流生成器输出的二元序列尽可能复杂 应保证其周期尽可能大 线性复杂度和不可预测性尽可能高 因此常使用多个LFSR来构造二元序列 称每个LFSR的输出序列为驱动序列 显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积 因此 提高输出序列的线性复杂度应从极大化其周期开始 2020 4 8 5 1 Geffe序列生成器 Geffe序列生成器由3个LFSR组成 如下图 其中LFSR2作为控制生成器使用 当LFSR2输出1时 LFSR2与LFSR1相连接 当LFSR2输出0时 LFSR2与LFSR3相连接 若设LFSRi的输出序列为 a i k i 1 2 3 则输出序列 bk 可以表示为 因为 2020 4 8 6 设LFSRi的特征多项式分别为ni次本原多项式 且ni两两互素 则Geffe序列的周期为 线性复杂度为 Geffe序列的周期实现了极大化 且0与1之间的分布大体上是平衡的 2020 4 8 7 2 J K触发器 J K触发器如下图所示 它的两个输入端分别用J和K表示 其输出ck不仅依赖于输入 还依赖于前一个输出位ck 1 即 其中x1和x2分别是J和K端的输入 由此可得J K触发器的真值表 如下表所示 J K触发器真值表 2020 4 8 8 利用J K触发器的非线性序列生成器见下图 在上图中 令驱动序列 ak 和 bk 分别为m级和n级m序列 则有 如果令c 1 0 则输出序列的最初3项为 当m与n互素且a0 b0 1时 序列 ck 的周期为 2m 1 2n 1 2020 4 8 9 例 令m 2 n 3 两个驱动m序列分别为 ak 0 1 1 和 bk 1 0 0 1 0 1 1 于是 输出序列 ck 是0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 0 其周期为 22 1 23 1 21 由表达式ck ak bk 1 ck 1 ak可得 因此 如果知道 ck 中相邻位的值ck 1和ck 就可以推断出ak和bk中的一个 而一旦知道足够多的这类信息 就可通过密码分析的方法得到序列 ak 和 bk 为了克服上述缺点 Pless提出了由多个J K触发器序列驱动的多路复合序列方案 称为Pless生成器 2020 4 8 10 3 Pless生成器 假定在时刻t输出第t mod4 个单元 则输出序列为 a0b1c2d3a4b5d6 Pless生成器由8个LFSR 4个J K触发器和1个循环计数器构成 由循环计数器进行选通控制 如下图所示 2020 4 8 11 4 钟控发生器 钟控发生器是由控制序列 由一个或多个移位寄存器来控制生成 的当前值决定被采样的序列寄存器移动次数 即由控制序列的当前值确定采样序列寄存器的时钟脉冲数目 控制序列和被采样序列可以是源于同一个LFSR 称为自控 也可以源于不同的LFSR 称为他控 还可以相互控制 称为互控 钟控发生器示意图如下图所示 2020 4 8 12 当控制序列当前值为1时 被采样序列生成器被时钟驱动k次后输出 当控制序列当前值为0时 被采样序列生成器被时钟驱动d次后输出 另外 停走式发生器也是一种钟控模型 它由2个LFSR组成 其中 LFSR 1控制LFSR 2的时钟输入 当且仅当LFSR 1的时间t 1的输出为1时 LFSR 2在时间t改变状态 也即LFSR 1输出时钟脉冲 使LFSR 2进行输出并反馈以改变移位寄存器的状态 2020 4 8 13 5 收缩和自收缩发生器 收缩发生器是又控制序列的当前值决定被采样序列移位寄存器是否输出 该发生器由2个LFSR组成 LFSR 1 LFSR 2分别按各自时钟运行 LFSR 1在时间t 1时刻的输出为1时 LFSR 2在时间t时刻输出为密钥流 否则舍去 自收缩发生器从一个LFSR抽出2条序列 其中一条为控制序列 另一条为百采样序列 当控制序列输出为1时 采样序列输出为密钥流 否则舍去 此外 还有多路复合序列 这类序列也归结为非线性组合序列 2020 4 8 14 设计一个性能良好的序列密码是一项十分困难的任务 最基本的设计原则是 密钥流生成器的不可预测性 它可分解为下述基本原则 序列密码的设计原则 长周期 高线性复杂度 统计性能良好 足够的 混乱 足够的 扩散 抵抗不同形式的攻击 2020 4 8 15 基于LFSR的序列密码非常适合于硬件实现 但是不特别适合软件实现 这导致出现了一些关于序列密码被计划用于快速软件实现的新建议 因为这些建议大部分具有专利 因此这里不讨论它们的技术细节 比较常用的序列密码是A5 SEAL和RC4序列密码算法 A5是典型的基于LFSR的序列密码算法 SEAL和RC4不是基于LFSR的序列密码算法 而是基于分组密码的输出反馈模式 OFB 和密码反馈模式 CFB 来实现的 其他不基于LFSR的序列密码生成器的安全性基于数论问题的难解性 这些生成器比基于LFSR的生成器要慢很多 4 5常用的序列密码算法 2020 4 8 16 A5序列密码算法是利用欧洲数字蜂窝移动电话 GSM 加密的序列密码算法 它用于从用户手机至基站的连接加密 GSM会话每帧数据包含228比特 A5算法每次会话将产生228比特的密钥 算法的密钥长度为64比特 还包含有一个22比特的帧数 A5算法有两个版本 强A5 1和弱A5 2 A5算法是一种典型的基于LFSR的序列密码算法 它由三个LFSR组成 是一种集控制与停走于一体的钟控模型 但是A5算法没有完全公开 因而各种资料的描述也不尽相同 重要是第二个和第三个LFSR的联接多项式以及钟控的位置 A5算法的3个LFSR中LFSR 1 LFSR 2 LFSR 3的级数分别为19 22和23 LFSR 1的反馈抽头是18 17 16 13 LFSR 2的反馈抽头是21 20 16 12 LFSR 3的反馈抽头是22 21 18 17 如下页图的数字表示抽头的位置 4 5 1A5序列密码算法 2020 4 8 17 2020 4 8 18 2020 4 8 19 A5的统计性很好 但是移位寄存器太短容易遭到穷举攻击 A5算法把主密钥作为算法中三个寄存器的初始值 长度为64比特 但有时密钥的大小会使人误解 认为密钥长度越长越安全 其实并不是这样 因为已知明文攻击只需要知道其中两个寄存器的初始值 就可以计算出另一个寄存器的初始值 这只需要240步就可以得出寄存器LFSR 1和LFSR 2 另外 A5 2是A5的一个简化版本 只需要216步就可以破解它 出了密钥长度小外 A5还有一个冲突问题 即不同寄存器初始值可能产生不同的密钥流 研究表明 在寄存器所有初始值中 只有70 的值可以产生唯一的密钥流 2020 4 8 20 2020 4 8 21 2020 4 8 22 2020 4 8 23 在GSM标准中 信息以帧序列的形式通过电波进行传输 帧序列包含数字化的用户语音数据以及用于移动互联网浏览的音 视频数据流 该系统按顺序传输每一个帧 时间间隔为4 6毫秒 每帧由228位构成 前114位称为 上行链路数据 后114位称为 下行链路数据 2020 4 8 24 2020 4 8 25 2020 4 8 26 2020 4 8 27 2020 4 8 28 2020 4 8 29 2020 4 8 30 2020 4 8 31 2020 4 8 32 2020 4 8 33 2020 4 8 34 4 5 2RC4序列密码体制 RC4是美国RSA数据安全公司1987年设计的一种一个可变密钥长度 40至2048比特可变 面向字节 256个bytes 操作的序列密码 RSA数据安全公司将其收集在加密工具软件BSAFE中 最初并没有公布RC4的算法 人们通过软件进行逆向分析得到了算法 在这种情况下 RSA数据安全公司于1997年公布了RC4密码算法 基本思想 对于n位长的字 RC4是8位长的字 它总共N 2n RC4是28个 个可能的内部置换状态矢量S表 这些状态是保密的 密钥流K由S中N个元素按照一定方式选出一个元素而生成 每生成一个K值 S中的元素就被重新置换一次 密钥流的生成有两个过程 密钥调度算法 KSA 和伪随机数生成算法 PRGA KSA主要用于设置数据表S的初始排列 初始化数据表S PRGA用于选取随机元素元素并修改S表中的排列顺序 2020 4 8 35 密钥调度算法KSA KSA主要用于初始化数据表S 即S i i 0 i 255 一个字节 通过选取一系列的数字 并加载到密钥数据表k 0 k 1 k 255 步骤 1 对S表进行线性填充 即S 0 0 S 1 1 S 255 255 2 用种子密钥填充另一个256字符的K表k 0 k 1 k 255 如果密钥的长度小于K的长度 则依次重复填充 直至将K表填满 3 j 0 4 for0 i 255 j j S i k i mod256 交换S i 和S j 2020 4 8 36 KSA算法描述如下 1 初始化阶段 N 256fori 0toN 1doS i i j 0 fori 0toN 1doj j S i K imodl modN swap S i S j 2020 4 8 37 伪随机子密钥生成算法PRGA 当KSA算法完成了S的初始化后 PRGA算法就开始工作 为密钥流选取字节 选取时时是从S表中选取随机元素 并修改S以便下一次选取 选取过程取决于索引i和j 1 i 0 j 0 2 i i 1 mod256 3 j j S i mod256 4 交换S i 和S j 5 t S i S j mod256 6 输出密钥字k S t 步骤 是选取密钥流的每个字 一个字节 2020 4 8 38 伪随机子密钥生成算法PRGA i 0 j 0 while true i i 1 modN j j S i modN swap S i S j t S i S j modN outputk S t 2020 4 8 39 实例 2020 4 8 40 2020 4 8 41 2020 4 8 42 RC4算法的优点是 算法简单 高效 特别适合软件实现 RC4是目前应用最广的商密级序列密码RC4目前使用在 1 目前被用于SSL TLS标准中 2 WEP WiredEquivalentPrivacy 有线对等保密 IEEE802 11 2020 4 8 43 第六次作业 1 3级线性反馈移位寄存器在c3 1时可有4种线性反