《【安全課件】第17講--bm算法》由會(huì)員分享,可在線閱讀,更多相關(guān)《【安全課件】第17講--bm算法(14頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、1移位寄存器序列的三種表示方法:v線性遞推式(一元多項(xiàng)式): at+n=c1at+n-1+c2at+n-2+cnat ,t=0v聯(lián)結(jié)多項(xiàng)式: f(x)=1+c1x+c2x2+cnxnv狀態(tài)轉(zhuǎn)移矩陣: 滿足:st+1=stTf 稱st=(at,at+1,at+2,at+n-1)為n維狀態(tài)2v非退化的移位寄存器v(不)可約多項(xiàng)式v極小多項(xiàng)式v序列和周期v本原多項(xiàng)式vm序列v1游程、游程、0游程游程vm序列的游程分布規(guī)律3線性移存器線性移存器(一)解方程法(一)解方程法 已知序列a是由n級(jí)線性移存器產(chǎn)生的,且知a的連續(xù)2n位,可用解線性方程組的方法得到線性遞推式。 例:設(shè)a=01111000是4級(jí)線
2、性移存器產(chǎn)生的序列的8個(gè)連續(xù)信號(hào),求該移存器的線性遞推式。4v設(shè)其聯(lián)結(jié)多項(xiàng)式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é)多項(xiàng)式為1+x3+x45(二)、(二)、B-MB-M迭代算法迭代算法 根據(jù)密碼學(xué)的需要,對(duì)線性反饋移位寄存器根據(jù)密碼學(xué)的需要,對(duì)線性反饋移位寄存器(LFSR)(LFSR)主要考慮下面兩個(gè)問(wèn)題:主要考慮下面兩個(gè)問(wèn)題:(1)如何利用級(jí)數(shù)盡可能短的LFSR產(chǎn)生周期大、隨機(jī)
3、性能良好的序列,即固定級(jí)數(shù)時(shí),什么樣的移存器序列周期最長(zhǎng)。這是從密鑰生成角度考慮,用最小的代價(jià)這是從密鑰生成角度考慮,用最小的代價(jià)產(chǎn)生盡可能好的產(chǎn)生盡可能好的、參與密碼變換的序列。參與密碼變換的序列。 (2)當(dāng)已知一個(gè)長(zhǎng)為N序列a時(shí),如何構(gòu)造一個(gè)級(jí)數(shù)盡可能小的LFSR來(lái)產(chǎn)生它。這是從密碼分析角度來(lái)考這是從密碼分析角度來(lái)考慮,要想用線性方法重構(gòu)密鑰序列所必須付出的最小代價(jià)。慮,要想用線性方法重構(gòu)密鑰序列所必須付出的最小代價(jià)。這個(gè)問(wèn)題可通過(guò)這個(gè)問(wèn)題可通過(guò)B-MB-M算法來(lái)解決。算法來(lái)解決。61 1、概念簡(jiǎn)介、概念簡(jiǎn)介設(shè) 是 上的長(zhǎng)度為N的序列,而 ),(11. 0Naaaa2F是 上的多項(xiàng)式,c0
4、=1.2Fllxcxcxccxf2210)(lxf),(如果f(x)是一個(gè)能產(chǎn)生a并且級(jí)數(shù)最小的線性移位寄存器的反饋多項(xiàng)式,l是該移存器的級(jí)數(shù),則稱 為序列序列a的的線性綜合解線性綜合解。如果序列中的元素滿足遞推關(guān)系: 則稱 產(chǎn)生二元序列a。其中 表示以f(x)為反饋多項(xiàng)式的l級(jí)線性移位寄存器。)2(1, 1,2211Nllkacacacalklkkklxf),(lxf),(7 幾點(diǎn)說(shuō)明:幾點(diǎn)說(shuō)明: 2、規(guī)定:規(guī)定:0級(jí)線性移位寄存器是以級(jí)線性移位寄存器是以f( (x)=1)=1為反饋多項(xiàng)式的為反饋多項(xiàng)式的線性移位寄存器,且線性移位寄存器,且n長(zhǎng)長(zhǎng)(n=1, 2, , N)全零序列,僅由全零序
5、列,僅由0級(jí)線性級(jí)線性移位寄存器產(chǎn)生。移位寄存器產(chǎn)生。事實(shí)上,以f(x)=1為反饋多項(xiàng)式的遞歸關(guān)系式是:ak=0,k=0, 1, , n-1.因此,這一規(guī)定是合理的。 1、反饋多項(xiàng)式反饋多項(xiàng)式f( (x) )的次數(shù)的次數(shù) l。因?yàn)楫a(chǎn)生因?yàn)楫a(chǎn)生a且級(jí)數(shù)最小的線性且級(jí)數(shù)最小的線性移位寄存器可能是退化的,在這種情況下移位寄存器可能是退化的,在這種情況下 f(x)的次數(shù)的次數(shù)l;并且此并且此時(shí)時(shí) f(x)中的中的cl=0=0,因此在反饋多項(xiàng)式因此在反饋多項(xiàng)式f(x)中中c0=1=1,但不要求但不要求cl=1=1。 3、給定一個(gè)N長(zhǎng)二元序列a,求能產(chǎn)生a并且級(jí)數(shù)最小的線性移位寄存器,就是求a的線性綜合解
6、的線性綜合解。利用利用B-MB-M算法算法可以有效的求出??梢杂行У那蟪?。82、B-M算法要點(diǎn)算法要點(diǎn)用歸納法求出一系列線性移位寄存器:nnlxf),(Nnlxfnn, 2 , 1,)(0每一個(gè) 都是產(chǎn)生序列a的前n項(xiàng)的最短線性移位寄存器,在 的基礎(chǔ)上構(gòu)造相應(yīng)的 ,使得 是產(chǎn)生給定序列前n+1項(xiàng)的最短移存器,則最后得到的 就是產(chǎn)生給定N長(zhǎng)二元序列a的最短的線性移位寄存器。nnlxf),(NNlxf),(11),(nnlxfnnlxf),(11),(nnlxf11),(nnlxf93 3、B-MB-M算法算法 1、取初始值:0, 1)(00lxf 2、設(shè) 均已求得,且)0(Nn nnlxflxf
7、lxf),(,),(,),(1100nlll10nnlxf),(任意給定一個(gè)N長(zhǎng)序列 ,按n歸納定義1, 2, 1, 0Nn),(11. 0Naaaa記: 再計(jì)算:稱dn為第n步差值。然后分兩種情形討論: , 1,)()(0)()(1)(0nlnlnnncxcxccxfnnnnlnnlnnnnnacacacd)(1)(1)(010最后得到的 便是產(chǎn)生序列a的最短線性移位寄存器。NNlxf),(11B - M 算 法 流 程12例2、求產(chǎn)生周期為7的m序列一個(gè)周期:0011101的最短線性移位寄存器。4、實(shí)例實(shí)例解:設(shè) ,首先取初值 f0(x)=1, l0=0 ,則由a0=0得d0=1a0=0從
8、而 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 知 f2(x)=1+x2+1 =1+x3, l3=3 第1步,計(jì)算d3:d3=1a3+ 0a2 + 0a1 + 1a0=1因?yàn)閘2l3,故m=2,由此31 , 3max313 , 3max1)()()(4322334lxxxfxxfxf13 第2步,計(jì)算d4:d4=1a4 + 1a3 + 0a2 + 1a1=0,從而31)()(45345llxxxfxf 第3步,計(jì)算d5:d5=1a5 + 1a4 + 0a3 + 1a2=0,從而 第4步,計(jì)算d6:d6=1a6 + 1a5 + 0a4 + 1a3=0,從而31)()(56356llxxxfxf31)()(67367llxxxfxf這表明, 即為產(chǎn)生所給序列一個(gè)周期的最短線性移位寄存器。 3 ,13xx 14