《系統(tǒng)結(jié)構(gòu)》PPT課件.ppt

第 2章對稱密碼 密碼學(xué)的歷史已有 4000多年 古埃及人曾把象形文字寫在石碑上 密碼學(xué)是一門研究秘密信息的隱寫技 術(shù)的學(xué)科 密碼學(xué)技術(shù)可以使消息的內(nèi)容對 (除發(fā) 送者和接收者以外 )的所有人保密 . 可以使接收者驗證消息的正確性 是解決計算機與通信安全問題重要技 術(shù)之一 . 密碼學(xué) 密碼學(xué)的發(fā)展 第 1階段： 1949年以前。 第 2階段：從 1949年到 1975年。 標(biāo)志： 1949年 Shannon發(fā)表的 保密系統(tǒng)的信息理論 一文。 第 3階段： 1976年至今。 標(biāo)志： 1976年 Diffie和 Hellman發(fā) 表了 密碼學(xué)新方向 一文。 Shannon模型 密碼的基本術(shù)語 密碼技術(shù)（ Cryptography） 把可 理解的消息變換成不可理解消息，同 時又可恢復(fù)原消息的方法和原理的一 門科學(xué)或藝術(shù)。 明文（ plaintext ） -變換前的原始消 息 密文（ ciphertext） -變換后的消息 密碼（ cipher ） -用于改變消息的替 換或變換算法 密鑰（ key ） -用于密碼變換的，只 有發(fā)送者或接收者擁有的秘密消息 編碼（ encipher /encode） -把 明文變?yōu)槊芪牡倪^程 譯碼（ decipher /decode) 把 密文變?yōu)槊魑牡倪^程 密碼分析（ cryptanalysis /codebreaking) 在沒有密鑰的情況下，破解密文的 原理與方法 . 密碼學(xué)（ cryptology ） -包括加 密理論與解密理論的學(xué)科 如果將加密過程看成是一個數(shù)學(xué)函 數(shù) F的話 ， 則密文 C可以表示為： C = F （ P， K ） 這個函數(shù)具有兩個自變量 P和 K， 在函數(shù) F的作用下得到密文。在已知 密鑰 K1、 K2、加密算法 E和解密算法 D時，則加密和解密過程可以表示如 下： EK1 （ P ） = C D K2（ C ） = P 顯然為使明文加密后能被解密必 須有： P = D K2 （ E K1（ P ） = P 在實際加密和解密時 ， 根據(jù)加密 算法的特點 ， K1與 K2的值可以不同 ， 也可以相同 。 密碼系統(tǒng)的攻擊方法 窮舉法 :又稱強力攻擊或者窮搜攻 擊，是指分析者一次試遍密鑰空 間中的所有的蜜鑰來獲取明文的 一種手段 典型的例子 1977年 DES密碼的破 譯 密碼系統(tǒng)的攻擊方法 統(tǒng)計分析攻擊：密碼分析者利用 明文和密文的概率統(tǒng)計規(guī)律，從 而找出符合規(guī)律的相應(yīng)明文的方 法，如 Caesar密碼 數(shù)學(xué)分析攻擊：密碼分析者對密 碼特征中表現(xiàn)出的數(shù)學(xué)特征，通 過數(shù)學(xué)求解的方法來獲取最后明 文。如公鑰密碼 RSA 密碼系統(tǒng)的攻擊方法 密碼分析 密碼分析 ：從密文推導(dǎo)出明文或密 鑰 。 密碼分析：常用的方法有以下 4類： 惟密文攻擊（ cybertext only attack）； 已知明文攻擊（ known plaintext attack）； 選擇明文攻擊（ chosen plaintext attack）； 選擇密文攻擊（ chosen ciphertext attack）。 惟密文攻擊 密碼分析者知道一些消息的密文 （加密算法相同），并且試圖恢 復(fù)盡可能多的消息明文，并進一 步試圖推算出加密消息的密鑰 （以便通過密鑰得出更多的消息 明文 。 已知明文攻擊 密碼分析者不僅知道一些消息的 密文，也知道與這些密文對應(yīng)的 明文，并試圖推導(dǎo)出加密密鑰或 算法（該算法可對采用同一密鑰 加密的所有新消息進行解密。 ) 選擇明文攻擊 密碼分析者不僅知道一些消息的 密文以及與之對應(yīng)的明文，而且 可以選擇被加密的明文（這種選 擇可能導(dǎo)致產(chǎn)生更多關(guān)于密鑰的 信息），并試圖推導(dǎo)出加密密鑰 或算法（該算法可對采用同一密 鑰加密的所有新消息進行解密）。 選擇密文攻擊 密碼分析者能夠選擇不同的密文 并能得到對應(yīng)的明文，密碼分析 的目的是推導(dǎo)出密鑰 。 古典密碼的 分類 代替密碼 置換密碼 代數(shù)密碼 代替密碼 對于一個密碼體制，如果構(gòu)造一 個或多個密文字母表，使得明文 中不同位置的同一個明文字母與 密文字母表中的字母或字母組相 對應(yīng)，這種密碼體制為代替密碼 體制。 它主要分為單表代替密碼、多表 代替密碼、多字母代替密碼 置換密碼 又稱換位密碼，換位就是將明文 中字母的位置重新排列。最簡單 的換位就是逆序法，即將明文中 的字母倒過來輸出。例如 明文 ： computer system 密文 ： metsys retupmoc 這種方法太簡單 ， 非常容易破密。 下面介紹一種稍復(fù)雜的換位方 法 列換位法。 使用列換位法，首先要將明文排成一個 矩陣，然后按列進行輸出。為此要解 決兩個問題： 排成的矩陣的寬度 有多少列； 排成矩陣后，各列按什么樣的順序輸 出。 為此，要引入一個密鑰 k，它既可定義 矩陣的寬度，又可以定義各列的輸出 順序。例如 k=computer，則這個單 詞的長度（ 8）就是明文矩陣的寬度， 而該密鑰中各字母按字母序出現(xiàn)的次 序，就是輸出的列的順序。表 6.3為按 密鑰對明文“ WHAT YOU CAN LEARN FROM THIS BOOK”的排列。 按密鑰對明文“ WHAT YOU CAN LEARN FROM THIS BOOK”的排列 代數(shù)密碼 利用代數(shù)數(shù)學(xué)知識對明文進行加 密的方式，如 Vernam密碼 簡單異或 異或運算具有如下特點： 0 0 = 0 0 1 = 1 1 0 = 1 1 1 = 0 a a = 0 即兩個運算數(shù)相同，結(jié)果為 0；不同，結(jié) 果為 1。 + + + + + 愷撒密碼 (Caesar) 愷撒密碼 (Caesar) 愷撒密碼 (Caesar) C=(m+k)mod26 愷撒密碼的一般形式 一般形式，可以把 Caesar cipher 中字母移動的位數(shù)由 3變?yōu)?1-25中的 任何一個 密碼分析 可以簡單的實驗每個密鑰（窮密鑰搜索） 給定一些密文，實驗每個密鑰。 LIZHZLVKWRUHSODFHOHWWHUV Original ciphertext KHYGYKUJVQTGRNCEGNGVVGTU try shift of 1 JGXFXJTIUPSFQMBDFMFUUFST try shift of 2 IFWEWISHTOREPLACELETTERS try shift of 3 * plaintext HEVDVHRGSNQDOKZBDKDSSDQR try shift of 4 MJAIAMWLXSVITPEGIPIXXIVW try shift of 25 eg. break ciphertext GCUA VQ DTGCM 維吉尼亞密碼（ Vigennere) 法國密碼學(xué)家 Vigenere以 他自己的名字命名的維吉利亞密 碼，在 1586年發(fā)明的，是一種 典型的多表代替密碼，其明文、 密文構(gòu)成的方陣為 Vigenere 方 陣 制作的方陣下表所示： 例如：明文為 data security， 密鑰為 best 按密鑰的長度將明文分解若干節(jié)。 這里 best的長度為 4，故將明文 分解為表 6.2所示的樣子 對每一節(jié)明文，利用密鑰 best進 行變換。以明文“ d”為例，變化 的方法是：由于 d處于 b列，因此 在維吉利亞方陣的第 d行 b列中 找。于是得到如下密文： C=Ek(M)=EELT TIUN SMLR Vigenere方陣的數(shù)學(xué)公式表達為 設(shè)明文為 m=m1m2m n , 密鑰 k=k1k2k n,密文 c=c1c2c n, 則 ci=Ek(mi)=(mi+ki)mod26,其中 i=1,2,n Vigenere 密碼可以看成是 Caesar密碼的 推廣 維吉尼亞密碼（ Vigennere) 可以看出，越安全的密碼使用起來越 復(fù)雜 因此，在有些場合還可以看到單碼替 換密碼 隨著破譯單碼密碼的技術(shù)提高， 使得 vigenre cipher 逐漸被各國使 用 1854年，首次被 Charles Babbage 攻破，但沒有公開 Friedrich Kasiski 于 1863年攻破并發(fā)表了 此密碼的各 種變形被沿用到 20世紀(jì) 普萊費厄（ Playfair）密碼 Playfair密碼是由 Charles Wheatstone于 1854年發(fā)明的，其名 稱以他的朋友 Playfair命名。 英國陸軍在第一次世界大戰(zhàn)，美國 陸軍在第二次世界大戰(zhàn)期間大量使用 的一種二字母組代替密碼。 它將明文中的雙字母組合作為一個 單元對待，該加密法是基于一個關(guān)鍵 詞的，該關(guān)鍵詞填寫在一個 5*5的矩 陣中（去出重復(fù)字母和字母 j），通過 該矩陣完成對明文、密文的加密、解 密過程。 對明文加密規(guī)則如下： 1 若 m1 m2在同一行，對應(yīng)密文 c1 c2 分別是緊靠 m1 m2 右端的字母。其中第一 列被看做是最后一列的右方。 2 若 m1 m2在同一列，對應(yīng)密文 c1 c2 分別是緊靠 m1 m2 下方的字母。其中第一 行被看做是最后一行的下方。 3 若 m1 m2不在同一行，不在同一列， 則 c1 c2是由 m1 m2確定的矩形的其他兩角 的字母，并且 c1和 m1， c2和 m2同行。 4 若 m1 m2相同，則插入一個事先約定 的字母，比如 X 。 5 若明文字母數(shù)為奇數(shù)時，則在明文的 末端添加某個事先約定的字母作為填充。 解密算法 Playfair解密算法首先將密鑰填寫在 一個 5*5的矩陣中（去出重復(fù)字母和 字母 j），矩陣中其它未用到的字母 按順序填在矩陣剩余位置中，根據(jù)替 換矩陣由密文得到明文。 1 若 c1 c2在同一行，對應(yīng)明文 m1 m2分別是緊靠 c1 c2 左端的字母。其 中最后一列被看做是第一列的左方。 2 若 c1 c2在同一列，對應(yīng)明文 m1 m2分別是緊靠 c1 c2 上方的字母。其 中最后一行被看做是第一行的上方。 3 若 c1 c2不在同一行，不在同一 列，則 m1 m2是由 m1 m2確定的矩形的 其他兩角的字母，并且 c1和 m1， c2 和 m2同行。 舉例說明 Vernam密碼 它是一種代數(shù)密碼，明文、密文、 密鑰都用二進制表示 M=m1,m2m n K=k1,k1k n C=c1,c2c n 加密 ci=mi ki i=1,2n 解密 mi=ci ki i=1,2,.n 因為加密和解密都是模 2加，所 以為代數(shù)運算 對合運算 Vernam經(jīng)不起明文的攻擊 如果密鑰有重復(fù)的， Vernam密 碼是不安全的 一種極端情況 一次一密 1. 密鑰是隨機的 2. 密鑰至少和明文一樣長 3. 一個密鑰只用一次 一次一密絕對是不可譯的，但 它不實用，但它又給密碼設(shè)計 指出一個方向，人們用序列密 碼逼近一次一密 序列密碼 序列密碼是一類非常重要的密碼體制，又稱 為流密碼。在流密碼中，將明文消息按一定 長度分組（長度較?。缓髮Ω鹘M用相關(guān) 但不同的密鑰進行加密，產(chǎn)生相應(yīng)的密文， 相同的明文分組會因在明文序列中的位置不 同而對應(yīng)于不同的密文分組。 優(yōu)點： 第一，在硬件實施上，流密碼的速度一般要 比分組密碼快，而且不需要有很復(fù)雜的硬件 電路： 第二，在某些情況下（例如對某些電信上的 應(yīng)用），當(dāng)緩沖不足或必須對收到的字符進 行逐一處理時，流密碼就顯得更加必要和恰 當(dāng)； 第三，流密碼有較理想的數(shù)學(xué)分析工具，如 代數(shù)方法等。 第四，流密碼能較好地隱藏明文的統(tǒng)計特征。 序列密碼 目前關(guān)于流密碼的理論和技術(shù)已取得 長足的發(fā)展。同時密碼學(xué)家也提出了 大量的流密碼算法，有些算法已被廣 泛地應(yīng)用于移動通信、軍事外交等領(lǐng) 域。 它是由 Vernam發(fā)展而來的，包括 RC4和 SEAL算法 序列密碼 序列密碼主要取決于密鑰序列的 安全，如果與密鑰是隨機的，咋 就成為一次一密密碼，理論上不 可破。序列密碼的加密和解密運 算簡單，主要是模 2加。 基于線性移位寄存器 LFSR的序列密碼 線性反饋移位寄存器 LFSR，簡稱移 位寄存器，其形成密碼算法主要是利 用反饋移位寄存器的工作原理來生成 密鑰序列。 N階反饋移位寄存器模型 如下：這是一個左移一位寄存器，寄 存器沒運動一次， n階移位寄存器的 內(nèi)容就向 n-1階進一次，即第 2階的內(nèi) 容 S1傳給第 1階作為 s0，依次類推， 第 n階的內(nèi)容傳給第 n-1階，最后 n階 的內(nèi)容由反饋函數(shù) f(s0,s1,s2,s n-1)傳送。 如果它是線性的，則此寄存器稱為線 性移位寄存器 N階反饋移位寄存器 f(s0,s1,s n-1) s0 s1 Sn-2 Sn-1 - 輸出 圖中 s0,s1,.組成左移移位寄存器，并 稱每一時刻移位寄存器的取值的一個 狀態(tài) f(s0,s1.s n-1)為反饋函數(shù)，如為線性 的，可寫成 f(s0,s1,s n-1)=g0s0+g1s1+g n-1sn-1 其中 g0,g1,g n-1為反饋系數(shù) 在二進制中 +為 ，反饋系數(shù) gi GF(2)如果 gi=0,表示式中 gisi不存 在，因此 si不連接，同理 gi=1,表示 si 連接，故 gi的作用相當(dāng)于一個開關(guān) ,如 圖所示： s0 s1 Sn-2 Sn-1 + + + - - g1 g2 gn-1 g0=1 gn=1 形式地：用 xi與 si相對應(yīng)，則根 據(jù)反饋函數(shù)得到一個關(guān)于 x的多 項式： g(x)=gnxn+gn-1xn-1+g 1x1+g0 稱 g(x)為線性移位寄存器的連接 多項式 例題： 一個上 GF(2)的 5階移位寄存器， 其反饋多項式為 f(x)=1+x+x4 ,初 始狀態(tài)為 s0=(10110)，則其狀態(tài) 序列與輸出序列是什么 ? 由反饋多項式可以表示出連接多項 式 g(x)=1+x+x4+x5 ,由反饋多項 式可知 g0=g1=g4=1,則反饋可表示 為 f(x)=s0 s1 s4, 如圖： s0 s1 s2 s3 s4 g1=1 g0=1 g4=1 g5-=1 狀態(tài) 10110 01101 11010 10100 01001 10010 輸出 1 0 0 1 0 1 狀態(tài) 00101 01011 10110 01101 輸出 1 0 1 0 該線性反饋寄存器的狀態(tài)序列和輸出序列的周 期為 8 輸出序列為 10010110 N級線性移位寄存器最多有 2n個 不同的狀態(tài)，若其初始狀態(tài)為 0， 其后狀態(tài)恒為 0.若初始狀態(tài)不為 0， 其后狀態(tài)也不為 0，因此 n級線性 反饋寄存器的狀態(tài)周期小于或等 于 2n-1,其輸出序列的周期小于或 等于 2n-1 只要選擇合適的連接多項式便 可使線性移位寄存器的狀態(tài)周 期達到 2n-1,此時的輸出序列為 m序列 M序列的優(yōu)點 1. 具有良好的隨機性 2. 0和 1出現(xiàn)的次數(shù)接近相等，都 為 2n-1 RC4 RC4序列密碼是美國 RSA數(shù)據(jù)安 全公司在 1987年設(shè)計的一種序列 密碼，直到 1994年有人破獲，在 1997年該公司公布了 RC4的算法。 該算法密鑰 40為，在 Interner網(wǎng) 上 32小時可破獲 RC4 它是一種基于非線性數(shù)據(jù)表的交 換序列密碼，它以一個足夠大的 數(shù)據(jù)表為基礎(chǔ)，對表進行非線性 變換，產(chǎn)生非線性的密鑰序列 RC4使用 256個字節(jié)的 S表和兩個指針 （ I和 J） S表的值為 S0,S1,S 255是 0， 1.255 的一個排列 I 、 J的處置為 0 我們把 RC4算法看成一個有限的狀態(tài) 自動機，把 S表和 I、 J的具體取值作 為 RC4的一個狀態(tài) T=,對狀態(tài) T進行非 線性變換，產(chǎn)生新的狀態(tài)，并且輸出 密鑰序列中的一個字節(jié) K RC4的下一個狀態(tài)函數(shù)如下 1. I=0,J=0 2. I=(I+1) MOD256 3. J=(J+SI )MOD 256 4. 交換 SI和 SJ RC4的輸出函數(shù)如下 1. h=(si+sj) mod 256 2. K=sh 在使用 RC4加解密之前，首先 對 S表初始化 對 S表進行線性填充 1、 S0=0,S1=1,S255=255 2、用密鑰填充另一個 256字節(jié)的 R表 R0,R1,R255, 如果密鑰的長度 小于 R表的長度，則一次重復(fù)填充， 直到 R表填滿 3、 J=0 4、對 I=0到 255重復(fù)一下操作 J=J+si+RI 交換 SI和 SJ RC4的算法優(yōu)點 算法簡單、高效，特別適合軟 件實現(xiàn)，目前應(yīng)用非常廣泛 注意 ，對 S表初始化的過程實質(zhì)上 是 對 S表進行隨機化處理 的過程，只 有當(dāng)這一個過程完成后，才能計算 產(chǎn)生密鑰序列，否則將是不安全的