现代密码学第4讲流密码2 ppt课件

第三章 流密码 一、流密码的基本概念 二、线性反馈移位寄存器序列 三 、 B-M综合算法 四 、非线性序列 Date 1 二、 线性反馈移位寄存器序列 * 2 m序列的性质 定理 3-5 以 f(x)为特征多项式的 LFSR的输出序列是 m序列的 充要条件为 f(x)是本原的。 系 n级 LFSR生成的不等价 m序列共有 (2n 1)/n个。 定理 3-6 m序列满足 Golomb的三条伪随机假设 。 Date 3 m序列的性质 m序列否满足密码要求？ n m-C1： n级 m序列的周期为 2n 1， n大，周期指数地 加大，例如 n=166时， p=1050(9.353610465 1049)。 n m-C2： 只要知道 n次本原多项式， m序列极易生成。 n m-C3： m序列极不安全，只要泄露 2n位连续数字， 就可完全确定出反馈多项式系数。 Date 4 m序列的破译 已知 ki, ki+1, ki+2n， 由递推关系式可得出下式 式中有 n个线性方程和 n个未知量，故可惟一解出 ci， 0in-1。 Date 5 三、 B-M综合算法 * 6 根据密码学的需要，对于 LFSR主要考虑下面两问题： (1)如何利用级数尽可能小的 LFSR产生周期长、统计特性 好的序列； (2)已知一个序列 a，如何构造一个尽可能短的 LFSR来产 生 a。 Date 7 B-M综合算法 Date 8 Date 9 B M综合算法的描述 Date 10 Date 11 四、 非线性序列 * 12 非线性序列 n 线性复杂度： 能产生周期序列 kii 0的 LFSR的最小级数 n。 显然 ， n级 m序列的线性复杂度为 n。 n 线性复杂度是研究和设计密码的重要指标和工具 。 n 一个伪随机序列若其线性复杂度低，就易于由部分序列 综合出生成它的 LFSR。 一般移存器序列的线性复杂度 nL2n。 L大不一定就安全；但 L小肯定是不安全的 ! Date 13 非线性前馈序列 n LFSR虽然不能直接作为密钥流用，但可作为驱动源以其 输出推动一个非线性组合函数所决定的电路来产生非线 性序列。这就是所谓非线性前馈序列生成器。 n LFSR用来保证密钥流的周期长度、平衡性等 n 非线性组合函数用来保证密钥流的各种密码性质，以抗 击各种可能的攻击。 Date 14 非线性前馈序列 LFSR F ki 研究的中心问题：前馈函数 F与输出序列的周期性、随机 性、线性复杂度以及相关免疫性之间的关系。 Date 15 多路选择 (Multiplexing)序列 有 n种输入序列 b0(t), , bn-1(t) ， 在地址序 列 a1(t), ,am -1 (t)的控制下决定输出取自某个 输入比特。 例如取 m级 LFSR生成 m序列作地址控制，取 n级 LFSR生成的 m序列作为输入序列。 Date 16 多路选择 (Multiplexing)序列 可供选择的输入 多路选择器 多路选择密码 Date 17 J-K触发器 J-K触发器是一个非线性器件，有两个输入端 j， k和一个内部 状态，即输出为 qi,， 其逻辑真值如表 3-3-2所示。一般令 q-1=0 。 表 3-3-2 J K qi Geffe1973采用三个 LFSR， 其中两个的输 0 0 qi-1 出通过一个 J-K触发器进行复合。如图 3-3- 9 0 1 0 所示。还可进一步推广由 s 1个 LFSR 1 0 1 进行复合。 LFSR-1的时钟必须较其它 s 1 1 个 LFSR的时钟快 log2(s)倍，其中 s为 2的 幂次。 Date 18 Geffe生成器 2中择 1多路选择器 LFSR-2 选择 b(t) LFSR-3 LFSR-1 图 3-3-9 Geffe生成器 多路复合器输入两两成对，并以 J-K触发器进行复合后送 入多路复用器。这类生成器的安全性不高，易受相关攻击 。 Date 19 钟控序列生成器 钟控序列 10多年前提出的一种新的密钥流生 成法，这种方法所生序列的线性复杂度与生成器 输