現(xiàn)在密碼學第14講BM算法

1、2線性移存器線性移存器（一）解方程法（一）解方程法 已知序列a是由n級線性移存器產(chǎn)生的，且知a的連續(xù)2n位，可用解線性方程組的方法得到線性遞推式。 例：設a=01111000是4級線性移存器產(chǎn)生的序列的8個連續(xù)信號，求該移存器的線性遞推式。3v設其聯(lián)結(jié)多項式f(x)=1+c1x+c2x2+c3x3+x4v線性遞推式at=at-4+c3at-3+c2at-2+c1at-1v0+c3+c2+c1=1v1+c3+c2+c1=0v1+c3+c2+0=0v1+c3+0+0=0v解得：c3=1；c2=0；c1=0v故其聯(lián)結(jié)多項式為1+x3+x44（二）、（二）、B-MB-M迭代算法迭代算法 根據(jù)密碼學的需

2、要，對線性反饋移位寄存器根據(jù)密碼學的需要，對線性反饋移位寄存器(LFSR)(LFSR)主要考慮下面兩個問題：主要考慮下面兩個問題：（1）如何利用級數(shù)盡可能短的LFSR產(chǎn)生周期大、隨機性能良好的序列，即固定級數(shù)時，什么樣的移存器序列周期最長。這是從密鑰生成角度考慮，用最小的代價這是從密鑰生成角度考慮，用最小的代價產(chǎn)生盡可能好的產(chǎn)生盡可能好的、參與密碼變換的序列。參與密碼變換的序列。 （2）當已知一個長為N序列a時，如何構(gòu)造一個級數(shù)盡可能小的LFSR來產(chǎn)生它。這是從密碼分析角度來考這是從密碼分析角度來考慮，要想用線性方法重構(gòu)密鑰序列所必須付出的最小代價。慮，要想用線性方法重構(gòu)密鑰序列所必須付出的最

3、小代價。這個問題可通過這個問題可通過B-MB-M算法來解決。算法來解決。51 1、概念簡介、概念簡介設 是 上的長度為N的序列，而 ),.,(11.0Naaaa)2(GF是 上的多項式，c0=1.llxcxcxccxf.)(2210lxf),(如果f(x)是一個能產(chǎn)生a并且級數(shù)最小的線性移位寄存器的聯(lián)系多項式，l是該移存器的級數(shù)，則稱 為序列序列a的的線性綜合解線性綜合解。如果序列中的元素滿足遞推關系： 則稱 產(chǎn)生二元序列a。其中 表示以f(x)為聯(lián)系多項式的l級線性移位寄存器。)2(1., 1,.2211Nllkacacacalklkkklxf),(lxf),()2(GF6 幾點說明：幾點說

4、明： 2、規(guī)定：規(guī)定：0級線性移位寄存器是以級線性移位寄存器是以f( (x)=1)=1為聯(lián)系多項式的為聯(lián)系多項式的線性移位寄存器，且線性移位寄存器，且n長長(n=1, 2, , N)全零序列，僅由全零序列，僅由0級線性級線性移位寄存器產(chǎn)生。移位寄存器產(chǎn)生。事實上，以f(x)=1為聯(lián)系多項式的遞歸關系式是：ak=0，k=0, 1, , n-1.因此，這一規(guī)定是合理的。 1、聯(lián)系多項式聯(lián)系多項式f( (x) )的次數(shù)的次數(shù) l。因為產(chǎn)生因為產(chǎn)生a且級數(shù)最小的線性且級數(shù)最小的線性移位寄存器可能是退化的，在這種情況下移位寄存器可能是退化的，在這種情況下 f(x)的次數(shù)的次數(shù)l；并且此；并且此時時 f(

5、x)中的中的cl=0=0，因此在聯(lián)系多項式，因此在聯(lián)系多項式f(x)中中c0=1=1，但不要求，但不要求cl=1=1。 3、給定一個N長二元序列a，求能產(chǎn)生a并且級數(shù)最小的線性移位寄存器，就是求a的線性綜合解的線性綜合解。利用利用B-MB-M算法算法可以有效的求出?？梢杂行У那蟪觥?2、B-M算法要點算法要點用歸納法求出一系列線性移位寄存器：nnlxf),(Nnlxfnn,.,2 , 1,)(0每一個 都是產(chǎn)生序列a的前n項的最短線性移位寄存器，在 的基礎上構(gòu)造相應的 ，使得 是產(chǎn)生給定序列前n+1項的最短移存器，則最后得到的 就是產(chǎn)生給定N長二元序列a的最短的線性移位寄存器。nnlxf),(

6、NNlxf),(nnlxf),(11),(nnlxf11),(nnlxf83 3、B-MB-M算法算法 1、取初始值：0, 1)(00lxf 2、設 均已求得，且)0(Nn nnlxflxflxf),(,.,),(,),(1100nlll.10nnlxf),(任意給定一個N長序列 ，按n歸納定義1, 2, 1, 0Nn),.,(11.0Naaaa記： 再計算：稱dn為第n步差值。然后分兩種情形討論： , 1,.)()(0)()(1)(0nlnlnnncxcxccxfnnnnlnnlnnnnnacacacd)(1)(1)(0.9最后得到的 便是產(chǎn)生序列a的最短線性移位寄存器。NNlxf),(10

7、B - M算法流程11例2、求產(chǎn)生周期為7的m序列一個周期：0011101的最短線性移位寄存器。4、實例實例解：設 ，首先取初值 f0(x)=1, l0=0 ，則由a0=0得d0=1a0=0從而 f1(x)=1, l1=0 ；同理由a1=0得d1=1a1=0從而 f2(x)=1, l2=0 。00111016543210aaaaaaa由a2=1得d2=1a2 =1，從而根據(jù)l0= l1 = l2=0 知 f3(x)=1+x2+1 =1+x3, l3=3 第1步，計算d3：d3=1a3+ 0a2 + 0a1 + 1a0=1因為l2l3，故m=2，由此31 , 3max313 , 3max1)()()(4322334lxxxfxxfxf12 第2步，計算d4：d4=1a4 + 1a3 + 0a2 + 1a1=0，從而31)()(45345llxxxfxf 第3步，計算d5：d5=1a5 + 1a4 + 0a3 + 1a2=0