西安电子科技大学：《现代密码学》课程教学资源（PPT课件讲稿）第三章 流密码（线性反馈移位寄存器序列、B-M综合算法、非线性序列）

第三章流密码 流密码的基本概念 二、线性反馈移位寄存器序列 三、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， 0in-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

三、BM综合算法 2021/2/21

2021/2/21 6 三、B-M综合算法

根据密码学的需要,对于LFSR主要考虑下面两问题: (1)如何利用级数尽可能小的LFSR产生周期长、统计特性 好的序列; (2)已知一个序列a,如何构造一个尽可能短的LFSR来产 生a 2021/2/21

2021/2/21 7 根据密码学的需要，对于LFSR主要考虑下面两问题： (1)如何利用级数尽可能小的LFSR产生周期长、统计特性 好的序列； (2)已知一个序列a，如何构造一个尽可能短的LFSR来产 生a

B-M综合算法 设a=an1…a:是一个有限序列,f(x)=1+x+…+x是一个多项式。用 ((x,4表示以f(x)为反馈多项式的级线性反馈移位寄存器。如果a“满足线性递归关 系式 k≥ 则称()产生a 2021/2/21

2021/2/21 8 B-M综合算法

线性反馈移位寄存器综合问题,即是对于一个给定N长的序列,求产生它的最短线性 反馈移位寄存器。 Berlekamp-Massey算法简称BM算法有效地解决了这个问题,从而使 序列的复杂度指生产该序列的最短LFSR的趿数)成为同步流密码的一个重要度量指标。该 算法是一个多项式时间的送代算法,以M长二元列2=a14…“为输入,输出产生 该序列的最短LⅠSR的联结多项式x)及该LSR6的长度1的二元组()4x) 我们约定,0级IFR是以f(x)=1为联结多项式的LFSR,并且n长(n=12…,M 零序5:00.0且仅由0级IFR产生。事实上,以(x)=1为联结多项式的递推关系 式是a1=0,=01…,n-1.因此这一约定是合理的 2021/2/21

2021/2/21 9

输入:N;a0,1,42,…aN1 步骤1:n←0,〈(x),)←(1,0) 步骤2:计算an=/n(D)an,其中D为延迟算子。 (1)当dn=0时,(m(x)n+)←《/(x),n),转步骤3 了综合算法的描述 (2)当dn=1,且l=l1 =0时 m+(x),)←①+x”,n+1),转步骤 (3)当dn=1,且lm<lm+1=lm+2=…=l2(n<n)时, fm+(x),m)((x)+x2mm(x),max{,n+1-ln),转步骤3 步骤3:若n<N-1,n←n+1,转步骤2 输出:(/N(x),lx) 2021/2/21

2021/2/21 10 B －M 综合算法的描述