Moderní metody substitučního šifrování

Moderní metody substitučního šifrování Ing. Jan Přichystal, Ph.D. PEF MZLU v Brně

11. listopadu 2010

Ing. Jan Přichystal, Ph.D.

Moderní metody substitučního šifrování

Úvod

V současné době se pro bezpečnou komunikaci používají elektronická média. Zprávy se před šifrováním převádí do tvaru zpracovatelného technickým vybavením, do binární podoby. Tak jako nám počítače a elektronická média usnadňují komunikaci i v šifrované podobě, stejně tak umožňují nepovolaným osobám použít komplikovanější metody odhalení tajného textu. Pro bezpečnou komunikaci nelze vystačit s běžnými šiframi používanými před sto lety. Základem moderních šifer jsou polyalfabetické šifry pracující s různou délkou klíče.



Rozdělení algoritmů

Proudové šifry Vstupní sekvence se kóduje bit po bitu, tak jak přichází na vstup. Typickou funkcí pro šifrování pomocí proudové šifry je operace XOR: Pi = Ci ⊕ K i Používají se například při šifrování telefonních hovorů.

Blokové šifry Vstupní sekvence je rozdělena do bloků o pevné délce. Používají se například při šifrování souborů dat.



Vlastnosti blokových šifer

Dobrý návrh – šifra je dobře navržená, pokud nejjednodušším útokem na ni je útok hrubou silou. Difúze – malá změna v otevřeném textu má nepředvídatelné změny v textu šifrovém. Konfúze – nic by nemělo naznačovat útočníkovi, že i při použití téměř shodného klíče se přiblížil správnému řešení. Úplnost – každá část textu se odvíjí od každé části klíče.



Módy blokových šifer

Blokové šifry pracují v různých módech, které ovlivňují bezpečnost výsledné šifry. ECB – Electronic code book – shodné bloky původní zprávy jsou šifrovány do shodných bloků kryptogramu. CBC – Cipher block chaining – každý blok šifrového textu závisí na odpovídajícím bloku otevřeného textu i všech předchozích blocích otevřeného textu. Ci = E (Mi ⊕ Ci−1 ). C1 je možno ponechat rovno M1 nebo C1 = M2 ⊕ IV .



Příklad blokové šifry – ECB

Velikost bloku je 4 bity. Máme klíč K = B a zprávu M = A23A9. Šifrujeme M ⊕ K a následným posunem o jednu pozici vlevo. 1. blok: M1 = 1010, K = 1011 → M1 ⊕ K = 0001 po rotaci C1 = 0010 = 2(HEX). 2. blok: M2 = 0010, K = 1011 → M2 ⊕ K = 1001 po rotaci C2 = 0011 = 3(HEX). atd. Výsledná zašifrovaná zpráva C = 23124. Bloky původní zprávy se projevují opakujícími se bloky v kryptogramu.



Problém ECB

Mějme zprávu „The price is four thousand poundsÿ, která je zašifrovaná blokovou šifrou s neznámým klíčem. Víme jen, že délka bloku jsou 2 byte. Kryptogram pak zní: c1 , c2 , c3 , c4 , c5 , c6 , c7 , c8 , c9 , c10 , c11 , c12 , c13 , c14 V případě, že útočník zprávu zná snadno si odvodí související části textu a bloků kryptogramu. Zašifrovanou zprávu pak pozmění tak, že se skádá jen z bloků: c1 , c2 , c3 , c4 , c5 , c6 , c7 , c12 , c13 , c14 Tím modifikuje znění zprávy na „The price is four poundsÿ.



Příklad blokové šifry – CBC Velikost bloku je 4 bity. Máme klíč K = B a zprávu M = A23A9. 1. blok: M1 = 1010, IV = 0000, K = 1011 → M1 ⊕ IV = 1010, M1 ⊕ K = 0001, po rotaci C1 = 0010 = 2(HEX). 2. blok: M2 ⊕ C1 = 0010 ⊕ 0010 = 0000, 0000 ⊕ K = = 0000 ⊕ 1011 = 1011, po rotaci C2 = 0111 = 7(HEX). 3. blok: M3 ⊕ C2 = 0011 ⊕ 0111 = 0100, 0100 ⊕ K = = 0100 ⊕ 1011 = 1111, po rotaci C2 = 1111 = F(HEX). atd. Výsledná zašifrovaná zpráva C = 27FDF. Bloky původní zprávy nesouvisí s bloky v kryptogramu. Ing. Jan Přichystal, Ph.D.


DES DES (Data Encryption Standard) je v dnešní době nejrozšířenější šifrovací algoritmus na světě i navzdory jeho nepříliš dobré bezpečnosti způsobené malou délkou klíče. Vychází z algoritmu LUCIFER publikovaného r. 1974 firmou IBM, který vyšel vítězně ze soutěže vyhlášené NBS o šifrovací standard v USA. DES byl přijat jako národní standard v r. 1977. Jedná se o blokovou symetrickou šifru pracující s délkou klíče 64 bitů (56 bitů). Vstupní sekvence se rozdělí na 64bitové bloky, které jsou zpracovávány odděleně. Vnitřní struktura algoritmu je vytvořena tak, aby šifrování i dešifrování používalo stejnou sekvenci kroků. To významně usnadňuje implementaci jak softwarovou tak především hardwarovou.



DES – příklad

Mějme text M znění „0123456789ABCDEFÿ, který má v binární podobě tvar: M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Klíč K zní „133457799BBCDFF1ÿ, přičemž binární podoba je: K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001



DES – ustavení klíče

Z 64bitového klíče K je 56 bitů transponováno podle tabulky a vznikne tak klíč K+. Ostatních osm bitů je ztraceno. 57 1 10 19 63 7 14 21

49 58 2 11 55 62 6 13

41 50 59 3 47 54 61 5

33 42 51 60 39 46 53 28

25 34 43 52 31 38 45 20

17 26 35 44 23 30 37 12

9 18 27 36 15 22 29 4

K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111



DES – ustavení klíče Klíč je následně rozdělen na dvě části C0 a D0 . Z takto vzniklých částí vytvoříme 16 klíčů pro každou iteraci šifrování na základě těchto posunů: Iterace: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Počet posunů vlevo: 1122222212222221 To znamená, že například C3 a D3 vzniknou posunem C2 a D2 o dva bity vlevo. C0 = 1111000011001100101010101111 D0 = 0101010101100110011110001111 C1 = 1110000110011001010101011111 D1 = 1010101011001100111100011110 Ing. Jan Přichystal, Ph.D.


DES – ustavení klíče Následně je každý z klíčů K1 . . . K16 transponován na výsledné klíče délky 48 bitů podle následující tabulky: 14 3 23 16 41 30 44 46

17 28 19 7 52 40 49 42

11 15 12 27 31 51 39 50

24 6 4 20 37 45 56 36

1 21 26 13 47 33 34 29

5 10 8 2 55 48 53 32

C1 D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110 K1 = 000110 110000 001011 101111 111111 000111 000001 110010 Ing. Jan Přichystal, Ph.D.


DES – šifrování Na text zprávy je aplikována úvodní transpozice, která zamění pořadí jednotlivých bitů podle následující tabulky: 58 60 62 64 57 59 61 63

50 52 54 56 49 51 53 55

42 44 46 48 41 43 45 47

34 36 38 40 33 35 37 39

26 28 30 32 25 27 29 31

18 20 22 24 17 19 21 23

10 12 14 16 9 11 13 15

2 4 6 8 1 3 5 7

M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010 Ing. Jan Přichystal, Ph.D.


DES – šifrování Transponovaná zpráva je rozdělena na dvě části Ln a Rn . L0 = 1100 1100 0000 0000 1100 1100 1111 1111 R0 = 1111 0000 1010 1010 1111 0000 1010 1010 Takto upravené části jsou upraveny v 16ti iteracích, kdy: Ln = Rn−1 Rn = Ln−1 ⊕ f (Rn−1 , Kn ) Funkce f nejprve expanduje Rn−1 z 32 bitů na 48 pomocí tabulky: 32 4 8 12 16 20 24 28

1 5 9 13 17 21 25 29

2 6 10 14 18 22 26 30

3 7 11 15 19 23 27 31

4 8 12 16 20 24 28 32

5 9 13 17 21 25 29 1



DES – šifrování

Dalším krokem je XOR klíče a rozšířené poloviny zprávy, Kn ⊕ E (Rn−1 ). K1 = 000110 110000 001011 101111 111111 000111 000001 110010 E (R0 ) = 011110 100001 010101 010101 011110 100001 010101 010101 K1 ⊕ E (R0 ) = 011000 010001 011110 111010 100001 100110 010100 100111.



DES – šifrování Předchozí transpozicí získáme 48bitové řetězce, jinak řečeno 8 sekvencí po 6ti bitech. Můžeme psát: Kn ⊕ E (Rn−1 ) = B1 B2 B3 B4 B5 B6 B7 B8 Každá z těchto sekvencí nám poslouží jako adresa do S-boxů, kdy první a poslední bit sekvence, udává index řádku a 4 vnitřní bity index sloupce: S1 (B1 )S2 (B2 )S3 (B3 )S4 (B4 )S5 (B5 )S6 (B6 )S7 (B7 )S8 (B8 ) 0 1 2 3

0 14 0 4 15

1 4 15 1 12

2 13 7 14 8

3 1 4 8 2

4 2 14 13 4

5 15 2 6 9

6 11 13 2 1

7 8 1 11 7

8 3 10 15 5

9 10 6 12 11

10 6 12 9 3

11 12 11 7 14

12 5 9 3 10

13 9 5 10 0

K 1 ⊕ E (R0) = 011000 010001 011110 111010 100001 100110 010100 100111. S1 (B1 )S2 (B2 )S3 (B3 )S4 (B4 )S5 (B5 )S6 (B6 )S7 (B7 )S8 (B8 ) = 0101 1100 1000 0010 1011 0101 1001 0111 Ing. Jan Přichystal, Ph.D.


14 0 3 5 6

15 7 8 0 13

DES – šifrování Posledním krokem funkce f je transponování výstupu z S-boxů f = P(S1 (B1 )S2 (B2 ) . . . S8 (B8 )) podle následující tabulky: 16 29 1 5 2 32 19 22

7 12 15 18 8 27 13 11

20 28 23 31 24 3 30 4

21 17 26 10 14 9 6 25

S1 (B1 )S2 (B2 )S3 (B3 )S4 (B4 )S5 (B5 )S6 (B6 )S7 (B7 )S8 (B8 ) = 0101 1100 1000 0010 1011 0101 1001 0111 f = 0010 0011 0100 1010 1010 1001 1011 1011 R1 = L0 ⊕ f (R0 , K1 ) = 1100 1100 0000 0000 1100 1100 1111 1111 ⊕ 0010 0011 0100 1010 1010 1001 1011 1011 = 1110 1111 0100 1010 0110 0101 0100 0100 Ing. Jan Přichystal, Ph.D.


DES – šifrování Posledním krokem je závěrečná transpozice podle tabulky: 40 39 38 37 36 35 34 33

8 7 6 5 4 3 2 1

48 47 46 45 44 43 42 41

16 15 14 13 12 11 10 9

56 55 54 53 52 51 50 49

24 23 22 21 20 19 18 17

64 63 62 61 60 59 58 57

32 31 30 29 28 27 26 25

L16 = 0100 0011 0100 0010 0011 0010 0011 0100 R16 = 0000 1010 0100 1100 1101 1001 1001 0101 Obrátíme pořadí dvou sekvencí a provedeme závěrečnou transpozici. R16 L16 = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100 IP −1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101 Ing. Jan Přichystal, Ph.D.


DES – výsledek

Výsledkem zašifrování řetězce M = 0123456789ABCDEF je potom sekvence C = 85E813540F0AB405.



3DES Symetrický šifrovací algoritmus pracující s délkou klíče 128 nebo 192 bitů. Rozšíření v dnešní době nepříliš bezpečného DESu. Používá trojité zašifrování pomocí DES, pokaždé s jiným, nezávislým klíčem. Z = DES(k3 ; DES(k2 ; DES(k1 ; O))) O = DES(k1 ; DES(k2 ; DES(k3 ; Z )))



AES Tento algoritmus (původním jménem Rijndael) byl vybrán v roce 2000 jako Advanced Encryption Standard (AES). Jedná se o symetrický šifrovací algoritmus s délkou klíče 128, 192 a 256 bitů aplikovaný na bloky délky 128 bitů. Pracuje se s bloky o velikosti 4 × 4 byty. Šifrování se skládá z několika kroků: 1

expanze klíče – šifrovací klíč se expanduje na rozšířený klíč, jehož části se následně užívají pro šifrování bloku v jednotlivých krocích,

2

úvodní iterace – blok je XORován s klíčem,

3

běžná iterace,

4

závěrečná iterace.

Počet běžných iterace přímo závisí na délce klíče a délce bloku, pohybuje se v rozmezí od 10 do 14. Ing. Jan Přichystal, Ph.D.


Postup algoritmu Round (State, RoundKey) { ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State, RoundKey); }

FinalRound(State, RoundKey) { ByteSub(State); ShiftRow(State); AddRoundKey(State, RoundKey); }

ByteSub: Jednotlivé slabiky v bloku jsou nahrazeny svými ekvivalenty z nelineární převodní tabulky. ShiftRow: Skupiny slabik bloku jsou podrobeny cyklickému posunu. Velikost posunu závisí na velikosti šifrovaného bloku. MixColumn: Skupiny čtyř slabik jsou podrobeny násobení definovanou maticí. To umožní každé slabice ovlivnit ostatní slabiky skupiny. AddRoundKey: Blok je podroben operaci XOR spolu s klíčem (RoundKey) pro tuto iterace získaného z rozšířeného klíče (Expanded Key).



IDEA

Jedná se o symetrický šifrovací algoritmus s délkou klíče 128 bitů a šifrovaným blokem délky 64 bitů. Šifrovací klíč se rozdělí na osm 16bitových klíčů, které jsou prvními osmi podklíči. V dalším kroku je původní 128bitový klíč cyklicky posunut o 25 bitů doleva a rozdělen na dalších osm 16bitových podklíčů. Tento krok se opakuje, dokud není vytvořeno 52 podklíčů. Vstupní 64bitový blok je rozdělen na čtyři 16bitové bloky. Neomezený produkt k volnému použití. Součástí programu GnuPG.



Problém výměny klíčů

Problém výměny klíčů mezi odesílatelem a příjemcem zprávy trápil kryptografy po několik století. Problém spočívá ve výměně tajné informace tak, aby ji nikdo třetí nebyl schopen odposlechnout. Pro distribuci klíčů se využívaly služby kurýrů ⇒ logistický problém. Neřešitelnou situace začínala být v případě elektronické komunikace, elektronického obchodování.



Diffie-Hellman-Merkle

Systém výměny klíčů pracuje s modulární aritmetikou. Vychází z předpokladu, že funkce (αx mod p) je funkce jednosměrná a tudíž obtížně převratitelná. Hodnota p je prvočíslo; α, 2 ≤ α ≤ p − 2; x, 1 ≤ x ≤ p − 2. Oba dva, Alice i Bob, dospějí ke stejnému číslu, které mohou použít jako klíč při šifrování. I v případě odposlouchávání není schopna třetí osoba ze znalosti vyměňovaných údajů získat stejný klíč.



Diffie-Hellman-Merkle

Postup: Alice a Bob se shodnou na p = 11 a α = 7. Alice zvolí x = 3

Bob zvolí y = 6

Alice určí 7x mod 11 = 2 (1)

Bob vypočítá 7y mod 11 = 4 (2)

Alice pošle výsledek (1) Bobovi

Bob pošle výsledek (2) Alici

Alice vezme Bobův výsledek a vypočítá 4x mod 11 = 9

Bob vezme Alicin výsledek a vypočítá 2y mod 11 = 9



Závěr

Děkuji za pozornost Dotazy?



Moderní metody substitučního šifrování

Recommend Documents