1、2021-10-1212.1 流密碼的基本概念流密碼的基本概念2.2 線性反饋移位寄存器線性反饋移位寄存器2.3 線性移位寄存器的一元多項式表示線性移位寄存器的一元多項式表示2.4 m序列的偽隨機性序列的偽隨機性2.5 m序列密碼的破譯序列密碼的破譯2.6 非線性序列非線性序列 第2章 流密碼2021-10-1222.1 流密碼的基本概念流密碼的基本思想流密碼的基本思想y=y0y1y2=Ez0(x0)Ez1(x1)Ez2(x2)。密鑰流密鑰流z=z0z1，明文串明文串x=x0 x1x2：2021-10-123E E的選取的選取n二元加法流密碼二元加法流密碼nE可表示為可表示為yi=zi xi。

2、 2021-10-124流加密舉例流加密舉例0110011111110010110101111001110100100001010110011111110010110101111001110100100001010110011111110100100010110101111011010111110100100001100111112021-10-1252.1.3 密鑰流產生器狀態轉移函數狀態轉移函數:ii+1輸出函數輸出函數:izi，目前最為流行和實用的密鑰流產生器是線性反饋移位寄存器。目前最為流行和實用的密鑰流產生器是線性反饋移位寄存器。密鑰流由密鑰流發生器密鑰流由密鑰流發生器f產生：產生：

3、zi=f(k,i)，i是加密器中的記憶元件（是加密器中的記憶元件（存儲器存儲器）在時刻）在時刻i的狀態，的狀態，f是由密鑰是由密鑰k和和i產生的函數。產生的函數。2021-10-1262.2線性反饋移位寄存器線性反饋移位寄存器2021-10-127反饋移位寄存器狀態：狀態：每一時刻的狀態對應于每一時刻的狀態對應于GF(2)上的一個上的一個n維向量維向量(a1,a2,an) ，ai是第是第i級存儲器的內容。共有級存儲器的內容。共有2n種可能的狀態。種可能的狀態。工作原理：工作原理：當第當第i個移位時鐘脈沖到來時，根據寄存器此時的狀態計算個移位時鐘脈沖到來時，根據寄存器此時的狀態計算f(a1,a2

4、,an)，作為作為an+1,每一級存儲器每一級存儲器ai都將其內容向下一級都將其內容向下一級ai-1傳遞，傳遞，（計算、移位、反饋、輸出（計算、移位、反饋、輸出 ）反饋函數反饋函數f(a1,a2,an)：n元布爾函數，即元布爾函數，即n個變元個變元a1,a2,an可以獨立地取可以獨立地取0和和1這兩個可能的值，函數中的運算有邏輯與、這兩個可能的值，函數中的運算有邏輯與、邏輯或、邏輯補等運算。邏輯或、邏輯補等運算。2021-10-128線性反饋移位寄存器線性反饋移位寄存器LFSR線性反饋移位寄存器線性反饋移位寄存器LFSR（linear feedback shift register）:反饋函數

5、反饋函數f(a1,a2,an)是線性函數是線性函數. f(a1,a2,an)=cna1cn-1a2c1an其中常數其中常數ci=0或或1，是模是模2加法。加法。ci=0或或1可用開關的斷開和閉合來實現，可用開關的斷開和閉合來實現，GF(2)上的上的n級線性反饋移位寄存器級線性反饋移位寄存器輸出序列輸出序列an+1線性反饋移位寄存器線性反饋移位寄存器實現簡單、速度快、實現簡單、速度快、理論成熟理論成熟, 是構造密是構造密鑰流生成器的最重要鑰流生成器的最重要的部件。的部件。例下圖是一個例下圖是一個5級線性反饋移位寄存器，其初始狀態為級線性反饋移位寄存器，其初始狀態為（a5，a4，a3， a2， a

6、1 ）=(1,1, 0,0,1)輸出序列為滿足遞推關系輸出序列為滿足遞推關系ak+5=ak+3+ ak1001101001000010101110110001111100110(a5,a4,a3,a2,a1)輸出0 1 0 1 111 1 0 0 110 0 1 0 110 1 1 0 001 0 0 1 001 0 1 1 000 1 0 0 11反饋函數反饋函數f(a1,a2,a3,a4,a5)=a4 + a1周期31LFSR反饋函數反饋函數f(a1,a2,a3,a4,a5)=C2a4+ C5a1 定義定義LFSR特征多項式（連接多項式）特征多項式（連接多項式）P(x)=1+x2x5C5=

7、1C2=12021-10-12112.3線性移位寄存器的特征多項式與序列周線性移位寄存器的特征多項式與序列周期期n級線性移位寄存器的輸出序列滿足級線性移位寄存器的輸出序列滿足遞推關系遞推關系an+k=c1an+k-1 c2an+k-2 cnak 用用一個一元高次多項式表示一個一元高次多項式表示P(x)=1+c1x+cn-1xn-1cnxn稱這個多項式為稱這個多項式為LFSR的的特征多項式特征多項式（連接多連接多項式項式）2021-10-1212序列周期序列周期n序列周期序列周期 使對所有使對所有k，ak+r=ak 成立的的最小整數成立的的最小整數rn多項式的周期多項式的周期使使f(x)除盡除盡

8、xp-1的最小整數的最小整數p的取值。的取值。n序列的周期序列的周期r與特征多項式的周期與特征多項式的周期p密切相關。密切相關。(r/p)n特征特征多項式是多項式是n次既約多項式周期為次既約多項式周期為p ，則生成序列的，則生成序列的周期為周期為p。n輸出序列最大周期為輸出序列最大周期為2n-1。n不可約多項式最大周期達到不可約多項式最大周期達到2n-1。序列為序列為m序列序列的充要條件特征多項式為的充要條件特征多項式為本原多項式。本原多項式。本原多項式本原多項式m序列序列a3a2a1+a3a2a1+a3a2a1+a3a2a1特征多項式特征多項式 x3+x+1多項式多項式周期周期 7輸出序列輸

9、出序列 ak+3=ak+ak+21 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 序列序列周期周期 7x3+x2+1 7ak+3=ak+ak+11 0 1 1 1 0 0 1 0 1 1 7特征多項式特征多項式 x3+x2+x+1多項式多項式周期周期 4輸出序列輸出序列 ak+3=ak+ak+1+ak+21 0 1 0 1 0 1 0 序列周期序列周期 2x3+13ak+3=ak 1 0 1 1 0 1 3初始初始1012021-10-1215m序列的偽隨機性隨機性隨機性:如果密鑰流是周期的，要完全做到隨機性是困難的。如果密鑰流是周期的，要完全做到隨機性是

10、困難的。游程游程:設設ai=(a1a2a3)為為0、1序列，例如序列，例如00110111，其前兩個數字是其前兩個數字是00，稱為，稱為0的的2游程；接著是游程；接著是11，是，是1的的2游游程；再下來是程；再下來是0的的1游程和游程和1的的3游程。游程。自相關函數自相關函數:R()=(1/T)k=1T (-1)ak(-1)ak+, 序列向后平序列向后平移移位，位，0T-1定義中的和式表示序列定義中的和式表示序列ai與與ai+在一在一個周期內對應位相同的位數與對應位不同的位數之差。當個周期內對應位相同的位數與對應位不同的位數之差。當=0時，時，R()=1；當當0時，稱時，稱R()為異相自相關函

11、數。為異相自相關函數。1 0 1 0 0 1 1 1 0 1 0R(1)=R(2)=.=-1/72021-10-1216在序列一個周期內，在序列一個周期內，0與與1出現出現個數相差至多為個數相差至多為1 1; （0和和1出現概率基本相同）出現概率基本相同）長為長為l l的的游程游程占占1/21/2l l，在等長的游程中，在等長的游程中，“0”“0”游游程程和和“1”“1”游程游程個數相等或至多差一個。個數相等或至多差一個。（0 0和和1 1在各位置上出現概率基本相同）在各位置上出現概率基本相同）異相自相關函數是常數異相自相關函數是常數, ,與白噪聲的自相關函數與白噪聲的自相關函數( ( 函數函

12、數) )相近相近（序列平移不能提供更多信息）（序列平移不能提供更多信息）PNPN序列可用于通信中同步序列、碼分多址序列可用于通信中同步序列、碼分多址( (CDMA)CDMA)、導航中多基站碼、雷達測距碼等。導航中多基站碼、雷達測距碼等。PNPN序列雖與序列雖與白噪白噪聲序列相似聲序列相似，但遠還不能滿足密碼體制要求。，但遠還不能滿足密碼體制要求。Golomb隨機性假設隨機性假設PN序列序列m序列滿足序列滿足Golomb的三的三條偽隨機假設條偽隨機假設。 1 0 1 02021-10-1217滿足密碼體制的另外三個條件滿足密碼體制的另外三個條件周期周期p p要足夠大，如大于要足夠大，如大于101

13、05050；序列序列 a ai i 產生易于高速生成；產生易于高速生成；當序列當序列 a ai i 的任何部分暴露時，要分析整個的任何部分暴露時，要分析整個序列，在計算上是不可行的序列，在計算上是不可行的 條件條件決定了密碼的強度，是流密碼理論的核心。它包決定了密碼的強度，是流密碼理論的核心。它包含了流密碼要研究的許多主要問題，如線性復雜度、含了流密碼要研究的許多主要問題，如線性復雜度、相關免疫性、不可預測性等等相關免疫性、不可預測性等等。2021-10-12182.4 m序列的偽隨機性序列的偽隨機性m序列否滿足密碼要求？序列否滿足密碼要求？n級級m序列的周期為序列的周期為2n1，n大，周期指

14、數地加大，大，周期指數地加大，例如例如n=166時，時，p=1050(9.353610465 1049)。只要知道只要知道n次本原多項式，次本原多項式，m序列極易生成。序列極易生成。m序列極不安全，只要泄露序列極不安全，只要泄露連續數字，就可完連續數字，就可完全確定出反饋多項式系數。全確定出反饋多項式系數。定理定理 m序列滿足序列滿足Golomb的三條偽隨機假設的三條偽隨機假設。2021-10-1219122311221112111nnnnnnnnnnnnaaaaaaaaacccaaacccX111122nnnnncccaaaX由于X可逆序列遞推關系序列遞推關系:限制了其在密碼學中的應用限制了

15、其在密碼學中的應用2.5 m序列密碼破譯序列密碼破譯n級級LFSR2021-10-1220122311221112111nnnnnnnnnnnnaaaaaaaaacccaaacccX12nXSSS111122nnnnncccaaaX1122h nh nh nnhac ac ac a 若X可逆序列遞推關系序列遞推關系:令令限制了其在密碼學中的應用限制了其在密碼學中的應用因為因為X是由是由S1,S2,Sn作為列向量，要證作為列向量，要證X可逆，可逆，只要證明這只要證明這n個向量線性無關。個向量線性無關。設設m是使是使S1,S2,Sm線性相關的最小整數，即線性相關的最小整數，即存在不全為存在不全為0

16、的系數的系數l1,l2,lm，其中不妨設其中不妨設l1=1，使得使得213210mmmmSl Sl Sl S11122111mmmmmjmjjSl SlSl SlS證明證明X是可逆的是可逆的設序列設序列ai滿足線性遞推關系：滿足線性遞推關系：12112110 1 000 0 10hhhhnnnh nh naaaaccccaa Sh+1=MSh122111221112211imimimmiimimmmmimiimSlSlSlSMlSMlSMlSlSlSlMSMS密鑰流的級數密鑰流的級數m-1=n 故故m=n+1S1,S2,Sn線性無關，由此構成的線性無關，由此構成的X可逆可逆攻擊實例：攻擊實例：

17、設敵手得到密文串設敵手得到密文串101101011110010和相應的明文和相應的明文串串011001111111001，因此可計算出相應的密鑰流，因此可計算出相應的密鑰流為為110100100001011。進一步假定敵手還知道密鑰。進一步假定敵手還知道密鑰流是使用流是使用5級線性反饋移位寄存器產生的，那么敵手可級線性反饋移位寄存器產生的，那么敵手可用密鑰流的前用密鑰流的前個比特建立如下方程個比特建立如下方程543211 1 0 1 01 0 1 0 00 1 0 0 00 1 0 0 11 0 0 1 00 0 1 0 0ccccc123452345667891054321345674567

18、856789aaaaaaaaaaaaaaacccccaaaaaaaaaaaaaaa11 1 0 1 00 1 0 0 11 0 1 0 01 0 0 1 00 1 0 0 10 0 0 0 11 0 0 1 00 1 0 1 10 0 1 0 01 0 1 1 0已知明文攻擊已知明文攻擊543210 1 0 0 11 0 0 1 00 1 0 0 00 0 0 0 10 1 0 1 11 0 1 1 0ccccc543211 0 0 1 0ccccc33255kkkkkaaacaca2021-10-1225n非線性移位寄存器序列nf(a1,a2,a3)=a1a2+a3n輸出序列10111011

19、.，周期為4.n對線性移位寄存器序列進行非線性組合n非線性移位寄存器研究困難，n對線性移位寄存器研究充分。2.6 非線性序列2021-10-1226密鑰流生成器密鑰流生成器驅動子系統驅動子系統p一個或多個一個或多個LFSR來實現來實現非線性組合子系統非線性組合子系統p用非線性組合函數用非線性組合函數F來實現來實現生成序列評價生成序列評價周期極大化周期極大化線性復雜度線性復雜度p最短最短LFSR級數級數極小特征多項式：最短極小特征多項式：最短LFSR的特征多項式的特征多項式非線性組合2021-10-12272.6.2 J-K觸發器111kkkkkkkkkcabcaabca001110122211

20、012111cacabaacababaaa令令c-1=0驅動序列驅動序列ak和和bk分別為分別為m級和級和n級級m序列序列m、n互素互素a0+b0=1Ck周期周期p = (2m-1)(2n-1) 2021-10-1228例例 令令m=2,n=3，兩個驅動兩個驅動m序列分別為序列分別為ak=0,1,1,0,1,1和和bk=1,0,0,1,0,1,1,輸出序列輸出序列ck111kkkkkkkkkcabcaabca其周期為其周期為(22-1)(23-1)=21。0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,11,0,1kkkkkaccbc如果知道如果知道ck中相

21、鄰位的值中相鄰位的值ck-1和和ck，就可以推就可以推斷出斷出ak和和bk中的一個，通過密碼分析的方法得到中的一個，通過密碼分析的方法得到序列序列ak和和bk。為了克服上述缺點，為了克服上述缺點，Pless提出了由多個提出了由多個J-K觸發觸發器序列驅動的多路復合序列方案器序列驅動的多路復合序列方案2021-10-12292.6.3 Pless生成器2021-10-12302.6.4 鐘控序列生成器鐘控序列最基本的模型是用一個鐘控序列最基本的模型是用一個LFSR控制另外一個控制另外一個LFSR的移位時鐘脈沖的移位時鐘脈沖.易于由硬件實現。易于由硬件實現。當當LFSR1輸出輸出1時，移位時鐘脈沖

22、通過與門使時，移位時鐘脈沖通過與門使LFSR2進行一次移位。進行一次移位。當當LFSR1輸出輸出0時，移位時鐘脈沖無法通過與門影響時，移位時鐘脈沖無法通過與門影響LFSR2,LFSR2狀態不改變。狀態不改變。2021-10-1231前提：前提：LFSR1和和LFSR2輸出序列分別是輸出序列分別是ak和和bk 對應極小特征多項式分別為對應極小特征多項式分別為GF(2)上的上的m和和n次本原多項式次本原多項式f1(x)和和f2(x)，且且m|n結論：序列結論：序列ck周期周期p=(2m-1)(2n-1) 線性復雜度為線性復雜度為n(2m-1) 極小特征多項式為極小特征多項式為212mfx相關結論相

23、關結論例設例設LFSR1為為3級級m序列生成器，其特征多項式為序列生成器，其特征多項式為f1(x)=1+x+x3。設初態為設初態為(1,1,1)，輸出序列為輸出序列為ak=1,1,1,0,1,0,0,。又設又設LFSR2為為3級級m序列生成器，其特征多項式為序列生成器，其特征多項式為f2(x)=1+x2+x3且初態為且初態為(1,1,1)則則bk=1,1,1,0,0,1,0，。LFSR2狀態向量為狀態向量為k，則變化為則變化為:012334445600111234455560112220122333456600ck的周期為的周期為(23-1)2=49ak+3=ak+ak+2bk+3=bk+bk

24、+1ck=1,1,1,0,0,0,0,0, 1,0,1,1,1,1,1, 1,0,0,0,1,1,1, 0,1,1,1,1,1,1, 0,0,1,1,0,0,0,.序號序號狀態狀態輸出輸出011111011120011310003100040100401004010001233444ck=1,1,1,0,0,0,0,0,bk+3bk+1bkckbk=1,1,1,0,0,1,0，。2021-10-1234ck的周期（的周期（23-1）* （23-1）=49極小特征多項式為極小特征多項式為1+x14+x21線性復雜度為線性復雜度為3（23-1）=21線性等價生成器如下圖線性等價生成器如下圖212m

25、fxf2(x)=1+x2+x3周期周期p=(2m-1)(2n-1) 線性復雜度為線性復雜度為n(2m-1)極小特征多項式極小特征多項式2021-10-1235有限狀態自動機有限狀態自動機具有離散輸入和輸出的一種數學模型具有離散輸入和輸出的一種數學模型由由3部分組成：部分組成： 有限狀態集有限狀態集S=si|i=1,2,l。 有限輸入字符集有限輸入字符集A1=A(1)j|j=1,2,m和和有限輸出字符集有限輸出字符集A2=A(2)k|k=1,2,n。 輸出函數輸出函數A(2)k=f1(si,A(1)j)，轉移函數轉移函數sh=f2(si,A(1)j)即在狀態為即在狀態為si，輸入為輸入為A(1)

26、j時，時，輸出為輸出為A(2)k，而狀態轉移為而狀態轉移為sh。2021-10-1236例例S=s1,s2,s3，A1=A(1)1,A(1)2,A(1)3，A2=A(2)1,A(2)2,A(2)3，轉移函數由表轉移函數由表2.1給出。給出。輸入序列為輸入序列為A(1)1A(1)2A(1)1A(1)3A(1)3A(1)1，初始狀態為初始狀態為s1，則得到狀態序列則得到狀態序列s1s2s2s3s2s1s2輸出字符序列輸出字符序列A(2)1A(2)1A(2)2A(2)1A(2)3A(2)12021-10-1237同步流密碼的同步流密碼的密鑰流產生器密鑰流產生器可看成一個可看成一個有限狀態自動機有限狀

27、態自動機。由一個輸出符號集由一個輸出符號集Z、一個狀態集一個狀態集、兩個函數兩個函數和和以及一個初始狀態以及一個初始狀態0組成。組成。2021-10-1238n藍牙是一種用于替代某些電子設備上使用電纜或連線的藍牙是一種用于替代某些電子設備上使用電纜或連線的短距離無線連接技術。短距離無線連接技術。n具有同樣藍牙接口的設備連接可以實現無線連接，有效具有同樣藍牙接口的設備連接可以實現無線連接，有效連接距離達連接距離達10米，一般的傳輸速度都有米，一般的傳輸速度都有1Mn目前配置藍牙接口的電子設備卻不是很多；沒有藍牙接目前配置藍牙接口的電子設備卻不是很多；沒有藍牙接口的電腦可通過加裝藍牙適配器來實現無線連接，適配口的電腦可通過加裝藍牙適配器來實現無線連接，適配器一般都是器一般都是USB接口，可以插在電腦上，使用方便。接口，可以插在電腦上，使用方便。n采用無線電波為載體，安全性差，信息傳輸需加密采用無線電波為載體，安全性差，信息傳輸需加密n加密算法使用流密碼加密算法使用流密碼.流密碼的應用流密碼的應用藍牙藍牙Bluetooth2021-10-1239藍牙流加密原理藍牙流加密原理2021-10-12404個個LFSR比