現(xiàn)代密碼學(xué)第二章ppt課件-文庫吧資料
2025-05-07 12:16本頁面
【正文】 密鑰長一些，但對非線性布爾函數(shù)的要求低一些。此時原始密鑰最短，但需要精心設(shè)計非線性布爾函數(shù)。 2022/5/29 39 三、非線性組合序列 cn cn 1? c1slsl + 1? sl + n 1‘ + ’gkl2022/5/29 40 三、非線性組合序列 當非線性前饋序列用作密鑰流時，通常只有三個部分可能作為通信伙伴的原始密鑰：初始狀態(tài)，極小多項式，非線性布爾函數(shù)。 則稱比特流 k為非線性前饋序列。 2022/5/29 38 三、非線性組合序列 非線性前饋序列 若比特流 k由如下的方式生成： （ 1） 選擇 n階 m序列 s=s1s2s3… ，其極小多項式為f(x) ，其初始狀態(tài)為 s1s2s3… sn ； （ 2）對每個 l0， kl=g(sl, sl+1, …, sl+n1)。 使得系數(shù)不為 0的項的最高次數(shù)稱為 n維布爾函數(shù)的次數(shù)。 2022/5/29 34 三、非線性組合序列 域 GF(2)上的 n維 函數(shù) （ n維 布爾函數(shù)） n維布爾函數(shù)是這樣的函數(shù) y=g(x1, x2, …, xn)： ? n個自變量 x1, x2, …, xn取值均為 0和 1； ? 因變量 y取值為 0和 1。因此，線性反饋移位寄存器序列不能作為密鑰流。 2022/5/29 32 二、線性反饋移位寄存器序列 線性反饋移位寄存器序列的小結(jié) 線性反饋移位寄存器序列能夠?qū)崿F(xiàn)： ? 小的計算量（ n階線性遞歸生成， 通常 n不大）； ? 極大的最小周期（對于 m序列，最小周期為2n1）； ? 良好的偽隨機性（ 對于 m序列， Golomb隨機性假設(shè)成立） 。 注意到雖然序列的線性復(fù)雜度大于 2n1，用GamesChan算法至多迭代 n步就可求出，因此對此類大的線性復(fù)雜度， GamesChan比 BM算法更加快速。 步驟 4：如果 N=1， B≠0，則輸出 (Lc, f(x))，停止；如果N=1， B=0， s≠0，則令 Lc= Lc+1， f(x)= f(x)(1x)，輸出(Lc, f(x))，停止；如果 N≠1，則轉(zhuǎn)步驟 1。 步驟 2：如果 B≠0，則令 Lc= Lc+ N/2， f(x)= f(x)(1‘+’x)N/2，s=B，轉(zhuǎn)步驟 3；如果 B=0，則令 s=L，轉(zhuǎn)步驟 3。 輸入：周期序列的一個最小周期 sN=s0s1s2… sN1；令 Lc=0；f(x)=1。） 2022/5/29 29 二、線性反饋移位寄存器序列 GamesChan算法 定理 比特流的最小周期為 2的冪時，其線性復(fù)雜度大于其最小周期的一半。如果 N不小于周期序列的線性復(fù)雜度的 2倍， lN就是該周期序列的線性復(fù)雜度， fN(x) 就是該周期序列的極小多項式。 2022/5/29 28 二、線性反饋移位寄存器序列 步驟 3：最后得到了 (fN(x), lN)。 ） 2022/5/29 27 二、線性反饋移位寄存器序列 （ 1）如果 dn=0，則 ? 令 fn+1(x)= fn(x)； ln+1= ln； ? 轉(zhuǎn)步驟 2。如果n=N，則直接轉(zhuǎn)步驟 3；否則計算 ? dn=fn(E)sn ? （此處 E是“時間延遲算子”。 ? 取初始值 ? 對于 j=0~ n01，令 dj=0；對于 j= n0，令 dj=sl； ? 對于 0≤j≤n0，令 fj(x)=1， lj=0 ； ? 再對于 j= n0+1，令 fj(x)=1‘+’dj1xj， lj=j。當 N≥周期序列的線性復(fù)雜度的 2倍時，該 線性遞歸關(guān)系的階數(shù)就是 線性復(fù)雜度，該 線性遞歸關(guān)系就給出了抽頭系數(shù)。 2022/5/29 24 二、線性反饋移位寄存器序列 BM算法 輸入：周期序列的一段長度為 N的比特串sN=s0s1s2… sN1。因此，周期序列的線性復(fù)雜度一定不超過它的最小周期） 所謂序列的綜合，就是尋找周期 序列的線性復(fù)雜度 n，并且求出 極小多項式 f(x)。 2022/5/29 23 二、線性反饋移位寄存器序列 定義 一個周期序列作為一個線性反饋移位寄存器序列，它的最小階數(shù)稱為它的線性復(fù)雜度。 則 lN后， kl=klN。 2022/5/29 22 二、線性反饋移位寄存器序列 線性反饋移位寄存器序列的綜合 定理 如果一個比特流是一個周期序列，則它一定是線性反饋移位寄存器序列。當 Eve不知道階 數(shù) n時，他 還 可以進行測試。 以上事實說明，當 Eve獲得了 n階 線性反饋移位寄存器序列的任意連續(xù) 2n個比特， Eve就獲得了整個密鑰流。 kl=c1kl1 ‘ +’ c2kl2 ‘ +’ … ‘ +’ kln， 其中 l=j+n+1， j+n+2， … ， j+2n。 注意到這是在有限域 GF(2)上的線性方程組，很容易解出抽頭系數(shù) {c c2 、 … 、 }。 則 Eve獲得了關(guān)于 抽頭系數(shù) {c c2 、 … 、 }的以下方程組。 其實不然。而且當 n并不大時，通信伙伴生成 n階 m序列的復(fù)雜度很小，得到的最小周期 2n1卻極大。（長為 n1的 0游程） 2022/5/29 17 二、線性反饋移位寄存器序列 （ ）對任何 1≤j≤2n2 ，下式為 0。（長為 n1的 0游程） 觀察 k的 連續(xù) 2n1個長 n+2的比特串： kl~kl+n+1， l=1~ 2n1。（長為 l2的 1游程） 觀察 k的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1