1 Kryptograficzne zabezpieczenie transmisji Kryptograficzne zabezpieczenie transmisji Semestr 8, rok ak. 2007/2008 dr hab. inż. Roman Rykaczewski prof. nadzw. PG pok. 610 Politechnika Gdańska Wydział Elektroniki, Telekomunikacji i Informatyki Katedra Sieci Teleinformacyjnych

2 Zasady zaliczenia przedmiotuDwa kolokwia: kwietnia br. godz Aud.1 czerwca br. godz Aud.1 Próg zaliczenia 50% Oba kolokwia muszą być zaliczone Kolokwium zaliczeniowe dla osób, które nie zaliczyły 1. lub 2. kolokwium Katedra Sieci Teleinformacyjnych

3 Katedra Sieci Teleinformacyjnych Literatura B. Schneier: Kryptografia dla praktyków, WN-T, Warszawa 2002 N. Ferguson,B. Schneier: Kryptografia w praktyce, Helion, 2004 W. Stallings: Cryptography and Network Security: Principles and Practice, Prentice Hall, 1998 Internet We wprowadzeniu wyjaśnij słuchaczom znaczenie tematu. Przedstaw krótki przegląd prezentacji oraz zaznacz znaczenie, jakie może ona mieć dla publiczności. Podczas doboru słownictwa, przykładów oraz ilustracji weź pod uwagę zainteresowanie słuchaczy tematem oraz ich znajomość rzeczy. Skoncentruj się na znaczeniu, jakie temat ma dla słuchaczy, a będą oni uważniej słuchali. Katedra Sieci Teleinformacyjnych

4 Katedra Sieci TeleinformacyjnychProgram wykładu Wprowadzenie, cel stosowania metod kryptograficznych przy transmisji informacji, wymagania stawiane systemom kryptograficznym (SK), terminologia Matematyczny opis funkcji realizowanych przez SK, klasyfikacja SK, symetryczne i asymetryczne SK, klasyczna kryptografia Ataki kryptoanalityczne, rodzaje zabezpieczeń dawanych przez SK, kompresja danych a zabezpieczenie kryptograficzne Zasady Shannon’a tworzenia bezpiecznych SK, przykłady rozwiązań klasycznych Symetryczne SK, systemy potokowe, generatory kluczy, przykłady rozwiązań Blokowe symetryczne SK, tryby pracy-ECB, CBC, OFB, przykładowe rozwiązania- DES, modyfikacje DES, IDEA, AES Asymetryczne SK, opis ogólny, funkcje jednokierunkowe, system RSA, podstawy matematycznej realizacji algorytmu, ograniczenia Algorytm Diffi’ego-Helman’a, wykorzystanie, podstawy matematyczne realizacji Jednokierunkowe funkcje skrótu, metody tworzenia, przykłady Podpis cyfrowy, zasada, algorytm DSA Protokoły kryptograficzne, dowody wiedzy zerowej Kryptografia a kodowanie nadmiarowe Katedra Sieci Teleinformacyjnych

5 Katedra Sieci Teleinformacyjnych Wprowadzenie Bezpieczeństwo informacji (ang. information security) - zabezpieczenia fizyczne i administracyjne - zabezpieczenia komputerów (ang. computer security) - zabezpieczenia sieciowe (ang. network security) - zabezpieczenie internetu (ang. internet security) Zabezpieczenia fizyczne i administracyjne dominowały przed wprowadzeniem komputerów. Z chwilą szerokiego wprowadzenia komputerów i możliwości korzystania z nich większej liczby użytkowników zaszła potrzeba zabezpieczenia przechowywanych w nich informacji przed niepowołanym dostępem. Wraz z rozwojem sieci komputerowych pojawiła się potrzeba zabezpieczania informacji podczas transmisji między komputerami w obrębie jednej sieci. Kiedy zaczęto łączyć sieci komputerów między sobą pojawiło się szereg nowych zagrożeń – stąd wyróżniamy zabezpieczenie internetu (pisane z małej litery dla podkreślenia, że dotyczy to dowolnego zbioru połączonych sieci komputerowych, a nie tylko globalnej sieci Internet). Katedra Sieci Teleinformacyjnych

6 Katedra Sieci TeleinformacyjnychZabezpieczenie internetu: zapobieganie, wykrywanie i naprawianie naruszeń bezpieczeństwa transmitowanych danych Przykłady naruszeń bezpieczeństwa w internecie: haker monitoruje transmisję i przechwytuje pliki przekazywane między dwoma użytkownikami; administrator sieci transmituje do komputera w zarządzanej przez siebie sieci listę nowych użytkowników, którzy są uprawnieni do dostępu do tego komputera. Haker przechwytuje tę listę i ją modyfikuje lub całkowicie zmienia, a następnie przesyła ją do komputera przeznaczenia jako wiadomość pochodzącą od administratora; haker może przechwycić wiadomość (np.wiadomość o konieczności zablokowania konta bankowego) i opóźnić jej przekazanie do serwera przeznaczenia, co może spowodować stratę finansową; haker zleca dokonania transakcji finansowych, a następnie wypiera się, że to on był autorem zlecenia. Katedra Sieci Teleinformacyjnych

7 Podstawowe aspekty bezpieczeństwa informacji: Podstawowe aspekty bezpieczeństwa informacji: Usługi – działania zwiększające bezpieczeństwo przetwarzania i przesyłania informacji poprzez przeciwdziałanie atakom za pomocą określonych mechanizmów - realizacja wymagań stawianych dokumentom papierowym; Mechanizmy – zapobieganie i wykrywanie ataków, przywracanie stanu pierwotnego; Ataki – działania mające na celu zmniejszenie bądź utratę bezpieczeństwa informacji. Usługi zabezpieczania informacji powinny spełniać wymagania, jakie stawiane są dokumentom papierowym. W szczególności dokumenty w postaci elektronicznej powinny zapewniać: -rozróżnienie oryginału od kopii;- wykrycie najmniejszych zmiany w dokumencie;- możliwość udowodnienia autentyczności dokumentu. Mechanizmy bezpieczeństwa powinny zapobiegać i wykrywać ataki na bezpieczeństwo informacji oraz powinny zabezpieczać odzyskanie stanu pierwotnego po ataku. Ataki na bezpieczeństwo informacji: wszelkie działania, których celem jest zmniejszenie/utrata bezpieczeństwa informacji. Katedra Sieci Teleinformacyjnych

8 Usługi bezpieczeństwa informacji Usługi bezpieczeństwa informacji Poufność (ang. confidentiality) – zapewnia, że informacje w systemie komputerowym i podczas transmisji są dostępne jedynie upoważnionym osobom; Uwierzytelnienie (ang. authentication) – zapewnia, że źródło pochodzenia informacji zostało zidentyfikowane i nie jest ono fałszywe; Integralność (ang. integrity) – zapewnia, że do modyfikowania informacji są uprawnione jedynie upoważnione osoby; Niezaprzeczalność (ang. nonrepudiation) – zapewnia, że ani nadawca ani odbiorca wiadomości nie może wyprzeć się faktu jej przesłania i odbioru; Poufność- poufny dostęp obejmuje drukowanie, wyświetlanie a także samo ujawnienie faktu istnienia informacji. Integralność- modyfikacje obejmują zapisywanie, zmiany, zmiany statusu, wymazywanie, tworzenie, opóźnianie nadawanych wiadomości. Katedra Sieci Teleinformacyjnych

9 Usługi bezpieczeństwa informacji c.d.Sterowanie dostępem (ang. access control) – zapewnia, że dostęp do zasobów informacyjnych może być sterowany przez system docelowy; Dostępność (ang. avaliability) – zapewnia, że zasoby informacyjne są dostępne upoważnionym w każdej chwili. Katedra Sieci Teleinformacyjnych

10 Mechanizmy bezpieczeństwaBędziemy zajmować się wyłącznie kryptograficznymi technikami zapewnienia bezpieczeństwa informacji. Katedra Sieci Teleinformacyjnych

11 Ataki na bezpieczeństwo informacjiPrzerwanie transmisji – atak na dostępność; Przechwycenie wiadomości – atak na poufność; Modyfikacja wiadomości – atak na integralność; Sfabrykowanie wiadomości – atak na uwierzytelnienie Katedra Sieci Teleinformacyjnych

12 Katedra Sieci Teleinformacyjnych Klasyfikacja ataków Pasywne | Przechwycenie || Ujawnienie treści Analiza ruchu Aktywne ||| Przerwanie Modyfikacja Sfabrykowanie Ataki pasywne są trudne do wykrycia. Analiza ruchu daje informację o lokalizacji źródeł informacji, częstości, długości, strukturze wysyłanych wiadomości. Ataki aktywne Katedra Sieci Teleinformacyjnych

13 Katedra Sieci TeleinformacyjnychAtaki aktywne Atak maskaradowy – podszycie się pod innego użytkownika za pomocą przechwyconej sekwencji danych uwierzytelniających; Atak powtórzeniowy – przechwycenie bloków danych i następnie ich retransmitowanie; Atak „odmowa usługi” ( ang. denial of service ) – zablokowanie dostępu do wybranego punktu przeznaczenia lub uszkodzenie całej sieci; Katedra Sieci Teleinformacyjnych

14 Model bezpieczeństwa sieciowego Model bezpieczeństwa sieciowego Wiadomość M przesyłana od A do B jest zabezpieczana za pomocą szyfrowania przed możliwością jej odczytania przez Hakera oraz przez dodanie dodatkowej informacji umożliwiającej uwierzytelnienie nadawcy. Tajna informacja TI wyznacza konkretne przekształcenie zabezpieczające i jest znana tylko obu stronom A i B. Zaufana trzecia strona może być konieczna dla zapewnienia bezpiecznej transmisji informacji poprzez np. dostarczenie stronie A i stronie B TI lub pośredniczenie w procesie uwierzytelniania stron. Katedra Sieci Teleinformacyjnych

15 Zadania konieczne przy projektowaniu systemu bezpieczeństwa:Zaprojektowanie odpornego na ataki algorytmu zabezpieczającego wiadomości; Opracowanie mechanizmu wytwarzania tajnych informacji wykorzystywanych przez algorytm zabezpieczający; Opracowanie metod rozdziału i ewentualnego współdzielenia tajnych informacji; Opracowanie protokołu, używanego przez obie strony, zabezpieczającego odpowiednie usługi bezpieczeństwa. Katedra Sieci Teleinformacyjnych

16 Model bezpieczeństwa dostępu sieciowegoLinie obrony: procedury logowania wykorzystujące hasła; wewnętrzne mechanizmy bezpieczeństwa. Katedra Sieci Teleinformacyjnych

17 Symetryczne systemy kryptograficzneX=[X1,X2,...,XN] - tekst otwarty (ang. plaintext), Xn A, A – alfabet; Y- szyfrogram; E(•) – algorytm szyfrujący; D(•) – algorytm deszyfrujący; Katedra Sieci Teleinformacyjnych

18 Systemy asymetryczne KA , KB - klucze jawne; TA , TB – klucze tajne;y = fK (x) – funkcja jednokierunkowa (ang. One-way trap-door f.): y jest łatwe do obliczenia, jeśli K i x są znane; x = fK-1(y,T) x jest łatwe do obliczenia, jeśli K, y i T są znane; x = fK-1(y) x jest praktycznie niemożliwe do obliczenia, jeśli K i y jest znane i T jest nieznane. Katedra Sieci Teleinformacyjnych

19 Katedra Sieci TeleinformacyjnychKlasyfikacja systemów kryptograficznych ze względu na różne kryteria klasyfikacji Typ wykorzystywanych operacji przekształcających wiadomość w szyfrogram : - podstawieniowe; - przestawieniowe; - wykorzystujące naprzemienne podstawienia i przestawienia (krypto-systemy iloczynowe); Liczba użytych kluczy: - symetryczne (tajnego klucza, konwencjonalne); - asymetryczne; Katedra Sieci Teleinformacyjnych

20 Katedra Sieci TeleinformacyjnychKlasyfikacja systemów kryptograficznych ze względu na różne kryteria klasyfikacji c.d. Rodzaj operacji przetwarzania wiadomości na szyfrogram: - blokowe; - strumieniowe ( ang. stream cipher). Katedra Sieci Teleinformacyjnych

21 Katedra Sieci Teleinformacyjnych Metody kryptoanalizy Kryptoanaliza: proces mający na celu uzyskanie wiadomości X lub klucza K za pomocą ataków kryptoanalitycznych. Rodzaje ataków (w każdym przypadku kryptoanalityk zna algorytm szyfrujący i algorytm deszyfrujący): Tylko z szyfrogramem ( znany jest tylko szyfrogram); Ze znanym tekstem otwartym ( znany jest szyfrogram oraz odpowiadający mu tekst otwarty, ewentualnie znana jest większa liczba par: tekst otwarty-szyfrogram utworzonych za pomocą tajnego klucza); Atak ze znanym tekstem otwartym- w wielu przypadkach w tekstach otwartych występują znane lub łatwe do odgadnięcia fragmenty. Katedra Sieci Teleinformacyjnych

22 Metody kryptoanalizy c.d. Metody kryptoanalizy c.d. Z wybranym tekstem otwartym (znany jest szyfrogram poddawany dekryptażowi oraz kryptoanalityk ma możliwość wyboru tekstów otwartych i ich szyfrowania); Z wybranym szyfrogramem (znany jest szyfrogram poddawany dekryptażowi oraz kryptoanalityk może wybierać szyfrogramy wraz z odpowiadającymi im zdeszyfrowanymi tekstami otwartymi; Przez kolizje : - urodzinowy - spotkanie pośrodku (przy podwójnym szyfrowaniu) Atak z wybranym tekstem otwartym – atakujący może mieć wpływ na wybór tekstu otwartego. Atak na bieżąco – kolejne fragmenty tekstu otwartego mogą być wybierane po otrzymaniu szyfrogramu poprzedniego fragmentu; Atak off-line – teksty otwarte są wybierane z góry. Ataki przez kolizje - Urodzinowy- paradoks dnia urodzin (wystarczą 23 osoby, aby wśród nich były co najmniej dwie urodzone tego samego dnia) szuka się dwóch wiadomości (komunikatów) zaszyfrowanych tym samym kluczem- można wtedy wykorzystać inne komunikaty zaszyfrowane tym samym kluczem dla ataku na integralność danych Spotkanie pośrodku- tworzy się tabelę możliwych kluczy i odpowiadających im szyfrogramów możliwych komunikatów- obserwując szyfrogramy przesyłane kanałem łączności szukamy kolizji (wystąpienia szyfrogramu z tabeli) Katedra Sieci Teleinformacyjnych

23 Katedra Sieci TeleinformacyjnychAtak urodzinowy: Wykorzystanie paradoksu dnia urodzin (wystarczą 23 osoby, aby z prawdopodobieństwem  0,5 wśród nich były co najmniej dwie urodzone tego samego dnia)  Szuka się dwóch wiadomości (komunikatów), z różnych sesji łączności, zaszyfrowanych tym samym kluczem- można wtedy wykorzystać komunikaty jednej sesji, zaszyfrowane tym samym kluczem, dla ataku na integralność danych drugiej sesji. Katedra Sieci Teleinformacyjnych

24 Atak spotkaniem pośrodku (ang. meet-in-the-middle):Atak został pierwotnie zaproponowany dla SK z podwójnym szyfrowaniem kluczami K1 i K2 Spostrzeżenie: Jeżeli C = EK2(EK1(M)), to DK2(C)= DK2(EK2(EK1(M))) = EK1(M) Stąd atak: Mając znaną parę (M, C) szyfrujemy M za pomocą wszystkich możliwych kluczy K1 i wyniki po posortowaniu zapisujemy w tablicy. Następnie deszyfrujemy C używając wszystkich możliwych kluczy K2 i po każdym deszyfrowaniu sprawdzamy, czy wyniku tego nie ma w tablicy. Jeżeli znajdziemy, to tak znalezioną parę kluczy sprawdzamy na nowej parze (M,C). Katedra Sieci Teleinformacyjnych

25 System kryptograficzny bezwarunkowo bezpiecznySzyfrogramy w systemie bezwarunkowo bezpiecznym nie zawierają dostatecznej ilości informacji, aby jednoznacznie określić tekst otwarty, niezależnie od długości szyfrogramu; Jedynym przykładem jest system klucza jednorazowego. Wszystkie pozostałe systemy kryptograficzne powinny spełniać kryteria bezpieczeństwa obliczeniowego: Koszt złamania systemu powinien przewyższać koszt utraty informacji; Czas konieczny do złamania systemu powinien być dłuższy od czasu życia informacji. Katedra Sieci Teleinformacyjnych

26 Kompresja danych a szyfrowanieromryk: Kompresja danych a szyfrowanie Minimalna długość szyfrogramu, konieczna dla dekryptażu szyfru przypadkowego (Shannon 1946): H(K)/D = entropia klucza/rozwlekłość języka  30 znaków dla języka angielskiego Kompresja danych powoduje zmniejszenie rozwlekłości – granicą zmniejszenia jest entropia danych; Poprzedzenie operacji szyfrowania kompresją bezstratną zwiększa bezpieczeństwo danych. Katedra Sieci Teleinformacyjnych

27 Tabela średniego czasu przeprowadzenia ataku brutalnego (wypróbowanie ½ liczby kluczy)Długość klucza [bit] Liczba kluczy Czas ataku przy szybkości 1. deszyfracja/s 106 deszyfracji /s 32 4,3 109 35,8 min 2,15 ms 56 7,2 1016 1142 lat 10,01 h 128 3,4 1038 5, lat 5, lat 26 znaków 26!= 4,0 1026 6, lat 6,4 106 lat Katedra Sieci Teleinformacyjnych

28 Katedra Sieci TeleinformacyjnychSzyfry klasyczne Szyfry podstawieniowe: zastąpienie każdego symbolu tekstu otwartego przez inny symbol Szyfr Cesara : zastąpienie każdej litery alfabetu przez literę leżącą K pozycji dalej (oryginalny szyfr Cesara: K=3) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 a 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 Algorytm: szyfrowanie: C = E(k) = ( k + K ) mod 26 deszyfrowanie: k = D(C) = ( C – K ) mod 26 Katedra Sieci Teleinformacyjnych

29 Katedra Sieci TeleinformacyjnychAtak na szyfr Cesara: atak brutalny (wypróbowanie wszystkich 25 kluczy) Założenia do przeprowadzenia powyższego ataku: Znany algorytm szyfrowania i deszyfracji; Mała liczba możliwych kluczy; Znany język tekstu otwartego (pojawia się problem, kiedy tekst otwarty jest tekstem skompresowanym). Katedra Sieci Teleinformacyjnych

30 Podstawienie monoalfabetyczneKażdy symbol alfabetu może być zastąpiony przez dowolny symbol tego alfabetu Liczba kluczy: 26! = 4· ( algorytm DES z kluczem 56 bitów ma tylko 256 = 7 ·1016 kluczy); Atak: częstość występowania znaków w szyfrogramie odpowiada częstości występowania odpowiednich znaków w tekście otwartym – wykorzystanie tablic częstości występowania pojedynczych znaków, par znaków, trójek znaków itd. Katedra Sieci Teleinformacyjnych

31 Katedra Sieci TeleinformacyjnychSzyfr Playfair (1854 r.) Charles Wheatstone wynalazca Lord Playfair propagator szyfru Katedra Sieci Teleinformacyjnych

32 Katedra Sieci TeleinformacyjnychSzyfr Playfair (1854 r.) S E K W O J A B C D F G H L M N P Q R T U V X Y Z Klucz: sekwoja Zapisując klucz pomijamy dublujące się litery I i J traktujemy jako jedną literę Zasada szyfrowania ( szyfrujemy po dwie litery) : Dwie jednakowe litery, które tworzyłyby parę rozdzielamy dopisując wybraną, rzadko występującą, literę np.q . Literę taką dopisujemy też jako brakujące uzupełnienie do pary liter na końcu tekstu otwartego-np. bar rybak  ba rr yb ak  ba rq ry ba kq; Litery, które znajdują się w tym samym wierszu tablicy są zastępowane przez litery znajdujące się na prawo od nich, przy czym dla ostatniej litery wiersza jest to pierwsza litera tego wiersza np. para ko będzie zaszyfrowana jako WS Katedra Sieci Teleinformacyjnych

33 Katedra Sieci TeleinformacyjnychSzyfr Playfair c.d. Litery pary, które znajdują się w tej samej kolumnie tablicy są zastępowane przez litery znajdujące się poniżej nich, przy czym dla ostatniej litery kolumny jest to pierwsza litera tej kolumny np. para mz będzie zaszyfrowana jako TO; W pozostałych przypadkach każda litera pary jest zastępowana przez literę, która leży w tym samym wierszu i kolumnie drugiego elementu pary np. para er będzie zaszyfrowana jako WP; S E K W O J A B C D F G H L M N P Q R T U V X Y Z Katedra Sieci Teleinformacyjnych

34 Katedra Sieci TeleinformacyjnychSzyfr Playfair c.d. Liczba digramów: 2626=676  Trudniejsza analiza częstotliwościowa, ale szyfrogram nadal zachowuje strukturę tekstu otwartego. Do złamania wystarcza kilkaset znaków szyfrogramu. Szyfr był używany przez armię brytyjską w czasie I Wojny Światowej, a także przez armię USA i innych krajów podczas II WŚ. Katedra Sieci Teleinformacyjnych

35 Katedra Sieci TeleinformacyjnychSzyfr Hill’a (1929 r.) W szyfrze Hill’a zespoły kolejnych m liter tekstu otwartego (TO), są zastępowane przez zespoły m liter szyfrogramu. Podstawienie jest dokonywane zgodnie z m równaniami liniowymi. Algorytmu szyfrowania w postaci macierzowej: C = K M, gdzie: Km x m - macierz klucza, Mm x 1 - macierz kolumnowa TO, Cm x 1 – macierz kolumnowa szyfrogramu. Deszyfrowanie: M = K-1 C ( macierz klucza musi być nieosobliwa) !!! Wszystkie działania są wykonywane w arytmetyce modulo 26 Szyfr Hill’a zaciera informację o częstościach występowania n- gramów, gdzie n < m, ale jest nieodporny na atak ze znanym tekstem otwartym. Katedra Sieci Teleinformacyjnych

36 Szyfr Hill’a Przykład: elektronika z  PCCGZRFUYJHBKatedra Sieci Teleinformacyjnych elektronika z  PCCGZRFUYJHB

37 Podstawienie polialfabetycznePodstawienie polialfabetyczne to podstawienie wykorzystujące więcej niż jedno podstawienie monoalfabetyczne: podany jest zbiór reguł podstawień monoalfabetycznych; klucz określa, które podstawienie należy wykorzystać. Przykład: szyfr Vigenere’a (Batista Belaso w 1553 r.): Klucz: ELEKT RONIK AELEK TRONI KAELE KTRON Tekst otwarty: TOBEO RNOTT OBETH ATIST HEQUE ST ION Szyfrogram: XZFOH IAABD OFPXR TKWFB REUFI SMZCA Katedra Sieci Teleinformacyjnych

38 Katedra Sieci TeleinformacyjnychTablica Vigenere’a A 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 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 A C 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 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 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 D F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Katedra Sieci Teleinformacyjnych

39 Szyfr Vigenere’a Giovan Batista Belaso: 1553r. książka: La cifra del. Sig. Giovan Batista Belaso Blaise de Vigenère Traicte de Chiffres (1585r.) system z autokluczem Katedra Sieci Teleinformacyjnych

40 Katedra Sieci TeleinformacyjnychAtak na szyfr Vigenera Określenie długości klucza N: powtarzające się fragmenty tekstu otwartego, odległe o całkowitą wielokrotność długości klucza będą powodować występowanie powtarzających się fragmentów szyfrogramu; Atak na każde z N podstawień monoalfabetycznych. Szyfr Vigenera z autokluczem Ciąg klucza stanowi klucz właściwy uzupełniony tekstem otwartym. Atak na ten szyfr bazuje na fakcie, że klucz i tekst otwarty mają taką samą charakterystykę częstościową. Katedra Sieci Teleinformacyjnych

41 Szyfr Vernama (Gilbert Vernam 1918)Klucz ma taką samą długość jak tekst otwarty i jest statystycznie niezależny od niego; Wykorzystywany jest głównie dla danych w postaci binarnej: szyfrowanie: Cn = Mn  Kn deszyfrowanie: Mn = Cn  Kn = Mn  Kn  Kn = Mn Szyfr klucza jednorazowego (ang. one-time pad): Joseph Mauborgne: klucz w szyfrze Vernama wytwarzany jest całkowicie losowo i ma długość tekstu otwartego. W ciągu klucza nie ma powtórzeń. Katedra Sieci Teleinformacyjnych

42 Szyfry przestawienioweSzyfrogram uzyskuje się dokonując permutacji symboli tekstu otwartego-np. Szyfr „płotkowy”: Tekst otwarty: ”szpieg wytropiony” Zapis: s p e w t o i n \ / \ / \ / \ / \ / \ / \ / \ z i g y r p o y Szyfrogram: SPEWTOINZIGYRPOY Szyfr przestawieniowy zachowuje częstości symboli tekstu otwartego Katedra Sieci Teleinformacyjnych

43 Szyfry przestawieniowe c.d.Przeplot blokowy: zapis tekstu otwartego wierszami, a odczyt kolumnami wybieranymi za pomocą klucza: np. Klucz: 9, 1, 3, 5, 11, 2, 4, 7, 6, 8, 10 Tekst otwarty: 1 2 3 4 5 6 7 8 9 10 11 a k c j z y n s i e d o w r t Szyfrogram: ZOOAAWCIRADENZYKSAJETAIWZZJCSNYCC Katedra Sieci Teleinformacyjnych

44 Szyfry przestawieniowe c.d.Wzmocnienie zabezpieczenia przez powtórne zastosowanie przeplotu do szyfrogramu (z tym samym kluczem: 9, 1, 3, 5, 11, 2, 4, 7, 6, 8, 10 ) 1 2 3 4 5 6 7 8 9 10 11 Z O A W C I R D E N Y K S J T Szyfrogram: REYZEIOZZAKJDACONWAYZCASWSCIJNATC Katedra Sieci Teleinformacyjnych

45 Szyfratory rotorowe - ENIGMA Szyfratory rotorowe - ENIGMA Wielokrotne stosowanie operacji szyfrujących (podstawienia, przestawienia) powoduje zwiększenie stopnia randomizacji symboli szyfrogramu. Zasada działania szyfratorów rotorowych: Działanie Enigmy i historia jej złamania opisana jest na stronie: Inne strony: Katedra Sieci Teleinformacyjnych

46 Szyfratory rotorowe - ENIGMAKatedra Sieci Teleinformacyjnych

47 Szyfratory rotorowe - ENIGMAKatedra Sieci Teleinformacyjnych

48 Szyfratory rotorowe - ENIGMAKatedra Sieci Teleinformacyjnych

49 Szyfratory rotorowe – ENIGMA cd. Szyfratory rotorowe – ENIGMA cd. Liczba możliwych ustawień: liczba możliwych wyborów rotorów – 3 z 5 = 5 · 4 · 3 = 60 4 z 8 = 8 · 7 · 6 · 5 = 1680 liczba możliwych ustawień pierścieni- 263 = ( 3 rotory) 264 = (4 rotory) liczba możliwych krosowań liter Liczba kluczy: =1020,75 dla (3 z 5) =1023,612 dla (4 z 8) Liczba możliwych ustawień maszyny Enigma: Wybór wirników: 3 spośród 5 ( armia lądowa i lotnictwo), 4 z 8 (marynarka) Początkowe ustawienie wirników: każdy wirnik ma 26 możliwych ustawień Liczba krosowań par liter spośród 26 (skrosowanie litery A z B powoduje, że każda litera A jest zamieniana na B i odwrotnie każda litera B na A a następnie są przetwarzane przez wirniki- taka sama zamiana jest dokonywana po przetworzeniu przez wirniki): od n=0 do 13 możliwych zamiandla n kabli krosujących mamy p(n)= 26!/((26-2n)! n! 2n) możliwości  p(n)= możliwości różnych krosowań Liczba możliwych ustawień: (3 z 5) (4 z 8) Katedra Sieci Teleinformacyjnych

50 Przyczyny złamania Enigmykolejność wykorzystywanych wirników nie powinna powtarzać się w ciągu jednego miesiąca; żaden wirnik nie powinien zajmować tej samej pozycji w kolejnych dwóch dniach; wykorzystywanie tylko 10 krosowań; używanie przewidywalnych słów i zwrotów; szyfrowanie tych samych tekstów otwartych różnymi kluczami; używanie łatwych do odgadnięcia ustawień początkowych. Katedra Sieci Teleinformacyjnych

51 SYMETRYCZNE SYSTEMY KRYPTOGRAFICZNESZYFRY BLOKOWE

52 Zasada działania szyfru blokowegoPodstawienie za n bitów tekstu otwartego n bitów szyfrogramu w taki sposób, aby odwzorowanie to było odwracalne t.j. każdemu z 2n możliwych bloków n bitów wejściowych musi odpowiadać inny blok n bitów wyjściowych; Liczba możliwych odwzorowań odwracalnych: 2n! Tekst otwarty Szyfrogram 00 11 01 10 Przykład: n =2 Katedra Sieci Teleinformacyjnych

53 Realizacja bloku podstawienia Realizacja bloku podstawienia Uwaga! Zastosowanie odwzorowania liniowego C= K M , gdzie wektory C i M reprezentują odpowiednio n-bitowy blok szyfrogramu i n-bitowy blok tekstu otwartego, a macierz K o wymiarach nxn jest kluczem jest odpowiednikiem szyfru Hill’a, łatwym do kryptoanalizy. Stąd wniosek: odwzorowanie realizowane w bloku podstawienia musi być nieliniowe. Dla małych wartości n możliwa jest kryptoanaliza częstościowa (jak dla klasycznego szyfru podstawieniowego). Duża wartość n  trudność realizacji bloku podstawienia 2n  2n ( 264  1020 ) ; Objętość klucza: n 2n bitów. Katedra Sieci Teleinformacyjnych

54 Katedra Sieci TeleinformacyjnychUwaga! Zastosowanie odwzorowania liniowego C= K M gdzie: wektor C to n-bitowy blok szyfrogramu, wektor M to n-bitowy blok tekstu otwartego, macierz K o wymiarach n x n jest kluczem, jest odpowiednikiem szyfru Hill’a, łatwym do kryptoanalizy. Stąd wniosek: odwzorowanie realizowane w bloku podstawienia musi być nieliniowe !!! Katedra Sieci Teleinformacyjnych

55 Zasada Shannona konstrukcji szyfrów (1945r.) Zasada Shannona konstrukcji szyfrów (1945r.) Szyfr iloczynowy (ang. product cipher) powinien być zbudowany za pomocą naprzemiennego stosowania operacji: mieszania (ang. confusion)- przez podstawienia rozpraszania (ang. diffusion)- przez przestawienia Confusion: uczynienie relacji między właściwościami statystycznymi szyfrogramu i wartościami klucza możliwie jak najbardziej złożonymi, aby utrudnić wydobycie klucza z szyfrogramu. Osiąga się to poprzez złożone algorytmy podstawiania. Diffusion: statystyczne właściwości tekstu otwartego są rozpraszane na symbolach szyfrogramu  pojedynczy symbol szyfrogramu jest uzależniany od wielu symboli tekstu otwartego (np. symbole szyfrogramu powstają przez uśrednienie bloku kolejnych symboli TO, można to też osiągnąć przez stosowanie permutacji symboli i pewnych funkcji urównomierniającymi charakterystyki częstościowe występowania symboli). Szyfr Feistela (1973r.) – praktyczna realizacja zasady Shannona: budowa mocnego systemu kryptograficznego za pomocą kaskadowego połączenia słabszych, prostych w realizacji systemów kryptograficznych Katedra Sieci Teleinformacyjnych

56 Data Encryption Standard (DES) 1977r.Lucifer- IBM 1971r. 2n=64, K=128 bitów DES – 1977r. 2n = 64, K=56 (64-8) bitów 1994r. przedłużenie na kolejnych 5 lat DES jako standardowego systemu kryptograficznego 2001r. nowy standard AES - (Advanced Encryption Standard - Rijndael) Lucifer- IBM 1971r. 2n=64, K=128 DES – 1977r. 2n = 64, K=56 (64-8) Katedra Sieci Teleinformacyjnych

57 Katedra Sieci TeleinformacyjnychSieć Feistela Długość bloku: 2 n – typowo bity; Długość klucza: najczęściej 64, , 256, 512; Liczba rund: typowa wartość-16; Algorytm wytwarzania podkluczy: im bardziej złożony, tym SK jest trudniejszy do kryptoanalizy; Funkcja rundowa f(): im bardziej złożona (nieliniowa), tym SK jest trudniejszy do kryptoanalizy; Katedra Sieci Teleinformacyjnych

58 Zasada szyfrowania i deszyfrowania w sieci Feistela - deszyfrowanieLE16=RE RE16=LE15 F(RE15,K16) LD1=RD0=LE16=RE15 RD1=LD0  F(RD0,K16) = RE16  F(RE15,K16) =[LE15  F(RE15,K16) ]  F(RE15,K16) =LE15 Ogólnie: LEi = REi-1 REi = LEi-1  F(REi-1,Ki) stąd REi-1= LEi LEi-1=REi  F(REi-1,Ki)=REi  F(LEi,Ki) (patrz prawa strona rysunku np. dla i=15) !!! Funkcja F(•,•) nie musi być odwracalna Katedra Sieci Teleinformacyjnych

59 DES – ogólny schemat działaniaKatedra Sieci Teleinformacyjnych

60 DES – tablice permutacji IP i IP-158 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 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Numery pozycji Katedra Sieci Teleinformacyjnych

61 Katedra Sieci TeleinformacyjnychDES – struktura rundy Katedra Sieci Teleinformacyjnych

62 DES – tablice permutacji w bloku f(•):32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Permutacja z rozszerzeniem (dublowanie bitów 1. i 4. kolumny) 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 Permutacja Katedra Sieci Teleinformacyjnych

63 DES – obliczenie f( Ri-1, Ki )Katedra Sieci Teleinformacyjnych

64 DES – definicje S-bloków DES – definicje S-bloków Sześć bitów wejściowych każdego bloku b1 , b2 , b3, , b4 , b5 , b6 określa element tabeli w następujący sposób: para bitów b1 b6 określa numer wiersza w tabeli; czwórka bitów b2 b3 b4 b5 określa numer kolumny w tabeli; Wyznaczony element macierzy po zamianie na postać binarną określa wyjście S-bloku. Katedra Sieci Teleinformacyjnych

65 DES – definicje S-bloków1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 14 4 13 1 2 15 11 8 3 10 6 12 5 9 7 Sześć bitów wejściowych każdego bloku b1 , b2 , b3 ,, b4 ,, b5 ,, b6 określa element tabeli w następujący sposób: para bitów b1b6 określa numer wiersza w tabeli; czwórka bitów b2 b3 b4 b5 określa numer kolumny w tabeli; Wyznaczony element macierzy, po zamianie na postać binarną, określa wyjście S-bloku. Każdy wiersz macierzy definiuje odwracalne podstawienie. Katedra Sieci Teleinformacyjnych

66 Katedra Sieci TeleinformacyjnychDES – definicje S-bloków: podstawienie realizowane w S-bloku 1-wiersz 3 Katedra Sieci Teleinformacyjnych

67 DES – generacja kluczy-tablice:Permutacja 1 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 32 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 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 Permutacja 2 9, 18, 22, 25, 35, 38, 43, 54 Przesunięcia cykliczne w lewo Runda 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Przesunięcie Katedra Sieci Teleinformacyjnych

68 Katedra Sieci TeleinformacyjnychDES – efekt lawinowy TO1: 64 zera ; TO2:1 i 63 zera; Klucz: Rund 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Różnic 21 35 39 34 32 31 29 42 44 30 26 TO: K1: K2: Rund 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Różnic 28 32 30 35 34 40 38 31 33 26 Katedra Sieci Teleinformacyjnych

69 DES – siła zabezpieczenia DES – siła zabezpieczenia 256 = 7, kluczy w tym: klucze słabe (wytwarzają 16 jednakowych podkluczy  podwójne szyfrowanie takim kluczem daje TO) Klucze słabe (zapis szesnastkowy) Klucze faktyczne 0101 1F1F 0E0E FFFFFFF E0E0 F1F1 FFFFFFF FEFE FFFFFFF FFFFFFF klucze pół-słabe – pary różnych kluczy, które szyfrują dany TO do jednakowych szyfrogramów - niebezpieczeństwo deszyfracji jednym z kluczy pary, wiadomości zaszyfrowanej drugim kluczem z tej pary; EK1(EK2(M))=M – jest 6 takich par. Katedra Sieci Teleinformacyjnych

70 DES – siła zabezpieczenia cd.Bruce Schneier:Applied Cryptography,John Wiley & Sons, Inc. Katedra Sieci Teleinformacyjnych

71 DES – siła zabezpieczenia cd.klucze komplementarne – klucz komplementarny do danego klucza uzyskujemy przez zamianę 0 na 1 i 1 na 0; Właściwość: Y=EK(X), Y’=EK’(X’) (apostrof oznacza tu komplementarność). Wniosek: przy ataku na DES metodą wybranego tekstu jawnego wystarczy przetestować tylko połowę wszystkich kluczy tj. 255 kluczy. Katedra Sieci Teleinformacyjnych

72 DES – Kryptoanaliza różnicowa (Biham 1993)Zasada kryptoanalizy różnicowej: Podawanie na wejście szyfratora, przy ustalonym kluczu, par TO różniących się na znanych pozycjach i analiza odpowiadających im szyfrogramów: Szyfrujemy losowo wybrany TO: M otrzymujemy szyfrogram C; Wprowadzamy zmiany do M na ustalonych pozycjach i otrzymujemy TO: M*; Obliczamy M= MÅM* Szyfrujemy M i otrzymujemy C = DES(K, M) Badamy relacje między M* = MÅ M i C* = CÅ C Wykorzystuje się to, że dla pewnych M odpowiednie C występują z większym prawdopodobieństwem niż dla szyfru z idealną randomizacją bitów. Katedra Sieci Teleinformacyjnych

73 DES – Kryptoanaliza różnicowaNowe bloki: m2=m0  f(m1,K1) m3=m1  f(m2,K2) mi+1=mi-1  f(mi,Ki) m17=m15  f(m16,K16) mi=mi mi* mi+1=mi+1mi+1*= mi-1[f(mi,Ki)f(m*i,Ki)] Katedra Sieci Teleinformacyjnych

74 DES – Kryptoanaliza różnicowaZakładamy, że przy tym samym podkluczu istnieje wiele par mi, mi*, różniących się na tych samych pozycjach i dających jednakowe, odpowiednie różnice na wyjściu funkcji f(·). Stąd, jeżeli znamy takie pary różnic mi-1 i mi, to także znamy mi+1 i dysponując odpowiednio dużą liczbą takich par możemy obliczyć elementy podklucza. Katedra Sieci Teleinformacyjnych

75 DES – Kryptoanaliza liniowa (Matsui 1993) DES – Kryptoanaliza liniowa (Matsui 1993) Oznaczamy poszczególne bity bloku TO i bloku szyfrogramu: odpowiednio M[1], M[2],...,M[n] ; C[1], C[2],...,C[n] oraz bloku klucza: K[1], K[2],...,K[m]. Definiujemy operację: A[i1, i2,...,ik]=A[i1]A[i2] ...A[ik] Zasada: Należy znaleźć równania: M[ i1, i2,..., ik ]  C[ j1, j2,..., jr ]=K[k1, k2,..., ks ] gdzie 1 k,r  n, 1 s  m które są spełnione z prawdopodobieństwem  0,5. Dla dużej liczby par M-C obliczamy lewą stronę równania. Jeżeli otrzymamy więcej 0 niż 1, to przyjmujemy, że K[k1, k2,..., ks ] =0. Jeżeli jest więcej 1, to przyjmujemy, że K[k1, k2,..., ks ] =1. Dla dużej liczby powyższych relacji możliwe jest obliczenie bitów klucza. Katedra Sieci Teleinformacyjnych

76 Zasady projektowania szyfrów blokowychWymagania stawiane S-blokom (DES): Żaden bit wyjściowy S-bloku nie powinien być zbyt bliski liniowej funkcji bitów wejściowych (jeżeli wybierzemy dowolny bit wyjściowy i dowolny podzbiór 6. bitów wejściowych S-bloku, to część tych ciągów 6. bitów, dla których bit wyjściowy jest równy sumie modulo 2 bitów wejściowych powinna być możliwie bliska 0,5). Każdy wiersz macierzy S-bloku powinien zawierać wszystkie możliwe kombinacje bitów wyjściowych. Jeżeli dwa ciągi 6. bitów wejściowych S-bloku różnią się 1. bitem, to odpowiednie ciągi wyjściowe muszą różnić się co najmniej 2. bitami. Katedra Sieci Teleinformacyjnych

77 Zasady projektowania szyfrów blokowychJeżeli dwa ciągi 6. bitów wejściowych S- bloku różnią się 2. środkowymi bitami, to odpowiednie ciągi wyjściowe muszą różnić się co najmniej 2. bitami. Jeżeli dwa ciągi 6. bitów wejściowych S- bloku różnią się pierwszymi dwoma bitami, a ostatnie 2. bity są jednakowe, to odpowiednie ciągi wyjściowe nie mogą być identyczne. Katedra Sieci Teleinformacyjnych

78 Zasady projektowania szyfrów blokowych6. Dla każdej niezerowej 6. bitowej różnicy między ciągami wejściowymi S-bloku, dla nie więcej niż 8. z 32. par takich ciągów wejściowych, odpowiednie ciągi wyjściowe mogą różnić się między sobą tak samo. Katedra Sieci Teleinformacyjnych

79 Zasady projektowania szyfrów blokowychWymagania stawiane permutacji po S-blokach (DES): Cztery bity wyjściowe z każdego S-bloku w rundzie i powinny być tak przestawione, aby 2 z nich wpływały na środkowe bity wejściowe S-bloku rundy i +1, a pozostałe dwa na bity końcowe wejścia tego S-bloku. Cztery bity wyjściowe każdego S-bloku powinny mieć wpływ na 6 innych S-bloków w kolejnej rundzie i żadne 2 z nich nie mogą dotyczyć tego samego S-bloku. Dla dwóch S-bloków r i s , jeżeli bit wyjściowy z Sr wpływa na środkowy bit Ss następnej rundy, to bit wyjściowy Ss nie może wpływać na środkowy bit Sr Stąd, dla s=r, bit wyjściowy Sr nie może wpływać na bit środkowy Sr w kolejnej rundzie. Cel: uzyskanie jak największego rozproszenia bitów Katedra Sieci Teleinformacyjnych

80 Wymagania stawiane liczbie rund:Liczba rund powinna być tak wybrana, aby najlepszy znany atak kryptoanalityczny wymagał większego nakładu niż atak brutalny. Dla DES z 16. rundami kryptoanaliza różnicowa wymaga 255,1 operacji natomiast atak brutalny 255 operacji (255,1 = 247 wybranych TO x 28,1 operacji związanych z wyborem odpowiednich TO) Katedra Sieci Teleinformacyjnych

81 Wymagania stawiane funkcji f():musi to być funkcja nieliniowa; zmiana wartości dowolnego bitu wejściowego powinna powodować, z prawdopodobieństwem 1/2, zmianę wartości dowolnego bitu wyjściowego (ang. Strict Avalanche Criterion (SAC)); wartości dwóch dowolnych bitów wyjściowych powinny zmieniać się niezależnie przy zmianie wartości dowolnego bitu wejściowego (ang. Bit Independence Criterion (BIC)). Katedra Sieci Teleinformacyjnych

82 Wymagania stawiane funkcji f():jeżeli zmianie ulegnie 1 bit wejściowy, to zmienia się co najmniej n bitów wyjściowych (GAC rzędu n)); GAC  ang. Guaranteed Avalanche Criterion Katedra Sieci Teleinformacyjnych

83 Zasady projektowania S-bloków:wymiary S-bloku: n wejść x m wyjść (DES:6x4; Blowfish, CAST:8 x 32 - zwykle n =8 do10); budowa: 2n wierszy po m bitów w wierszu; powinny spełniać kryteria SAC i BIC; powinny spełniać kryterium GAC rzędu 2 do 5 . Katedra Sieci Teleinformacyjnych

84 Zasady projektowania S-bloków:Losowa generacja tablic (może być stosowana do S-bloków dużych rozmiarów); Losowa generacja tablic z testowaniem zawartości na zgodność z kryteriami; Metoda „ręczna” – przykład DES- ograniczona do małych S-bloków; Metody matematyczne; S-bloki z zawartością zależną od klucza (znaczne zwiększenie odporności na kryptoanalizę). Katedra Sieci Teleinformacyjnych

85 Katedra Sieci TeleinformacyjnychZasady użycia klucza: tworzenie podkluczy powinno zabezpieczać przed ich łatwą identyfikacją i tym samym przed możliwością odtworzenia klucza pierwotnego; proces tworzenia podkluczy powinny zabezpieczać spełnienie SAC i BIC. Katedra Sieci Teleinformacyjnych

86 Tryby pracy szyfrów blokowychKsiążki kodowej (ang. Electronic Codebook (ECB)); (każdy blok TO jest oddzielnie szyfrowany przy użyciu tego samego klucza) Wiązania bloków (ang. Cipher Block Chaining (CBC)); (kolejne bloki wejściowe są sumą XOR aktualnego bloku TO i poprzedniego bloku szyfrogramu) Sprzężenia zwrotnego szyfrogramu (ang. Cipher Feedback (CFB)); (tryb pozwalający na użycie szyfru blokowego jako szyfru strumieniowego) Sprzężenia zwrotnego wyjścia (ang. Output Feedback (OFB)); Katedra Sieci Teleinformacyjnych

87 Tryby pracy szyfrów blokowych-tryb EBCWada: identyczne bloki N bitów są dają identyczne bloki szyfrogramu. Stosuje się przy przesyłaniu małych ilości danych, np. kluczy szyfrujących. Katedra Sieci Teleinformacyjnych

88 Tryby pracy szyfrów blokowych-tryb CBCStrona nadawcza: Cn=EK(Cn-1mn) Strona odbiorcza: DK(Cn)=DK(EK(Cn-1mn)) DK(Cn)= Cn-1mn DK(Cn)  Cn-1=Cn-1mn Cn-1 = mn Możliwe są ataki bazujące na znanym WI – dlatego WI należy przekazywać zabezpieczonym kanałem (stosując szyfrowanie w trybie ECB)! WIWektor Inicjujący (ang. Initialization Vector (IV)) – musi być znany obu stronom Katedra Sieci Teleinformacyjnych

89 Tryb CBC – atak wykorzystujący niezabezpieczony WIC1=EK(WIm1); m1=WI DK(C1) Jeżeli oznaczymy X[k] k-ty bit bloku X, to m1[k]=WI[k]  (DK(C1))[k] Stąd ( A’ oznacza dopełnienie A ): m1’[k]=WI[k]’  (DK(C1))[k] Oznacza to, że zmieniając bity WI możemy zmienić odpowiednie bity m1 Katedra Sieci Teleinformacyjnych

90 Tryby pracy szyfrów blokowych-tryb CFBJednostką transmisji jest blok j bitów. Najczęściej j = 8 bitów. Szyfrowanie: C1 = m1  MSBj(EK(WI)); Kolejne jednostki szyfrogramu są zależne od wcześniejszych jednostek TO  Wada: propagacja błędów transmisji. Katedra Sieci Teleinformacyjnych

91 Tryby pracy szyfrów blokowych-tryb CFBDeszyfrowanie: C1 = m1  MSBj(EK(WI)) m1 = C1  MSBj(EK(WI)) !!! Do deszyfrowania używana jest funkcja szyfrująca. Katedra Sieci Teleinformacyjnych

92 Tryby pracy szyfrów blokowych-tryb OFBSzyfrowanie: Zaleta: brak propagacji błędów transmisji; Wada: podatność na atak modyfikujący bity szyfrogramu (dopełnienie bitu szyfrogramu  dopełnienie odpowiedniego bitu TO  możliwość „oszukania” kodu nadmiarowego) Katedra Sieci Teleinformacyjnych

93 Tryby pracy szyfrów blokowych-tryb OFBDeszyfrowanie: Zaleta: brak propagacji błędów transmisji. Wada: łatwość modyfikacji strumienia wiadomości (dopełnienie bitu szyfrogramu powoduje dopełnienie odpowiedniego bitu TO) . Katedra Sieci Teleinformacyjnych

94 Podwójne szyfrowanie:C=EK2(EK1(M)); M=DK1(DK2(C) Dwukrotne powiększenie długości klucza – dla DES, z 56 bitów do 112 bitów. Katedra Sieci Teleinformacyjnych

95 Podwójne szyfrowanie - redukcjaCzy możliwe jest zredukowanie systemu z podwójnym szyfrowaniem do systemu z szyfrowaniem pojedynczym tzn. EK2(EK1(M))= EK3(M) W 1992r udowodniono, że dla DES nie jest to możliwe. System jest podatny na atak spotkaniem pośrodku. Katedra Sieci Teleinformacyjnych

96 Atak spotkaniem pośrodku (ang. meet-in-the-middle):Spostrzeżenie: Jeżeli C=EK2(EK1(M)), to DK2(C)= DK2(EK2(EK1(M)))= EK1(M) . Stąd atak: Mając znaną parę (M, C) szyfrujemy M za pomocą wszystkich możliwych kluczy K1 i wyniki po posortowaniu zapisujemy w tablicy. Następnie deszyfrujemy C używając wszystkich możliwych kluczy K2 i po każdym deszyfrowaniu sprawdzamy, czy wyniku tego nie ma w tablicy. Jeżeli znajdziemy, to tak znalezioną parę kluczy sprawdzamy na nowej parze (M,C). Dla DES 256 operacji dla K1 i K2. Katedra Sieci Teleinformacyjnych

97 Podwójne szyfrowanie – atak spotkaniem pośrodkuDla DDES dla danego bloku wiadomości M mamy 264 możliwych bloków szyfrogramu C i 2112 możliwych kluczy  liczba różnych kluczy dających ten sam C jest równa =248  248 fałszywych alarmów; Znajomość dodatkowej pary (M,C) redukuje prawdopodobieństwo fałszywego alarmu do =2-16; Stąd, jeżeli atak spotkaniem pośrodku jest prowadzony dla dwóch par bloków (M,C), to prawdopodobieństwo znalezienia właściwych kluczy jest równe ; Wniosek: dla DDES z kluczem 112 bitów atak ze znanym TO wymaga średnio 256 operacji w porównaniu do 255 dla DES. Katedra Sieci Teleinformacyjnych

98 Szyfrowanie potrójne – dwa kluczeC=EK1(DK2(EK1(M))); M=DK1(EK2(DK1(C))) Podwojenie długości klucza – dla DES 2x56=112 bitów Kompatybilność z DES  K2=K1: C= EK1(DK1(EK1(M)))=EK1(M); Atak brutalny: 2112 (5x1033) Atak z wybranymi TO: 256 par (TO,C) Katedra Sieci Teleinformacyjnych

99 Szyfrowanie potrójne – trzy kluczeC=EK3(DK2(EK1(M))); M=DK1(EK2(DK3(C))) Potrojenie długości klucza – dla DES 3x56=168 bitów Kompatybilność z DES: K3=K2 albo K1=K2 Katedra Sieci Teleinformacyjnych

100 System kryptograficzny IDEAIDEA (International Data Encryption Algorithm) – 1990r. Szyfr blokowy – długość bloku 64 bity, długość klucza bitów; Operacje zapewniające mieszanie (ang. confusion): - poelementowe sumowanie ciągów modulo 2 () - dodawanie liczb całkowitych modulo 216 ( ‡ ) - mnożenie liczb całkowitych modulo ( ) (blok zer traktujemy jako 216) np. (1)  = 216 · 215 mod = ponieważ = (215-1)(216+1) { (215-1)(216+1) = – = ·215 – 216 = } Katedra Sieci Teleinformacyjnych

101 System kryptograficzny IDEAŻadna para operacji ,  , ‡ nie spełnia prawa rozłączności tj. np.: a  (b ‡ c) ≠ (a  b) ‡ (a  c) Żadna para operacji   ‡ nie spełnia prawa łączności tj. np.: a  (b ‡ c) ≠ (a  b) ‡ c Dzięki powyższym właściwościom IDEA jest dużo trudniejszym algorytmem do kryptoanalizy niż DES, gdzie wykorzystywana jest tylko operacja . Katedra Sieci Teleinformacyjnych

102 System kryptograficzny IDEATabela ilustrująca operacje matematyczne w SK IDEA dla bloków 2-bitowych: Katedra Sieci Teleinformacyjnych W.Stallings: Cryptography and Network Security

103 System kryptograficzny IDEAPodstawowa struktura rozpraszająca algorytmu: F1, F2 – bloki 16 bitów tekstu; Z1, Z2 - bloki 16 bitów podkluczy; G1, G2 - bloki 16 bitów wyjściowych; Struktura jest powtarzana 8 razy w przebiegu szyfrowania pojedynczego bloku 64 bitów tekstu otwartego. Katedra Sieci Teleinformacyjnych

104 System kryptograficzny IDEAStruktura algorytmu Katedra Sieci Teleinformacyjnych

105 System kryptograficzny IDEAPrzekształcenie wyjściowe: Struktura rundy (runda 1): Każda runda wymaga 6. podkluczy, natomiast przekształcenie wyjściowe 4. Katedra Sieci Teleinformacyjnych

106 System kryptograficzny IDEATworzenie podkluczy: Pierwszy podklucz każdej rundy zawiera podzbiór innych bitów klucza: Z1=Z[1...16], Z7=Z[ ], Z13=Z[ ], Z19=Z[ ], Z25=Z[ ], Z31=Z[ ], Z37=Z[ ], Z43=Z[ ]. Za wyjątkiem 1. i 8. rundy, 96 bitów podkluczy w każdej rundzie nie zawiera podciągów będących cyklicznymi przesunięciami podkluczy innych rund. Katedra Sieci Teleinformacyjnych

107 IDEA - podklucze deszyfrujące1st round: z49* z50# z51# z52* z47 z48 2nd round: z43* z45# z44# z46* z41 z42 3rd round: z37* z39# z38# z39* z35 z36 4th round: z31* z33# z32# z34* z29 z30 5th round: z25* z27# z26# z28* z23 z24 6th round: z19* z21# z20# z22* z17 z18 7th round: z13* z15# z14# z16* z11 z12 8th round: z7* z9# z8# z10* z5 z6 Final transformation: z1* z2# z3# z4* zXX* = multiplicative inverse of zXX modulus ((2^16)+1) zXX# = additive inverse of zXX modulus (2^16) Katedra Sieci Teleinformacyjnych

108 Katedra Sieci Teleinformacyjnych AES AES (Advanced Encryption Standard) 01/02/97 ogłoszenie konkursu Wymagania: wysokie bezpieczeństwo; efektywność obliczeniowa; niskie wymagania pamięciowe; możliwość wydajnej realizacji sprzętowej i programowej; prostota; elastyczność; brak elementów wymagających licencji. 10/02/00 ogłoszenie, że zwycięskim algorytmem AES jest Rijndael: Joan Daemen i Vincent Rijmen Rijndael (Rijmen & Daemen) Literatura uzupełniająca: 8-1 RR rijndael.pdf Katedra Sieci Teleinformacyjnych

109 Katedra Sieci TeleinformacyjnychAES Podstawy matematyczne: bajty są reprezentowane przez elementy ciała Galois GF(28) za pomocą reprezentacji wielomianowej tzn. bajt „b7b6b5b4b3b2b1b0” jest reprezentowany przez wielomian b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0x0; np. bajtowi „73”hex „ ”bin odpowiada wielomian „x6+x5+x4+x+1; dodawanie: sumowanie wielomianów z operacją sumowania modulo 2 współczynników  poelementowe sumowanie modulo 2 ciągów binarnych – element jednostkowy ciała względem operacji dodawania ’00’; mnożenie: wielomian nieredukowalny generujący ciało CG(28): m(x)=x8+x4+x3+x+1; iloczyn dwóch elementów ciała = reszta z podziału iloczynu odpowiadających im wielomianów przez wielomian m(x)  mnożenie wielomianów modulo wielomian m(x) – element jednostkowy ciała względem operacji mnożenia ’01’; Katedra Sieci Teleinformacyjnych

110 Katedra Sieci Teleinformacyjnych AES np. ’72’•’52’=‘1A’, ponieważ: (x6+x5+x4+x)(x6+x4+x)=x12+x11+x10+x7+ x10+x9+x8+x5+ x7+x6+x5+x2= =x12+x11+x9+x8+x6+x2 x12+x11+x9+x8+x6+x2 modulo x8+x4+x3+x+1=x4+x3+x =‘1A’ { x12+x11+x9+x8+x6+x2 = (x4+x3+x)m(x)+ x4+x3+x } ’73’   x6 +x5 +x4 +x ’52’   x6 + x4 + x Katedra Sieci Teleinformacyjnych

111 Katedra Sieci TeleinformacyjnychAES Mnożenie przez x (x’02’) x b(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x x•b(x)=x b(x) mod m(x) = Jeżeli b7=1, to jest to równoważne przesunięciu bajtu o jeden element w lewo i poelementowym zsumowaniu go z ciągiem ‘1B’ { b6x7+b5x6+b4x5+(b31)x4+(b2 1)x3+b1x2+(b0 1)x+1 } Operację tę oznacza się b = xtime (a) (w realizacji sprzętowej wymaga ona 4 XOR) Katedra Sieci Teleinformacyjnych

112 Katedra Sieci TeleinformacyjnychAES Wielomiany ze współczynnikami z GF(28): 4. bajtowym wektorom odpowiadają wielomiany stopnia mniejszego od 4; dodawanie wielomianów  dodawaniu odpowiednich współczynników  poelementowe XOR bitów; mnożenie: a(x)=a3x3+a2x2+a1x+a0 ; b(x)=b3x3+b2x2+b1x+b0 ; c(x) = a(x) b(x) = c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0 c0=a0•b0; c1=a1b0a0b1; c2= a2b0a1b1 a0b2; c3= a3b0a2b1 a1b2 a0b3; c4= a3b1 a2b2  a1b3; c5=a3b2a2b3; c6=a3•b3 Katedra Sieci Teleinformacyjnych

113 Katedra Sieci TeleinformacyjnychAES redukcja wielomianu c(x) modulo wielomian M(x) = x4 + 1 ; ponieważ x j mod (x4 + 1) = x j mod 4 zatem d(x) = a(x)  b(x) = c(x) mod (x4 + 1) = d3x3+d2x2+d1x+d0 ; d0= a0b0a3b1 a2b2 a1b3; d1= a1b0a0b1 a3b2 a2b3; d2= a2b0a1b1 a0b2 a3b3; d3= a3b0a2b1 a1b2 a0b3; Katedra Sieci Teleinformacyjnych

114 AES postać macierzowa mnożenie przez x : c(x) = x  b(x) mod x4+1jest równoważne postaci macierzowej: Katedra Sieci Teleinformacyjnych

115 AES Postać macierzowa iloczynu: c(x) = x  b(x) mod x4+1Wynika stąd, że mnożenie przez x (potęgę x) jest równoważne cyklicznemu przesunięciu bajtów wektora o jeden bajt w prawo. Katedra Sieci Teleinformacyjnych

116 Katedra Sieci TeleinformacyjnychAES AES nie ma postaci sieci Feistela. Pojedyncza runda zbudowana jest z trzech odwracalnych przekształceń nazywanych warstwami (ang. layers): liniowa warstwa mieszająca (ang. linear mixing layer) warstwa nieliniowa (ang.non-linear layer) warstwa dodawania klucza Przed pierwszą rundą występuje warstwa dodawania klucza. Liniowa warstwa mieszająca ostatniej rundy różni się od odpowiednich warstw rund pozostałych. Długości bloku i klucza (mogą być wybierane niezależnie): 128, 192, 256 bitów. Katedra Sieci Teleinformacyjnych

117 Katedra Sieci TeleinformacyjnychAES Przekształcenia w AES bazują na Stanach ( ang. State ) będących pośrednimi stanami szyfratora, reprezentowanymi przez macierz bajtów o 4. wierszach i liczbie kolumn Nb, równej długości bloku podzielonej przez 32  Nb= 4, 6, 8; Klucz Szyfrujący ( ang. Cipher Key) jest macierzą bajtów o 4. wierszach i liczbie kolumn Nk, równej długości klucza podzielonej przez 32  Nk= 4, 6, 8; Katedra Sieci Teleinformacyjnych

118 Katedra Sieci TeleinformacyjnychAES Macierz Stanu dla Nb = 4 (zapis kolumnami): Macierz Klucza dla Nk = 4 (zapis kolumnami): Katedra Sieci Teleinformacyjnych

119 Katedra Sieci TeleinformacyjnychAES Liczba rund algorytmu Nr zależy od Nb i Nk: Katedra Sieci Teleinformacyjnych

120 AES Struktura pojedynczej rundy, nie będącej rundą końcową:Struktura rundy końcowej: Round(State,RoundKey) { ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State,RoundKey); Round(State,RoundKey) { ByteSub(State); ShiftRow(State); AddRoundKey(State,RoundKey); Katedra Sieci Teleinformacyjnych

121 Katedra Sieci TeleinformacyjnychAES – struktura rundy John Savard Katedra Sieci Teleinformacyjnych

122 AES Operacja ByteSub(State)Blok podstawienia: operacja ByteSub (odwracalna): obliczenie elementu odwrotnego (multiplikatywnego) w CG(28) (przyjmuje się, że elementem odwrotnym do’00’ jest ’00’); zastosowanie transformacji afinicznej nad CG(2) Katedra Sieci Teleinformacyjnych

123 Katedra Sieci TeleinformacyjnychAES Ilustracja działania bloku podstawienia: Katedra Sieci Teleinformacyjnych

124 AES Transformacja ShiftRow(State)wiersze macierzy State są cyklicznie przesuwane w lewo o różną wartość przesunięcia: wiersz 0 nie jest przesuwany, wiersz 1 jest przesuwany o C1 bajtów; wiersz 2 jest przesuwany o C2 bajtów; wiersz 3 jest przesuwany o C3 bajtów. Przesunięcia C1, C2, C3 zależą od długości bloku Nb: Nb C1 C2 C3 4 1 2 3 6 8 Katedra Sieci Teleinformacyjnych

125 AES Transformacja ShiftRow(State) ilustracjaKatedra Sieci Teleinformacyjnych

126 AES Transformacja MixColumn(State)Kolumny macierzy State traktowane są jako wielomiany nad CG(28) i mnożone, modulo wielomian x4+1, przez ustalony wielomian c(x)=’03’x3+’01’x2+’01’x+’02’. Ponieważ wielomian c(x) jest względnie pierwszy do wielomianu x4+1, zatem przekształcenie to jest odwracalne. Działanie b(x)=c(x)  a(x) zapisane w postaci macierzowej: (patrz slajd 113) Katedra Sieci Teleinformacyjnych

127 AES Transformacja MixColumn(State) - ilustracjaTransformacja odwrotna: mnożenie kolumn przez wielomian d(x)=‘0B’x3+’0D’x2+’09’x+’0E’ { c(x)d(x)=’01’ } Katedra Sieci Teleinformacyjnych

128 AES Operacja AddRoundKey(State, RoundKey)RoundKey jest obliczany z CipherKey i ma długość bloku Nb. Katedra Sieci Teleinformacyjnych

129 AES Tworzenie kluczy rundowychKlucze rundowe Round Keys są tworzone z Cipher Key za pomocą dwóch operacji: Key Expansion (z CK tworzony jest Expanded Key) Round Key Selection (kolejne RK są tworzone z EK jako pobierane z niego kolejne Nb słowa (każde słowo składa się z 4. bajtów) Całkowita liczba bitów kluczy rundowych = Nb*(Nr + 1) Katedra Sieci Teleinformacyjnych

130 Katedra Sieci TeleinformacyjnychAES Key Expansion Expanded Key = liniowa tablica słów 4-bajtowych W[Nb*(Nr + 1)]. Pierwszych Nk słów to Cipher Key. Kolejne słowa są tworzone rekursywnie ze słów poprzedzających. Algorytm zależy od wartości Nk: Nk  6 , Nk > 6. Katedra Sieci Teleinformacyjnych

131 Katedra Sieci Teleinformacyjnych AES Zalety: Możliwość bardzo szybkiej implementacji na procesorze Pentium; Możliwość implementacji na Smart Card, mała objętość : kodu, pamięci RAM, mała liczba cykli; Przekształcenia rundowe są tak zaprojektowane, że mogą być realizowane równolegle; Niezależność od architektury procesora (czy „little endian” czy „big endian”); Przejrzysta konstrukcja matematyczna; Duża liczba możliwych wariantów długości bloku i długości klucza – od 128 do 256 bitów z krokiem 32 bitów. Katedra Sieci Teleinformacyjnych

132 Katedra Sieci TeleinformacyjnychAES Ograniczenia: Deszyfracja jest bardziej złożona niż szyfrowanie i mniej przystosowana do implementacji na Smart Card; Przy realizacji programowej szyfrowanie i deszyfrowanie są realizowane za pomocą różnych programów i wykorzystują inne tablice; Przy realizacji sprzętowej tylko niewielka część układów może być wykorzystana zarówno do szyfrowania jak i do deszyfrowania; Katedra Sieci Teleinformacyjnych

133 Katedra Sieci TeleinformacyjnychOgólne właściwości, współczesnych, zaawansowanych, blokowych, symetrycznych SK Zmienna długość klucza, długość bloku i liczba rund; Użycie operatorów arytmetycznych i boolowskich, nie spełniających praw łączności i rozłączności, jako nieliniowej alternatywy do S-bloków; Użycie przesunięć cyklicznych (rotacji) zależnych od szyfrowanych danych lub podkluczy; S-bloki zależne od klucza; Złożone algorytmy generacji podkluczy; Funkcja rundowa zależna od numeru rundy; Przeprowadzanie operacji na całym bloku. Katedra Sieci Teleinformacyjnych

134 Umiejscowienie systemu kryptograficznego w sieciach komputerowychZagadnienia: szyfrowanie w łączu telekomunikacyjnym; szyfrowanie end-to-end; szyfrowanie dla zapobieżenia analizie ruchu; rozdział kluczy. Katedra Sieci Teleinformacyjnych

135 Potencjalne miejsca przeprowadzenia ataku na poufnośćlinie telekomunikacyjne; węzeł okablowania; sieć telefoniczna. Ataki: aktywne; pasywne. Tory: metaliczne, światłowodowe, radiowe. Katedra Sieci Teleinformacyjnych

136 Szyfrowanie w łączu telekomunikacyjnym i szyfrowanie „end-to-end”Szyfrowanie w łączach (w warstwie łącza ew. w warstwie fizycznej) zabezpiecza przed analizą ruchu (nagłówki są zaszyfrowane), ale w węźle wiadomości muszą być rozszyfrowane (routing) oraz wymagana jest duża liczby kluczy, które muszą być dostarczone tylko do dwóch węzłów. Katedra Sieci Teleinformacyjnych

137 Szyfrowanie w łączu telekomunikacyjnym i szyfrowanie „end-to-end” c.d.Szyfrowanie „end-to-end” zabezpiecza przed ujawnieniem wiadomości wewnątrz sieci, ale możliwa jest analiza ruchu (nagłówki pakietów muszą pozostać niezaszyfrowane). Dla zapewnienia bezpieczeństwa należy stosować jednocześnie oba rodzaje szyfrowania: szyfr E-T-E do danych użytkownika, szyfr łącza do całego pakietu, nagłówek jest w otwartej postaci jedynie w węźle. Katedra Sieci Teleinformacyjnych

138 Szyfrowanie w łączu i end-to-endSzyfrowanie end-to-end Bezpieczeństwo end-to-end i na etapach pośrednich wiadomość widoczna w węźle nadawczym (host); wiadomość widoczna w węzłach pośrednich; przezroczyste dla użytkownika; węzeł zarządza szyfrowaniem; jedno urządzenie dla wszystkich użytkowników; realizacja sprzętowa; wszystkie wiadomości są szyfrowane; jeden klucz na każde łącze; zapewnia uwierzytelnienie węzła. wiadomość zaszyfrowana w węźle nadawczym(host); wiadomość zaszyfrowana w węzłach pośrednich; użytkownik przeprowadza szyfrowanie; użytkownik wybiera algorytm; użytkownik wybiera tryb szyfrowania; realizacja programowa; użytkownik decyduje o tym, czy szyfrować dana wiadomość, czy nie; jeden klucz na parę użytkowników; zapewnia uwierzytelnienie użytkownika; Rola użytkownika Implementacja Katedra Sieci Teleinformacyjnych

139 Przeciwdziałanie analizie ruchuAnaliza ruchu może udostępnić atakującemu: tożsamość stron; częstość komunikowania się; strukturę, liczbę i długości wiadomości; korelację przesyłanych wiadomości z zewnętrznymi zdarzeniami. Utrudnienie analizy ruchu przy szyfrowaniu w łączu: traffic padding – przy braku wiadomości nadawane są ciągi losowe. Utrudnienie analizy ruchu przy szyfrowaniu tylko E-T-E: zunifikowanie długości wiadomości przez odpowiednie uzupełnianie losowymi danymi. Katedra Sieci Teleinformacyjnych

140 Metody dystrybucji kluczyStrona A wybiera klucz i dostarcza go fizycznie stronie B; Trzecia strona wybiera klucz i dostarcza go fizycznie stronom A i B; Jeżeli strony A i B komunikowały się używając SK, to jedna ze stron może przesłać nowy klucz drugiej stronie używając SK ze starym kluczem; Jeżeli strony A i B używają szyfrowanego połączenia z trzecią stroną C, to strona C może dostarczyć klucz stronom A i B. Katedra Sieci Teleinformacyjnych

141 Katedra Sieci TeleinformacyjnychLiczba kluczy Przy szyfrowaniu E-T-E, przy N użytkownikach jeden klucz jest potrzebny dla każdej komunikującej się pary  liczba kluczy: Dla N=1000 liczba kluczy: Dla N=10000 liczba kluczy: 50 milionów Katedra Sieci Teleinformacyjnych

142 Centrum dystrybucji kluczy (CDK)CDK dokonuje rozdziału kluczy dla par użytkowników  każdy użytkownik musi posiadać unikatowy klucz do komunikowania się z CDK; Hierarchia kluczy: Klucze główne (ang. master keys) - liczba kluczy N - służą do przesyłania kluczy sesyjnych; Klucze sesyjne (ang. session keys) – służą do szyfrowania E-T-E dla danego połączenia, po czym są wymazywane; Katedra Sieci Teleinformacyjnych

143 Przykład systemu rozdziału kluczyZałożenia: Każdy użytkownik dysponuje kluczem głównym z CDK – użytkownik A – KA , użytkownik B - KB ; Użytkownik A chce ustanowić połączenie logiczne z użytkownikiem B i potrzebuje klucza sesyjnego dla zabezpieczenia transmisji. Realizacja: A, używając KA , wysyła zapotrzebowanie do CDK na klucz sesyjny dla transmisji do B, które zawiera: identyfikator A; identyfikator B; unikatowy identyfikator transakcji N1 ( znacznik czasu, liczba losowa itp.) różny dla każdej transakcji i trudny do odgadnięcia dla hakera chcącego przeprowadzić atak maskaradowy); Katedra Sieci Teleinformacyjnych

144 Przykład systemu rozdziału kluczy – c.d.CDK odpowiada A używając klucza KA (tylko A może odczytać wiadomość i A ma pewność, że wiadomość pochodzi od CDK). Wiadomość ta zawiera 2. informacje dla A: - jednorazowy klucz sesyjny KS; - powtórzenie wiadomości otrzymanej od A (daje to A możliwość sprawdzenia, czy oryginalne zapotrzebowanie na klucz sesyjny nie zostało zmodyfikowane przed jego odbiorem przez CDK albo nie jest powtórzeniem wcześniejszego zapotrzebowania); oraz 2. informacje przeznaczone dla B, zaszyfrowane kluczem KB: - identyfikator A: IDA A zapamiętuje klucz sesyjny KS i wysyła do B otrzymane od CDK informacje przeznaczone dla B tj ( B zna teraz klucz sesyjny- wie, że nastąpi komunikacja z A i wie, że wiadomości te pochodzą od CDK); Obie strony dysponują teraz kluczem sesyjnym Katedra Sieci Teleinformacyjnych

145 Przykład systemu rozdziału kluczy – c.d.Dla upewnienia B, że otrzymane dane nie są powtórzeniem wiadomości wcześniejszych: B, używając klucza sesyjnego KS wysyła do A identyfikator N2; A, używając KS wysyła B f(N2), gdzie funkcja f() jest pewnym, znanym przekształceniem N2 Katedra Sieci Teleinformacyjnych

146 Przykład systemu rozdziału kluczy – c.d.Katedra Sieci Teleinformacyjnych

147 Generowanie liczb losowych Generowanie liczb losowych Cel: identyfikatory, klucze do SK Właściwości: losowość w sensie 2. podstawowych kryteriów: rozkład równomierny, niezależność statystyczna symboli; spełnienie testów losowości. Praktyczne znaczenie mają deterministyczne algorytmy wytwarzania liczb o charakterze zbliżonym do losowego- możliwie niewiele różniące się od realizacji dyskretnego białego szumu o rozkładzie równomiernym. Katedra Sieci Teleinformacyjnych

148 Testy losowości dla ciągów binarnychTest częstości pojedynczych bitów - statystyka: X1=(n0 - n1)2/n ma rozkład 2 z 1. stopniem swobody dla n 10; Test par bitów- statystyka: X2=(n002 + n012 +n102 +n112)2 4/(n-1) - (n02 + n12) 2/n +1 ma rozkład 2 z 2. stopniami swobody dla n 21; Katedra Sieci Teleinformacyjnych

149 Katedra Sieci TeleinformacyjnychTesty losowości dla ciągów binarnych Test pokerowy - bada, czy podciągi o długości m występujące w ciągu o długości n występują w przybliżeniu tak samo często- statystyka: ma rozkład 2 z 2m-1. stopniami swobody; Katedra Sieci Teleinformacyjnych

150 Katedra Sieci TeleinformacyjnychTesty losowości dla ciągów binarnych Test serii - bada, czy liczby serii zer i serii jedynek różnych długości są takie jak dla ciągu losowego- statystyka: Bi - liczba serii długości i; Gi - liczba pauz między seriami długości i; ei = (n-i+3)/2i+2 - średnia liczba serii (albo pauz) w losowym ciągu binarnym o długości n; ma rozkład 2 z 2j-2. stopniami swobody; Katedra Sieci Teleinformacyjnych

151 Testy losowości dla ciągów binarnychTest autokorelacyjny- bada korelację między badanym ciągiem i jego przesunięciem o zadaną liczbę pozycji d A(d) - odległość ciągu badanego od jego przesuniętej wersji Statystyka: ma w przybliżeniu rozkład N(0,1) jeżeli n-d  10 Katedra Sieci Teleinformacyjnych

152 Katedra Sieci TeleinformacyjnychTesty losowości dla ciągów binarnych Test FIPS-140-1: badany jest ciąg bitów. Jeżeli nie jest spełniony jeden z 4. testów, to generator jest dyskwalifikowany: -test monobitowy: 9654 -test pokerowy- X3 dla m=4 musi spełniać nierówności: 1,03 -test serii-1 i  6, Bi, Gi muszą zawierać się w granicach podanych w tabeli: Katedra Sieci Teleinformacyjnych

153 Katedra Sieci TeleinformacyjnychTesty losowości dla ciągów binarnych Test FIPS cd Długość serii Przedział 1 2 3 4 5 90-223 6 Test długich serii - jest spełniony, jeżeli jeżeli nie występują serie długości 34 lub dłuższe. Katedra Sieci Teleinformacyjnych

154 Generatory liczb pseudolosowychLiniowe generatory kongruencyjne: Xn+1 = (a Xn + c) mod m 0  X0 < m – wartość początkowa (ziarno); 0  a < m - mnożnik; 0  c < m - przyrost; m > 0 - moduł. Jeżeli X0 , a, c, m są liczbami całkowitymi, to Xn są liczbami całkowitymi 0  Xn  m-1 . Katedra Sieci Teleinformacyjnych

155 Liniowe generatory kongruencyjne c.d.Typowa wartość m : 231-1; Kryteria dla LGK: - generator pełnego okresu (ang. full period) ( wszystkie wartości z zakresu 0 do m-1 powinny wystąpić przed ich powtórzeniem); - ciąg liczb powinien spełniać kryteria losowości; - algorytm powinien być łatwo realizowalny w arytmetyce 32- bitowej. Katedra Sieci Teleinformacyjnych

156 Liniowe generatory kongruencyjne c.d.Jeżeli m jest liczbą pierwszą i c=0, to dla niektórych wartości a okres generatora jest równy m-1 (bez wartości 0). Dla m = 231 –1 (liczba pierwsza) Xn+1 = a Xn mod 231 –1 Tylko dla niewielkiej liczby wartości a generatory spełniają wszystkie 3 kryteria. np. a = 75 = – generator dla IBM 360 Katedra Sieci Teleinformacyjnych

157 Liniowe generatory kongruencyjne c.d.Jedynym losowym elementem generatora jest wartość ziarna X0  łatwość kryptoanalizy: - jeżeli znamy wartości X0, X1, X2, X3, to z równań: X1 = (a X0 + c) mod m X2 = (a X1 + c) mod m X3 = (a X2 + c) mod m możemy obliczyć a, c, m. Katedra Sieci Teleinformacyjnych

158 Kryptograficzne generatory liczb losowychKatedra Sieci Teleinformacyjnych

159 Generatory liczb losowych c.d.Ciągi binarne wytwarzane przez rejestry przesuwające ze sprzężeniem zwrotnym (ang. feedback shift register): Funkcja sprzężenia zwrotnego może być liniowa albo nieliniowa. Katedra Sieci Teleinformacyjnych

160 Generatory liczb losowych c.d.Rejestr przesuwający z liniowym sprzężeniem zwrotnym (ang. linear feedback shift register (LFSR)): przykład Wielomian generujący: g(x) = 1 + x + x3 Wielomian pierwotny: wielomian pierwszy (nieredukowalny) stopnia m będący dzielnikiem dwumianu Jeżeli g(x) jest wielomianem pierwotnym, to ciąg{ak} jest ciągiem maksymalnego okresu – m – ciągiem. Okres m-ciągu: 2m - 1 Katedra Sieci Teleinformacyjnych

161 Kombinacje generatorów LFSRf ( x1 , x2 , ... , xn ) Katedra Sieci Teleinformacyjnych

162 Przykład kombinacji trzech generatorów - generator GeffeZłożoność liniowa generatora: długość najkrótszego rejestru LFSR, który może wytworzyć ciąg wyjściowy tego generatora Złożoność liniowa generatora Geffe: n = ( n2 + 1) n1 + n2 n3 Szyfr A5 ( stosowany w GSM ) : 3 LFSR o długościach 19,22,23 Katedra Sieci Teleinformacyjnych

163 Generator klucza dla szyfru A5/1 stosowanego w GSMLFSR o długościach 19,22,23 W każdym cyklu analizowane są bity taktowania i określany jest bit większościowy. Rejestr jest taktowany, jeżeli odpowiedni bit taktowania jest zgodny z bitem większościowym. Katedra Sieci Teleinformacyjnych

164 Generator klucza w szyfrze E0 stosowanym w BluetoothKatedra Sieci Teleinformacyjnych

165 Katedra Sieci TeleinformacyjnychGenerator klucza w szyfrze E0 stosowanym w Bluetooth Katedra Sieci Teleinformacyjnych

166 Katedra Sieci TeleinformacyjnychGenerator klucza w szyfrze E0 stosowanym w Bluetooth Ophir Levy Avishai Wool:A Uniform Framework for Cryptanalysis of the Bluetooth E0 Cipher Katedra Sieci Teleinformacyjnych

167 Katedra Sieci TeleinformacyjnychGenerator ANSI X9.17 i – numer cyklu generacji; DTi –aktualna data i czas; Vi – ziarno; K1, K2 – klucze dla 3DES; Ri – wyjście generatora Katedra Sieci Teleinformacyjnych

168 Katedra Sieci TeleinformacyjnychGenerator Blum Blum Shub (1986r.) Lenore Blum, Manuel Blum, and Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364–383, May 1986. Wybieramy dwie duże liczby pierwsze: p i q takie, że p  q  3 mod 4 np. 7  19  3 mod 4 Obliczamy: n = p · q; Wybieramy losowo liczbę s względnie pierwszą do n ( ani p ani q nie jest dzielnikiem s ); Katedra Sieci Teleinformacyjnych

169 Generator Blum Blum Shub - algorytmCiąg bitów Bi , i = 1,2,..., N wytwarzany jest zgodnie z algorytmem: X0 = s2 mod n for i = 1 to N Xi = ( Xi-1 )2 mod n Bi = Xi mod 2 end Katedra Sieci Teleinformacyjnych

170 Generator Blum Blum ShubGenerator spełnia „test następnego bitu”: Nie istnieje algorytm, działający w czasie wielomianowym*), który na podstawie znajomości k pierwszych bitów ciągu pseudolosowego może przewidzieć wartość bitu k +1 z prawdopodobieństwem istotnie większym od 0.5; Generator jest uznawany jako praktycznie bezpieczny. *)algorytm, którego czas działania jest ograniczony przez wielomian od rozmiaru danych wejściowych Katedra Sieci Teleinformacyjnych

171 Asymetryczne systemy kryptograficzne (systemy klucza publicznego)Katedra Sieci Teleinformacyjnych

172 Katedra Sieci TeleinformacyjnychProblem z dystrybucją kluczy przy wykorzystaniu symetrycznych systemów kryptograficznych dla bezpiecznej wymiany informacji w sieciach komputerowych: Dla każdej z n osób komunikujących się z sobą konieczne jest wytworzenie i bezpieczne przesłanie n – 1 kluczy; Łączna liczba kluczy, wymagających bezpiecznego przesłania, dla n = 500, przy zmianie kluczy co godzinę: kluczy na dobę Katedra Sieci Teleinformacyjnych

173 Katedra Sieci TeleinformacyjnychSystem asymetryczny Przy wykorzystaniu systemów kryptograficznych z kluczem jawnym: wystarcza opublikowanie n kluczy jawnych (szyfrujących) każdej osoby; brak konieczności bezpiecznego przesyłania kluczy (para kluczy: jawny (szyfrujący) i tajny (deszyfrujący) wytwarzane są przez każdą z n osób lokalnie. Katedra Sieci Teleinformacyjnych

174 System asymetryczny KA , KB - klucze jawne; TA , TB – klucze tajne;y = fK (x) – funkcja jednokierunkowa (ang. One-way trap-door f.): y jest łatwe do obliczenia, jeśli K i x są znane; x = fK-1(y) x jest łatwe do obliczenia, jeśli K, T i y są znane; x = fK-1(y) x jest praktycznie niemożliwe do obliczenia, jeśli y i K jest znane i T jest nieznane. Katedra Sieci Teleinformacyjnych

175 Porównanie systemów symetrycznych i asymetrycznychSymetryczny SK | Asymetryczny SK Konieczne do działania: - ten sam algorytm z tym samym kluczem używany do szyfrowania i deszyfrowania; - nadawca i odbiorca współdzielą algorytm i klucz; Konieczne dla bezpieczeństwa: - klucz musi być tajny; - bez znajomości klucza odczytanie wiadomości niemożliwe lub praktycznie niemożliwe; Konieczne do działania: - jeden algorytm jest wykorzystywany do szyfrowania i deszyfrowania z dwoma kluczami: jeden do szyfrowania, drugi do deszyfrowania; - nadawca i odbiorca współdzielą algorytm, ale każda strona dysponuje jedną z dopasowanych par kluczy (KB,TA), (KA,TB) ; Katedra Sieci Teleinformacyjnych

176 Porównanie systemów symetrycznych i asymetrycznychKonieczne dla zapewnienia bezpieczeństwa: Symetryczny SK | Asymetryczny SK Klucze muszą być utajnione; dekryptaż szyfrogramu bez dodatkowych informacji powinien być co najmniej praktycznie niemożliwy; znajomość algorytmu i próbek szyfrogramów powinna być niewystarczająca do określenia klucza. jeden z dwóch kluczy musi być kluczem tajnym; dekryptaż szyfrogramu bez dodatkowych informacji powinien być co najmniej praktycznie niemożliwy; znajomość algorytmu i próbek szyfrogramów oraz jednego z kluczy powinna być niewystarczająca do określenia drugiego klucza. Katedra Sieci Teleinformacyjnych

177 Uwierzytelnianie za pomocą asymetrycznego SKC = ETA( M) M = DKA( C) Tylko A mógł wytworzyć C, bo tylko A dysponuje tajnym kluczem TA  szyfrowanie tajnym kluczem stanowi odpowiednik podpisu. Katedra Sieci Teleinformacyjnych

178 Zapewnienie bezpieczeństwa i uwierzytelnienia przez asymetryczny SKF = EKB[ ETA(M)] M = DKA[ DTB(F)]  utajnienie podpis (uwierzytelnienie) Katedra Sieci Teleinformacyjnych

179 System RSA (Autorzy:Ron Rivest, Adi Shamir, Leonard Adleman)Funkcja jednokierunkowa: Obliczenie y = f(x) jest łatwe. Obliczenie x = f-1 ( y ) jest praktycznie niewykonalne bez dodatkowych informacji. Trudny problem wykorzystany w systemie RSA, zabezpieczający odkrycie tajnego klucza: trudność faktoryzacji dużych liczb na czynniki pierwsze Katedra Sieci Teleinformacyjnych

180 RSA – algorytm generacji kluczyWybieramy dwie duże ( 512 – 1024 bitów) liczby pierwsze p i q Obliczamy ich iloczyn: n = p q Wybieramy losowo liczbę naturalną e < (p – 1) ( q – 1) względnie pierwszą z liczbą ( p – 1 ) ( q – 1) , która razem z liczbą n stanowi klucz jawny ( n, e ) Za pomocą algorytmu Euklidesa obliczamy liczbę d = e -1 mod ( p – 1) ( q – 1 ) { ed = 1 mod (p-1)(q-1)} która razem z liczbą n stanowi klucz tajny ( n, d ) 5. Liczby p i q wymazujemy z pamięci Katedra Sieci Teleinformacyjnych

181 RSA – przykład generacji kluczyp = 3, q = 11 n = p q = 33 (p-1) (q-1) = 2 • 10 = 2 • 2 • 5 = 20 Liczbę e musimy wybrać tak, aby była względnie pierwsza do 20 tzn. nie może zawierać czynników 2 i 5  możliwe pary liczb e i d: e d e • d e • d mod 20 Katedra Sieci Teleinformacyjnych

182 Katedra Sieci TeleinformacyjnychRSA – szyfrowanie Wiadomość szyfrowaną dzielimy na bloki mi i=1,2,...,L o takiej długości, aby ich reprezentacja liczbowa była mniejsza od n; Obliczamy bloki szyfrogramu: ci = mie mod n ; i=1,2,...,L Katedra Sieci Teleinformacyjnych

183 RSA – deszyfrowanie Obliczamy bloki wiadomości:Twierdzenie Eulera: Jeżeli liczby naturalne m i n są względnie pierwsze i m < n, oraz k jest dowolną liczbą całkowitą, to m k (n) = 1 mod n gdzie funkcja (n) jest funkcją Eulera ( liczba dodatnich liczb całkowitych < n i względnie pierwszych do n . Jeżeli n=p q, gdzie p i q są liczbami pierwszymi, to (n) = (p-1)(q-1) ). (a·b) mod n = [(a mod n) · (b mod n)] mod n Obliczamy bloki wiadomości: mi = cid mod n ; i=1,2,...,L Katedra Sieci Teleinformacyjnych

184 Katedra Sieci TeleinformacyjnychRSA – ograniczenia Znajomość tylko jednej pary ( e, d ) umożliwia atakującemu faktoryzację modułu n; Znajomość tylko jednej pary ( e, d ) umożliwia atakującemu obliczenie innych par wykładników bez konieczności faktoryzacji modułu n; Nie powinno się wykorzystywać jednego modułu przy pracy w sieci; Nie powinno się wybierać małych wartości wykładników (przyspieszają szyfrowanie, ale ułatwiają ataki). Katedra Sieci Teleinformacyjnych

185 Katedra Sieci TeleinformacyjnychRSA – ograniczenia Jeżeli moduł n=p q, gdzie liczby pierwsze p i q mają takie wartości, że q < p < 2 q , a wykładnik d < 1/3 n1/4, to istnieje efektywny algorytm pozwalający na obliczenie d, przy znajomości n oraz drugiego wykładnika e (klucza jawnego). Jeżeli moduł n=p q ma m cyfr binarnych i znane jest m/4 pierwszych lub m/4 ostatnich cyfr, to możliwa jest efektywna faktoryzacja modułu n. Jeżeli moduł n=p q ma m cyfr binarnych i znane jest co najmniej m/4 ostatnich cyfr wykładnika d, to możliwe jest obliczenie d w czasie proporcjonalnym do wartości e ln(e). Katedra Sieci Teleinformacyjnych

186 Asymetryczne SK - zarządzanie kluczamiDystrybucja kluczy publicznych: - rozdział niekontrolowany ( ang. Public Announcement of P-K ); - ogólnie dostępny katalog ( ang. Publicly Availiable Directory ); - centralny rejestr kluczy ( ang. Public-Key Authority ); - centrum certyfikacyjne ( ang. Public-Key Certificate Authority ) Katedra Sieci Teleinformacyjnych

187 Rozdział niekontrolowanyWada: łatwość podszycia się pod inną osobę Katedra Sieci Teleinformacyjnych

188 Ogólnie dostępny katalogKatalogiem zarządza zaufana jednostka albo organizacja; Katalog zawiera nazwisko (nazwę) oraz klucz publiczny każdego użytkownika; Każdy użytkownik może w dowolnej chwili zastąpić dany klucz innym; Zarządzający katalogiem okresowo publikuje cały katalog albo jego aktualizacje; Dostęp elektroniczny do katalogu powinien być zabezpieczony (uwierzytelnianie i bezpieczna transmisja). Wada: złamanie zabezpieczenia 5. "odkrywa" wszystkich uż. Katedra Sieci Teleinformacyjnych

189 Centralny rejestr kluczy (CRK)A wysyła do CRK żądanie, oznaczone czasowo (ang. time-stamped), dostarczenia klucza publicznego B; CRK odpowiada wiadomością, zaszyfrowaną kluczem prywatnym CRK, która zawiera: Klucz publiczny B ; Powtórzenie żądania A; Znacznik czasowy; A wysyła do B wiadomość zaszyfrowaną kluczem publicznym B, podając swój identyfikator IDA i identyfikator transmisji IT1; Katedra Sieci Teleinformacyjnych

190 Centralny rejestr kluczy (CRK)5. B uzyskuje klucz publiczny A z CRK w analogiczny sposób, jak A uzyskał klucz B; B wysyła do A wiadomość zaszyfrowaną kluczem publicznym A, dołączając znacznik transmisji IT1 otrzymany od A (ponieważ tylko B mógł odszyfrować wiadomość 3, obecność IT1 upewnia A, że autorem wiadomości jest B) i swój znacznik transmisji IT2; A odpowiada B wysyłając znacznik IT2 zaszyfrowany kluczem publicznym B- upewnia to B, że autorem wiadomości jest A. Wada: duży nakład protokolarny, CRK może stać się "wąskim gardłem" Katedra Sieci Teleinformacyjnych

191 Katedra Sieci TeleinformacyjnychCentrum certyfikacji Każdy użytkownik może odczytywać certyfikat, aby określić nazwę i publiczny klucz właściciela certyfikatu; Każdy użytkownik może sprawdzić, że certyfikat pochodzi z CC i nie jest podrobiony; Tylko CC może tworzyć i uaktualniać certyfikaty; Każdy użytkownik może sprawdzić aktualność certyfikatu Za pomocą bezpiecznej, uwierzytelnionej transmisji A uzyskuje certyfikat: CA= ETcc(T, IDA , KA) (T=czas ważności) Sprawdzenie certyfikatu: DKcc(CA)=DKcc(ETcc(T, IDA , KA)= {T, IDA , KA} Katedra Sieci Teleinformacyjnych

192 Algorytm Diffiego-HellmanaAlgorytm D-H może być wykorzystywany do dystrybucji kluczy dla symetrycznych systemów kryptograficznych; Wykorzystywany trudny problem: trudność obliczenia logarytmów dyskretnych w ciałach skończonych- potęgowanie w takich ciałach jest łatwe; Katedra Sieci Teleinformacyjnych

193 Algorytm Diffiego-Hellmana c.d.Strony A i B wybierają dwie duże ( bity) liczby całkowite n i g, takie, że 1 < g < n. Liczby n i g nie muszą być tajne. Strona A wybiera losowo dużą liczbę całkowitą x i oblicza X = gx mod n Strona B wybiera losowo dużą liczbę całkowitą y i oblicza Y = gy mod n ( liczby x i y są utrzymywane w tajemnicy przez obie strony) Katedra Sieci Teleinformacyjnych

194 Algorytm Diffiego-Hellmana c.d.Strona A oblicza: K = Y x mod n; Strona B oblicza: K’ = X y mod n. Liczby K i K’ stanowią wspólny klucz dla stron A i B K= (gy)x = gxy = (gx)y= K’ Atakujący zna tylko liczby n, g, X i Y i bez obliczenia logarytmu dyskretnego liczb X i Y nie jest w stanie obliczyć K (K’). Katedra Sieci Teleinformacyjnych

195 Algorytm Diffiego-Hellmana c.d.Katedra Sieci Teleinformacyjnych

196 Katedra Sieci Teleinformacyjnych Kryptografia oparta o krzywe eliptyczne (ang. Elliptic Curve Cryptography (ECC)) Zaleta w stosunku do RSA: dużo mniejsze nakłady obliczeniowe przy porównywalnym bezpieczeństwie. Krzywe eliptyczne Opisane są równaniami 3 stopnia: y2 + d x y + e y = x3 + c x2 + a x + b gdzie a, b, c, d, e są liczbami rzeczywistymi, spełniającymi pewne, proste warunki. Do definicji krzywych eliptycznych należy także element O nazywany punktem w nieskończoności (ang. point at infinity) albo punktem zerowym ( ang. zero point ). Katedra Sieci Teleinformacyjnych

197 Katedra Sieci TeleinformacyjnychECC Każda prosta przecina krzywą eliptyczną w trzech punktach, wliczając punkt zerowy, lub jest do niej styczna. Dodawanie dla krzywych eliptycznych (KE): Jeżeli 3 punkty na KE leżą na linii prostej, to ich suma jest równa O; O jest elementem jednostkowym względem dodawania  O = -O i dla dowolnego punktu P na KE zachodzi P + O = P; Linia pionowa przecina KE w dwóch punktach i przechodzi przez punkt zerowy - Q + R + O = O  R= -Q; Aby podwoić dany punkt Q należy poprowadzić styczną przechodzącą przez ten punkt i znaleźć punkt R jej przecięcia z KE  Q + Q + S = O  2 Q = - S Katedra Sieci Teleinformacyjnych

198 Katedra Sieci TeleinformacyjnychECC y2 = x3-3x+1 Q+R+P1 = O Q+R = -P1 y2 = x3-x+1 Q+R+P1 = O Q+R = - P1 P1 + (-P1) = O Katedra Sieci Teleinformacyjnych

199 ECC – mnożenie przez liczbę naturalnąW punkcie Q prowadzimy styczną do KE Q + Q +P = O 2 Q = -P 2 Q = (0,2) 3 Q = 2Q + Q= (-2,-2) Katedra Sieci Teleinformacyjnych

200 Katedra Sieci TeleinformacyjnychECC – grupa eliptyczna Ep(a,b) - grupa eliptyczna mod p ( p jest liczbą pierwszą ), której elementy (x,y) są parami liczb całkowitych nieujemnych, mniejszych od p, spełniających równanie; y2  x3 + a x + b (mod p) gdzie a, b są nieujemnymi liczbami całkowitymi, mniejszymi od p, takimi, że: 4 a3 +27 b2 (mod p)  0 oraz zawiera punkt w nieskończoności O (element jednostkowy grupy). Katedra Sieci Teleinformacyjnych

201 ECC- grupa eliptyczna - przykładp = 23; y2=x3+x+1; 4•13+27• 13 = 31 mod 23 = 8  0; p = 23 Katedra Sieci Teleinformacyjnych

202 ECC- grupa eliptyczna – przykład c.d.dla każdej wartości x = 0,1,2,...,p-1 obliczamy x3+a x + b (mod p); dla każdej tak obliczonej wartości sprawdzamy, czy istnieje dla niej pierwiastek kwadratowy mod p; jeżeli pierwiastek nie istnieje, to nie ma elementów grupy eliptycznej dla tej wartości x; jeżeli pierwiastek istnieje, to dla tej wartości x istnieją dwa elementy grupy eliptycznej Ep(a,b) Katedra Sieci Teleinformacyjnych

203 ECC- grupa eliptyczna – przykład c.d.(0,1) (6,4) (12,19) (0,22) (6,19) ( 13, 7) ( 1,7 ) (7 ,11 ) (13 , 16) ( 1, 16) ( 7,12 ) ( 17, 3) (3 ,10 ) ( 9,7 ) (17 , 20) ( 3,13 ) (9 ,16 ) ( 18,3 ) ( 4, 0) ( 11,3) (18 , 20) ( 5,4) ( 11,20) ( 19, 5) (5 , 19) (12 , 4) ( 19, 18) x=1 y2 = = 3 mod 23=(3+223) mod23=49 mod 23  31/2mod23=7 -7mod23=(-7+23)mod23=16 Katedra Sieci Teleinformacyjnych

204 ECC- grupa eliptyczna – reguły dodawaniaDla dowolnych dwóch punktów P, Q  Ep(a,b): P + O = P ; Jeżeli P = (x,y), to P + (x,-y) = O; - P = (x,-y)  Ep(a,b) ; Jeżeli P = (x1,y1) i Q = (x2,y2) i P - Q ,to punkt P+Q=(x3,y3) ma współrzędne: x3 = 2 – x1 – x (mod p) y3 =  (x1 – x3) – y1 (mod p) Katedra Sieci Teleinformacyjnych

205 ECC- grupa eliptyczna – reguły dodawania c.d.gdzie P=(5,4) P+P=(x3,y3)  = (3·52+1)/2 · 4 = 76/8 = 7/8  21 mod 23 { 7/8 = (7+7 · 23)/8 = 21 } x3 = 212 –5 – 5 = = 431 = 19*23+4  4 mod 23 y3 = 21 · (5 - 4) - 4  17 mod 23 2*P = (4,17) Katedra Sieci Teleinformacyjnych

206 ECC – trudny problem Weźmy równanie:Q = k P; Q, P  Ep(a,b) , k < p Mając dane k i P łatwo jest obliczyć Q. Trudnym problemem wykorzystywanym w kryptografii jest trudność obliczenia k, mając dane Q i P. Katedra Sieci Teleinformacyjnych

207 Katedra Sieci TeleinformacyjnychECC – wymiana kluczy Definiujemy grupę eliptyczną Ep(a,b) p2180; Wyznaczamy t.zw. punkt generujący G(x1,y1), w taki sposób, aby najmniejsza wartość n, dla której n G(x1,y1)=O była bardzo dużą liczbą pierwszą; Ep(a,b) i G(x1,y1) są znane wszystkim użytkownikom; Katedra Sieci Teleinformacyjnych

208 Katedra Sieci TeleinformacyjnychECC – wymiana kluczy c. d. Wymiana kluczy pomiędzy A i B: A wybiera liczbę całkowitą nA < n ; nA to klucz prywatny A; klucz publiczny A: KA = nA G (punkt w Ep(a,b) ); B analogicznie wyznacza klucz prywatny nB i klucz publiczny KB = nB G; A wytwarza klucz tajny TA= nA KB B wytwarza klucz tajny TB=nB KA Ponieważ nA KB= nA nB G= nB(nA G )=nB KA , zatem zarówno A, jak i B dysponują tym samym, tajnym kluczem TAB=TA=TB. Katedra Sieci Teleinformacyjnych

209 ECC – szyfrowanie i deszyfrowanienie można bezpośrednio zaszyfrować danej wiadomości M jako punktu P(x,y)Ep(a,b), ponieważ grupa eliptyczna zawiera tylko ograniczoną liczbę punktów; użytkownik A wybiera grupę eliptyczną Ep(a,b), punkt G, klucz tajny nA , klucz publiczny PA=nA G; Katedra Sieci Teleinformacyjnych

210 ECC – szyfrowanie i deszyfrowanieA wysyła do B szyfrogram zawierający parę punktów: CA = { k G, MA + k PB }, gdzie PB jest kluczem publicznym B; B wykonuje działanie: (MA + k PB ) – nB (kG) = MA + k (nB G) - nB (kG) = MA Katedra Sieci Teleinformacyjnych

211 ECC- bezpieczeństwo- miara MIPS-Years1 MIPS-Year =1 x 106 operacji/sek. x 3600sek./h x 24h/dzień x 365 dni/rok x 1rok = 3, operacji arytmetycznych ECC Dł. klucza MIPS-Years 150 3,8 1010 205 7,1 1018 234 1,6 1028 RSA Dł. klucza MIPS-Years 3 104 Katedra Sieci Teleinformacyjnych

212 ECC - długości kluczy przy porównywalnym bezpieczeństwieSymmetric Key Size (bits) RSA and Diffie-Hellman Key Size (bits) Elliptic Curve Key Size (bits) 80 1024 160 112 2048 224 128 3072 256 192 7680 384 15360 521 Table 1: NIST Recommended Key Sizes Katedra Sieci Teleinformacyjnych

213 Uwierzytelnianie wiadomościAtaki przy przesyłaniu wiadomości w sieci: ujawnienie; analiza ruchu; maskarada; modyfikacja zawartości; modyfikacja kolejności; modyfikacja czasowa; zaprzeczenie. Poufność Autentyczność Podpis cyfrowy Katedra Sieci Teleinformacyjnych

214 Uwierzytelnianie wiadomościUwierzytelnienie wiadomości - procedura sprawdzająca, czy odebrane wiadomości pochodzą z uprawnionego źródła i czy nie zostały zmienione. Funkcje wykorzystywane w procedurach uwierzytelniania: Szyfrowanie wiadomości; Kod uwierzytelnienia wiadomości (MAC- Message Authentication Code); Funkcja skrótu (ang. hash function) Katedra Sieci Teleinformacyjnych

215 Uwierzytelnianie wiadomości c. d.Uwierzytelnianie za pomocą szyfrowania - symetryczny SK Warunek: wiadomość M nie może być dowolnym ciągiem bitów - - Zastosowanie kodowania nadmiarowego Katedra Sieci Teleinformacyjnych

216 Uwierzytelnianie wiadomości c. d.- zabezpieczenie wewnętrzne: - zabezpieczenie zewnętrzne: Katedra Sieci Teleinformacyjnych

217 Uwierzytelnianie wiadomości c. d.- asymetryczny SK uwierzytelnienie i podpis utajnienie, uwierzytelnienie, podpis Katedra Sieci Teleinformacyjnych

218 Uwierzytelnianie wiadomości c. d.MAC - kryptograficzna suma kontrolna Zakładamy, że obie strony A i B dysponują wspólnym, tajnym kluczem TAB MAC nie musi być funkcją odwracalną Ten schemat zapewnia tylko uwierzytelnienie - brak tajności Katedra Sieci Teleinformacyjnych

219 Uwierzytelnianie wiadomości c. d.uwierzytelnienie i tajność zapewnia schemat: MAC przed szyfrowaniem - uwierzytelnienie związane jest z wiadomością Katedra Sieci Teleinformacyjnych

220 Uwierzytelnianie wiadomości c. d.Uwierzytelnienie i tajność - MAC po szyfrowaniu  uwierzytelnienie szyfrogramu Katedra Sieci Teleinformacyjnych

221 Uwierzytelnianie wiadomości c. d.Dlaczego używamy MAC, a nie wyłącznie szyfrowania symetrycznego? MAC jest dogodniejsze w przypadkach: powiadamianie wielu użytkowników z jednego punktu - jeden użytkownik jest odpowiedzialny za uwierzytelnianie -po sprawdzeniu powiadamia pozostałych; użytkownik jest mocno obciążony (deszyfracja jest złożoną operacją)- za pomocą MAC wiadomości są uwierzytelniane wyrywkowo; Katedra Sieci Teleinformacyjnych

222 Uwierzytelnianie wiadomości c. d.przy jawnym przesyłaniu programów komputerowych; w systemach z rozdzieleniem procesów uwierzytelniania i utajniania- np. uwierzytelnienie na poziomie aplikacji, a utajnienie na poziomie warstwy transportowej Katedra Sieci Teleinformacyjnych

223 Uwierzytelnianie wiadomości c. d.Wymagania dla MAC Długość MAC n bitów; długość klucza k bitów  2n możliwych MAC << liczby możliwych wiadomości o różnych długościach. Atak brutalny: k > n ; mając parę: wiadomość M1-MAC1 kryptoanalityk oblicza MACi = CKi(M1) i =1,...,2k  co najmniej dla jednego klucza MACi=MAC1 { 2k > 2n  średnio dla 2(k-n) kluczy wystąpi zgodność }  algorytm ataku: Katedra Sieci Teleinformacyjnych

224 Uwierzytelnianie wiadomości c. d.Algorytm ataku na MAC: Runda 1 Dane: M1, MAC1=CK(M1); MACi = CKi(M1); i=1,...,2k; liczba koincydencji MACi=MAC1 : 2(k-n) ; Runda 2 Dane: M2, MAC2=CK(M2); MACi = CKi(M2); i=1,...,2(k-n) ; liczba koincydencji MACi=MAC2 : 2(k-2n) ; Jeżeli k = m n, to potrzeba średnio m rund do wyznaczenia klucza Katedra Sieci Teleinformacyjnych

225 Uwierzytelnianie wiadomości c. d.MAC utworzone za pomocą DES – ANSI standard X9.17 : Data Authentication Code M={ m1, m2, .... , mN }; Długość mi : 64 bity. Katedra Sieci Teleinformacyjnych

226 Jednokierunkowe funkcje skrótu (ang. one-way hash functions)Jednokierunkową funkcją skrótu nazywamy funkcję: h = H (M) gdzie: M jest wiadomością o dowolnej długości, h jest liczbą o ustalonej długości m bitów Katedra Sieci Teleinformacyjnych

227 Funkcja skrótu - właściwościObliczenie wartości funkcji h dla danej wiadomości M jest łatwe; Mając h jest obliczeniowo niewykonalne otrzymanie M; Dla danej wiadomości M praktycznie niemożliwe jest znalezienie innej wiadomości M’ takiej, że H(M’)=H(M) Zmiana dowolnego bitu (bitów) M powoduje zmianę h. Katedra Sieci Teleinformacyjnych

228 Funkcja skrótu (FS) - właściwościDla danej wiadomości M praktycznie niemożliwe jest znalezienie innej wiadomości M’ takiej, że H(M’)=H(M); Aby to wymaganie mogło być spełnione, to długość funkcji skrótu m musi być równa co najmniej 128 bitów (np. w SHS (Secure Hash Standard m=160) ponieważ można w 2m/2 próbach uzyskać dwie wiadomości o jednakowym skrócie. Katedra Sieci Teleinformacyjnych

229 Funkcja skrótu - metody wykorzystania FS do uwierzytelniania wiadomościZapewnienie: tajności i uwierzytelnienia Katedra Sieci Teleinformacyjnych

230 Funkcja skrótu - metody wykorzystania FS do uwierzytelniania wiadomościZapewnia: uwierzytelnienie  MAC Katedra Sieci Teleinformacyjnych

231 Funkcja skrótu - metody wykorzystania FS do uwierzytelniania wiadomościZapewnia: uwierzytelnienie i podpis cyfrowy Katedra Sieci Teleinformacyjnych

232 Funkcja skrótu - metody wykorzystania FS do uwierzytelniania wiadomościZapewnia: tajność i podpis Katedra Sieci Teleinformacyjnych

233 Funkcja skrótu - metody wykorzystania FS do uwierzytelniania wiadomościZapewnia: uwierzytelnienie Katedra Sieci Teleinformacyjnych

234 Funkcja skrótu - metody wykorzystania FS do uwierzytelniania wiadomościZapewnia: uwierzytelnienie i tajność Katedra Sieci Teleinformacyjnych

235 Funkcja skrótu – zasada realizacjif(•) – algorytm kompresujący; Yi – b-bitowe bloki wiadomości; CVi - n-bitowe bloki zmiennej łańcuchowej (ang. chaining variable); n – długość skrótu; b > n. Algorytmy FS: MD5, MD4, SHA, RIPEMD-160 Katedra Sieci Teleinformacyjnych

236 Katedra Sieci TeleinformacyjnychPrzykład wykorzystania symetrycznego blokowego SK do tworzenia funkcji skrótu- algorytm Daviesa-Meyera IV - losowy blok początkowy Długość skrótu jest równa długości bloku wykorzystywanego blokowego systemu kryptograficznego Katedra Sieci Teleinformacyjnych

237 Katedra Sieci TeleinformacyjnychPodpis cyfrowy Właściwości podpisu: ·  każda osoba ma właściwy dla siebie , niepodrabialny podpis; ·  powinna istnieć możliwość stwierdzenia autentyczności podpisu złożonego pod dokumentem; ·  powinno być niemożliwe kopiowanie podpisu z jednego dokumentu na drugi. Schemat tworzenia i odczytywania podpisu cyfrowego: Podpisywanie Odczytywanie podpisu KSA - klucz tajny osoby A ; KPA - klucz jawny osoby A Katedra Sieci Teleinformacyjnych

238 Katedra Sieci TeleinformacyjnychPodpis cyfrowy Wspólne cechy podpisu odręcznego i podpisu cyfrowego: ·   są przypisane do jednej osoby; ·  są trudne do podrobienia; ·  uniemożliwiają wyparcie się go przez autora; ·  możliwa jest weryfikacja przez czynniki niezależne; ·  są proste do wytworzenia. Katedra Sieci Teleinformacyjnych

239 Różnice między podpisem odręcznym i podpisem cyfrowym:Podpis cyfrowy Różnice między podpisem odręcznym i podpisem cyfrowym: Podpis odręczny Podpis cyfrowy ·       jest na stałe związany z dokumentem ·       może być przesyłany niezależnie od dokumentu ·       jest taki sam dla wszystkich dokumentów ·       jest funkcją dokumentu ·       stawiany jest na końcu dokumentu (końcu każdej strony dokumentu) ·       obejmuje cały dokument Katedra Sieci Teleinformacyjnych

240 Katedra Sieci TeleinformacyjnychAlgorytm podpisu cyfrowego DSA ( Digital Signature Algorithm - 19 maja 1994) Tworzenie klucza publicznego: Wybieramy liczbę pierwszą p o długości 512 do 1024 bitów; Obliczamy czynnik pierwszy q liczby p –1 o długości 160 bitów; Wybieramy liczbę h < p -1 oraz h ( p – 1 )/q mod p > 1 Liczby p, q i h mogą być wspólne dla grupy użytkowników; Obliczamy liczbę: g = h ( p – 1 )/q mod p ; Klucz jawny: | Klucz prywatny: y = gx mod p | liczba x < q o długości bitów Katedra Sieci Teleinformacyjnych

241 Algorytm podpisu cyfrowego DSAProces podpisywania wiadomości M: Wybieramy losowo liczbę k < q o długości 160 bitów; Obliczamy liczby tworzące podpis cyfrowy: r = ( gk mod p ) mod q s = ( k -1 ( H(M ) + x r )) mod q *) Weryfikacja podpisu: w = s -1 mod q u1 = ( H(M) w ) mod q u2 = ( r w ) mod q v = (( gu1 yu2 ) mod p ) mod q Jeżeli v = r , to uznajemy podpis za prawdziwy. *)H( M ) – skrót wiadomości M obliczony za pomocą SHA-1 Katedra Sieci Teleinformacyjnych

242 Katedra Sieci Teleinformacyjnych Problem nr 1 Przedstaw problem, używając prostego języka Przedstaw dowody werbalne i wizualne na poparcie swojej argumentacji Rozszerz wystąpienie o przykład lub anegdotę Przechodząc do następnego problemu, logicznie połącz go z poprzednim Jeśli omawiasz kilka argumentów, kroków czy problemów kluczowych powtórz procedurę wielokrotnie. Stwierdź, czy słuchacze są w stanie zrozumieć nowy pomysł, nauczyć się metody, czy zagłębić się bardziej w znane już pojęcie. Każdy punkt zaopatruj w odpowiednie wyjaśnienie. Uzupełniaj prezentację stosownymi danymi technicznym na wydrukach, dyskietkach, przez pocztę lub Internet. Każdy krok rozwijaj odpowiednio, tak aby utrzymać kontakt ze słuchaczami. Katedra Sieci Teleinformacyjnych

243 Katedra Sieci Teleinformacyjnych Zakończ Streść problemy omawiane w wystąpieniu Przedstaw wnioski. Przedstaw ich znaczenie dla słuchaczy Ustal zakończenie prezentacji najlepsze dla publiczności i dla prezentacji. Zakończ streszczeniem; zaoferuj alternatywy; zaproponuj strategię; zasugeruj plan; ustanów cel. Trzymaj się tematu podczas całej prezentacji, a łatwiej osiągniesz swój cel. Katedra Sieci Teleinformacyjnych