# DES Algorithm
[豪難]: 真的好難
對稱式密碼學，主要分為兩個大項，stream cipher 和 block cipger，下文主要會介紹block cipher其中的一個例子：DES 。
(Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)
**Stream 可以想像是一次加密1個 bits，block ciphper 則是一次加密多個bits，我們稱這多個bits為一個block。**
---
兩大主要概念被在許多密碼演算法可見。
* **Confusion** ： an encryption operation where the relationship between key and ciphertext is obscured.
* **Diffusion** is an encryption operation where the influence of one plaintext symbol is spread over many ciphertext symbols with the goal of hiding statistical properties of the plaintext.
> **Confusion** 主要使加密出來的明文和密鑰的關係模糊化，Diffusion主要使改變明文的一些小地方將會使結果更改很多。例如：兩個明文只差了1個bit，但結果卻是截然不同的。
---
## Structure
DES主要為64 bits進，64 bits出的block cipher，其中搭配key size 為 56 bits。意味著DES將可以一次加密64 bits。DES 主要以 Feistel network 為架構，DES的加解密運算其實實際上是一樣的，這是 Feistel network的一個主要特色。
(Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)
可以看到DES做了16次相同的操作，但其中的subkey是不一樣的。$L_i$ 和 $R_i$ 分別代表各一半的bit，所以是各32 bits 的長度。由圖片可知一開始 plaintext $x$，先透過一個 permutation function $IP(x)$，簡單來說這一個function所做的事情是將這64 bits的位元，做順序的重排，但其中所有 bit 是 1 和 bit 是 0 的個數分別都不會被改變。
下一部分我們將來介紹:
* $f$ $function$
* $subkey$ $derivation$ $funciton$
---
## $f$ $function$
我們先來看看 $f$ $function$ 的架構圖。
(Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)
對照著上面的DES 架構圖，可得知$f$ $function$ 的 input 為 $R_{i-1}$，透過一個 $expansion$ $function$ 變成output 48 bits 後，才和 subkey $k_i$ 做 XOR 運算，下一步則是將48 bits 切割成 8 個 6 bits 為一組的bit string，分別帶入 $S_i$ $function$ 做代換，最後將各 8 個 4 bits 為一組的 bit string 做合併成 32 bits，經過一個 $permutation$，輸出最後結果。
簡單來說 $f$ $funtion$ 是一個 32 bits 進，32 bits 出的 $function$，其中輸入需要 $R_{i-1}$、subkey $k_i$。
---
那麼permutation 到底怎麼做出來的呢? 我們給出下列一個對映表，相信大家就可以很清楚知道了。
(Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)
(Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)
$E$ 這張對映表的讀法，將第一個bit轉換成原本地32個bit，什麼意思呢?我們簡單舉一個例子，假如原本 32 bits 長成下列樣子，只有第32 bit 是 1 。
$$00000000000000000000000000000001$$
那麼經過表 $E$ 的第一個運算，將會變成以下長像
$$10000000000000000000000000000000$$
---
## $S-box$
$S-box$ ， 是一個 6 bits 進， 4 bits 出的 function，我們一樣透過圖片來介紹會比較清楚，注意每一個 $S_i$ 所對映的表都是不一樣的。
(Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)
(Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)
我們來看 $$100101$$ 首先中間的4 bits 代表colum number
$$(0010)_2 = 2$$
所以代表第2行。
接下來把最前面bit 和最後面bit 拼起來
$$(11)_2 = 3$$
所以代表第3列。
因此 $100101$ 透過 $S_1-box$ 運算將會是表上的第3列，第2行 ( 注意index )，即是 08，我們再將其轉換成 4 bits 二進位表示後，即位最後輸出結果， $8=(1000)_2$。
---
## $subkey$ $derivation$ $funciton$
此部分和 DES 結構圖極為相似，其中 $PC-1$、$PC-2$ 分別為兩個不同的 $permutation$ $function$。
(Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)
---
簡單的教學影片
https://www.youtube.com/watch?v=Y61qn_SQl40
---
## 簡單撰寫C語言實作
https://github.com/kaichieh0524/DES_C_implement
供大家學習使用，(關於mode of operation 之後空閒再補上 XD，程式碼也需要再修，總之先上一版)
---
### DES.h
``` c=
#ifndef DES_H
#define DES_H
#include<stdlib.h>
#include<stdio.h>
#include<stdint.h>
#include<string.h>
#define mask28bit 268435455UL
/*====================================================================
*======================== static variable ============================
*=====================================================================
*/
static int IP[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 };
static int IP_inv[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 };
static int E[48] = { 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[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 } };
static int P[32] = { 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 PC_1[56] = { 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 };
static int PC_2[48] = { 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 shift_table[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };
#endif
```
### DES.c
```c=
#include"DES.h"
/* This is a project to implementation DES using C language, and it is just for
* self-learning.
*/
/*====================================================================
*============================ function ===============================
*=====================================================================
*/
uint32_t left_rot(uint32_t value, int shift) {
if ((shift %= 28) == 0)
return value;
return ((value << shift) | (value >> (28 - shift))) & mask28bit;
}
uint32_t right_rot(uint32_t value, int shift) {
if ((shift %= 28) == 0)
return value;
return ((value >> shift) | (value << (28 - shift))) & mask28bit;
}
uint8_t PC_1_permutation(uint8_t* key){
uint8_t res[8];
for (int j = 0; j < 8; j++){
uint8_t temp = 0;
for (int i = j*7; i < (j+1)*7; i++){
int k_1 = (PC_1[i] >> 3);
int k_2 = PC_1[i] & 0b111;
if (key[k_1] & (1 << ( 8 - k_2)) ){
temp = (temp << 1) + 1;
}
else{
temp = temp << 1;
}
}
res[j] = temp;
}
memcpy(key, res, sizeof(uint8_t)*8);
return 0;
}
uint8_t PC_2_permutation(uint8_t* key, uint8_t* subkey){
uint8_t res[8];
for (int j = 0; j < 8; j++){
uint8_t temp = 0;
for (int i = j*6; i < (j+1)*6; i++){
int k_1 = (PC_2[i] - 1) / 7;
int k_2 = (PC_2[i] - 1) % 7;
if (key[k_1] & (1 << (6 - k_2)) ){
temp = (temp << 1) + 1;
}
else{
temp = temp << 1;
}
}
res[j] = temp;
}
memcpy(subkey, res, sizeof(uint8_t)*8);
return 0;
}
uint8_t IP_or_IP_inv(uint8_t* plaintext, const int* table){
uint8_t res[8];
for (int j = 0; j < 8; j++){
uint8_t temp = 0;
for (int i = j*8; i < (j+1)*8; i++){
int k_1 = (table[i] - 1) / 8;
int k_2 = (table[i] - 1) % 8;
if (plaintext[k_1] & (1 << (7 - k_2)) ){
temp = (temp << 1) + 1;
}
else{
temp = temp << 1;
}
}
res[j] = temp;
}
memcpy(plaintext, res, sizeof(uint8_t)*8);
return 0;
}
uint8_t Expansion(uint8_t* R, uint8_t* output){
uint8_t res[8];
for (int j = 0; j < 8; j++){
uint8_t temp = 0;
for (int i = j*6; i < (j+1)*6; i++){
int k_1 = (E[i] - 1) / 8;
int k_2 = (E[i] - 1) % 8;
if (R[k_1] & (1 << (7 - k_2)) ){
temp = (temp << 1) + 1;
}
else{
temp = temp << 1;
}
}
res[j] = temp;
}
memcpy(output, res, sizeof(uint8_t)*8);
return 0;
}
uint8_t S_box(uint8_t* xored_R){
for (int i = 0; i < 8; i++){
int column = (xored_R[i] & 0b011110) >> 1;
int row = ((xored_R[i] & 0b100000) >> 4) | (xored_R[i] & 0b000001);
xored_R[i] = S[i][row][column];
}
return 0;
}
uint8_t P_perm_and_xored(uint8_t* s_boxed, uint8_t* plaintext){
uint8_t res[4];
for (int j = 0; j < 4; j++){
uint8_t temp = 0;
for (int i = j*8; i < (j+1)*8; i++){
int k_1 = (P[i] - 1) / 4;
int k_2 = (P[i] - 1) % 4;
if (s_boxed[k_1] & (1 << (3 - k_2)) ){
temp = (temp << 1) + 1;
}
else{
temp = temp << 1;
}
}
res[j] = temp ^ plaintext[j];
}
memcpy(plaintext, res, sizeof(uint8_t)*4);
return 0;
}
uint8_t DES(uint8_t* plaintext, uint8_t* ciphertext, uint8_t* key){
uint8_t subkey[8];
uint8_t expansion[8];
uint32_t temp1, temp2;
memcpy(ciphertext, plaintext, sizeof(uint8_t)*8);
IP_or_IP_inv(ciphertext, IP);
PC_1_permutation(key);
/* 16 round encrypt*/
for (int j = 0; j < 16; j++){
/* compute round key */
memset(subkey, 0, sizeof(subkey));
memset(&temp1, 0, sizeof(temp1));
memset(&temp2, 0, sizeof(temp2));
temp1 = (key[0] << 21) | (key[1] << 14) | (key[2] << 7) | key[3];
temp2 = (key[4] << 21) | (key[5] << 14) | (key[6] << 7) | key[7];
temp1 = left_rot(temp1, shift_table[j]);
temp2 = left_rot(temp2, shift_table[j]);
for (int i = 0; i < 4; i++){
key[3 - i] = temp1 & 0b1111111;
key[7 - i] = temp2 & 0b1111111;
temp1 = temp1 >> 7;
temp2 = temp2 >> 7;
}
PC_2_permutation(key, subkey);
/* compute f function */
Expansion(ciphertext+4, expansion);
/* XOR operation */
for (int i = 0; i < 8; i++){
expansion[i] = expansion[i] ^ subkey[i];
}
S_box(expansion);
P_perm_and_xored(expansion, ciphertext);
/* exchange L and R*/
if(j != 15){
for (int i = 0; i < 4; i++){
ciphertext[i] = ciphertext[i] ^ ciphertext[4 + i];
ciphertext[4 + i] = ciphertext[i] ^ ciphertext [4 + i];
ciphertext[i] = ciphertext[i] ^ ciphertext[4 + i];
}
}
/* printf("round [%d] : ", j+1);
for (int i = 0; i < 8; i++){
printf("%02X", ciphertext[i]);
if(i+1==4){
printf(" ");
}
}
printf("\n"); */
}
IP_or_IP_inv(ciphertext, IP_inv);
/* printf("\n================================================\n");
printf("Ciphertext : ");
for (int i = 0; i < 8; i++){
printf("%02X", ciphertext[i]);
} */
return 0;
}
```
### test.c
```c=
#include"DES.h"
static uint8_t test_plaintext[8] = {0x12, 0x34, 0x56, 0xAB, 0xCD, 0x13, 0x25, 0x36};
static uint8_t test_key[8] = {0xAA, 0xBB, 0x09, 0x18, 0x27, 0x36, 0xCC, 0xDD};
static uint8_t test_ciphertext[8] = {0xC0, 0xB7, 0xA8, 0xD0, 0x5F, 0x3A, 0x82, 0x9C};
int main(int argc, char* argv[]){
uint8_t plaintext[8];
uint8_t ciphertext[8];
uint8_t key[8];
memcpy(plaintext, test_plaintext, sizeof(uint8_t)*8);
memcpy(key, test_key, sizeof(uint8_t)*8);
printf("================================================\n");
printf("Plaintext : ");
for (int i = 0; i < 8; i++){
printf("%02X", plaintext[i]);
}
DES(plaintext, ciphertext, key);
printf("\n================================================\n");
printf("Ciphertext : ");
for (int i = 0; i < 8; i++){
printf("%02X", ciphertext[i]);
}
if(memcmp(ciphertext, test_ciphertext, sizeof(uint8_t)*8)!=0){
printf("\nERROR : the encryption does not match the test case\n");
return -1;
}
printf("\n================================================\n");
return 0;
}
```
###### tags: `Cryptography` `密碼學` `DES`
Google Drive
Gist
Clipboard
Sign in with Wallet
