區塊加密法.pptVIP

* * * * * * * * * * * * * * * 差異破解法 差異破解法是近幾年密碼破解領域最大的發展 早在1974年DES的設計人員就已經知道差異破解法 Murphy、Biham Shamir都在90年代發表過論文 破解區塊加密的有力工具 是第一個能夠在複雜度低於255就破解DES的方法 DES的S-boxes和重排函數P能夠抵擋差異破解法 差異破解法 差異破解法的整體策略是以單一回合為基礎 破解的程序會先選取特定差距的兩段明文m與m’ 再追蹤每個回合 看某個輸入差距樣式會產生出什麼密文差距樣式 在不知道金鑰的情況下實際加密m與m’來觀察輸出的差距 再比較結果與之前得到的密文差距樣式 差異破解法(differential cryptanalysis) 差異破解法很複雜。簡單來說，是藉由觀察加密法每一回合對一組文字區塊所作的行為 我們先改變DES的表示法，將原本的明文區塊m分為m0與m1 如果將每回合產生的新區塊命名為mi (2 ≦ i ≦ 17)，中間的訊息就有以下的關聯： 差異破解法 先從m與m’兩個訊息開始使用差異破解法 它們之間的XOR差距是?m = m ⊕ m’，而且中間形式的一半差距為?m = mi ⊕ mi’，即可得到： 差異破解法 假設使用相同的子金鑰，若函數f的好幾組輸入都有相同的差距，輸出也會有相同的差距 如果XOR的輸入為X、輸出為Y的比例是p，那麼X導致Y的機率是p 假設某些X的值有很高的機率會導致某個輸出差距 因此若知道?mi-1和?mi出現的機率很高，那麼即可得知?mi+1出現的機率也會很高 如果找出好幾組這類的差距，就很有可能找出函數f所用的子金鑰 差異破解法 線性破解法(linear cryptanalysis) 線性破解法是最近所發展的破解技巧 原理是尋找描述DES轉換行為的線性近似值，用這個方法來破解DES的金鑰 需要243個已知明文（差異破解法需要247個選定明文 ） 線性破解法 線性破解法的目的是找到具有以下形式的有效線性方程式： P[i1,i2,...,ia] ? C[j1,j2,...,jb] = K[k1,k2,...,kc] ia,jb,kc是P、C、K裡固定且唯一的位元位置 能得到金鑰位元的線性方程式 還可以試著找出更多類似的關係來解出金鑰位元 DES的設計標準 由Coppersmith在1994年提出 [COPP94] 7項S-boxes的設計準則 任何輸出位元不應是其輸入位元的線性函數 S-boxes每列應包含所有可能的16種輸出組合 3項重排程序P的設計準則 目的是希望增加這個演算法的混淆程度 S-boxes的設計準則 S-boxes的任何輸出位元不應是其輸入位元的線性函數 S-boxes的每一列應包含所有可能的16種輸出組合 若S-boxes某兩組輸入只相差一個位元，其輸出必須相差兩個位元以上 若S-boxes某兩組輸入只有中間的兩個位元不同，其輸出必須相差兩個位元以上 若S-boxes某兩組輸入的前兩個位元不同，但後兩個位元相同，則輸出必須不同 任何非0的6個位元完全不同的組合有32種，其中輸入差距與輸出差距相同的情況不可以超過8種 若一次考慮3個S-boxes，上一條件仍須成立 重排程序P的設計準則 每個S-boxes第i回合的四個輸出位元，其中的兩個位元影響第i+1回合輸入的中間位元，另兩個位元影響此輸入的末端位元。 S-boxes輸入的中間位元與其相鄰的S-boxes無關。相鄰的S-boxes會共用它們的末端位元。 S-boxes的四個輸出位元會影響下個回合6個不同的S-boxes，但是不同的輸入位元不會影響相同的S-boxes。 對j與k兩個S-boxes而言，如果sj的輸出位元影響下一回合sk的中間位元，sk的輸出位元就不能影響sj的中間位元。 菲仕托加密法的強度 菲仕托加密法的強度來自 回合數、函數F、產生金鑰的演算法 即使函數F很脆弱，但只要回合數夠多就不易破解 函數F的基本原則仍如70年代的菲仕托 函數F的演算法應具有很好的崩塌效應，而所產生的結果必須是難以復原 S-boxes之間的關係應該是非線性，而且應該無法以線性函數來逼近模擬 金鑰的產生方式應該要確保金鑰與密文的完全崩塌準則與位元獨立準則 * * * * * * * * * * * * * * * * * * * * 本章重點 區塊加密法與串流加密法 菲仕托加密 資料加密標準DES 差異破解與線性破解 區塊加密的設計原則 區塊加密法與串流加密法 區塊加密法(Block Ciphers)：將一小段明文視為一體，然後產生長度相同的密文區塊，每個區塊的大小通常是64或128位元。 串流加密法(Stream Ciphers)：一次加密資料流裡的一個位元或是位元組。 目前許多加密法