Algoritmus DES bol štandardizovaný inštitúciou ANSI. Označuje
sa tiež ako šifrovací algoritmus DEA (Data Encryption Algorithm).
Od 80. rokov je platným štandardom v celom svete na základe
definície medzinárodnou organizáciou ISO (International Standardization
Organization) ako DEA-1.
Tento algoritmus je predstaviteľom blokového šifrátora, ktorý
šifruje údaje po 64 bitových blokoch. Vstupom šifrátora je
64 bitový text (plaintext) a výstupom je 64 bitový zašifrovaný
text (cipher - šifra). Tento algoritmus predstavuje model
symetrickej kryptografie, tj. na šifrovanie a dešifrovanie
používa rovnaký kľúč. Kľúč má dĺžku 64 bitov, ale pri šifrovaní
textu sa využíva len 56 bitov. Zvyšné bity (každý 8. bit)
sa môžu využiť napríklad ako paritné.
Šifrovaný blok dát najskôr prejde počiatočnou permutáciou
(Initial permutation - IP), potom komplexným
výpočtom založenom na kľúči a nakoniec inverznou permutáciou
IP-1 k IP. Komplexný výpočet môže
byť zjednodušene definovaný funkciou f, nazývanou šifrovacia
funkcia (cipher function) a funkciou KS (key
schedule). Po počiatočnej permutácii sa text rozdelí na dve
polovice L a R po 32 bitoch. Následne
sa vykoná komplexný výpočet - 16 round identických operácií
(funkcia f), kde nastáva kombinácia dát s kľúčom.
Po 16. operácii sa L a R polovica spojí a na záver sa vykoná
záverečná permutácia.
Komplexný výpočet (samotné šifrovanie) je znázornený na obr. 1.
Obr. 1 Šifrovací výpočet
64 bitov vstupného bloku dát sa v počiatočnej faze permutuje podľa Tab. 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
Tab. 1 Permutácia IP
Ide v podstate o výmenu poradia jednotlivých bitov, a to
tak, že na prvé miesto sa dá 58. bit, na druhé miesto 50.
bit, atď. Takýto permutovaný blok je potom vstupom pre šifrovací
výpočet. Jeho výstup, tzv. preoutput, sa znova permutuje
(IP-1) inverzným spôsobom k permutácii
IP podľa Tab. 2.
Nech K je blok 48 bitov vybratých zo 64-bitového
kľúča. Potom výstup L'R' ľubovoľnej iterácie
so vstupom LR môžeme napísať takto:
L' = R
(1) R'= L xor f(R,K)
Ako bolo spomenuté vyššie, vstupom prvej iterácie je permutovaný
blok. Ak L'R' je výstupom 16. iterácie, potom
R'L' je tzv. preotput block. Pri každej
iterácii je rozdielny blok K kľúčov vyberaný
zo 64-bitového kľúča nazývaného KEY.
Podrobnejšie môžeme iterácie opísať s (2) tak, že KS
je funkciou, ktorej vstupnými operandmi sú celé číslo n v
rozsahu 1 až 16 a 64-bitový blok KEY a výstupom
je 48-bitový blok Kn predstavujúci permutovaný
výber bitov z KEY.
Kn = KS(n,KEY) (2)
KS sa nazýva "key schedule", lebo blok K
použitý v n-tej iterácii (1) je blokom Kn
v (2). Schéma funkcie KS je znázornená na obr 2.
Obr. 2 Funkcia KS
Jeden bit z každého oktetu bitov kľúča KEY je
možné použiť na detekciu chyby v generovaní kľúča. Sú to bity
8,16,...,64 a používajú sa ako paritné bity pre každý byte.
Predtým, ako sa daný kľúč použije, prechádza ešte dvoma permutáciami
PC-1 a PC-2 (permutation choice)
podľa Tab. 3 a Tab. 5 a posuvom left shift podľa Tab. 4.
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
64
46
38
30
22
14
6
61
53
45
37
29
21
13
5
28
20
12
4
Tab. 3 Permutácia PC-1
Horná časť Tab. 3 ukazuje, ako sú vyberané bity pre C(
) a dolná ukazuje výber bitov pre D(
). Týmito funkciami definujeme, ako sa z blokov
Cn-1 a Dn-1
vytvoria bloky Cn a Dn
pre n = 1,2,...,16.
Tab. 4 ukazuje tento spôsob pomocou posuvu bitov doľava
(left shift).
iterácia
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
počet posuvov
1
1
2
2
2
2
2
2
1
2
2
2
2
2
2
1
Tab. 4 Posuv bitov kľúča - left shift
Napríklad, C3 a D3 dostanem z
C2 a D2 posuvom bitov 2x doľava.
Tab. 5 permutácie PC-2 ukazuje, ako sú bity
kľúča Kn priradené k CnDn.
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
Tab. 5 Permutácia PC-2
Nech L0 a R0
sú L a R, Ln
a Rn sú L' a R'
z (1), kde L a R sú Ln-1
a Rn-1, K je Kn
a n je z intervalu <1,16>.
Potom
Ln = Rn-1 (3) Rn = Ln-1 xor f(Rn-1, Kn )
Celkovým výsledkom (preoutput block) bude R16L16.
V každom kole šifrovacieho výpočtu sa bity kľúča posunú a
potom sa z nich vyberie 48 bitov podkľúča permutáciou PC-2
(Tab. 5). Pravá polovica údajov (32 bit) sa rozšíri permutáciou
podľa funkcie E (Tab. 6) na 48 bitov a prevedie
sa operácia sčítania modulo 2 (v hardvérovej implementácii
je to operácia XOR). Na výsledok tejto operácie sa použije
štandardom definovaná množina funkcií nazývaných S-box.
Tieto funkcie kódujú 6 vstupných bitov na 4
výstupné bity. Výstup S-boxov sa znovu permutuje permutáciou
P (Tab. 15). Tieto štyri operácie sa nazývajú
funkcia f. Výsledok funkcie f
a ľavú polovicu L údajov opäť sčítame (mod 2).
Výsledok potom bude novou pravou polovicou údajov a stará
polovica údajov sa stane novou ľavou polovicou údajov. Tieto
operácie sa opakujú 16-krát.
Každá výberová funkcia S1, S2, ... S8 vytvára
zo 6-bitových blokov 4-bitové bloky podľa tzv. S-boxov
(Tab. 7 až 14).
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
Tab. 7 S1
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
Tab. 8 S2
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
Tab. 9 S3
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
Tab. 10 S4
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
Tab. 11 S5
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
Tab. 12 S6
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
Tab. 13 S7
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
Tab. 14 S8
Ak S1 je definovaná podľa Tab. 7 a B
je blok 6 bitov, potom S1(B) predstavuje takúto
funkciu:
Prvý a posledný bit z B reprezentuje
v binárnom tvare číslo v rozsahu 0 až 3. Označme ho i.
Stredné 4 bity z B reprezentujú číslo v rozsahu
0 až 15. Označme ho j. Potom číslo v i-tom riadku
a v j-tom stĺpci je v rozsahu 0 až 15 a je reprezentované
blokom 4 bitov. Tento blok je výstupom S1(B)
funkcie S1 so vstupom B.
Každá funkcia S má teda 6 bitový vstup a 4
bitový výstup. Takýchto funkcií je 8, (8x6=48 bitov). Z toho
vyplýva, že vstupných 48 bitov sa rozdelí na 6 bitové bloky,
ktoré sa samostatne spracujú. S1 spracuje prvých
6 bitov, S2 druhých 6 bitov atď. Potenciál algoritmu
DES spočíva práve v týchto funkciách, pretože na rozdiel od
ostatných sa jedná o nelineárne funkcie.
Zoberme, napríklad, že vstupom S6 (tj. 31..36.
bit vstupu) je hodnota 110011. Prvý a posledný bit je 1 a
teda kombinácia 11 je 4. riadok tabuľky. Prostredné štyri
bity sú 1001, teda ide o 9. stĺpec tabuľky. Na príslušnom
mieste sa nachádza číslo 14, teda prebehne substitúcia hodnoty
110011 na 1110. Po spojení týchto ôsmich 4-bitových blokov
vznikne jeden 32-bitový blok. Tento bude vstupom pre permutáciu
P.
Permutácia P predstavuje funkciu s 32-bitovým
vstupom a 32-bitovým výstupom, ktorá vykoná permutáciu vstupného
bloku podľa Tab. 15.
Ak S1 až S8 sú výberové funkcie,
P je permutačná funkcia a E je
funkcia definovaná v Tab. 6, môžeme definovať nasledovné funkcie:
B1B2...B8 = K xor E(R) (4)
Potom blok f(R,K) je definovaný ako
P(S1(B1)S2(B2)...S8(B8)) (5)
Výraz K xor E(R) je najprv rozdelený na 8 blokov
podľa (4). Potom každý člen Bi bude vstupom
pre Si a 8 blokov S1(B1)S2(B2)...S8(B8)
pozostávajúcich zo 4 bitov je nakoniec zložených do jedného
32 bitového bloku, ktorý predstavuje vstup pre P.
Výstup z (5) predstavuje potom výstup funkcie f
so vstupmi R a K.
Permutácia IP-1 aplikovaná na výsledok (preoutput
block) je inverzná k počiatočnej permutácii IP,
ktorá sa aplikuje na vstup. Možno to vyjadriť rovnicami:
R = L' (6) L = R' xor f(L', K )
Podmienkou pre správne dešifrovanie údajov je použitie rovnakého
algoritmu s rovnakým blokom bitov kľúča K v
každej iterácii, ako sme použili pri šifrovaní. Vyjadrené
rovnicami:
Rn-1 = Ln (7) Ln-1 = Rn xor f(Ln, Kn)
kde R16L16 predstavuje permutovaný vstupný blok,
ktorý bol použitý ako vstup pre šifrovaciu funkciu a L0R0
predstavuje výsledok (preoutput block). Pri tomto procese
je kľúč K16 použitý v prvej iterácii, K15
v druhej iterácii atď. až po K1 v 16. iterácii.
