密码学PPT电子课件教案-第二章 序列密码.ppt

2020 4 20 1 第二章序列密码 一 序列密码的基本概念二 线性反馈移位寄存器三 b m综合算法四 非线性序列 一 序列密码的基本概念 2020 4 20 3 序列密码的分类 同步序列密码ssc synchronousstreamcipher i与明文消息无关 密钥流将独立于明文 特点 对于明文而言 这类加密变换是无记忆的 但它是时变的 只有保持两端精确同步才能正常工作 对主动攻击时异常敏感而有利于检测无差错传播 errorpropagation 2020 4 20 4 序列密码的分类 自同步序列密码sssc self synchronousstreamcipher i依赖于 ki i 1 mi 使密文ci不仅与当前输入mi有关 而且由于ki对 i的关系而与以前的输入m1 m2 mi 1有关 一般在有限的n级存储下将与mi 1 mi n有关 优点 具有自同步能力 强化了其抗统计分析的能力缺点 有n位长的差错传播 2020 4 20 5 序列密码的分类 n级移存器n级移存器 kiffkikikimieki cicidki mi 2020 4 20 6 序列的伪随机性 周期序列 ki i 0 使对所有i ki p ki成立的的最小整数p长为l的串 run kt kt 1 kt l 1 序列 ki 的一个周期中 kt 1 kt kt 1 kt l 1 kt l例 长为l的1串和长为l的0串 2020 4 20 7 序列的伪随机性 周期自相关函数周期为p的序列 ki i 0 其周期自相关函数r j a d p j 0 1 式中 a 0 i p ki ki j d 0 i p ki ki j 同相自相关函数当j为p的倍数 即p j时为 r j 1 异相自相关函数当j不是p的倍数时 2020 4 20 8 例2 2 二元序列111001011100101110010 周期p 7同相自相关函数r j 1异相自相关函数r j 1 7 2020 4 20 9 golomb随机性假设 pn序列 g1 若p为偶 则0 1出现个数相等 皆为p 2 若p为奇 则0出现个数为 p 1 2 g2 长为l的串占1 2l 且 0 串和 1 串个数相等或至多差一个 g3 r j 为双值 即所有异相自相关函数值相等 这与白噪声的自相关函数 函数 相近 这种序列又称为双值序列 twovaluesequence pn序列可用于通信中同步序列 码分多址 cdma 导航中多基站码 雷达测距码等 但仅满足g1 g3特性的序列虽与白噪声序列相似 但远还不能满足密码体制要求 2020 4 20 10 满足密码体制的另外三个条件 c1 周期p要足够大 如大于1050 c2 序列 ki i 0产生易于高速生成 c3 当序列 ki i 0的任何部分暴露时 要分析整个序列 提取产生它的电路结构信息 在计算上是不可行的 称此为不可预测性 unpredictability c3决定了密码的强度 是序列密码理论的核心 它包含了序列密码要研究的许多主要问题 如线性复杂度 相关免疫性 不可预测性等等 二 线性反馈移位寄存器序列 2020 4 20 12 线性反馈移位寄存器序列概念 级数 stages 存储单元数 状态 state n个存储单元的存数 ki ki n 1 反馈函数 f ki ki 1 ki n 1 是状态 ki ki n 1 的函数 线性反馈移位寄存器 lfsr f为线性函数非线性反馈移位寄存器 f为非线性函数 2020 4 20 13 反馈移位寄存器 x1 x2 xnf ki ki 1 ki n 1 ki nki n 1ki n 2ki 1kiki 1 k1k0 xnxn 1x2x1 2020 4 20 14 线性反馈移位寄存器 f x 为线性函数 输出序列满足下式cn cn 1 cn 2 c1 c0ki n 1ki n 2ki 1kiki 1 k1 k0 xnxn 1x2x1 2020 4 20 15 二元线性移位寄存器 二元条件下ki 0 1 cj 0 1 即断开或连通 为模2加 反馈函数可写成n阶线性递推关系式cncn 1cn 2c1c0ki n 1ki n 2ki 1kiki 1 k1 xnxn 1x2x1 2020 4 20 16 线性反馈移位寄存器 例n 4的lfsr 输出序列满足ki 4 ki 3 ki 0 初始状态为1000 序列的周期为15 24 1 c4c3c2c1c0ki0001线性移存器序列的最长周期为2n 1 2020 4 20 17 状态转移和相应输出 时刻状态输出32100000011110000201000300100410011511000601100710111801011910100101101111111001211111130111114001111500011 2020 4 20 18 m序列 为2n 1的lfsr序列称为m序列 m序列是一类pn序列 n级m序列 ki i 0循环地遍历所有2n 1个非零状态 且任一非零输出皆为 ki i 0的移位 或为其循环等价 cyclicallyequivalent 序列 初始状态不同2n 1个的m序列共有2n 1个 他们的全体记为 f 他们只是状态前后次序之别 2020 4 20 19 特征多项式 以lfsr的反馈系数所决定的多项式又称反馈多项式 式中 c0 cn 1反多项式称作是lfsr的联接多项式 cn 0称之为非奇异lfsr 2020 4 20 20 特征多项式 定义 给定序列 ki i 0 幂级数称为该序列的生成函数定理3 1令 ki i 0 f f x 是反馈多项式 令k x 是 ki i 0的生成函数 则其中 2020 4 20 21 特征多项式 证 a x 就是移存器初始值所对应的多项式 2020 4 20 22 特征多项式 系 证 f 的每个元素均可由a x f x 惟一决定 式中 deg a x n 另一方面 f 有2n个元素 而deg a x n的多项式也恰有2n个 2020 4 20 23 多项式的周期 多项式f x 的周期p为使f x 除尽xn 1的最小整数n的取值 序列的周期与生成序列特征多项式的周期密切相关 引理3 2 令f x 为n次式 周期为p 令 ki i 0 f 则 ki i 0的周期p p 2020 4 20 24 多项式的周期 引理3 3令f x 是周期为p的n次既约多项式 令 ki i 0 f 则 ki i 0的周期为p 证 令 ki i 0周期为p 由引理3 2 3 有p p 则有 deg u x p 由 3 2 12 式有k x a x f x 故有 由此可得因为f x 为n次既约式 deg a x n 因此有f x 1 xp 但f x 的周期为p 故有p p 所以p p 2020 4 20 25 多项式的周期 引理3 4令f x 为n次式 令 ki i 0 f 为m序列 则f x 为既约的 证 采用反证法 假定f x f1 x f2 x f1 x 为既约式 次数为n1 n2 0 n1 n2 由 3 2 14 式 1 f1 x f1 故由引理3 2 3及附录3a 1 f1 x 的周期除尽 类似地有 由定理3 2 1知1 f1 x 应是 ki i 0的移位 因而其周期为2n 1 惟一可能是n n1 即f x f1 x 2020 4 20 26 m序列的性质 定理3 5以f x 为特征多项式的lfsr的输出序列是m序列的充要条件为f x 是本原的 系n级lfsr生成的不等价m序列共有 2n 1 n个 定理3 6m序列满足golomb的三条伪随机假设 2020 4 20 27 m序列的性质 m序列否满足密码要求 m c1 n级m序列的周期为2n 1 n大 周期指数地加大 例如n 166时 p 1050 9 353610465 1049 m c2 只要知道n次本原多项式 m序列极易生成 m c3 m序列极不安全 只要泄露2n位连续数字 就可完全确定出反馈多项式系数 2020 4 20 28 m序列的破译 已知ki ki 1 ki 2n 由递推关系式可得出下式式中有n个线性方程和n个未知量 故可惟一解出ci 0 i n 1 三 b m综合算法 2020 4 20 30 根据密码学的需要 对于lfsr主要考虑下面两问题 1 如何利用级数尽可能小的lfsr产生周期长 统计特性好的序列 2 已知一个序列a 如何构造一个尽可能短的lfsr来产生a 2020 4 20 31 b m综合算法 2020 4 20 32 2020 4 20 33 b m综合算法的描述 2020 4 20 34 四 非线性序列 2020 4 20 36 非线性序列 线性复杂度 能产生周期序列 ki i 0的lfsr的最小级数n 显然 n级m序列的线性复杂度为n 线性复杂度是研究和设计密码的重要指标和工具 一个伪随机序列若其线性复杂度低 就易于由部分序列综合出生成它的lfsr 一般移存器序列的线性复杂度n l 2n l大不一定就安全 但l小肯定是不安全的 2020 4 20 37 非线性前馈序列 lfsr虽然不能直接作为密钥流用 但可作为驱动源以其输出推动一个非线性组合函数所决定的电路来产生非线性序列 这就是所谓非线性前馈序列生成器 lfsr用来保证密钥流的周期长度 平衡性等非线性组合函数用来保证密钥流的各种密码性质 以抗击各种可能的攻击 2020 4 20 38 非线性前馈序列 lfsr fki研究的中心问题 前馈函数f与输出序列的周期性 随机性 线性复杂度以及相关免疫性之间的关系 2020 4 20 39 多路选择 multiplexing 序列 有n种输入序列b0 t bn 1 t 在地址序列a1 t am 1 t 的控制下决定输出取自某个输入比特 例如取m级lfsr生成m序列作地址控制 取n级lfsr生成的m序列作为输入序列 2020 4 20 40 多路选择 multiplexing 序列 可供选择的输入 多路选择器多路选择密码 2020 4 20 41 j k触发器 j k触发器是一个非线性器件 有两个输入端j k和一个内部状态 即输出为qi 其逻辑真值如表3 3 2所示 一般令q 1 0 表3 3 2jkqigeffe 1973 采用三个lfsr 其中两个的输00qi 1出通过一个j k触发器进行复合 如图3 3 9010所示 还可进一步推广由s 1个lfsr101进行复合 lfsr 1的时钟必须较其它s11个lfsr的时钟快log2 s 倍 其中s为2的幂次 2020 4 20 42 geffe生成器 2中择1多路