現(xiàn)在密碼學(xué)講BM算法

B-M算法1整理ppt線性移存器〔一〕解方程法序列a是由n級(jí)線性移存器產(chǎn)生的，且知a的連續(xù)2n位，可用解線性方程組的方法得到線性遞推式。

例：設(shè)a=01111000是4級(jí)線性移存器產(chǎn)生的序列的8個(gè)連續(xù)信號(hào)，求該移存器的線性遞推式。2整理ppt解：產(chǎn)生a=01111000……的聯(lián)系

多項(xiàng)式設(shè)其聯(lián)結(jié)多項(xiàng)式f(x)=1+c1x+c2x2+c3x3+x4線性遞推式at=at-4+c3at-3+c2at-2+c1at-10+c3+c2+c1=11+c3+c2+c1=01+c3+c2+0=01+c3+0+0=0解得：c3=1；c2=0；c1=0故其聯(lián)結(jié)多項(xiàng)式為1+x3+x43整理ppt〔二〕、B-M迭代算法根據(jù)密碼學(xué)的需要，對(duì)線性反響移位存放器(LFSR)主要考慮下面兩個(gè)問題：〔1〕如何利用級(jí)數(shù)盡可能短的LFSR產(chǎn)生周期大、隨機(jī)性能良好的序列，即固定級(jí)數(shù)時(shí)，什么樣的移存器序列周期最長。這是從密鑰生成角度考慮，用最小的代價(jià)產(chǎn)生盡可能好的、參與密碼變換的序列?！?〕當(dāng)一個(gè)長為N序列a時(shí)，如何構(gòu)造一個(gè)級(jí)數(shù)盡可能小的LFSR來產(chǎn)生它。這是從密碼分析角度來考慮，要想用線性方法重構(gòu)密鑰序列所必須付出的最小代價(jià)。這個(gè)問題可通過B-M算法來解決。4整理ppt1、概念簡(jiǎn)介設(shè)是上的長度為N的序列，而是上的多項(xiàng)式，c0=1.如果f(x)是一個(gè)能產(chǎn)生a并且級(jí)數(shù)最小的線性移位寄存器的聯(lián)系多項(xiàng)式，l是該移存器的級(jí)數(shù)，則稱為序列a的線性綜合解。如果序列中的元素滿足遞推關(guān)系：

則稱產(chǎn)生二元序列a。其中表示以f(x)為聯(lián)系多項(xiàng)式的l級(jí)線性移位寄存器。5整理ppt線性移位存放器的綜合問題可表述為：給定一個(gè)N長二元序列a，如何求出產(chǎn)生這一序列的最小級(jí)數(shù)的線性移位存放器，即最短的線性移存器？幾點(diǎn)說明：2、規(guī)定：0級(jí)線性移位存放器是以f(x)=1為聯(lián)系多項(xiàng)式的線性移位存放器，且n長(n=1,2,…,N)全零序列，僅由0級(jí)線性移位存放器產(chǎn)生。事實(shí)上，以f(x)=1為聯(lián)系多項(xiàng)式的遞歸關(guān)系式是：ak=0，k=0,1,…,n-1.因此，這一規(guī)定是合理的。1、聯(lián)系多項(xiàng)式f(x)的次數(shù)l。因?yàn)楫a(chǎn)生a且級(jí)數(shù)最小的線性移位存放器可能是退化的，在這種情況下f(x)的次數(shù)<l；并且此時(shí)f(x)中的cl=0，因此在聯(lián)系多項(xiàng)式f(x)中c0=1，但不要求cl=1。3、給定一個(gè)N長二元序列a，求能產(chǎn)生a并且級(jí)數(shù)最小的線性移位存放器，就是求a的線性綜合解。利用B-M算法可以有效的求出。6整理ppt2、B-M算法要點(diǎn)用歸納法求出一系列線性移位寄存器：每一個(gè)都是產(chǎn)生序列a的前n項(xiàng)的最短線性移位存放器，在的根底上構(gòu)造相應(yīng)的，使得是產(chǎn)生給定序列前n+1項(xiàng)的最短移存器，那么最后得到的就是產(chǎn)生給定N長二元序列a的最短的線性移位存放器。7整理ppt3、B-M算法1、取初始值：

2、設(shè)均已求得，且任意給定一個(gè)N長序列，按n歸納定義記：再計(jì)算：稱dn為第n步差值。然后分兩種情形討論：8整理ppt最后得到的便是產(chǎn)生序列a的最短線性移位寄存器。9整理pptB-M算法流程10整理ppt例2、求產(chǎn)生周期為7的m序列一個(gè)周期：0011101的最短線性移位存放器。4、實(shí)例解：設(shè)，首先取初值f0(x)=1,l0=0，則由a0=0得d0=1?a0=0從而f1(x)=1,l1=0；同理由a1=0得d1=1?a1=0從而f2(x)=1,l2=0。由a2=1得d2=1?a2=1，從而根據(jù)l0=l1=l2=0知

f3(x)=1+x2+1=1+x3,l3=3

第1步，計(jì)算d3：d3=1·a3+0·a2

+0·a1+

1·a0=1因?yàn)閘2<l3，故m=2，由此11整理ppt

第2步，計(jì)算d4：d4=1·a4+1·a3

+0·a2+

1·a1=0，從而

第3步，計(jì)算d5：d5=1·a5+1·a4

+0·a3+

1·a2=0，從而