【文章內容簡介】 x6=4289914828771740133546190658266515171326 x7=4431066711454378260890386385593817521668 x8=7336876124195046397414235333675005372436 第 2章 信息保密技術 取上述任意一個比特串，當 x的值為奇數時， b的值取 1，當 x的值為偶數時， b的值取 0，故產生的隨機序列 b1， b2， ? ，b8=0， 1， 1， 1， 0， 0， 0， 0 可見，產生密鑰流序列的方法很多，常見的方法有線性同余法、線性反饋移位寄存器、非線性反饋移位寄存器、有 2. 通常，產生密鑰流序列的硬件是反饋移位寄存器。一個反饋移位寄存器由兩部分組成 : 移位寄存器和反饋函數 (如圖242所示 ) 第 2章 信息保密技術 圖 242 反饋移位寄存器 第 2章 信息保密技術 移位寄存器由 n個寄存器組成，每個寄存器只能存儲一個位，在一個控制時鐘周期內，根據寄存器當前的狀態(tài)計算反饋函數 f(a1， a2， ? ， an)作為下一時鐘周期的內容，每次輸出最右端一位 a1，同時，寄存器中所有位都右移一位，最左端的位由反饋函數計算得到。 用 ai(t)表示 t時刻第 i個寄存器的內容，用 ai(t+1)表示 ai(t)下 移位 : ai(t+1)=ai+1(t) (i=1， 2， ? ， n1) 反饋 : an(t+1)=f(a1(t)， a2(t)， ? ， an(t)) 第 2章 信息保密技術 如果反饋函數 f(a1， a2， ? ， an)=k1an k2an1 ? kna1，其中 ki∈ {0， 1}，則該反饋函數是 a1， a2， ? ， an的線性函數，對應的反饋移位寄存器稱為線性反饋移位寄存器 (Linear Feedback Shift Register， LFSR) ai(t+1)=ai+1 (t) (i=1， 2， 3， 4) a4(t+1)=a1(t) a3(t) 對應 (k1， k2， k3， k4)=(0， 1， 0， 1)，設初始狀態(tài)為 (a1，a2， a3， a4)=(0， 1， 1， 1)，各個時刻的狀態(tài)如表 241所示。 ??第 2章 信息保密技術 表 241 LFSR 第 2章 信息保密技術 由表 241可知， t=6時的狀態(tài)恢復到 t=0時的狀態(tài)，且往后循環(huán)。因此，該反饋移位寄存器的周期是 6，輸出序列為0111100? ，表中對應 a1的狀態(tài)。本例中，若反饋函數為a4(t+1)=a1(t) a4(t)，則周期達到 15，輸出序列為0110010001111010? 。對于 4級線性反饋移位寄存器而言，所有可能狀態(tài)為 24=16種，除去全 0狀態(tài)，最大可能周期為 15。對于 n級線性反饋移位寄存器，不可能產生全 0狀態(tài)，因此，最大可能周期為 2n1，而能夠產生最大周期的 LFSR是我們所需要的，這就要求線性反饋函數符合一定的條件。關于隨機序列的周期及線性復雜度的有關知識，需要讀者具備一定的數學基礎，本書不再展開討論。 ?第 2章 信息保密技術 選擇線性反饋移位寄存器作為密鑰流生成器的主要原因有 : 適合硬件實現 。 能產生大的周期序列 。 能產生具有良好的統(tǒng)計特性的序列 。 它的結構能夠應用代數方法進行很好的分 實際應用中，通常將多個 LFSR組合起來構造非線性反饋移位寄存器， n級非線性反饋移位寄存器產生偽隨機序列的周期最大可達 2n，因此，研究產生最大周期序列的方法具有 第 2章 信息保密技術 3. RC4 RC4是由麻省理工學院的 Ron Rivest教授在 1987年為 RSA公司設計的一種可變密鑰長度、面向字節(jié)流的序列密碼。RC4是目前使用最廣泛的序列密碼之一，已應用于 Microsoft Windows、 Lotus Notes和其他應用軟件中，特別是應用到 SSL RC4算法很簡單，它以一個數據表為基礎，對表進行非線性變換，從而產生密碼流序列。 RC4包含兩個主要算法 : 密鑰調度算法 (Key Scheduling Algorithm， KSA)和偽隨機生 成算法 (Pseudo Random Generation Algorithm， PRGA) 第 2章 信息保密技術 KSA的作用是將一個隨機密鑰 (大小為 40~256位 )變換成一個初始置換表 S。過程如下 : (1) S表中包含 256個元素 S［ 0］ ~S［ 255］，對其初始化，令 S［ i］ =i， 0≤i≤255。 (2) 用主密鑰填充字符表 K，如果密鑰的長度小于 256個字節(jié)，則依次重復填充，直至將 K填滿。 K={K［ i］，0≤i≤255} (3) 令 j=0 (4) 對于 i從 0到 255循環(huán) : ① j=j+S［ i］ +K［ i］ (mod 256)。 ② 交換 S［ i］和 S［ j 第 2章 信息保密技術 PRGA的作用是從 S表中隨機選取元素，并產生密鑰流。過程如下 : (1) i=0， j=0 (2) i=i+1(mod 256) (3) j=j+S［ i］ (mod 256) (4) 交換 S［ i］和 S［ j (5) t=S［ i］ +S［ j］ (mod 256) (6) 輸出密鑰字 k=S［ t 雖然 RC4要求主密鑰 K至少為 40位，但為了保證安全強度，目前至少要達到 128位。 第 2章 信息保密技術 設明文消息被劃分成若干固定長度的組 m=(m1， m2， ? ，mn)，其中 mi=0或 1， i=1， 2, ? ， n，每一組的長度為 n，各組分別在密鑰 k=(k1， k2， ? ， kt)的作用下變換成長度為 r的密文分組 c=(c1， c2， ? ， cr)。分組密碼的模型如圖 243所示。 第 2章 信息保密技術 圖 243 分組密碼的模型 第 2章 信息保密技術 分組密碼的本質就是由密鑰 k=(k1， k2， ? ， kt)控制的從明文空間 M(長為 n的比特串的集合 )到密文空間 C(長為 r的比特串的集合 )的一個一對一映射。為了保證密碼算法的安全強度，加密變換的構造應遵循下列幾個原則 : (1) 分組長度足夠大。 當分組長度 n較小時，容易受到暴力窮舉攻擊，因此要有足夠大的分組長度 n來保證足夠大的明文空間，避免給攻 第 2章 信息保密技術 (2) 密鑰量空間足夠大， 以抵抗攻擊者通過窮舉密鑰破譯密文或者獲得密鑰信息。 (3) 加密變換足夠復雜， 以加強分組密碼算法自身的安全性，使攻擊者無法利用 (4) 加密和解密運算簡單，易于實現。 分組加密算法將信息分成固定長度的二進制位串進行變換。為便于軟、硬件的實現，一般應選取加法、乘法、異或 第 2章 信息保密技術 (5) 加密和解密的邏輯結構最好一致。 如果加密、解密過程的算法邏輯部件一致，那么加密、解密可以由同一部件實現，區(qū)別在于所使用的密鑰不同，以 古典密碼中最基本的變換是代替和移位，其目的是產生盡可能混亂的密文。分組密碼同樣離不開這兩種最基本的變換，代替變換就是經過復雜的變換關系將輸入位進行轉換，記為 S，稱為 S盒 。 移位變換就是將輸入位的排列位置進行變換，記為 P，稱為 P盒，如圖 244 第 2章 信息保密技術 分組密碼由多重 S盒和 P盒組合而成，如圖 245所示。 S盒的直接作用是將輸入位進行某種變換，以起到混亂的作用 。 P盒的直接作用就是移動輸入位的排列位置關系，以起到擴散的作用。分組密碼算法就是采用 “ 混亂與擴散 ” 兩個主要思想進行設計的，這是 Shannon為了有效抵抗攻擊者對密碼體制的統(tǒng)計分析提出的基本設計思想，也可以認為是分組密碼算法設計的基本原理。 第 2章 信息保密技術 圖 244 兩種基本變換 第 2章 信息保密技術 圖 245 S盒和 P盒所組成的網絡結構 第 2章 信息保密技術 (1) 代替。代替指將明文位用某種變換關系變換成新的位，以使所產生的密文是一堆雜亂無章的亂碼，這種變換與明文和密鑰密切相關，要求盡可能地使密文與明文和密鑰之間的關系十分復雜，不便破譯者從中發(fā)現規(guī)律和依賴關系， 從而加強隱蔽性。 在分組密碼算法中采用復雜的非線性代替 第 2章 信息保密技術 (2) 移位。移位指讓明文中的每一位 (包括密鑰的每一位 )直接或間接影響輸出密文中的許多位，即將每一比特明文 (或密鑰 )的影響盡可能迅速地作用到較多的輸出密文位中去，以便達到隱蔽明文的統(tǒng)計特性。這種效果也稱為 “ 雪崩效應 ” ，也就是說，輸入即使只有很小的變化，也會導致輸出位發(fā)生巨大變化。分組密碼算法設計中的移位操作就是為了達到擴 第 2章 信息保密技術 (3) 乘積變換。在分組密碼算法設計中，為了增強算法的復雜度，常用的方法是采用乘積變換的思想，即加密算法不僅是簡單的一次或兩次基本的 S盒和 P盒變換，而是通過兩次或兩次以上Ｓ盒和Ｐ盒的反復應用，也就是迭代的思想，克服單一密碼變換的弱點，構成更強的加密結果，以強化其復雜程度。后面介紹的一些分組密碼算法，無一例外地都采 第 2章 信息保密技術 數據加密標準 —— DES 20世紀 60年代末， IBM公司開始研制計算機密碼算法，在 1971年結束時提出了一種稱為 Luciffer的密碼算法，它是當時最好的算法，也是最初的數據加密算法。 1973年美國國家標準局 (NBS，現在的美國國家標準技術研究所， NIST)征求國家密碼標準方案， IBM就提交了這個算法。 1977年 7月 15日，該算法被正式采納作為美國聯邦信息處理標準生效，成為事實上的國際商用數據加密標準被使用，即數據加密標準 (Data Encryption Standard， DES)。當時規(guī)定其有效期為 5年，后經幾次授權續(xù)用，真正有效期限長達 20 第 2章 信息保密技術 在這 20年中， DES算法在數據加密領域發(fā)揮了不可替代的作用。進入 20世紀 90年代以后，由于 DES密鑰長度偏短等缺陷，不斷受到諸如差分密碼分析 (由以色列密碼專家 Shamir提出 )和線性密碼分析 (由日本密碼學家 Matsui等人提出 )等各種攻擊威脅，使其安全性受到嚴重的挑戰(zhàn)，而且不斷傳出被破解的消息。鑒于這種情況，美國國家保密局經多年授權評估后認為， DES算法已沒有安全性可言。于是 NIST決定在1998年 12月以后不再使用 DES來保護官方機密，只推薦作為一般商業(yè)使用。 1999年又頒布新標準，并規(guī)定 DES只能用于遺留密碼系統(tǒng)，但可以使用加密的 3DES加密算法。 第 2章 信息保密技術 但不管怎樣， DES的出現推動了分組密碼理論的研究，起到了促進分組密碼發(fā)展的重要作用，而且它的設計思想對掌握分組密碼的基本理論和工程應用有著重要的參考價值。 第 2章 信息保密技術 1. DES DES算法的加密過程如圖 246所示。 1) 初始置換 IP 如圖 247所示，初始置換方法是將 64位明文的位置順序打亂，表中的數字代表 64位明文的輸入順序號，表中的位置代表置換后的輸出順序，表中的位置順序是先按行后按列進行排序。 第 2章 信息保密技術 圖 246 DES算法的加密過程 第 2章 信息保密技術 例如 : 表中第一行第一列的數字為 58，表示將原來排在第 58位的比特位排在第１位 。 第一行第二列的數字為 50，表示將原來排在第 50位的比特位排在第 2位，依次類推。不妨設輸入位序為 m1m2? m64，初始置換后變?yōu)?m1′m2′? m64′=m58m50? m7。 初始置換表中的位序特征 : 64位輸入按 8行 8列進行排列，最右邊一列按 8和 7的次序進行排列，往左邊各列的位序號依次緊鄰其右邊一列各序號加 8 第 2章 信息保密技術 圖 247 初始置換 IP 第 2章 信息保密技術 2) 乘積變換 (16輪迭代 ) 乘積變換部分要進行 16輪迭代，如圖 248所示。將初始置換得到的 64位結果分為兩半，記為 L0和 R0，各 32位。設初始密鑰為 64位，經密鑰擴展算法產生 16個 48位的子密鑰，記為 K1， K2， ? ， K16，每輪迭代的邏輯關系為 其中 1≤i≤16 ?????????)K,f(RLRRLi1i1ii1ii第 2章 信息保密技術 圖 248 DES算法的乘