DES算法實現

實驗目標

完成一個DES 算法的詳細設計,內容包括：

  • 算法概述；
  • 總體結構；
  • 數據結構。

實驗概述

算法原理

DES（Data Encryption Standard）是一種用于電子數據加密的對稱密鑰塊加密算法.它以64位為分組長度，64位一組的明文作為算法的輸入，通過一系列復雜的操作，輸出同樣64位長度的密文。DES 同樣采用64位密鑰，但由于每8位中的最后1位用于奇偶校驗，實際有效密鑰長度為56位。密鑰可以是任意的56位的數，且可隨時改變。

DES 使用加密密鑰定義變換過程，因此算法認為只有持有加密所用的密鑰的用戶才能解密密文。DES的兩個重要的安全特性是混淆和擴散。其中混淆是指通過密碼算法使明文和密文以及密鑰的關系非常復雜，無法從數學上描述或者統(tǒng)計。擴散是指明文和密鑰中的每一位信息的變動，都會影響到密文中許多位信息的變動，從而隱藏統(tǒng)計上的特性，增加密碼的安全。

DES算法的基本過程是換位和置換。如圖，有16個相同的處理階段，稱為輪。還有一個初始和最終的排列，稱為 IP 和 FP，它們是反向的 (IP 取消 FP 的作用，反之亦然)。

在主輪之前，塊被分成兩個32位的一半和交替處理；這種縱橫交錯的方案被稱為Feistel 方法。Feistel 結構確保了解密和加密是非常相似的過程——唯一的區(qū)別是在解密時子鍵的應用順序是相反的。其余的算法是相同的。這大大簡化了實現，特別是在硬件中，因為不需要單獨的加密和解密算法。

\oplus 符號表示異或（XOR）操作。Feistel 函數將半塊和一些鍵合在一起。然后，將Feistel 函數的輸出與塊的另一半組合在一起，在下一輪之前交換這一半。在最后一輪之后，兩隊交換了位置；這是 Feistel 結構的一個特性，使加密和解密過程類似。

image

數據結構

Initial permutation (IP)

IP 置換表指定64位塊上的輸入排列。其含義如下：輸出的第一個比特來自輸入的第58位;第二個位來自第50位，以此類推，最后一個位來自第7位輸入。

image

Final permutation ( IP^{-1})

最后的排列是初始排列的倒數。

image

Expansion function (E)

展開函數被解釋為初始排列和最終排列。注意，輸入的一些位在輸出時是重復的;輸入的第5位在輸出的第6位和第8位中都是重復的。因此，32位半塊被擴展到48位。

image

Permutation (P)

P排列打亂了32位半塊的位元。

image

Permuted choice 1 ( PC-1 )

表的“左”和“右”部分顯示了來自輸入鍵的哪些位構成了鍵調度狀態(tài)的左和右部分。輸入的64位中只有56位被選中；剩下的8（8、16、24、32、40、48、56、64）被指定作為奇偶校驗位使用。

image

Permuted choice 2 ( PC-2 )

這個排列從56位鍵調度狀態(tài)為每輪選擇48位的子鍵。

image

S-box

這個表列出了DES中使用的8個S-box，每個S-box用4位的輸出替換6位的輸入。給定一個6位輸入，通過使用外部的兩個位選擇行，以及使用內部的四個位選擇列，就可以找到4位輸出。例如，一個輸入“011011”有外部位“01”和內部位“1101”。第一行為“00”，第一列為“0000”，S-box S5對應的輸出為“1001”(=9)，即第二行第14列的值。

image
image

基本流程

DES算法的基本流程圖如下：

image

DES算法是典型的對稱加密算法，在輸入64比特明文數據后，通過輸入64比特密鑰和算法的一系列加密步驟后，可以得到同樣為64比特的密文數據。反之，我們通過已知的密鑰，可以將密文數據轉換回明文。我們將算法分為了三大塊：IP置換、16次T迭代和IP逆置換，加密和解密過程分別如下：

  • C = E_k(M) = IP^{-1} \cdot W \cdot T_{16} \cdot T_{15}\cdots T_1 \cdot IP(M)
  • M = D_k(C)=IP^{-1} \cdot W \cdot T_{1} \cdot T_{2}\cdots T_{16} \cdot IP(C)
符號 釋意
M 算法輸入的64位明文塊
E 描述以K 為密鑰的加密函數，由連續(xù)的過程復合構成
IP 64位初始置換
T_n 一系列的迭代變換
W 為64位置換，將輸入的高32位和低32位交換后輸出
IP^{-1} 是IP的逆置換
C 算法輸出的64位密文塊

實驗過程

實驗的設計模式是自頂向下的結構，用C語言去分別是先各個函數的功能，最后通過主函數將所有函數進行整合，讓算法更加清晰客觀。

表置換

通過IP置換表，根據表中所示下標，找到相應位置進行置換。

const char IP_Table[64]={             
    58,50,42,34,26,18,10,2, 
    60,52,44,36,28,20,12,4,
    62,54,46,38,30,22,14,6, 
    64,56,48,40,32,24,16,8,
    57,49,41,33,25,17, 9,1, 
    59,51,43,35,27,19,11,3,
    61,53,45,37,29,21,13,5, 
    63,55,47,39,31,23,15,7 
};

void TablePermute(bool *DatOut,bool *DatIn,const char *Table,int Num)  
{
    int i=0;
    static bool Temp[256]={0};
    for(i=0;i<Num;i++)                
    {
        Temp[i]=DatIn[Table[i]-1]; 
    }
    BitsCopy(DatOut,Temp,Num);  
}

對于16次 T 迭代，我們先將傳入的經過 IP 混淆過的64位明文的左右兩部分，分別為32位的 L_{0} 和32位的 R_0。之后我們將 L_{16} 和 R_{16} 進行交換，得到作為IP逆置換的輸入：

R_i= L_{i-1} \oplus f(R_{i-1,K_i}),i = 1,2 \cdots 16 ，L_i=R_{i-1}

生成子密鑰

子密鑰的生成，經歷下面一系列步驟：首先對于64位密鑰，進行置換選擇，因為將用戶輸入的64 位經歷壓縮變成了56位，所以我們將左面和右面的各28位進行循環(huán)位移。左右兩部分分別按下列規(guī)則做循環(huán)移位：當flag = 1, 2,9,16，循環(huán)左移1位；其余情況循環(huán)左移2位。最后將得到的新的左右兩部分進行連接得到56位密鑰。

static char Move_Table[16]={
    1, 1, 2, 2, 2, 2, 2, 2, 
    1, 2, 2, 2, 2, 2, 2, 1
};

void SetKey(char KeyIn[8])  
{
    int i=0;
    static bool KeyBit[64]={0};  
    static bool *KiL=&KeyBit[0],*KiR=&KeyBit[28]; 
    ByteToBit(KeyBit,KeyIn,64); 
    TablePermute(KeyBit,KeyBit,PC1_Table,56); 
    for(i=0;i<16;i++)
    {
        LoopMove(KiL,28,Move_Table[i]); 
        LoopMove(KiR,28,Move_Table[i]);
        TablePermute(SubKey[i],KeyBit,PC2_Table,48); 
    }       
}

Feistel 函數

image

對半塊的 Feistel 操作分為以下五步：

  1. 展開：32位的半塊通過重復一半位的展開排列擴展到48位。輸出由8個6位（48位）塊組成，每個塊包含4個相應的輸入位的副本，加上從每個輸入塊到任意一側的相鄰位的副本。
  2. 密鑰混合：結果與使用 XOR 操作的子密鑰結合。16個48位的子鍵（每個輪一個）由主鍵派生，使用下面描述的鍵調度。
  3. 替換：將子鍵混合后，將塊分割成8個6位的塊，再用 S-box 或替換盒進行處理。根據一個非線性變換，八個 S-box 中的每一個都用四個輸出位替換了它的六個輸入位。S-box 提供了 DES 安全的核心，如果沒有它們，密碼就會是線性的，而且容易被破解。
  4. 排列：根據一個固定的排列，即 P-box，將s -box的32個輸出重新排列。這樣設計的目的是，經過排列后，這一輪中每個 S-box 輸出的比特被分散到下一輪的4個不同的 S-box 上。
  5. 置換：最后的 IP 逆置換同之前的 IP 置換基本相同，我們通過 IP 逆置換表，根據表中所示下標，找到相應位置進行置換。
const char IPR_Table[64]={              
    40,8,48,16,56,24,64,32, 
    39,7,47,15,55,23,63,31,
    38,6,46,14,54,22,62,30, 
    37,5,45,13,53,21,61,29,
    36,4,44,12,52,20,60,28, 
    35,3,43,11,51,19,59,27,
    34,2,42,10,50,18,58,26, 
    33,1,41, 9,49,17,57,25  
};

void F_Change(bool DatIn[32],bool DatKi[48]) 
{
    static bool MiR[48]={0};
    TablePermute(MiR,DatIn,E_Table,48); 
    Xor(MiR,DatKi,48);
    S_Change(DatIn,MiR);  
    TablePermute(DatIn,DatIn,P_Table,32);
}

實驗結果

如下三圖展示了實驗的結果（黃色代表明文，藍色代表暗碼，紅色表示密碼，綠色表示結果）

正確解碼

image
image

如上二圖表明，在給出正確的密碼后，可以得到對應的明文。

密碼錯誤

image

若密碼錯誤，將解碼出錯誤答案。

實驗參考

【1】Data Encryption Standard

【2】DES算法的詳細設計（簡單實現）

【3】深入理解并實現DES算法

【4】DES算法原理完整版

【5】安全體系（一）—— DES算法詳解

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容