DES je symetrická bloková šifra, která byla kryptografickým standardem do konce devadesátých let. Je považována za zastaralou a bezpečnostně překonanou.

Bloková šifra DES

DES (Data Encryption Standard) představuje obsolentní kryptografický standard pro blokové symetrické šifry. Není obecně bezpečný, úspěšná kryptoanalýza je na specializovaném hardware možná v čase do 24 hodin. Šifra pracuje se vstupem o velikosti 64 bitů a 64 bitovým klíčem (ovšem pouze 56 bitů klíče se využívá při šifrování, zbylých 8 bitů je kontrolních). Principiálně vychází z Feistelovy šifry. Právě pro slabý klíč používaný při šifrování se šifra nepovažuje za bezpečnou.

Šifrování i dešifrování bylo na většině architektur osobních počítačů ještě na konci 90 let hardwarově optimalizováno, tedy probíhalo rychle značně rychle. Především z tohoto důvodu vznikla šifra Triple DES, která částečně odstraňovala nedostatky DES. Používá klíč o velikosti 168 efektivních bitů. Šifrování probíhá pouhým skládáním jednotlivých šifer DES dle vzoru: C = Ek3(Dk2(Ek1(M))), kde E značí šifrovací funkci, D dešifrovací funkci a ki jednotlivé klíče. Tato šifra byla používaná především na přelomu tisíciletí, právě z důvodu rychlosti. Poté, co se hardware optimalizoval i pro šifru AES ztratila na významu. Stále se s ní však lze setkat.

Princip

Princip šifry DES

Šifrování probíhá v 16 rundách. Algoritmus začíná počáteční permutací, která nemá žádný zásadní vliv na bezpečnost systému, a končí finální permutací, která je inverzní permutace k počáteční.

Pořadí na výstupu: 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
Pořadí na vstupu:58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157
Počáteční permutace má tento tvar

Jednotlivé rundy mají následující strukturu:

  1. Expanzně permutační část: v této části se vstup (32 bitový, viz Feistel) expanduje na 48 bitový (pomocí duplikováním některých bitů, další se permutují).

    2. Pořadí na výstupu: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
    Pořadí na vstupu: 3212345456789891011121312131415161716171819202120212223242524252627282928293031321
    Expanzně permutační část má tento předpis

  2. XOR s příslušným klíčem pro danou rundu.

  3. S-box: jedná se o nelineární substituci. Jednotlivé bajty se substituují dle tabulky. Vstup se rozdělí po 6 bitech. První a poslední bit určuje číslo řádku v příslušné substituční tabulce, prostřední 4 bity určují sloupeček. Jednotlivé šestice se substituují dle předpisu 8 tabulek:

    Předpis substituce pro 1. šest bitů
    Řádek \ Sloupeček0123456789101112131415
    01441312151183106125907
    10157414213110612119538
    24114813621115129731050
    31512824917511314100613

    Zbývající substituční tabulky jsou představeny ve stejné logice níže:

    Předpis pro Si-tých 6 bitů ve vstupu
    S2
    1518146113497213120510
    3134715281412011069115
    0147111041315812693215
    1381013154211671205149
    S3
    1009146315511312711428
    1370934610285141211151
    1364981530111212510147
    1101306987415143115212
    S4
    7131430691012851112415
    1381156150347212110149
    1069012117131513145284
    3150610113894511127214
    S5
    2124171011685315130149
    1411212471315015103986
    4211110137815912563014
    1181271142136150910453
    S6
    1211015926801334147511
    1015427129561131401138
    9141552812370410113116
    4321295151011141760813
    S7
    4112141508133129751061
    1301174911014351221586
    1411131237141015680592
    6111381410795015142312
    S8
    1328461511110931450127
    1151381037412561101492
    7114191214206101315358
    2114741081315129035611

  4. P-box: proběhne opět permutace na základě předpisu. V tomto kroku se nic neexpanduje.

    Pořadí na výstupu: 1234567891011121314151617181920212223242526272829303132
    Pořadí na vstupu: 1672021291228171152326518311028241432273919133062211425

Dešifrování probíhá identicky v inverzním pořadí jednotlivých rund (standardní Feistel).

Generování klíče

Efektivní bity klíče se rozdělí na 2 poloviny. Generování probíhá opět v rundách (ale strany se na rozdíl od Feistela nepřeklápí). V jednotlivých rundách dochází ke spojování odrotovaných částí o určitý počet bitů. Platí, že v 1., 2., 9. a 16. rundě se rotuje o 1 bit, ve zbývajících o dva (vždy vlevo).

Princip generování klíče DES

Programování

Jedna z možností, jak implementovat algoritmus DES následuje (zdroj ZDE):

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "des.h"

static unsigned char ip_first[] = {
	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
};

/*
 * First permutation
 */
static void des_ip_first(unsigned char *current)
{
	unsigned char prev[8];
	unsigned char swap;
	int i;

	memcpy(prev, current, sizeof(prev));
	for (i = 0; i < 64; ++i) {
		/* swap the two bits using the matrice ip_first */
		swap = prev[BYTE_POS(ip_first[i] - 1)] & (1 << (BIT_POS(ip_first[i] - 1)));
		swap >>= BIT_POS(ip_first[i] - 1);
		swap <<= BIT_POS(i);
		current[BYTE_POS(i)] &= ~(1 << BIT_POS(i));
		current[BYTE_POS(i)] |= swap;
	}
}

static unsigned char ip_second[] = {
	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
};

/*
 * Second permutation
 */
static void des_ip_second(unsigned char *current)
{
	unsigned char prev[8];
	unsigned char swap;
	int i;

	memcpy(prev, current, sizeof(prev));
	for (i = 0; i < 64; ++i) {
		/* swap the two bits using the matrice ip_second */
		swap = prev[BYTE_POS(ip_second[i] - 1)] & (1 << BIT_POS(ip_second[i] - 1));
		swap >>= BIT_POS(ip_second[i] - 1);
		swap <<= BIT_POS(i);
		current[BYTE_POS(i)] &= ~(1 << BIT_POS(i));
		current[BYTE_POS(i)] |= swap;
	}
}

static unsigned char exp_right[] = {
	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
};

/*
 * Block expansion
 */
static void des_exp(unsigned char *exp)
{
	unsigned char block[4];
	unsigned char swap;
	int i;

	memcpy(block, exp, sizeof(block));
	for (i = 0; i < 48; ++i) {
		/* swap the two bits using the matrice exp_right */
		swap = block[BYTE_POS(exp_right[i] - 1)] & (1 << BIT_POS(exp_right[i] - 1));
		swap >>= BIT_POS(exp_right[i] - 1);
		swap <<= BIT_POS(i);
		exp[BYTE_POS(i)] &= ~(1 << BIT_POS(i));
		exp[BYTE_POS(i)] |= swap;
	}
}

static unsigned char 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 void des_p(unsigned char * s)
{
	unsigned char swap, tmp[4];
	int i;

	memcpy(tmp, s, sizeof(tmp));
	for (i = 0; i < 32; ++i) {
		/* swap the two bits using the matrice p */
		swap = tmp[BYTE_POS(p[i] - 1)] & (1 << BIT_POS(p[i] - 1));
		swap >>= BIT_POS(p[i] - 1);
		swap <<= BIT_POS(i);
		s[BYTE_POS(i)] &= ~(1 << BIT_POS(i));
		s[BYTE_POS(i)] |= swap;
	}
}

static unsigned char sboxes[8][4][16] = {

	{	/* s-box 1 */
		{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}
	},

	{	/* s-box 2 */
		{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}
	},

	{	/* s-box 3 */
		{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}
	},

	{	/* s-box 4 */
		{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}
	},


	{	/* s-box 5 */
		{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}
	},


	{	/* s-box 6 */
		{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}
	},

	{	/* s-box 7 */
		{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}
	},

	{	/* s-box 8 */
		{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}
	}
	/*
	 * I wish I knew emacs lisp ;) wasted 30 minuts copy/pasting, adding commas ...
	 */
};

/*
 * each rank in b is made of 6 linear bits from tmp
 */
static void des_split_6b(unsigned char * tmp, unsigned char * b)
{
	b[0] = (tmp[0] & 0xFC) >> 2;
	b[1] = ((tmp[0] & 0x03) << 4) | ((tmp[1] & 0xF0) >> 4);
	b[2] = ((tmp[1] & 0x0F) << 2) | ((tmp[2] & 0xC0) >> 6);
	b[3] = tmp[2] & 0x3F;
	b[4] = (tmp[3] & 0xFC) >> 2;
	b[5] = ((tmp[3] & 0x03) << 4) | ((tmp[4] & 0xF0) >> 4);
	b[6] = ((tmp[4] & 0x0F) << 2) | ((tmp[5] & 0xC0) >> 6);
	b[7] = tmp[5] & 0x3F;
}

/*
 * construct S picking 8 times 4bits from sboxes, then permute and xor it with
 * the left key.
 */
static void des_sub_s(unsigned char *s, unsigned char *b, unsigned char *left)
{
	int i;
	unsigned char row, col;

	memset(s, 0, sizeof(s));
	for (i = 0; i < 8; ++i) {
		row = (b[i] & 0x01) | ((b[i] & 0x20) >> 4);
		col = (b[i] & 0x1E) >> 1;
		s[i / 2] |= sboxes[i][row][col] << (!(i % 2) ? 4 : 0);
	}

	des_p(s);

	s[0] ^= left[0];
	s[1] ^= left[1];
	s[2] ^= left[2];
	s[3] ^= left[3];
}

/*
 * Main entry to cipher one block
 */
void des_cipher_block(struct des *des, unsigned char *block)
{
	int i, j, subkey_rank;
	unsigned char left[4], right[6], tmp[6], b[8], s[4], oldr[4];

	des_ip_first(block);
	memcpy(left, block, sizeof(left));
	memcpy(right, block + 4, 4 * sizeof(unsigned char));
	for (i = 0; i < 16; ++i) {
		memcpy(oldr, right, sizeof(oldr));
		des_exp(right);
		/* the only difference between crypt/encrypt is the order of subkeys */
		subkey_rank = des->op == ENCRYPT ? i : (15 - i);
		for (j = 0; j < 6; ++j)
			tmp[j] = right[j] ^ des->subkeys[subkey_rank][j];
		des_split_6b(tmp, b);
		des_sub_s(s, b, left);
		memcpy(left, oldr, sizeof(left));
		memcpy(right, s, sizeof(s));
	}
	memcpy(block, right, 4 * sizeof(unsigned char));
	memcpy(block + 4, left, sizeof(left));
	des_ip_second(block);
}