序列密碼體制ppt課件(編輯修改稿)
2025-05-26 00:59 本頁面
【文章內(nèi)容簡介】 核心在于密鑰流生成器的設(shè)計，序列密因此，序列密碼的設(shè)計核心在于密鑰流生成器的設(shè)計，序列密碼的安全強度取決于密鑰流生成器生成的密鑰周期、復(fù)雜度、隨機碼的安全強度取決于密鑰流生成器生成的密鑰周期、復(fù)雜度、隨機（偽隨機）特性等。（偽隨機）特性等。Date 16線性反饋移位寄存器 ? 產(chǎn)生密鑰序列的最重要部件是線性反饋移位寄存器 (LFSR),是因為 :(1)LFSR非常適合于硬件實現(xiàn) 。(2)能產(chǎn)生大的周期序列 。(3)能產(chǎn)生較好統(tǒng)計特性的序列 。(4)其結(jié)構(gòu)能應(yīng)用代數(shù)方法進行很好的分析 . 移位寄存器是流密碼產(chǎn)生密鑰流的一個主要組成部分。 GF(2)上一個 n級反饋移位寄存器由 n個二元存儲器與一個反饋函數(shù)f(a1,a2,…,a n)組成，如下頁圖所示。 Date 17 每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)， 每一狀態(tài)對應(yīng)于 GF(2)上的一個 n維向量，共有 2n種可能的狀態(tài)。 每一時刻的狀態(tài)可用 n長序列 “a1,a2,…,a n”n維向量 “(a1,a2,…,a n)”來表示， 其中 ai是第 i級存儲器的內(nèi)容 。 初始狀態(tài)由用戶確定，當?shù)?i個移位時鐘脈沖到來時， 每一級存儲器 ai都將其內(nèi)容向下一級 ai1傳遞，并計算 f(a1,a2,…,a n)作為下一時刻的 an。Date 18 反饋函數(shù) f(a1,a2,…,a n)是 n元布爾函數(shù)， 即 n個變元 a1,a2,…,a n可以獨立地取 0和 1兩個可能的值 ，函數(shù)中的運算有邏輯與、邏輯或、邏輯補等運算，最后的函數(shù)值也為 0或 1。 例：下 圖是一個 3級反饋移位寄存器，其初始狀態(tài)為 (a1,a2,a3)=(1,0,1)， 輸出可由下表求出。 即輸出序列為 101110111011… ，周期為 4。Date 19 如果 f(a1,a2,…,a n)是 (a1,a2,…,a n)的線性函數(shù)，則稱之為線性反饋移位寄存器 LFSR（ linearfeedbackshiftregister）， 否則稱為非線性移位寄存器。 此時 f可寫為：f(a1,a2,…,a n)=a1?1a2?… ?c1an 其中常數(shù) ci=0或 1， ?是模 2加法。 ci=0或 1可用開關(guān)的斷開和閉合來實現(xiàn)， 如下圖所示 ，這樣的線性函數(shù)共有 2n個。Date 20 輸出序列 {at}滿足： an+t=at?1at+1?? … ? ?c1an+t1 其中， t為非負正整數(shù)。 線性反饋移位寄存器因其實現(xiàn)簡單、速度快、有較為成熟的理論等優(yōu)點而成為構(gòu)造密鑰流生成器的最重要的部件之一。例： 下圖是一個 5級線性反饋移位寄存器，其初始狀態(tài)為（a1,a2,a3,a4,a5） =(1,0,0,1,1)， 可求出輸出序列為 1001101001000010101110110001111100110… ，周期為 31。Date 21 在線性反饋移位寄存器中總是假定 c1,c2,…, 中至少有一個不為 0，否則 f(a1,a2,…,a n)≡0， 這樣的話，在 n個脈沖后狀態(tài)必然是 00…0 ，且這個狀態(tài)必將一直持續(xù)下去。 若只有一個系數(shù)不為 0，設(shè)僅有 cj不為 0，實際上是一種延遲裝置。一般對于 n級線性反饋移位寄存器，總是假定 =1。 n級線性反饋移位寄存器的狀態(tài)周期小于等于 2n1。 輸出序列的周期與狀態(tài)周期相等，也小于等于 2n1。 只要選擇合適的反饋函數(shù)便可使序列的周期達到最大值 2n1。 定義 1： n級線性反饋移位寄存器產(chǎn)生的序列 {ai}的周期達到最大值 2n1時，稱 {ai}為 n級 m序列。Date 22 根據(jù)密碼學需要，對于線性移位寄存器需考慮以下問題： （ 1）如何利用級數(shù)盡可能小的線性移位寄存器產(chǎn)生周期長、統(tǒng)計性能好的序列； （ 2）已知一個序列 {ai}， 如何構(gòu)造一個盡可能短的線性移位寄存器來產(chǎn)生它。 因為 n級線性移位寄存器的輸出序列 {ai}滿足遞推關(guān)系：an+k=c1an+k1?c2an+k2?? … ? ?ak， 對任何 k≥1成立。 這種遞推關(guān)系可用一個一元高次多項式 p(x)=1+c1x+… ＋ 1xn1＋ cnxn 表示，稱這個多項式為 LFSR的特征多項式。 由于 ai∈ GF(2)(i =1,2,…, n)， 所以共有 2n組初始狀態(tài)，即有 2n個遞推序列， 其中非恒零的有 2n1個，記 2n1個非零序列的全體為G(p(x))。Date 23 定義 2： 給定序列 {ai}， 冪級數(shù) ，稱為該序列的生成函數(shù)。 定義 3： 設(shè) p(x)是 GF(2)上的多項式，使 p(x)|(xp1)的最小 p稱為p(x)的周期或階。 定理 1： 設(shè) p(x)=1+c1x+… ＋ 1xn1＋ xn是 GF(2)上的多項式，G(p(x))中任一序列 {ai}的生成函數(shù) A(x)滿足： A(x)=Ф(x)/p(x)， 其中=(a1+a2x+…+a nxn1)+c1x(a1+a2x+…+a n－ 1xn2)+c2x(a1+a2x+
教學課件相關(guān)推薦
鄂ICP備17016276號-1