一.DES的簡(jiǎn)介

? ? ? Data Encryption Standard(DES)汛骂，雖然已被淘汰使用罕模，但是對(duì)于研究密碼攻擊人員，學(xué)習(xí)差分分析很有必要帘瞭。

? ? ? 首先簡(jiǎn)單介紹一下DES工作原理淑掌，是分組密碼的一種，明文是６４位蝶念，每一輪的子密鑰是５６位抛腕。16輪Feistel結(jié)構(gòu)。下圖是一個(gè)3輪的例子媒殉。

１.首先担敌，６４位明文經(jīng)過初始置換（Initial Permutation,IP）函數(shù)，對(duì)明文進(jìn)行初始置換廷蓉。初始置換只進(jìn)行一次全封，在第一輪之前進(jìn)行，根據(jù)初始置換表進(jìn)行（在我看來就是打亂初始明文的順序）

2.初始置換之后桃犬，64位明文被分成左右兩部分明文刹悴，稱左明文L0，右明文R0.

3.每一輪DES都包括以下：

（1）子密鑰變換攒暇，一開始密鑰是有64位土匀，分別放棄第8i（i=1，...,8）位得到56位密鑰形用，56位密鑰經(jīng)過壓縮置換表選擇其中的48位就轧。

（2）擴(kuò)展置換，擴(kuò)展置換是將右明文R0從32位擴(kuò)展到48位田度。具體過程大概是把右明文R0分為8組妒御，每一組4位，然后每個(gè)4位通過重復(fù)第1位和第4位擴(kuò)展為6位镇饺，經(jīng)過擴(kuò)展置換之后右明文變?yōu)榱?8位携丁。

（3）S盒置換，如下圖所示兰怠。經(jīng)過擴(kuò)展之后的48位右明文R0和48位子密鑰進(jìn)行異或反應(yīng)。異或之后的48位分成8組李茫，每組6位揭保，分別進(jìn)入Si（i=1,...,8）盒，每一個(gè)S盒通過查表把6位轉(zhuǎn)換成4位魄宏，最后形成32位輸出秸侣。

（5）異或和交換。最初的左明文L0和P盒置換之后輸出的結(jié)果進(jìn)行異或運(yùn)算，形成下一輪的右明文味榛。最初的右明文是下一輪的左明文椭坚。如下圖所示（以三輪為例）

4.經(jīng)過16輪之后，最后搏色，把左明文和右明文重新連接起來善茎，對(duì)組成的塊進(jìn)行最終置換（Final Permutation,FP）,最終置換只進(jìn)行一次，最終置換之后频轿，輸出64位密文垂涯。

二．差分分析簡(jiǎn)介

１．差分分析的原理

　　差分分析是一種選擇明文攻擊，通過分析明文對(duì)中的差異對(duì)結(jié)果密文的差分的影響航邢，這些差分是用來給可能的密鑰進(jìn)行分配概率耕赘，確定最有可能的密鑰。差分在這里指的是明文對(duì)的異或膳殷。

２．３輪ＤＥＳ的差分分析

? 我們以3輪ＤＥＳ為例操骡，選擇明文異或，L0’為任意值赚窃，R0'=0.找出在第三輪中進(jìn)入Ｓ１盒的６個(gè)子密鑰比特册招，以下圖為例，設(shè)Ｌ是初始的左明文考榨，Ｒ是初始右明文跨细，ｌ是三輪之后的輸出密文。ａ河质，ｂ冀惭，ｃ分別代表第一輪第二輪第三輪的輸入異或，Ａ掀鹅，Ｂ散休，Ｃ分別代表第一輪，第二輪乐尊，第三輪的輸出異或戚丸。根據(jù)DES基本原理，我們可以得出結(jié)論 l=L(+)A(+)C（這里不能添加異或符號(hào)扔嵌，用（+）代替）限府。針對(duì)本例選擇的明文，R0’=0痢缎，所以a=0胁勺，自然A=0.所以l=L(+)C,即C=l(+)L.

? ? ? ? 假設(shè)k是輸入S1盒的可能對(duì)數(shù)，再回顧一下F函數(shù)中關(guān)于S盒的工作流程独旷，首先輸入6比特的值（Se）和6位密鑰（Sk）進(jìn)行異或署穗，異或之后進(jìn)入S盒成為進(jìn)入S盒的實(shí)際值（Si表示）寥裂，得出Sk=Se（+）Si.

? ? ? 進(jìn)一步舉例說明，如果在DES第三輪里面進(jìn)入S1的密文比特分別是Se=1案疲，Se*=35封恰，且輸出XOR是D，則Sk的值一定會(huì)在下表中出現(xiàn)褐啡。（我來解釋一下為什么哦诺舔，首先輸入對(duì)一個(gè)是1，一個(gè)是35春贸，那他們的輸入異或是34混萝，輸出異或是D，我們可以查S1XOR分布表萍恕，共有8對(duì)逸嘀，實(shí)際不算順序應(yīng)該只有4對(duì)，跟師姐請(qǐng)教之后說應(yīng)該是窮舉得出的允粤。如下表崭倘，然后根據(jù)Sk=Se(+)Si,每一行都產(chǎn)生兩個(gè)密鑰，分別是Se(+)Si,Se*(+)Si）

3.n輪特征

? ? ?3.1一輪特征

? ? ?下面一輪特征概率是1（對(duì)任何L'）,這是概率大于1/4的唯一一圈特征类垫。該特征在破譯DES型密碼體質(zhì)的所有特征中具有特殊的重要性司光。（這個(gè)很好理解，輸入異或是0悉患，那么這兩個(gè)輸入值相同残家，輸出的值一定相同，則輸出異或一定是0）

下面這一輪特征的概率是14/64.

? a'=0110,0000,0000,0000,0000,0000,0000,0000? ??

a’經(jīng)過擴(kuò)展之后是001100,000000,000000,000000,000000,000000,000000,000000? （C,0,0,0,0,0,0,0）x

? ?A'=0000,0000,1000,0000,1000,0010,0000,0000

P置換之后是（E0000000）x

接下來查S1盒的XOR分布表售躁，可以發(fā)現(xiàn)Cx——>Ex,概率p=14/64,其余都是0x——>0x坞淮，p=1，所以整個(gè)這一輪的特征概率是14/64.

2.三輪特征

這種情況是可能出現(xiàn)的陪捷，當(dāng)X=19600000時(shí)回窘，概率大約是1/234嫌蚤，用來對(duì)9輪及以上的ＤＥＳ進(jìn)行攻擊系吭。

３．六輪ＤＥＳ的破譯

　　　　六輪ＤＥＳ9比三輪ＤＥＳ更加復(fù)雜，采用兩個(gè)ｐ＝１／１６的統(tǒng)計(jì)特征镀脂，選擇最常計(jì)算的密碼值苍碟。在這兩個(gè)特征中酒觅，每一個(gè)特征都能找到Ｋ６的３０個(gè)密鑰比特，加上公用的３個(gè)Ｓ盒微峰，所以由兩個(gè)特征發(fā)現(xiàn)的密鑰比特為４２阐滩，其他的１４個(gè)密鑰比特可以通過窮舉得出。