第三章流密码 流密码的基本概念 二、线性反馈移位寄存器序列 三、B-M综合算法 四、非线性序列 2021/2/21
2021/2/21 1 第三章 流密码 一、流密码的基本概念 二、线性反馈移位寄存器序列 三、B-M综合算法 四、非线性序列
线性反馈移位寄存器序列 2021/2/21
2021/2/21 2 二、 线性反馈移位寄存器序列
m序列的性质 定理35以f(x)为特征多项式的LFSR的输出序列是m序列的 充要条件为风x)是本原的 系n级LFSR生成的不等价m序列共有g(2n-1)/m个。 定理3-6m序列满足 Golomb的三条伪随机假设。 2021/2/21
2021/2/21 3 m序列的性质 定理3-5 以f(x)为特征多项式的LFSR的输出序列是m序列的 充要条件为f(x)是本原的。 系 n级LFSR生成的不等价m序列共有(2 n－1)/n个。 定理 3-6 m序列满足Golomb的三条伪随机假设
m序列的性质 m序列否满足密码要求? mC1:n级m序列的周期为2n-1,n大,周期指数地 加大,例如n=166时,p=1059.353610465×104)。 C2:只要知道n次本原多项式,m序列极易生成 mC3:m序列极不安全,只要泄露2n位连续数字, 就可完全确定出反馈多项式系数。 2021/2/21
2021/2/21 4 m序列的性质 m序列否满足密码要求？ ◼ m-C1：n级m序列的周期为2 n－1，n大，周期指数地 加大，例如n=166时，p=1050(9.353610465×1049)。 ◼ m-C2：只要知道n次本原多项式，m序列极易生成。 ◼ m-C3：m序列极不安全，只要泄露2n位连续数字， 就可完全确定出反馈多项式系数
m序列的破译 已知k,k+1…,k+2n,由递推关系式可得出下式 k. k i+1 k 0 i+1 k l+2 k k I+n i+n+1 k l+n一」 ki k 2 k i+2 式中有n个线性方程和n个未知量,故可惟一解出c;, 0<长n-1。 2021/2/21 5
2021/2/21 5 m序列的破译 已知ki , ki+1 ,…, ki+2n，由递推关系式可得出下式 式中有n个线性方程和n个未知量，故可惟一解出ci， 0in-1。 = + − + + + + − + + − + + + + + − 2 1 1 1 1 0 1 2 1 2 1 1 . . . . . . ...... . . . . . . . . . . . . ...... ...... i n i n i n i n i n i n n i i i n i i i n k k k c c c k k k k k k k k k