# 【IS】DES #2
## DES的歷史
* 這部分其實不太重要，但因為蠻有趣的就寫下來了XD
* 只想看實作的人可以直接下拉。
### 開發
- 在電腦資訊準備發展起來的時間點，還沒有所謂**國家認證的標準加密法**，因此大家都各做各的加密法。
- 當時超級龍頭公司**IBM**也不例外地在研發自己的加密法，而他們不只有自己研究，還和NSA(美國國家安全局)一同研發，最後研發出了DES(後來有些微調整，但也可以說是DES的前身了)。
- 後來大家意識到資安的重要性之後，NBS(國家標準局)辦了一場投稿大賽，讓大家投稿自己的加密演算法，最好的那個就會成為標準。
- 大家都踴躍的投稿，IBM也不例外。然後NBS就發現一個問題......他們不知道哪個比較好，因此只好求助同樣為國家單位的NSA來協助評測。
- 而NSA最後當然選擇了自己有協助開發的DES為標準。然而這導致後續的爭議不斷。
### 爭議
- 爭議是質疑DES不夠好嗎？錯！是**太好了**！
- DES不愧是龍頭公司IBM和國家單位共同研究出來的，它強到甚至對2000年常見的攻擊手段有防禦能力。也就是說DES領先了世界上加密相關的學者們大約30年。
- 而且DES不但強，實作也十分簡單。大多只用到一些table位移和XOR等運算。
- DES實作中使用到的幾個talbe(尤其是S-Box)基本上沒有明顯邏輯，卻有如此好的效果，因此被大多人懷疑藏有後門，只要使用某一組萬能表就必定能解密。
### 後續
- 即便大家一直懷疑DES有問題，卻也找不到所謂的後門，DES就這樣繼續用了幾年後，還是被暴力破解法給破解了。
- 由於DES設計上只支援`56`bits的金鑰，在現今的硬體強度之下簡直不堪一擊。又加上後門的風險，後來標準加密法就被AES取代。
## DES實作
### 輸入輸出
* DES加密法的明文、Key、密文長度皆為`64`bits。
* 我們假設輸入格式是十六進制，直接使用argc的方式讀入。
```C++
/* Input: 0x1259ACBD6544FCDA 0xabcdef0123456789 */
/* Transform to unsigned long long int by stringstream. */
/* Note that you should use unsigned long long int or it will overflow. */
unsigned long long int key;
unsigned long long int plaintext;
string str = argc[1];
stringstream ss(str);
ss >> std::hex >> key;
str = argc[2];
ss = stringstream(argc[2]);
ss >> std::hex >> plaintext;
```
* 為了方便後續處理，我們將數字轉成Vector的型態。
```C++
vector<int> ChangeToVector(unsigned long long int data)
{
vector<int> newData;
while (data != 0)
{
newData.push_back(data % 2);
data /= 2;
}
return newData;
}
```
```C++
// Transform to vector
vector<int> v_key, v_plaintext;
v_key = ChangeToVector(key);
while ((int)v_key.size() != 64) v_key.push_back(0);
v_plaintext = ChangeToVector(plaintext);
while ((int)v_plaintext.size() != 64)v_plaintext.push_back(0);
reverse(v_plaintext.begin(), v_plaintext.end());
reverse(v_key.begin(), v_key.end());
```
* 記得要將vector補滿`64`bits。
* reverse是為了讓最左邊的數字擺在`vector[0]`，方便理解。
### 第一次換位
* 單純地將明文做一次換位的動作，這個換位是**固定的**。
* 根據下面的表作換位，代表將第`58`個bit換到第`1`個去，以此類推。
```
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
```
* 我們可以很簡單的做一個轉換用的function。
```C++
vector<int> ChangeWithTable(vector<int> data, vector<int> table)
{
int s = table.size();
vector<int> newdata;
for (int i = 0; i < s; i++)
{
if ((int)data.size() < table[i] - 1)
throw string("table error!");
newdata.push_back(data[table[i] - 1]);
}
return newdata;
}
```
* 接下來只要初始化好table的內容，就可以很快速地轉換。
```C++
const vector<int> table_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 };
// Initial permutation
v_plaintext = ChangeWithTable(v_plaintext, table_IP);
```
### 明文、鑰匙前處理
* 接著我們將明文切成左右兩個部分。
```C++
// Break plaintext to 2 parts
////////////////////////////////////////////
//
// l[0] l[1] ... l[31] r[0] r[1] ... r[31]
//
////////////////////////////////////////////
vector<int> l_plaintext, r_plaintext;
for (int i = 0; i < (int)v_plaintext.size(); i++)
{
if (i < (int)v_plaintext.size() / 2)
l_plaintext.push_back(v_plaintext[i]);
else
r_plaintext.push_back(v_plaintext[i]);
}
```
* 然後將key壓縮成`56`bits。
* 這代表key裡面有`8`個bit根本沒用到。
```C++
// 64 bits of key goto PC1 to 56 bits
const vector<int> table_PC1{
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,
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 };
v_key = ChangeWithTable(v_key, table_PC1);
```
* 然後我們將key也拆成兩個部分。
```C++
// Break key to 2 parts
vector<int> l_subkey, r_subkey;
for (int i = 0; i < (int)v_key.size(); i++)
{
if (i < (int)v_key.size() / 2)
l_subkey.push_back(v_key[i]);
else
r_subkey.push_back(v_key[i]);
}
```
### 16 Rounds
* 接下來我們會進行`16`次**round**。
* 每一個round包含以下動作：
* 位移兩把subkey
* 將subkey合併且丟進table重組
* 利用key和右邊的明文做**FeistelCipher**
* 將結果與左邊的明文做XOR後，放到明文右邊
* 將原本的右邊明文放置左邊
```C++
// 16 rounds
// L' = R
// R' = L XOR F(R,k)
for (int i = 0; i < 16; i++)
{
// get subkey
KeyRotate(l_subkey, i);
KeyRotate(r_subkey, i);
vector<int> subkey = l_subkey;
subkey.insert(subkey.end(), r_subkey.begin(), r_subkey.end());
subkey = ChangeWithTable(subkey, table_PC2);
// Function F
vector<int> temp;
temp = FeistelCipher(r_plaintext, subkey);
for (int j = 0; j < 32; j++)
{
temp[j] = temp[j] ^ l_plaintext[j];
}
l_plaintext = r_plaintext;
r_plaintext = temp;
}
```
### Subkey
* 其中位移鑰匙的部分，左右兩邊的方式是一樣的。
* 位移是往左位移，其中第`1` `2` `9` `16` 次只位移一個bit，否則位移兩次。
```C++
void KeyRotate(vector<int>& key, int round)
{
key.push_back(key.front());
key.erase(key.begin());
if (round != 0 && round != 1 && round != 8 && round != 15)
{
key.push_back(key.front());
key.erase(key.begin());
}
}
```
* 然後是位移完的鑰匙使用的table。
```C++
const vector<int> table_PC2{
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 };
```
### FeistelCipher(Function F)
* 再來是FeistelCipher，俗稱Function F。
* 內容稍微有點多，但也是DES最核心的部分。
* 先將傳進來的右邊明文做一個增廣，一樣直接用前面的table function即可。
```C++
const vector<int> table_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 };
```
* 然後讓`48`bits的右邊明文對前面處理完的subkey做XOR。
* 將結果切成8等分，每一份有`6`bits；拿去做**S_BOX**的運算。
* 將八個BOX的結果合併起來，得到`32`bits的密文，再做一次table位移即完成。
```C++
const vector<int> table_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 };
```
```C++
vector<int> FeistelCipher(vector<int> R, vector<int> subkey)
{
// Expansion R to 48 bits
R = ChangeWithTable(R, table_E);
if (R.size() != 48 || subkey.size() != 48)
{
throw string("Function F error!");
}
for (int i = 0; i < 48; i++)
{
R[i] = R[i] ^ subkey[i];
}
// S-Box substitution
vector<int> s_box[8];
for (int i = 0; i < 8; i++)
{
vector<int> sub_R(R.begin() + i * 6, R.begin() + (i + 1) * 6);
s_box[i] = S_Box(sub_R, i);
}
R.clear();
for (int i = 0; i < 8; i++)
{
R.insert(R.end(), s_box[i].begin(), s_box[i].end());
}
if ((int)R.size() != 32)
throw string("S-Box output error!");
R = ChangeWithTable(R, table_P);
if ((int)R.size() != 32)
throw string("Function F output error!");
return R;
}
```
### S_Box
* S_Box其實就是一個查表的動作。
* 輸入為`6`bits，我們將這`6`bits拆成頭尾兩個和中間四個，分別對應到直行和橫列的索引值。
* 查到的數字轉換為二進制即為輸出的`4`bits。
```C++
const int table_s_box[8][4][16] = {
{
{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},
},
{
{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},
},
{
{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},
},
{
{ 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},
},
{
{ 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},
},
{
{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},
},
{
{ 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},
},
{
{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},
}
};
```
* 須隨時注意bit數是否有誤，然後記得八個S_BOX都不一樣。
```C++
vector<int> S_Box(vector<int> input, int boxID)
{
if ((int)input.size() != 6)
throw string("S-Box error!");
int row = input.front() * 2 + input.back();
int col = input[4] + input[3] * 2 + input[2] * 4 + input[1] * 8;
int temp = table_s_box[boxID][row][col];
vector<int> newdata;
for (int i = 0; i < 4; i++)
{
newdata.push_back(temp % 2);
temp /= 2;
}
reverse(newdata.begin(), newdata.end());
if ((int)newdata.size() != 4)
throw string("S-box error!");
return newdata;
}
```
### 最後處理
* 完成十六round後其實已經差不多結束了。
* 最後將<u>左邊接到右邊後面</u>，因為最後一次其實不需要交換。
```C++
// Combine two part of plaintext, change back left and right
v_plaintext = r_plaintext;
v_plaintext.insert(v_plaintext.end(), l_plaintext.begin(), l_plaintext.end());
```
* 然後再做一個table位移就完成啦！
```C++
const vector<int> table_IPP{
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 };
// Final permutation
v_plaintext = ChangeWithTable(v_plaintext, table_IPP);
```
* 如果你想將vector轉換回去，用for loop跑即可。
```C++
// Transform to hex format
plaintext = 0;
for (int i = 0; i < 64; i++)
{
plaintext <<= 1;
plaintext += v_plaintext[i];
}
cout << "0x" << std::uppercase << std::hex << plaintext;
```
###### tags: `IS` `note`
Sign in with Wallet
Connect another wallet