1 Szyfrowanie symetryczne 1
2 Plan wykładu Historia Model szyfrowanie konwencjonalnego SteganografiaAlgorytmy podstawieniowe Algorytmy transpozycyjne Sieci Fiestela Algorytm DES Algorytm IDEA Podsumowanie
3 Plan wykładu Historia Model szyfrowanie konwencjonalnego SteganografiaAlgorytmy podstawieniowe Algorytmy transpozycyjne Sieci Fiestela Algorytm DES Algorytm IDEA Podsumowanie
4 Historia W VII w p.n.e w Grecji stosowano do szyfrowania scytaleTekst pisany był na nawiniętym na patyk pasku skórzanym Po rozwinięciu tekst widoczny na pasku był trudny do odszyfrowania Odszyfrowanie wymaga ponownego nawięnięcia na patyk Na przykład tekst „Proszę o pomoc” Pros zęop omoc Po odczytaniu na pasku wygląda „pzoręmooospc”
5 Historia Szyfr Cezara polegający na przesunięciu liter tesktu o 3 używany przez Juliusz Cezara do komunikacji z wojskami Dzięki stosowaniu tego szyfru Juliusz Cezar podbił całą Galię z wyjątkiem pewnej małej wioski ;-)
6 Historia Polacy w czasie wojny polsko-bolszewickiej ( ) potrafili odszyfrować depesze wroga, co ułatwiało działania wojenne (więcej na serwisy.gazeta.pl/df/1,34467, html
7 Historia Enigma – maszyna szyfrująca używana przez wojska niemieckie od lat 20 XX wieku do czasów drugiej wojny światowej. W 1932 roku Enigma została złamana przez polskich matematyków: Marian Rejewski, Jerzy Różycki i Henryk Zygalski)
8 Plan wykładu Historia Model szyfrowanie konwencjonalnego SteganografiaAlgorytmy podstawieniowe Algorytmy transpozycyjne Sieci Fiestela Algorytm DES Algorytm IDEA Podsumowanie
9 Uproszczony model szyfrowania konwencjonalnego
10 Model szyfrowania konwencjonalnegoSzyfrator tworzy tekst zaszyfrowany Y=EK(X) Odbiorca posiadający klucz może odwrócić przekształcenie X=DK(Y) Przeciwnik śledzący Y, ale pozbawiony dostępu do X i K, próbuje odgadnąć hipotetyczny tekst jawny X` i hipotetyczny klucz K`. Zakładamy, że zna on algorytm szyfrujący E i deszyfrujący D
11 Techniki szyfrowania Steganografia służy do ukrycia faktu istnienia komunikatu, np. zaznaczanie liter, atrament sympatyczny Techniki podstawiania polega na zastępowaniu elementów (bitów) tekstu jawnego innymi elementami (bitami) Techniki transpozycyjne polegają na permutacji liter (przestawieniu) tekstu jawnego
12 Plan wykładu Historia Model szyfrowanie konwencjonalnego SteganografiaAlgorytmy podstawieniowe Algorytmy transpozycyjne Sieci Fiestela Algorytm DES Algorytm IDEA Podsumowanie
13 Steganografia Herodot w "Dziejach" opisuje następujący tajny przekaz informacji Despota Hiastus przetrzymywany przez króla perskiego Dariusza postanawia przesłać informację do swego zięcia Arystogorasa z Miletu, tak aby mogła się ona przedostać mimo pilnujących go strażników Aby tego dokonać na wygolonej głowie swego niewolnika tatuuje przesłanie Kiedy niewolnikowi odrosły włosy posyła go z oficjalnym, mało istotnym listem
14 Steganografia Stosowanie atramentu sympatycznegoNakłuwanie szpilką liter tekstu (książki) Sformułowanie komunikatu, aby sekwencja kolejnych liter, sylab bądź wyrazów tworzyła ukrytą wiadomość
15 Steganografia w informatyceW komputerowym zapisie obrazu (zdjęcie jpg, film mpg) lub dźwięku (mp3) pewne bity można zmienić bez wpływu na jakość obrazu (dźwięku) Na tych bitach przesyłane są tajne informacje, które można odczytać wiedząc gdzie zostały ukryte
16 Plan wykładu Historia Model szyfrowanie konwencjonalnego SteganografiaAlgorytmy podstawieniowe Algorytmy transpozycyjne Sieci Fiestela Algorytm DES Algorytm IDEA Podsumowanie
17 Techniki podstawianiaTechnika podstawienia polega na zastępowaniu elementów (liter, bitów) tekstu jawnego innymi elementami (b literami, bitami) według ustalonego schematu Przykładowe algorytm: szyfr Cezara, Szyfr Playfair, szyfr Vigenere’a
18 C=E(p)=(p+k) mod (26), 0
19 Szyfr Cezara Przykład dla szyfru Cezara (przesunięcie o 3 znaki) Klucza b c d e f g h i j k l m n o p q r s t u v w x y z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C Szyfrowanie tekst jawny : szyfr juliusza cezara tekst zaszyfrowany: VCBIU MXOLXVCD FHCDUD Dla szyfru Cezara łatwo można przeprowadzić kryptoanalizę metodą brutalną polegającą na wypróbowaniu 25 możliwych kluczy k
20 Szyfry jednoalfabetoweDla szyfrów jednoalfabetowych możemy zastosować jako szyfr dowolną permutację 26 znaków alfabetu Oznacza to 26!=4*1026 możliwych kluczy, czyli można wykluczyć próby rozszyfrowania metodą brutalną Jednak, jeśli krypotanalityk zna tekst zaszyfrowany i jego charakter (język tekstu jawnego), może on wykorzystać regularności zawarte w języku
21 Szyfry jednoalfabetowe - kryptoanalizaDla każdego języka można określić względną częstość występowania liter (film „Motyl i skafander”) Poniższa tabela prezentuje procentową częstość względną występowania poszczególnych liter w tekście angielskim
22 Szyfry jednoalfabetowe - kryptoanalizaMożna również przeanalizować częstość występowania kombinacji dwuliterowych, zwanych dwuznakami Szyfry jednoalfabetowe są łatwe do złamania ponieważ odzwierciedlają częstości alfabetu oryginału Aby temu zaradzić można jednej literze przypisać rotacyjnie kilka symboli szyfrowych (homofony)
23 Szyfr Playfair O N A R C H Y B D E F G I/J K L P Q S T U V W X ZSzyfr Playfair, traktuje dwuznaki tekstu jawnego jako osobne jednostki i tłumaczy na dwuznaki zaszyfrowane Algorytm Playfair używa matrycy 5x5, zbudowanej przy użyciu słowa kluczowego Np. dla słowa kluczowego MONARCHY matryca wygląda następująco: M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z
24 Szyfr Playfair Powtarzające się litery tekstu jawnego oddziela się literą wypełniającą W przypadku, gdy litery pary liter tekstu jawnego występują w tym samym wierszu matrycy, zastępuje się każdą z nich literą o jedną pozycję w prawo W przypadku, gdy litery pary liter tekstu jawnego występują w tej samej kolumnie matrycy, zastępuje się każdą z nich literą o jedną pozycję w dół Jeżeli nie zachodzi żaden z powyższych przypadków, każda litera z pary liter tekstu jawnego zastępuje się literą leżącą w tym samym, co ona rzędzie, lecz w kolumnie, w której leży druga litera
25 Szyfr Playfair – przykładjawny : the Playfaif is good jawny : th eP la yf ai fi sg ox od zaszyfrowany: PD FL SM HG BS GK QI AV RH M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z
26 Szyfry wieloalfabetoweSzyfr wieloalfabetowy polega na stosowaniu różnych podstawień jednoalfabetowych podczas szyfrowania jednego komunikatu Przykładem szyfru wieloalfabetowego jest szyfr Vigenere’a, w którym stosuje się szyfr Cezara z przesunięciami od 0 do 25 Litera klucza wyznacza wiersz tablicy Litera tekstu jawnego kolumnę tablicy
27 Szyfr Vigenere’a - przykładklucz : deceptivedeceptivedeceptive tekst jawny : wearediscoveredsaveyourself tekstzaszyfrowany: ZICVTWQNGRZGVTWAVZHCQYGLMGJ
28 Losowe szyfry wieloalfabetoweDla szyfru wieloalfabetowego można zastosować losowy klucz, o takiej samej długości co komunikat, bez powtórzeń Taki system, zwany systemem z kluczem jednorazowym (ang. one time pad), jest nie do złamania Wynikiem jego działania jest losowy tekst, który nie ma żadnych statystycznych związków z tekstem jawnym Praktycznym utrudnieniem jest konieczność posiadania i strzeżenia losowego klucza przez nadawcę i odbiorcę
29 Porównanie szyfrów
30 Plan wykładu Historia Model szyfrowanie konwencjonalnego SteganografiaAlgorytmy podstawieniowe Algorytmy transpozycyjne Sieci Fiestela Algorytm DES Algorytm IDEA Podsumowanie
31 Techniki transpozycyjneTechniki transpozycyjne polegają na permutacji liter tekstu jawnego Najprostszym takim szyfrem jest tzw. technika płotu, polegająca na tym, że tekst jawny zapisuje się jako ciąg kolumn, a odczytuje jako ciąg wierszy Na przykład dla płotu o wysokości 2 tekst jawny : szyfrtranspozycyjny syrrnpzcjy zftasoyyn tekst zaszyfrowany: syrrnpzcjyzftasoyyn
32 Techniki transpozycyjneBardziej skomplikowany system polega na zapisaniu komunikatu w prostokącie, a następnie odczytanie ze zmianą kolejności kolumn Klucz : tekst jawny : b a r d z i e j s k o m p l i k o w a n y s y s t e m p o l e g a n a tekst zaszyfrowany: ASKYLDOWTGBJISORKOSEELYPAIPNMNZMAEA Szyfr transpozycyjny można uczynić znaczenie bezpieczniejszym poprzez stosowanie kilku etapów transpozycji, co utrudnia znacznie rekonstrukcję klucza
33 Konfuzja i dyfuzja Shannon, twórca teorii informacji przedstawił w 1949 roku dwie główne zasady szyfrowania: Konfuzja oznacza rozmycie zależności pomiędzy tekstami jawnymi a ich zaszyfrowanymi wersjami Dyfuzja oznacza rozłożenie zawartych w tekście jawnym informacji w całym tekście zaszyfrowanym Proste szyfry podstawieniowe (szyfr Cezera, szyfr Vigenere’a) zapewniają tylko konfuzję, gdyż każda litera jest szyfrowana oddzielnie
34 Efekt lawinowy Efektem lawinowym określamy intensywniejszy niż dla dyfuzji rozmazanie tekstu jawnego w tekście zaszyfrowanym Jest spotykany dla szyfrowania blokowego Każdy bit zaszyfrowanego tekstu zależy od wszystkich bitów tekstu jawnego w danym bloku Dla zmiany pojedynczego bitu tekstu jawnego lub klucza, każdy bit tekstu zaszyfrowanego powinien zmienić swoją wartość z prawdopodobieństwem równym dokładnie 50% Kryptoanaliza różnicowa wykorzystuje nawet niewielkie odstępstwo od tej zasady
35 Algorytmy produktowe Większość współczesnych algorytmów blokowych to algorytmy produktowe – po kolei wykonywane są proste, stosunkowo mało bezpieczne kroki szyfrujące zwane rundami (iteracjami) Dzięki stosowaniu wielu rund bezpieczeństwo algorytmu znacząco rośnie
36 Plan wykładu Historia Model szyfrowanie konwencjonalnego SteganografiaAlgorytmy podstawieniowe Algorytmy transpozycyjne Sieci Fiestela Algorytm DES Algorytm IDEA Podsumowanie
37 Sieci Feistela Wiele algorytmów blokowych z jednym kluczem wykorzystuje tzw. Sieci Feistela
38 Sieci Feistela Każdy blok dzielony jest na dwie równe połówki, oznaczane dla i-tej rundy jako Li (lewa połówka) oraz Ri (prawa połówka) Właściwe szyfrowanie polega na zamianie miejscami obu połówek, a następnie zastąpieniu prawego bloku Ri przez XOR fS,i(Ri) oraz Li Funkcja fS,i wprowadza klucz i-tej rundy, czyli klucz obliczany na podstawie klucza głównego S Zazwyczaj każda runda ma inny klucz rundy Funkcje fS,i nie muszą być odwracalne
39 Sieci Feistela Szyfrowanie Li+1 = Ri Ri+1 = Li XOR fS,i(Ri) WłaściwośćLi = (Li XOR fS,i(Ri)) XOR fS,i(Ri) = Ri+1 XOR fS,i(Ri) Deszyfrowanie Rn-1 = Ln Ln-1 = Rn XOR fS,n-1(Rn-1) . . . R0 = L1 L0 = R1 XOR fS,0(R0)
40 Plan wykładu Historia Model szyfrowanie konwencjonalnego SteganografiaAlgorytmy podstawieniowe Algorytmy transpozycyjne Sieci Fiestela Algorytm DES Algorytm IDEA Podsumowanie
41 Algorytm DES - historia1971 – pierwszy patent dotyczący algorytmu Lucifer opracowanego przez Horst Fiestel i jego kolegów w IBM 1973 – NBS (National Bureau of Standar) ogłosza konkursu na algorytm szyfrujący 1977 – FIPS (wcześniej NBS) publikuje algorytm DES (ang. Data Encryption Standard) oparty na Lucifer jako standard FIPS 46 1999 – DES potwierdzony po raz 4 przez NIST w wersji Triple DES jako FIPS 46-3 2001 – publikacja AES (Advanced Encryption Standard) jako FIPS 197 2005 – NIST wycofuje DES (FIPS 46-3)
42 DES w pigułce Dane są szyfrowane w 64-bitowych blokachKlucz ma długość 56 bitów Algorytm produktowy – stosuje transpozycje w kolejnych etapach (iteracjach) Szyfrowanie polega na serii etapów przetwarzających 64-bitowe dane wejściowe na 64-bitowy wynik Deszyfrując wykonuje się te same etapy i ten sam klucz, ale w odwrotnej kolejności Najważniejszym elementem algorytmu są S-bloki (ang. S-box)
43 Ogólny schemat DES
44 Permutacja wstępna Permutację wstępną IP i jej odwrotność IP-1 definiuje poniższa tabela Obie funkcje są odwrotne względem siebie Jeżeli szyfrujemy blok M to tekst po permutacji wygląda następująco X=IP(M) Po permutacji odwrotnej otrzymujemy Y= IP-1(X)=IP-1(IP(M))=M
45 Pojedyncza iteracja DES
46 Permutacja rozszerzającaPermutacja rozszerzająca powoduje wygenerowanie z 32 bitów wejściowych 48 bitów wyjściowych według podanej tabeli
47 S-blok
48 S-blok Pierwszy i ostatni bit wejścia S-bloku wskazuje odpowiedni wiersz tabeli S-bloku Środkowe 4 bity określają kolumnę Na przykład wejście: wiersz 01 (1) kolumna 1101 (13) wyjście: 5 (0101)
49
50 Łamanie DES Krótki klucz 56 bitowych – metoda brute force ma złożoność 256 = 7*1016 Kryptoanaliza różnicowa Kryptoanaliza liniowa
51 Tryby pracy DES Elektroniczna książka kodowa ECB (ang. electronic codebook) Każdy 64-bitowy blok tekstu jawnego jest kodowany niezależnie z zastosowaniem tego samego klucza Zastosowania: bezpieczna transmisja pojedynczych wartości P P1 P2 P3 C C1 C2 C3 K K K K K K E E E D D D C1 C2 C3 P1 P2 P3
52 Tryby pracy DES Wiązania bloków zaszyfrowanych CBC (ang. cipher block chaining) Dane wejściowe algorytmu szyfrującego stanowią XOR następnych 64 bitów tekstu jawnego i poprzednich 64 bitów tekstu zaszyfrowanego Zastosowania: transmisja blokowa ogólnego zastosowania, uwierzytelnienie P P1 P2 P3 C C1 C2 C3 K K K D D D K K K E E E C1 C2 C3 P1 P2 P3
53 Tryby pracy DES Szyfrowanie ze sprzężeniem zwrotnym CFB (ang. cipher feedback) Dane wejściowe przetwarzane są po j bitów Zastosowania: transmisja strumieniowa ogólnego zastosowania, uwierzytelnienie
54 Tryby pracy DES Sprzężenia zwrotnego wyjściowego OFB (ang. output feedback) Transmisja strumieniowa przez kanał narażony na zakłócenia
55 Tryby pracy DES Przedstawione tryby pracy mogą być stosowane również dla innych algorytmów blokowych
56 Podwójny DES W związku z zagrożeniem załamania szyfrowanie DES z kluczem 56 bitowym, pojawiły się propozycje wielokrotnego użycia DES z wieloma kluczami Najprostsza wersja wielokrotnego DES to podwójny DES Przy danym tekście jawnym P i dwóch kluczach K1 i K2, tekst zaszyfrowany C jest generowany jako C=EK1(EK2(P)) Deszyfrowanie wymaga odwrócenia kolejności zastosowania kluczy P=DK2(DK1(C)) K1 K2 K2 K1 X Y P C C P E E D D
57 Potrójny DES z dwoma kluczamiPrzy danym tekście jawnym P i dwóch kluczach K1 i K2, tekst zaszyfrowany C jest generowany jako C=EK1(DK2(EK1(P))) Deszyfrowanie wymaga odwrócenia kolejności zastosowania kluczy P=DK1(EK2(DK1(C))) K1 K2 K1 A B P E C E D K1 K2 K1 B A C P D E D
58 Potrójny DES Przy danym tekście jawnym P i trzech kluczach K1, K2 i K3 tekst zaszyfrowany C jest generowany jako C=EK1(EK2(EK3(P))) Deszyfrowanie wymaga odwrócenia kolejności zastosowania kluczy P=DK1(DK2(DK3(C))) K1 K2 K3 A B P E C E E K3 K2 K1 B A C P D E D
59 Plan wykładu Historia Model szyfrowanie konwencjonalnego SteganografiaAlgorytmy podstawieniowe Algorytmy transpozycyjne Sieci Fiestela Algorytm DES Algorytm IDEA Podsumowanie
60 Algorytm IDEA International Data Encryption Algorithm (IDEA) to algorytm szyfrowania blokowego opublikowany przez Xueji Lai i James Massey (ETH Zurich) w 1991 roku IDEA to szyfr blokowy – bloki mają po 64 bity stosujący Stosowany jest 128 bitowy klucz
61 Założenia projektowe algorytmu IDEAZastosowanie 16-bitowych podbloków Zastosowanie prostych operacji arytmetycznych Podobieństwo między szyfrowaniem i deszyfrowaniem Regularna struktura ułatwiająca realizację w technice VLSI
62 Skuteczność kryptograficzna IDEADługość bloków powinna być duża, by utrudnić kryptoanalizę Długość klucza powinna uniemożliwić atak brutalną siła. Mieszanie (konfuzja) - zależność tekstu zaszyfrowanego od tekstu jawnego i klucza powinna być skomplikowana, aby utrudnić kryptoanalizę Rozpraszanie (dyfuzja)- każdy bit wejścia powinien wpływać na każdy bit tekstu zaszyfrowanego
63 Mieszanie w algorytmie IDEAW IDEA mieszanie uzyskuje się za pomocą trzech operacji wykonywanych na dwóch wejściowych 16-bitowych blokach: XOR logiczny oznaczany znakiem Dodawanie liczb całkowitych modulo 216 (65536) oznaczane jako Dane wejściowe to nieujemne liczby 16-bitowe Mnożenie liczb całkowitych modulo (65537) oznaczane jako znak
64 Rozpraszanie w algorytmie IDEARozpraszanie jest osiągane za pomocą podstawowej jednostki algorytmu nazywanej strukturą mnożenia/dodawania MA (ang. multiplication/addition) Struktura ta produkuje dwa 16-bitowe wyniki (G1,G2) z dwóch 16-bitowych wartości wejściowych tekstu jawnego (F1,F2) i dwóch 16-bitowych podkluczy wyprowadzanych z klucza (Z1,Z2)
65 Szyfrowanie za pomocą IDEA
66
67 Etap przekształcania wyników algorytmu IDEA
68 Generowanie podkluczy w algorytmie IDEAWszystkie 52 podklucze o długości 16 bitów są generowane na podstawie głównego 128 bitowego klucza Pierwsze 8 podkluczy Z1 - Z8 generowane są bezpośrednio z klucza Następnie cyklicznie przesuwamy klucz w lewo o 25 bitów i generujemy kolejne 8 podkluczy Procedurę powtarzamy do wygenerowanie 52 podkluczy 128 bitowy klucz Z15 Z1 Z16 Z2 Z9 Z3 Z10 Z4 Z17 Z11 Z5 Z18 Z12 Z6 Z19 Z13 Z7 Z20 Z14 Z8 Z15
69 Plan wykładu Historia Model szyfrowanie konwencjonalnego SteganografiaAlgorytmy podstawieniowe Algorytmy transpozycyjne Sieci Fiestela Algorytm DES Algorytm IDEA Podsumowanie
70 Podsumowanie W przeszłości stosowano głównie algorytmy wykorzystujące technikę podstawienia Współczesna kryptografia rozpoczęła się w latach 70-tych XX wieku Efektywny symetryczny algorytm szyfrujący opiera się na wykonywaniu wielu iteracji w celu zapewnienia dyfuzji i konfuzji Pierwszym powszechnie używanym algorytmem szyfrującym był DES Obecnie w związku ze wzrostem mocy obliczeniowej komputerów algorytm DES jest za słaby