1. 前言
DES是一種數據加密標準（ Data Encryption Standard） , 有30多年歷史，是一種對稱密碼算法，是第一個得到廣泛應用的密碼算法，是一種分組加密算法，輸入的明文為64位，密鑰為64位（實際上只有56位，原因是每隔7個比特設置一個奇偶校驗位），生成的密文分組長度為64位。但是現在已經不再安全。
課件來自我們老師上課的PPT。
2. Feistel網絡
我們可以參考這裡，Feistel講解
下面簡單說下：
Feistel網絡利用乘積密碼實現關鍵密碼模塊。所謂乘積密碼就是順序或循環地執行兩個或多個基本密碼模塊，提高密碼強度。其思想就是Shannon提出的利用乘積密碼
實現擴散和混淆。
Feistel網絡的加密結構：將2w bit明文分成為左右兩半、長為1 w bit的段，以L和R表示。然後進行n輪迭代，其第i輪迭代的輸入為上一輪（第i-1輪）輸出。
其中Ki是第i輪用的子密鑰， f是密碼設計者選取或設計密碼輪函數。 稱這種分組密碼算法為Feistel網絡（ Feistel Network） ， 它保證加密和解密可採用同一算法實施。
每次迭代稱為一輪(Round)。 相應函數f 稱作輪函數。
Feistel網絡的解密結構：Feistel解密過程本質上與加密過程一樣。密文作為輸入，使用子密鑰Ki的次序與加密過程相反， Kn,Kn-1,…,K1。保證了加密與解密過程可採用同一算法。
3. DES算法框架
輪函數：
Li=Ri-1；
Ri=Li-1⊕f(Ri-1, Ki)。
4. DES加密模塊
4.1 初始置換IP
4.2 DES的輪結構
擴充變換：擴充變換E的作用是將32比特的明文擴充為48比特。設m=m1m2…m31m32; c=c1c2…c47c48。滿足E(m)=c， c1=m32,c2=m1,…,c7=m4,…,c48=m1。
8個S盒：
每個S盒Sj將6比特輸入縮減為4比特輸出。 8個S盒總共將48比特輸入縮減為32比特輸出。
每個S盒的輸入為6比特串m=m1m2m3m4m5m6，輸出為4比特串c=c1c2c3c4。
將m1m6, m2m3m4m5, c1c2c3c4都用10進位來表示，則在下表中位於m1m6 (0~3)行 m2m3m4m5 (0~15)列的數就是S盒的輸出 c1c2c3c4(十進位轉化成二進位)。
例如若S1的輸入為100110，則通過查表(S1)輸出應該是表中的第2(10)行第3(0011)列的數字8，所以二進位輸出為1000。
置換P:
置換P將32比特的輸入，改變位置順序：輸出的第1位為輸入的第16位，輸出的第2位為輸入的第7位， …，輸出的第32位為輸入的第25位。
4.3 子密鑰生成算法
64位密鑰（8位奇偶校驗位，有效位為56位）經過置換選擇1、循環左移、置換選擇2等變換，產生出16個48位長的子密鑰。
置換選擇1：
64位密鑰分為8個字節。每個字節的前7位是真正的密鑰位，第8位是奇偶校驗位。奇偶校驗位可以從前7位密鑰位計算得出，不是隨機的，因而不起密鑰的作用。因此，DES真正的密鑰只有56位。
置換選擇1的作用有兩個：一是從64位密鑰中去掉8個奇偶校驗位；二是把其餘56位密鑰位打亂重排，且將前28位作為C0，後28位作為D0。
置換選擇1的矩陣如下：
循環左移：
每一次迭代，將Ci-1和Di-1按照一定的位數循環左移分別得到Ci和Di。
循環左移位數表如下：
置換選擇2
將Ci和Di合併成一個56位的中間數據，置換選擇2從中選擇出一個48位的子密鑰Ki。置換選擇2的矩陣如下：
縮減變換PC-1, PC-2 : PC-1將64比特串縮為56比特； PC-2將56比特長的串縮為48比特。兩個變換的輸出比特順序如下：
5. DES的加解密過程
DES的加密過程：
64位密鑰經子密鑰產生算法產生出16個48位子密鑰：K1,K2,...,K16，分別供第1次，第2次，...，第16次加密迭代使用。64位明文首先經過初始置換IP，將數據打亂重新排列並分成左右兩半，左邊32位構成L0，右邊32位構成R0。第i次加密迭代：由輪函數f實現子密鑰Ki對Ri-1的加密，結果為32位的數據組f ( Ri-1 , Ki )。f ( Ri-1 , Ki )再與Li-1模2相加，又得到一個32位的數據組Li-1 ⊕ f ( Ri-1 , Ki )。以Li ⊕ f ( Ri-1 , Ki )作為下一次加密迭代的Ri，以Ri-1作為下一次加密迭代的Li ( i = 1,2,...,16)。按照上一步的規則進行16次加密迭代。第16次加密迭代結束後，以R16為左，L16為右，合併產生一個64位的數據組。再經過逆初始置換IP-1，將數據重新排列，便得到64位密文。DES的解密過程：
64位密鑰經子密鑰產生算法產生出16個48位子密鑰：K1,K2,...,K16，分別供第1次，第2次，...，第16次解密迭代使用。64位密文首先經過初始置換IP，將數據打亂重新排列並分成左右兩半，左邊32位構成R16，右邊32位構成L16。第17-i次解密迭代：由輪函數f實現子密鑰Ki對Li的解密，結果為32位的數據組f ( Li , Ki )。f ( Li , Ki )再與Ri模2相加，又得到一個32位的數據組Ri ⊕ f ( Li , Ki )。以Ri ⊕ f ( Li , Ki )作為下一次解密迭代的Li-1，以Li作為下一次解密迭代的Li-1 ( i = 16,15,...,1)。按照上一步的規則進行16次解密迭代。第16次解密迭代結束後，以L0為左，R0為右，合併產生一個64位的數據組。再經過逆初始置換IP-1，將數據重新排列，便得到64位明文。6. DES的安全性
DES算法中除了S盒是非線性變換外，其餘變換均為線性變換，所以DES安全的關鍵是S盒（保密 ）。因為算法中使用了16次迭代，從而使得改變輸入明文或密鑰中的1位，密文都會發生大約32位的變化，具有良好的雪崩效應，大大提高了保密性。S盒用來提供混淆，使明文、密鑰、密文之間的關係錯綜複雜，而P置換用來提供擴散，把S盒提供的混淆作用充分擴散開來。這樣，S盒和P置換互相配合，形成了很強的抗差分攻擊和抗線性攻擊能力，其中抗差分攻擊能力更強些。
7. DES加密的一個例子
取16進位明文X： 0123456789ABCDEF
密鑰K為： 133457799BBCDFF1
去掉奇偶校驗位以二進位形式表示的密鑰是
00010010011010010101101111001001101101111011011111
111000
應用IP，我們得到：
L0=11001100000000001100110011111111
L1=R0=11110000101010101111000010101010
然後進行16輪加密。
最後對L16, R16使用IP-1得到密文： 85E813540F0AB405
8. java版的DES算法
DES工具類：
public class DESUtil {//置換選擇1矩陣 static int[] replace1C = { 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36 }; static int[] replace1D = { 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4 }; //循環左移位數表 static int[] moveNum = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1}; //置換選擇2矩陣 static int[] replace2 = { 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32 }; //初始置換矩陣 static int[] IP = { 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 }; //選擇運算矩陣 static int[] E = { 32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1 }; //代替函數組 static int[][][] S = { //S1 { {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7}, { 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8}, { 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0}, {15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13} }, //S2 { {15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10}, { 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5}, { 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15}, {13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9} }, //S3 { {10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8}, {13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1}, {13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7}, { 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12} }, //S4 { { 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15}, {13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9}, {10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4}, { 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14} }, //S5 { { 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9}, {14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6}, { 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14}, {11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3} }, //S6 { {12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11}, {10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8}, { 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6}, { 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13} }, //S7 { { 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1}, {13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6}, { 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2}, { 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12} }, //S8 { {13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7}, { 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2}, { 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8}, { 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11} } }; //置換運算矩陣 static int[] P = { 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25 }; //逆初始置換矩陣 static int[] rIP = { 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 };/***************************子密鑰的產生**********************************************************************/ /** * 子密鑰的產生 * @param sKey 64位密鑰 * @return 16個48位子密鑰 */ static byte[][] generateKeys(byte[] sKey) { byte[] C = new byte[28]; byte[] D = new byte[28]; byte[][] keys = new byte[16][48]; //置換選擇1 //一是從64位密鑰中去掉8個奇偶校驗位；二是把其餘56位密鑰位打亂重排 for (int i = 0; i < 28; i++) { C[i] = sKey[replace1C[i] - 1]; D[i] = sKey[replace1D[i] - 1]; } for (int i = 0; i < 16; i++) { //循環左移 C = RSHR(C, moveNum[i]); D = RSHR(D, moveNum[i]); //置換選擇2 for (int j = 0; j < 48; j++) { if (replace2[j] <= 28) keys[i][j] = C[replace2[j] - 1]; else keys[i][j] = D[replace2[j] - 29]; } } return keys; } /** * 循環左移 * @param b 數組 * @param n 位數 * @return */ static byte[] RSHR(byte[] b, int n) { String s = new String(b); s = (s + s.substring(0, n)).substring(n); return s.getBytes(); }/**********************初始置換IP**************************************************************************/ /** * 初始置換IP * @param text 64位數據 * @return */ static byte[] IP(byte[] text) { byte[] newtext = new byte[64]; for (int i = 0; i < 64; i++) newtext[i] = text[IP[i] - 1]; return newtext; }/**********************輪函數**************************************************************************/ /** * 輪函數 * @param A 32位輸入 * @param K 48位子密鑰 * @return 32位輸出 */ static byte[] f(byte[] A, byte[] K) { byte[] t = new byte[48]; byte[] r = new byte[32]; byte[] result = new byte[32]; //選擇運算E,擴充變換為48bit for (int i = 0; i < 48; i++) t[i] = A[E[i] - 1]; //模2相加，逐位異或，得到一個48位的結果 for (int i = 0; i < 48; i++) t[i] = (byte) (t[i] ^ K[i]); //代替函數組S， 8個S盒總共將48比特輸入縮減為32比特輸出。 for (int i = 0, a = 0; i < 48; i += 6, a += 4) { int j = t[i] * 2 + t[i + 5]; //b1b6 int k = t[i + 1] * 8 + t[i + 2] * 4 + t[i + 3] * 2 + t[i + 4]; //b2b3b4b5 byte[] b = Integer.toBinaryString(S[i / 6][j][k] + 16).substring(1).getBytes(); for (int n = 0; n < 4; n++) r[a + n] = (byte) (b[n] - '0'); } //置換運算P，重新打亂順序輸出 for (int i = 0; i < 32; i++) result[i] = r[P[i] - 1]; return result; }/**********************逆初始置換IP^-1**************************************************************************/ /** * 逆初始置換IP^-1 * @param text 64位數據 * @return */ static byte[] rIP(byte[] text) { byte[] newtext = new byte[64]; for (int i = 0; i < 64; i++) newtext[i] = text[rIP[i] - 1]; return newtext; }}
DES實現類：
public class DES {/** * 加密 * @param plaintext 64位明文 * @param sKey 64位密鑰 * @return 64位密文 */ static byte[] encrypt(byte[] plaintext, byte[] sKey) { byte[][] L = new byte[17][32]; byte[][] R = new byte[17][32]; byte[] ciphertext = new byte[64]; //子密鑰的產生 byte[][] K = DESUtil.generateKeys(sKey); //初始置換IP plaintext = DESUtil.IP(plaintext); //將明文分成左半部分L0和右半部分R0 for (int i = 0; i < 32; i++) { L[0][i] = plaintext[i]; R[0][i] = plaintext[i + 32]; } //加密迭代 for (int i = 1; i <= 16; i++) { L[i] = R[i - 1]; R[i] = xor(L[i - 1], DESUtil.f(R[i - 1], K[i - 1])); } //以R16為左半部分，L16為右半部分合併 for (int i = 0; i < 32; i++) { ciphertext[i] = R[16][i]; ciphertext[i + 32] = L[16][i]; } //逆初始置換IP^-1 ciphertext = DESUtil.rIP(ciphertext); return ciphertext; } /** * 解密 * @param ciphertext 64位密文 * @param sKey 64位密鑰 * @return 64位明文 */ static byte[] decrypt(byte[] ciphertext, byte[] sKey) { byte[][] L = new byte[17][32]; byte[][] R = new byte[17][32]; byte[] plaintext = new byte[64]; //子密鑰的產生 byte[][] K = DESUtil.generateKeys(sKey); //初始置換IP ciphertext = DESUtil.IP(ciphertext); //將密文分成左半部分R16和右半部分L16 for (int i = 0; i < 32; i++) { R[16][i] = ciphertext[i]; L[16][i] = ciphertext[i + 32]; } //解密迭代 for (int i = 16; i >= 1; i--) { L[i - 1] = xor(R[i], DESUtil.f(L[i], K[i - 1])); R[i - 1] = L[i]; R[i] = xor(L[i - 1], DESUtil.f(R[i - 1], K[i - 1])); } //以L0為左半部分，R0為右半部分合併 for (int i = 0; i < 32; i++) { plaintext[i] = L[0][i]; plaintext[i + 32] = R[0][i]; } //逆初始置換IP^-1 plaintext = DESUtil.rIP(plaintext); return plaintext; } /** * 兩數組異或 * @param a * @param b * @return */ static byte[] xor(byte[] a, byte[] b) { byte[] c = new byte[a.length]; for (int i = 0; i < a.length; i++) c[i] = (byte) (a[i] ^ b[i]); return c; }}
DES測試：
public class TestDES {public static void main(String[] args) { String strKey = "0011000100110010001100110011010000110101001101100011011100111000"; byte[] sKey = strKey.getBytes(); for (int i = 0; i < sKey.length; i++) sKey[i] -= '0'; System.out.print("密鑰："); printByteArr(sKey); String strPlain = "0011000000110001001100100011001100110100001101010011011000110111"; byte[] plaintext = strPlain.getBytes(); for (int i = 0; i < plaintext.length; i++) plaintext[i] -= '0'; System.out.print("明文："); printByteArr(plaintext); byte[] ciphertext = DES.encrypt(plaintext, sKey); System.out.print("密文："); printByteArr(ciphertext); byte[] plainText = DES.decrypt(ciphertext, sKey); System.out.print("明文："); printByteArr(plainText); } static void printByteArr(byte[] b) { for (int i = 0; i < b.length; i++) { System.out.print(b[i]); if (i % 8 == 7) System.out.print(" "); } System.out.println(); }}
測試結果：
9. 3DES
為提高安全性， 並利用實現DES的現有軟硬體， 將DES算法在多密鑰下重複使用。
三重DES：
兩個密鑰的三重DES。C=Ek1[Dk2[Ek1[P]]]
三個密鑰的三重DES。C=Ek3[Dk2[Ek1[P]]]
10. 結束語
我們學習了DES加密算法。DES作為對稱加密，其實現還是比較複雜的。我們來簡單回顧下，DES的加密過程。首先，我們需要生成16*48位的子密鑰（子密鑰的生成需要三步，即置換選擇1，循環左移和置換選擇2）。然後執行輪函數（分為四步，分別是擴充變換E，與密鑰按位異或，S盒變換，P盒變換）。最後進行逆初始變換即可得到加密後的密文。
解密與之類似。不再贅述。