上海交大密碼學(xué)教學(xué)課件-第二講：序列密碼

時間反復(fù)無常，鼓著翅膀飛逝上海交大密碼學(xué)課件--第二講：序列密碼上海交大密碼學(xué)課件--第二講：序列密碼時間反復(fù)無常，鼓著翅膀飛逝上海交大密碼學(xué)課件--第二講：序列密碼2.1序列密碼流密碼(也稱序列密碼)：將被加密的消息m分成連續(xù)的符號(一般為比特串)，m=m1m2m3……；然后使用密鑰流k=k1k2k3……中的第i個元素ki對ｍ的第i個元素mi執(zhí)行加密變換，i=1,2,3,……；所有的加密輸出連接在一起就構(gòu)成了對m執(zhí)行加密后的密文。第二講序列密碼安全性:流密碼的安全性完全取決于密鑰的安全等級.實(shí)用的流密碼以少量的、一定長度的種子密鑰經(jīng)過邏輯運(yùn)算產(chǎn)生周期較長、可用于加解密運(yùn)算的偽隨機(jī)序列。2.1.2同步流密碼與自同步流密碼同步流密碼:密鑰流的產(chǎn)生與明文消息流相互獨(dú)立密鑰流與明文串無關(guān)，所以同步流密碼中的每個密文ci不依賴于之前的明文mi-1，……，m1。從而，同步流密碼的一個重要優(yōu)點(diǎn)就是無錯誤傳播：在傳輸期間一個密文字符被改變只影響該符號的恢復(fù)，不會對后繼的符號產(chǎn)生影響。自同步流密碼:密鑰流的產(chǎn)生與之前已經(jīng)產(chǎn)生的若干密文有關(guān)，其加密過程形如：２.１.3線性反饋移位寄存器密鑰流的生成方法:有多種產(chǎn)生同步密鑰流生成器的方法，最普遍的是使用一種稱為線性反饋移位寄存器(linearfeedbackshiftregister,LFSR)。

LFSR的結(jié)構(gòu)非常適合硬件實(shí)現(xiàn)；LFSR的結(jié)構(gòu)便于使用代數(shù)方法進(jìn)行理論分析；產(chǎn)生的序列的周期可以很大；產(chǎn)生的序列具有良好的統(tǒng)計特性。

反饋移位寄存器如圖為一個反饋移位寄存器的流程圖，信號從左到右。a_i表示存儲單元，取值為0或1，a_i的個數(shù)n稱為反饋移位寄存器的級。在某一時刻，這些級的內(nèi)容構(gòu)成該反饋移位寄存器的一個狀態(tài)，共有個2^n個可能的狀態(tài)，每一個狀態(tài)對應(yīng)于與F2上的一個n維向量，用(a_1,a_2,…,a_n)表示。函數(shù)f是一個n元布爾函數(shù)，稱之為反饋函數(shù)。反饋移位寄存器線性反饋移位寄存器如果反饋函數(shù)形如:這里的加法運(yùn)算為模2加，乘法運(yùn)算為普通乘法，則稱該反饋函數(shù)是a1,a2,…,an的線性函數(shù)，對應(yīng)的反饋移位寄存器稱為線性反饋移位寄存器，用LFSR表示。否則，稱為非線性反饋移位寄存器(non-linearfeedbackshiftregister,NLFSR)LFSR中反饋函數(shù)的系數(shù)取值的不同，這樣的反饋函數(shù)有2^n種。令表示t時刻第i級寄存器的內(nèi)容，則第t+1時刻寄存器的內(nèi)容為：稱多項式為上述LFSR的聯(lián)接多項式例.如圖所示為一4級線性反饋移位寄存器，狀態(tài)轉(zhuǎn)移關(guān)系為：假設(shè)初始狀態(tài)為(a1,a2,a3,a4)=(0,1,1,0)則可根據(jù)反饋函數(shù)計算出該線性反饋移位寄存器在各時刻的所有狀態(tài)，如表所示在t=15時刻該寄存器的狀態(tài)恢復(fù)至t=0時刻的狀態(tài)，因此之后的狀態(tài)將開始重復(fù)。移位寄存器輸出的序列就是011001000111101011001000111101……，序列的周期為15，也稱該移位寄存器的周期為15(=2＾4-1)。圖2-10狀態(tài)轉(zhuǎn)移圖例2.2如圖所示是一個聯(lián)接多項式為

的線性反饋移位寄存器

反饋函數(shù)為設(shè)初始狀態(tài)為(a1,a2,a3)=(1,1,1),其狀態(tài)轉(zhuǎn)移圖為：從初始狀態(tài)開始，沿著箭頭所指示的路徑依次取出最左邊的分量便得到該LFSR的輸出序列：11101001110100……，周期為7(=23-1)。若以狀態(tài)轉(zhuǎn)移圖中任一狀態(tài)作為初始狀態(tài)，沿箭頭所指示的路徑依次取出最左邊的分量還可得到另外6個序列：11010011101001……；10100111010011……；01001110100111……；10011101001110……；00111010011101……；01110100111010……。全部7個序列取自同一個狀態(tài)轉(zhuǎn)移圖上，將這7個序列之一經(jīng)過適當(dāng)?shù)囊莆豢梢缘玫狡溆嗳我恍蛄?，稱這7個序列是移位等價的。例4.如圖為一個4級LFSR，其聯(lián)接多項式為如取初始狀態(tài)為(a1,a2,a3,a4)=(1,1,1,1)其狀態(tài)轉(zhuǎn)移圖為：輸出序列為1000110001……，周期為5。如取初始狀態(tài)為(a1,a2,a3,a4)=(0,0,0,1)，其狀態(tài)轉(zhuǎn)移圖為：對應(yīng)的輸出序列為0101001010……，周期為5。如取初始狀態(tài)為(a1,a2,a3,a4)=(1,0,1,0)，其狀態(tài)轉(zhuǎn)移圖為：輸出序列為0101001010……，周期為5。以上15個狀態(tài)連同狀態(tài)(0,0,0,0,0)即為4級移位寄存器所有可能的16個狀態(tài)。m序列與最大周期移位寄存器

根據(jù)LFSR的狀態(tài)轉(zhuǎn)移圖可以看出，一個n級LFSR序列的周期最大只能為2n-1

ＧF(2)上n次多項式為聯(lián)接多項式的n級LFSR所產(chǎn)生的非零序列的周期為2n-1，稱這個序列是n級最大周期線性移位寄存器序列，簡稱m序列.如果一個n級LFSR產(chǎn)生了m序列，則該LFSR的狀態(tài)轉(zhuǎn)移圖僅由2個圈構(gòu)成，其中一個是由全零狀態(tài)構(gòu)成的長度為1的圈，另一個是由全部其余2n-1個狀態(tài)構(gòu)成的長度為2n-1的圈。

一個n級LFSR為最長移位寄存器的充要條件是它的聯(lián)接多項式為F2上的n次本原多項式

2n-1為素數(shù)時，F(xiàn)2上的每一個n次不可約多項式均為n次本原多項式

2.1.4偽隨機(jī)序列1.隨機(jī)序列假定拋擲一枚硬幣，倘若出現(xiàn)正面，就記為1，出現(xiàn)反面則記為-1。反復(fù)拋擲硬幣就得到一個二元隨機(jī)變量序列：由于每次試驗的結(jié)果與以前各次試驗不發(fā)生任何關(guān)系，因此這種序列是獨(dú)立試驗的結(jié)果

性質(zhì):1)1出現(xiàn)的次數(shù)與-1出現(xiàn)次數(shù)近乎相等。用概率論的語言來說就是1與-1出現(xiàn)的概率是相等的，都是2)聯(lián)在一起的1的一段，它的兩端都是-1，叫做1的游程,其中1的個數(shù)叫做游程的長度.類似地，能夠定義-1的游程.類似可以定義長度為k的游程

Golomb隨機(jī)性假設(shè)

在每一周期內(nèi)，0的個數(shù)與1的個數(shù)近似相等；在每一周期內(nèi)，長度為i的游程數(shù)占游程總數(shù)的定義自相關(guān)函數(shù)為

這是一個二值函數(shù)：其值c為一個常數(shù)。m序列的偽隨機(jī)性在n級m序列的一個周期段內(nèi)，1出現(xiàn)的次數(shù)恰為2n-1，0出現(xiàn)的次數(shù)恰為2n-1-1；在n級m序列的一個周期段內(nèi)，游程總數(shù)為2n-1；長為k(1≤k≤n-2)的0-游程(或1-游程)數(shù)為2n-2-k；長為n-1的游程只有1個，為0-游程；長為n的游程也只有1個，為1-游程；自相關(guān)函數(shù)是二值的，且為

丁石孫，《線性移位寄存器序列》，上?？萍汲霭嫔?982肖國鎮(zhèn)，梁傳甲，王育民《偽隨機(jī)序列及其應(yīng)用》，國防科技出版社1985年2.２.１線性復(fù)雜度二元序列:線性復(fù)雜度:能夠輸出該序列的最短線性移位寄存器的級數(shù)。例如，給定序列011011……，聯(lián)接多項式為x2+x+1的LFSR可以生成該序列，聯(lián)接多項式為x3+1的LFSR也可以生成該序列。但聯(lián)接多項式為x+1的LFSR則無法做到這一點(diǎn)，所以，該序列的線性復(fù)雜度為2

如果序列的線性復(fù)雜度為，則只要知道序列中任意相繼的位，就可確定整個序列.序列線性復(fù)雜度是流密碼安全性的重要指標(biāo)

安全的密鑰流應(yīng)該滿足這樣三個基本條件：周期充分長；隨機(jī)統(tǒng)計特性好(即基本滿足Golomb的隨機(jī)性公設(shè))；大的線性復(fù)雜度。這里長周期一般指不少于1016，而線性復(fù)雜度為序列長度的一半是比較合適的

2.２.２基于LFSR的偽隨機(jī)序列生成器

如何生成好的偽隨機(jī)序列？在LFSR的基礎(chǔ)上加入非線性化的手段，產(chǎn)生適合于流密碼應(yīng)用的密鑰序列。這也是目前實(shí)現(xiàn)密鑰流生成器的主流方法，可進(jìn)一步將這種方法分為三類：濾波生成器、組合生成器和鐘控生成器。濾波生成器由一個n級線性移位寄存器和一個m(<n)元非線性濾波函數(shù)組成，濾波函數(shù)的輸出為密鑰流序列，工作模式如下圖：g為一個m元布爾函數(shù)組合生成器若干個線性移位寄存器LFSRi(i=1,…,n)和一個非線性組合函數(shù)組成，組合函數(shù)的輸出構(gòu)成密鑰流序列。組合生成器工作模式如下：

其中LFSRi(i=1,…,n)為n個級數(shù)分別為的線性移位寄存器，相應(yīng)的移位寄存器序列為。函數(shù)是n元布爾函數(shù)

鐘控生成器基本思想是：用一個或多個移位寄存器來控制另一個或多個移位寄存器的時鐘，這樣的序列生成器叫做鐘控生成器(clock-controlledgenerator)，也叫停走生成器(stopandgogenerator)，最終的輸出被稱為鐘控序列，基本模型如圖所示。假設(shè)LFSR1和LFSR2分別輸出序列{ak}和{bk}。當(dāng)LFSR1輸出1時，移位時鐘脈沖通過與門使LFSR2進(jìn)行一次移位，從而生成下一位。當(dāng)LFSR1輸出0時，移位時鐘脈沖無法通過與門影響LFSR2，因此LFSR2重復(fù)輸出前一位。例如，假設(shè)LFSR1輸出周期序列1010110101……，LFSR2輸出周期為3的序列a0,a1,a2,a0,a1,a2,……。則上述鐘控生成器輸出的鐘控序列為a0,a0,a1,a1,a2,a0,a0,a1,a1,a2,……，周期為5。交錯停走式生成器(一種鐘控序列)這個生成器使用了3個不同級數(shù)的移位寄存器，如圖所示。當(dāng)LFSR1的輸出是1時，LFSR2被時鐘驅(qū)動；當(dāng)LFSR1的輸出是0時，LFSR3被時鐘驅(qū)動。最后，LFSR1的輸出與LFSR2的輸出做異或運(yùn)算即為這個交錯式停走生成器的輸出，輸出的序列具有長周期和大的線性復(fù)雜度

實(shí)用流密碼2.２.３全球移動通信系統(tǒng)GSM的組成一個GSM語音消息被轉(zhuǎn)換成一系列的幀，每幀具有228比特。每幀用A5算法加密。A5是GSM中執(zhí)行加密運(yùn)算的流密碼算法，它用于從用戶手機(jī)到基站的連接加密。A5中的鐘控機(jī)制是：如果在某一時刻鐘控單元中三個值的某兩個或三個相同，則對應(yīng)的移位寄存器在下一時刻被驅(qū)動，而剩下的一個(或0個)值對應(yīng)的移位寄存器則停走。A5算法的效率很高，輸出的序列統(tǒng)計性好，能夠通過所有的已知測試。但使用的移位寄存器太短，極易受窮盡攻擊。若A5采用級數(shù)較長的移位寄存器則會更安全。RC4RC4(RivestCipher)算法是Rivest在1987年為RSA數(shù)據(jù)安全公司開發(fā)的一種序列密碼，該算法的密鑰長度可變，且面向字節(jié)操作。設(shè)計出來時，RC4一直處于保密狀態(tài)，直到1994年9月有人將其源代碼匿名張貼到Cypherpunks郵件列表中，從而迅速傳遍互聯(lián)網(wǎng)。RC4是全球范圍內(nèi)使用最廣泛的流密碼之一，已被應(yīng)用于MSWindows、LotusNotes、OracleSQL以及使用安全套接字層SSL協(xié)議的Internet通信等方面。RC4參數(shù)ｎ，長為n的秘密內(nèi)部狀態(tài)(２n數(shù)組)，通常取n=8.對應(yīng)的內(nèi)部狀態(tài)由256(=28)個元素構(gòu)成，每個元素都是0~255間的一個數(shù)字輸入是一個可變長度的密鑰,該密鑰用于初始化內(nèi)部狀態(tài)。RC4的輸出是狀態(tài)中按照一定方式選出的某一個元素K，該輸出構(gòu)成密鑰流的一個字節(jié)，加解密時這個字節(jié)K與一個明文/密文字節(jié)執(zhí)行XOR運(yùn)算。

每生成一個K值，內(nèi)部狀態(tài)中的元素會被重新置換一次，以便下次生成K值

密鑰調(diào)度算法用來設(shè)置內(nèi)部狀態(tài)的隨機(jī)排列

開始時，內(nèi)部狀態(tài)被初始化為0～255，即密鑰長度可變，假設(shè)為L個字節(jié)，,一般L在5～32之間。用這L個字節(jié)不斷重復(fù)填充，直至得到。數(shù)組K將被用于對內(nèi)部狀態(tài)S進(jìn)行隨機(jī)化偽隨機(jī)生成算法它從內(nèi)部狀態(tài)中選取一個隨機(jī)元素作為密鑰流中的一個字節(jié)，并修改內(nèi)部狀態(tài)以便下一次選取。選取過程取決于兩個索引值i和j，它們的初始值均為0。具體選取過程如下：參考書１．SignalDesignforgoodcorrelation-forwirelesscommunicationcrytographyandradar,Solo