计算机安全与必威体育官网网址14_图文.ppt

第六章重点 6.1 线性同余产生器 线性同余产生器：伪随机序列产生器 Xn = (aXn-1+b) mod m Xn为序列中第n个数，Xn-1为序列中第n-1个数 变量a，b和m为常数 X0为密钥或种子 最大周期：m-1 不能用于密码学 6.2 线性反馈移位寄存器 移位寄存器：一个二进制位序列。需要1位时，所有位都向右移动一位，空出的最左边一位由寄存器中其他位的一个函数来计算。 移位寄存器的输出为1位，通常是最低位。 周期为输出序列开始重复之前的长度。 线性反馈移位寄存器：由一个移位寄存器和一个反馈函数组成。 线性反馈移位寄存器（LFSR）：反馈函数为寄存器中特定位的异或。Linear feedback shift register 这些位的列表称为一个选择序列。 具有特定选择序列的LFSR会遍历所有的2n-1个内部状态，为最大周期的LFSR。 bn bn-1 … b4 b3 b2 b1 反 馈 函 数 反馈移位寄存器 bn bn-1 … b4 b3 b2 b1 线性反馈移位寄存器 输出位 b4 b3 b2 b1 4位的LFSR 输出位 用1111对4位的LFSR初始化 重复之前的内部状态：1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110 输出序列：1111010110010001… m序列：最大周期的LFSR产生的输出序列。 最大周期的LFSR的选择序列构成的多项式加上常数1为模2的本原多项式，多项式的阶为移位寄存器的长度。 n阶本原多项式：一个不可约多项式，能整除x2n-1+1，但对任意整数d，满足d整除2n-1，多项式不能整除xd+1。 用本原多项式x32+x7+x5+x3+x2+x+1构造最大周期的LFSR： b32 … b7 b6 b5 b4 b3 b2 b1 32位的最长周期的LFSR 输出位 6.3 进位反馈移位寄存器 进位反馈移位寄存器（FCSR）：包括一个移位寄存器，一个反馈函数和一个进位寄存器。 进位寄存器：将选择序列的各位相加，并加上进位寄存器的内容，结果模2成为新位，结果除以2成为进位寄存器的新内容。 bn bn-1 … b4 b3 b2 b1 和 进位反馈移位寄存器 和除以2 和模2 输出位 例：3位FCSR 移位寄存器的初值为001，进位寄存器的初值为0。 如下图所示： b3 b2 b1 和 和除以2 和模2 输出位 3位FCSR 移位寄存器 001 100 010 101 110 111 011 101 010 001 000 100 进位寄存器 0 0 0 0 0 0 1 1 1 1 1 0 周期为10 最大周期：q-1 q为连接整数，定义为：q = 2q1+22q2+23q3+…+2nqn-1, qi对应于各选择位，从左向右，q只能是素数，2为其原根 q=2*0+22*1+23*1-1=4+8-1=11 周期为：10 练习 2. 3位FCSR，求输出状态，周期，输出序列 移位寄存器的初值为101，进位寄存器的初值为1。 如下图所示： b3 b2 b1 和 和除以2 和模2 输出位 3位FCSR 答案：