DES online - Popis

Text vznikl jako podklad pro zápočet z předmětu Algoritmy a datové struktury 2 na Matematicko-fyzikální fakultě Univerzity Karlovy v zimním semestru 2007/08. Nečiní si nároky být profesionálním článkem. Budu rád, když mi jakékoliv chyby a připomínky napíšete na mail bruinee [zavináč] gmail.com.

Obsah

Zpět na obsah

Úvod

DES (Data Encryption Standard) je symetrická bloková šífra pracující s textem o velikosti 64 bitů, vracící šifrový text, který má opět 64 bitů. Počet možných vstupů i výstupů je ted 2^64.

Obecně můžeme mluvit o jedné z nejznámnějších a nejvíce používaných šifer v historii. Přestože dnes již je překonána, tak ji stále mnoho subjektů používá. Náklady na její prolomení jsou totiž značně vysoké. Když byla šifra poprvé v 90. letech prolomena, tak se cena počítače pohybovala okolo $250.000

Pokud bychom měli být naprosto korektní, tak by bylo potřeba rozlišovat mezi DES jako standardem a DEA (Data Encryption Algorithm) jako algorimem. Běžne se ale používá termín DES jak pro algoritmus, tak pro standard a tohoto značení se bude držet i tento text. Výslovnost je anglická, buď [des] nebo hláskovaně [di: i: es].

Zpět na obsah

Historie

Původ DES se datuje v počátcích 70. let. V roce 1972, vyhlásil tehdejší americký stanardizační institut (NBS, nyní NIST) potřebu po nové, šifře pro neutajené, ale citlivé informace. V roce 1974 navrhl IMB kandidáta, který byl nakonec v roce 1976 uznán federálním sandardem. O rok později vyšel jako FIPS PUB 46, později FIPS PUB 46-2, FIPS PUB 46-3. Dnes je již překonaný a rozlomitelný hrubou silou, především díky malé délce klíče. Byl nahrazen Trile DESem a v roce 2002 definitivně překonán standardem AES.

Zpět na obsah

Šifrování + Příklad

Zakódování vstupu

Vezměme si jako příklad vstup "počítače", který zakódujeme pomocí kódování Windows-1250 takto:

p = 01110000
o = 01101111
č = 11101000
í = 11101101
t = 01110100
a = 01100001
č = 11101000
e = 01100101

Vstup označme M a bude tedy vypadat následovně:
M = 01110000 01101111 11101000 11101101 01110100 01100001 11101000 01100101

Zpět na obsah

Vytvoření klíčů

DES pracuje s klíči délky 64 bitů, ale ve skutečnosti se používá jen 56 z nich, protože každý osmý bit slouží jako paritní kontrola. Označme klíč K a vygenerujme například:

K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

Na začátku klíč projde následující funkcí, jejíž význam vidím pouze v odstranění paritních bitů. Na bezpečnosti celé šifry se žádným způsobem nepodílí. V prvním sloupci je pozice bitu. V druhém pak pozice jeho obrazu. Násobky osmi pozici nemají, protože se nezobrazují. Funkci budeme říkat redukce1.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
8 16 24 58 53 44 36 - 7 15 23 57 52 43 35 -

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
6 14 22 56 50 42 34 - 5 13 21 55 49 41 33 -

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
4 12 20 54 48 40 32 - 3 11 19 27 47 39 31 -

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
2 10 18 26 46 38 30 - 1 9 17 25 45 37 29 -

Náš klíč K tedy upravíme na K+ a bude vypadat následovně:
K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111

V dalším fázi vytvoříme posloupnost {Cn}, {Dn} pro n=0 až 16. V prvním kroku rozdělíme klíč na dvě stejně velké půlky, tu první označíme C0, druhou D0.

Dvojici (Cn, Dn), n=1..16 vytvoříme z dvojice (Cn-1, Dn-1) posunem bitů do leva. Hodnoty ze začátku posloupnosti, které se nemají kam posunout přepojíme na konec klíče. Počet bitů, o které se původní hodnoty posunou, je v každé iteraci různý a odpovídá následující tabulce:

Krok iterace 12 34 56 78 910 1112 1314 1516
Počet posunů 11 22 22 22 12 22 22 21

Data encryption standard

Z klíče K+ tedy dostáváme:
C0 = 1111000011001100101010101111
D0 = 0101010101100110011110001111
C1 = 1110000110011001010101011111
D1 = 1010101011001100111100011110
C2 = 1100001100110010101010111111
D2 = 0101010110011001111000111101
C3 = 0000110011001010101011111111
D3 = 0101011001100111100011110101
C4 = 0011001100101010101111111100
D4 = 0101100110011110001111010101
C5 = 1100110010101010111111110000
D5 = 0110011001111000111101010101
C6 = 0011001010101011111111000011
D6 = 1001100111100011110101010101
C7 = 1100101010101111111100001100
D7 = 0110011110001111010101010110
C8 = 0010101010111111110000110011
D8 = 1001111000111101010101011001
C9 = 0101010101111111100001100110
D9 = 0011110001111010101010110011
C10 = 0101010111111110000110011001
D10 = 1111000111101010101011001100
C11 = 0101011111111000011001100101
D11 = 1100011110101010101100110011
C12 = 0101111111100001100110010101
D12 = 0001111010101010110011001111
C13 = 0111111110000110011001010101
D13 = 0111101010101011001100111100
C14 = 1111111000011001100101010101
D14 = 1110101010101100110011110001
C15 = 1111100001100110010101010111
D15 = 1010101010110011001111000111
C16 = 1111000011001100101010101111
D16 = 0101010101100110011110001111

Hodnoty Cn, Dn zkombinujeme zpět dohromady a vytvoříme tak Ln, 1≤n≤16. Hodnoty C0, D0 již potřebovat nebudeme.

Finální Kn, neboli subklíče dotaneme z hodnot Ln aplikováním podobné funkce, jakou jsme používali úplně na začátku. Budu jí říkat redukce2, protože zredukuje bity klíče z 56 na 48. V prvním sloupci tabulky je pozice bitu. V druhém pak pozice jeho obrazu.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
5 24 7 16 6 10 20 18 - 12 3 15 23 1 9 19

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
2 - 14 22 11 - 13 4 5 17 21 8 47 31 27 48

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
35 41 - 46 28 - 39 32 25 44 - 37 - 43 29 36

49 50 51 52 53 54 55 56
38 45 33 26 42 - 30 40

V našem případě vycházejí hodnoty následovně:

K1 = 000110 110000 001011 101111 111111 000111 000001 110010
K2 = 011110 011010 111011 011001 110110 111100 100111 100101
K3 = 010101 011111 110010 001010 010000 101100 111110 011001
K4 = 011100 101010 110111 010110 110110 110011 010100 011101
K5 = 011111 001110 110000 000111 111010 110101 001110 101000
K6 = 011000 111010 010100 111110 010100 000111 101100 101111
K7 = 111011 001000 010010 110111 111101 100001 100010 111100
K8 = 111101 111000 101000 111010 110000 010011 101111 111011
K9 = 111000 001101 101111 101011 111011 011110 011110 000001
K10 = 101100 011111 001101 000111 101110 100100 011001 001111
K11 = 001000 010101 111111 010011 110111 101101 001110 000110
K12 = 011101 010111 000111 110101 100101 000110 011111 101001
K13 = 100101 111100 010111 010001 111110 101011 101001 000001
K14 = 010111 110100 001110 110111 111100 101110 011100 111010
K15 = 101111 111001 000110 001101 001111 010011 111100 001010
K16 = 110010 110011 110110 001011 000011 100001 011111 110101

Tím je tvorba klíčů hotova. Věnujme se nyní samotnému zašifrování zprávy.

Zpět na obsah

Vlastní šifrování

Připomeneme, že otevřenou zprávu jsme označili M. Nejprve ji přeskupíme pomocí inicializační permutace IP. Po provedení celého kódování pak použijeme inverzní permutaci k IP. Tento postup nám umožní použít stejný algoritmus i pro dešifraci.

Naše ilustrační zprávu "počítače" jsme na začátku textu přepsali do binární podoby a dostali jsme:
M = 01110000 01101111 11101000 11101101 01110100 01100001 11101000 01100101

Proveďme tedy IP. Formát tabulky je stále stejný jako v předešlém textu. Nyní je rozdíl v tom, že nedochází k žádné ignoraci bitů a použijí se všechny, tedy matematicky mluvíme o permutaci.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

Po permutaci našeho vstupního M vychází:
IP(M) = 11111111 00010001 10011010 10101010 01001100 11111111 01001110 00000010

První bit vstupu se tedy zobrazil na 40. místo výstupu, druhý na 8., atd. Nic překvapivého, nebo nového. Všechny následující permutace a zobrazení fungují na stejném principu a zde tedy znázorňování příkladu ukončíme.

Data encryption standard

Výstup IP rozdělíme na dvě stejně velké části, které nazveme L0 a P0, levá a pravá.

Nyní provedeme 16 iterací podle definice:
Ln = Pn-1
Pn = Ln-1 XOR f(Pn-1,Kn)

XOR značí exkluzivní or. Funkce f bude vysvětlena v následujícím textu. Jejím vstupem je předchozí hodnota Pn-1, která je 32 bitová a hodnota Kn, která je 48 bitová. Výstupem je 32 bitová hodnota Pn.

Nejprve stručně naznačíme, jak funkce f se vstupy pracuje a potom rozebereme průběh detailně.

  1. Vstup Pn-1 je rozšířen z 32 na 48 bitů pomocí funkce E
  2. Výstup funkce E xorujeme s klíčem Kn a výsledek rozepíšeme do šestic
  3. Každou šestici zakódujeme na 4 bitovou hodnotu
  4. Provedeme finální permutaci

Nyní postupně k jednotlivým bodům

Funkce E je tradičně nějaké přeskupení bitů. Nyní ovšem místo ignorace některých bitů, jak bylo doposud zvykem, použijeme některých 16 vstupních bitů na dvou místech. Abychom byli korektní, tak jen podotknu, že E není tedy v matematickém slova smyslu funkce, ale spíš zobrazení. Tady ho máme:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
48
2
3 4 5
7
6
8
9 10 11
13
10
14
15 16 17
19
16
20
21 22 23
25

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
24
26
27 28 29
31
30
32
33 34 35
37
36
38
39 40 41
43
42
44
45 46 47
1

Dvě hodnoty v tabulce hodnot znamenají, že se daný vzor zobrazil na dvě různá místa. Tak například první bit vstupního kódu bude pro aplikaci funkce E na 2. a 48. místě výstupního kódu.

Překódování 6 bitové hodnoty na 4 bitovou probíhá opět podle předem daných tabulek, pouze je situace o něco složitější, než v předcházejících případech. V úvahu se berou dvě hodnoty. Ta první vznikne složením prvního a posledního bitu vstupní šestice, druhá pak složením prostředních 4. V tabulce si pak najdete v prvním řádku danou dvou bitovou hodnotu, v prvním sloupci čtyřbitovou hodnotu a výsledkem je honota, která leží na spojnici nalezeného řádku a sloupce.

Aby nebylo vše tak jednoduché, tak tabulek je celkem 8, T1 až T8, pro každou šestici jedna. První se kóduje pomocí první tabulky, druhá pomocí druhé tabulky, atd...

T100011011
00001110000001001111
00010100111100011100
00101101011111101000
00110001010010000010
01000010111011010100
01011111001001101001
01101011110100100001
01111000000110110111
10000011101011110101
10011010011011001011
10100110110010010011
10111010101101111110
11000101100100111010
11011001010110100000
11100000001101010110
11110111100000001101
T200011011
00001111001100001101
00010001110111101000
00101000010001111010
00111110011110110001
01000110111110100011
01011011001001001111
01100011100011010100
01110100111000010010
10001001110001011011
10010111000010000110
10100010000111000111
10111101101001101100
11001100011010010000
11010000100100110101
11100101101100101110
11111010010111111001
T300011011
00001010110111010001
00010000011101101010
00101001000001001101
00111110100110010000
01000110001110000011
01010011010011111001
01101111011000111000
01110101101000000111
10000001001010110100
10011101100000011111
10101100010100101110
10110111111011000011
11001011110001011011
11010100101110101001
11100010111111100010
11111000000101111100
T400011011
00000111110110100011
00011101100001101111
00101110101110010000
00110011010100000110
01000000011011001010
01010110111110110001
01101001000001111101
01111010001111011000
10000001010011111001
10010010011100010011
10101000001000110101
10110101101011101011
11001011000101011100
11011100101000100111
11100100111010000010
11111111100101001110
T500011011
00000010111001001011
00011100101100101000
00100100001000011100
00110001110010110111
01000111010010100001
01011010011111011110
01101011110101110010
01110110000110001101
10001000010111110110
10010101000010011111
10100011111111000000
10111111101001011001
11001101001101101010
11010000100100110010
11101110100000000101
11111001011011100011
T600011011
00001100101010010100
00010001111111100011
00101010010011110010
00111111001001011100
01001001011100101001
01010010110010000101
01100110100111001111
01111000010100111010
10000000011001111011
10011101000100001110
10100011110101000001
10110100111010100111
11001110000000010110
11010111101111010000
11100101001110111000
11111011100001101101
T700011011
00000100110100010110
00011011000001001011
00100010101110111101
00111110011111011000
01001111010011000001
01010000100100110100
01101000000101111010
01111101101011100111
10000011111010101001
10011100001111110101
10101001010101100000
10110111110010001111
11000101001000001110
11010110111101010010
11100110100010010011
11110001011000101100
T800011011
00001101000101110010
00010010111110110001
00101000110101001110
00110100100000010111
01000110101010010100
01011111001111001010
01101011011111101000
01110001010000101101
10001010110000001111
10011001010101101100
10100011011010101001
10111110101111010000
11000101000011110011
11010000111000111001
11101100100101010110
11110111001010001011

Data encryption standard

Výsledkem je tedy osm čtyřbitových znaků, neboli 32 bitů. Označme tuto hodnotu třeba Tn, jako výsledek tabulek T1 až T8 v n-té iteraci.

T je opět potřeba popřeházet dle předem nadefinované permutace, říkeme jí P. Formát tabulek už každý zná, takže tady je. Vstupem je 32 bitová hodnota, výstupem taktéž.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
9 17 23 31 13 28 2 18 24 16 30 6 26 20 10 1

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
8 14 25 3 4 29 11 19 32 12 22 7 5 27 15 21

Výstup P(T) je již námi hledaná hodnota f(Pn-1,Kn) a můžeme dle vzorce dopočítat Pn = Ln-1 XOR f(Pn-1,Kn).

V našem příkladě v poslední iteraci vychází
L16 =
T16 = f(P15,K16) =
P16 =
L16 o P16 =

Po poslední iteraci máme L16 a P16, které spojíme za sebe přesně v tomto pořadí, tedy obráceně, než bylo doposud zvykem. Jak již bylo avizováno dříve, tak na konci algoritmu čeká ještě inverzní permutace IP-1. Tabulka:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
61 53 45 37 29 21 13 5 62 55 47 39 31 23 15 7

L16 o P16 =
IP-1 (L16 o P16) =

No a to je celé, tedy alespoň, co se šifrování týče.

Naše původní slovo "počítače" bylo zašifrováno na binární hodnotu ... neboli po zpětném převodu dle Windows-1250 kódování vychází ..., což je pravděpodobně to, co budete chtít poslat komunikující straně jako šifrový text.

Zpět na obsah

Dešifrování

Dešifrování probíhá téměř identicky jako šifrování. Jedinou změnou je pořádí podklíčů K1 - K16, jsou aplikovány v opačném pořadí.

Zpět na obsah

Důkaz správnosti

Aneb, proč to vlastně celé funguje?

  1. Algoritmus je konečný. Nikde v jeho průběhu nedochází k nějakým smyčkám, nekonečným cyklům nebo něčemu podobnému. Není třeba nějak zvlášť komentovat.
  2. Algoritmus vydá výsledek. Je zřejmé z naznačeného postupu. To, že výsledek je správný je dáno definitoricky. Algoritmus je jejím doslovným přepisem.
  3. To, že šifra je bezpečná zdaleka přesahuje rámce tohoto textu a vydala by na celou publikaci. Rozebrání tohoto problému tedy necháme stranou.

Zpět na obsah

Analýza složitosti

Myslí se časová složitost. Nejprve se věnujme vytvořní subklíčů. Náhodnou posloupnost 64 bitů umíme vygenerovat v konstantním čase. Funkce 'redukce1' je také konstantní. Projde posloupnost bit po bitu a u každého rozhodne, jestli se vůbec zobrazí, respektive na které místo se zobrazí. Zjistit, na které místo se konkrétní bit zobrazí dokážeme v konstantním čase, protože tabulky máme uloženy v poli. Podobnými úvahami dospějeme k tomu, že vytvoření subklíčů je konstantní. Je to přece zřejmé, protože maximální počet bitů, s kterými v jednom kroku pracuji je 64 a počet kroků je také konstantní.

Jak to vypadá se složitostí vlastního šifrování. Věnujme se nejprve složitosti zašifrování jednoho bloku, tedy 64 bitů textu. Permutace na 64 bitech je konstantní, xor 64 bitů je konstantní, zbývá si rozmyslet složitost funkce f. V prvním kroku je nějaká permutace, poté opět xor, kódování šestic znaků je pouze konstantní počet přístupů do tabulky a finální permutace dle předchozích úvah opět konstantní. Žádně překvapení se nekoná, vyšlo to, co všichni čekali. Neboli zašifrování jednoho bloku trvá konstantní čas, bloků je n/64, kde n je délka zprávy. Takže zašifrování celého textu dle DES probíhá v lineárním čase. Dešifrování je ten stejný algoritmus, takže taky lineární.

Prostorová složitost závisí hodně na konkrétní implementaci a zde se jí zabývat nebudeme. Domnívám se, že by mohla být konstantní.

Zpět na obsah

Literatura

Zpět na obsah

Live šifrování/dešifrování

Zatím bohužel nefunguje a ještě dlouho fungovat nebude.

Vstupní text:

Klíč: