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

#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

#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

#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