DES Algorithm

對稱式密碼學，主要分為兩個大項，stream cipher 和 block cipger，下文主要會介紹block cipher其中的一個例子：DES 。

123
(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

I P (x)

，簡單來說這一個function所做的事情是將這64 bits的位元，做順序的重排，但其中所有 bit 是 1 和 bit 是 0 的個數分別都不會被改變。

下一部分我們將來介紹:

$f$
$f u n c t i o n$
$s u b k e y$
$d e r i v a t i o n$
$f u n c i t o n$

$f$
$f u n c t i o n$

我們先來看看

f

f u n c t i o n

的架構圖。

(Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl)

對照著上面的DES 架構圖，可得知

f

f u n c t i o n

的 input 為

R_{i - 1}

，透過一個

e x p a n s i o n

f u n c t i o n

變成output 48 bits 後，才和 subkey

k_{i}

做 XOR 運算，下一步則是將48 bits 切割成 8 個 6 bits 為一組的bit string，分別帶入

S_{i}

f u n c t i o n

做代換，最後將各 8 個 4 bits 為一組的 bit string 做合併成 32 bits，經過一個

p e r m u t a t i o n

，輸出最後結果。

簡單來說

f

f u n t i o n

是一個 32 bits 進，32 bits 出的

f u n c t i o n

，其中輸入需要

R_{i - 1}

、subkey

k_{i}

。

那麼permutation 到底怎麼做出來的呢? 我們給出下列一個對映表，相信大家就可以很清楚知道了。

(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 - b o x$

S - b o x

，是一個 6 bits 進， 4 bits 出的 function，我們一樣透過圖片來介紹會比較清楚，注意每一個

S_{i}

所對映的表都是不一樣的。

(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} - b o x

運算將會是表上的第3列，第2行 ( 注意index )，即是 08，我們再將其轉換成 4 bits 二進位表示後，即位最後輸出結果，

8 = (1000)_{2}

。

$s u b k e y$
$d e r i v a t i o n$
$f u n c i t o n$

此部分和 DES 結構圖極為相似，其中

P C - 1

、

P C - 2

分別為兩個不同的

p e r m u t a t i o n

f u n c t i o n

。

(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;
}

DES Algorithm

Structure

f function

S−box

subkey derivation funciton

簡單撰寫C語言實作

DES.h

DES.c

test.c

tags: Cryptography 密碼學 DES

Read more

List of Articles

Elliptic Curve Cryptorgraphy

rand() function in C lib

密碼學簡介(一)_Cryptography

$f$
$f u n c t i o n$

$S - b o x$

$s u b k e y$
$d e r i v a t i o n$
$f u n c i t o n$

tags: `Cryptography` `密碼學` `DES`