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

LFSR的結構非常適合硬件實現；LFSR的結構便于使用代數方法進行理論分析；產生的序列的周期可以很大；產生的序列具有良好的統計特性。

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

的線性反饋移位寄存器

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

根據LFSR的狀態轉移圖可以看出，一個n級LFSR序列的周期最大只能為2n-1

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

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

2n-1為素數時，F2上的每一個n次不可約多項式均為n次本原多項式

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

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

Golomb隨機性假設

在每一周期內，0的個數與1的個數近似相等；在每一周期內，長度為i的游程數占游程總數的定義自相關函數為

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

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

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

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

2.２.２基于LFSR的偽隨機序列生成器

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

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

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

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

每生成一個K值，內部狀態中的元素會被重新置換一次，以便下次生成K值

密鑰調度算法用來設置內部狀態的隨機排列

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