We współczesnej kryptografii możemy wyróżnić dwa działy: Systemy kryptogra­ficzne symetryczne i systemy z kluczem publicznym (asymetryczne). Jeśli za system kryptograficzny uznamy algorytm szyfrujący, algorytm deszyfrujący wraz z klu­czami odpowiednio szyfrującym i deszyfrującym, to za system symetryczny uznamy taki, w którym znajomość klucza szyfrującego jest równoważna znajomości klucza deszyfrującego. Inaczej mówiąc znając klucz szyfrujący lub deszyfrujący jesteśmy w stanie w prosty sposób wyznaczyć drugi klucz z tej pary. Często bywa tak, że te klucze są identyczne. W systemach symetrycznych wyróżnia się dwa podstawowe sposoby szyfrowania: Są to szyfry blokowe i szyfry strumieniowe. W systemach z kluczem publicznym znalezienie klucza deszyfrującego na podstawie klucza szyfrującego (lub odwrotnie) jest problemem trudnym obliczenio­wo. Jest to co prawda możliwe, ale wymaga ogromnie długiego czasu. Dlatego przyjmuje się, że nie jest osiągalne w realnym czasie, czyli w czasie, w którym uzyskane tą drogą informacje miałyby jeszcze jakieś znaczenie. Szyfr blokowy jest to najkrócej mówiąc szyfr, który szyfruje bloki danych o ustalo­nej długości. A dokładniej szyfrem blokowym nazywamy algorytm, który na pod­stawie zadanego klucza przekształca wejściowy blok danych w inny blok w taki sposób, że niemożliwe jest odwrócenie tego przekształcenia, czyli odzyskanie tego samego bloku wejściowego na podstawie bloku wyjściowego bez znajomości klu­cza. Współczesne szyfry blokowe operują na bitach, mają ustaloną długość bloku wejściowego (w bitach) równą zwykle długości bloku wyjściowego i ustaloną dłu­gość klucza. Przykładami szyfrów blokowych są najpopularniejsze: DES, IDEA, oraz: Lucifer, Madrygi, FEAL-N, REDOC, LOKI, RC2, RC4, MMB, Skipjack i mne. W roku 1997 ogłoszono konkurs na nowy szyfr blokowy. W ramach tego konkursu zaprojektowano wiele nowych nowoczesnych szyfrów blokowych np: RC6, Rijndael, 'Serpent, Mars, TwoFish i inne. Aby przedstawić ideę szyfru strumieniowego zacznijmy od zaprezentowania znane­go od dawna szyfru zwanego szyfrem z kluczem bieżącym. Dla uproszczenia przyjmijmy kilka założeń:

1. Posługujemy się alfabetem 35 znakowym (wszystkie znaki polskiego al­fabetu bez spacji. Ogólnie można by używać wszystkich znaków ASCII).

2. Każdej literze przyporządkowujemy jej pozycję w alfabecie począwszy od zera (A - O, Ą - 1, B - 2, ..., Ż -34). Dla znaków można by przyjąć ich ko­dy ASCII.

3. Przez dodawanie dwóch liter rozumiemy dodanie ich odpowiedników liczbowych modulo 35, a wynikiem niech będzie litera odpowiadającaotrzymanej liczbie.

Szyfrowanie szyfrem z kluczem bieżącym odbywa się w następujący sposób:

P = T A J N E A K T A Z N A J D U J Ą S I Ę

K = K L U C Z E M J E S T F R A G M E N T K

EK(P) = Ć L Ć Ó C E W B E P F F A D Ą V Ę E B Ó

Przez P oznaczono tekst jawny, przez K - tekst stanowiący klucz, a przez EK(P) szyfrogram tekstu P zaszyfrowanego kluczem K. Szyfrowanie polega na dodawaniu kolejnych liter tekstu P do odpowiadających im liter klucza K. Przykładowo: T (26) + K (13) = (26 + 13 =39 mod 35 = 4) = Ć. Kluczem może być fragment książki lub jakiegoś dokumentu, byle jego dłu­gość była nie mniejsza od długości tekstu jawnego. Deszyfrowanie polega na analo­gicznym odejmowaniu modulo 35 odpowiednich liter klucza od liter szyfrogramu. Szyfr ten możemy zaliczyć do szyfrów strumieniowych, ponieważ kluczem jest tutaj nieokresowy strumień liter danego tekstu. Szyfr ten można jednak złamać tzn. odczytać zaszyfrowaną informację używając metody Friedmana wykorzystują­cą redundancję języka. Aby mieć pewność zachowania tajności informacji należy jako klucza użyć losowego ciągu liter. Losowego, cyzli nie stanowiącęgo żadnej sensownej informacji, nie układającego się w żadne słowa. Dodatkowo ciągu losowego nie powinniśmy używać więcej niż raz, tzn. do zaszyfrowania więcej jak jednej informacji. Szyfr z kluczem bieżącym wykorzystującymnieokresowy, losowy ciąg liter (użyty tylko raz) nazywamy szyfrem z kluczem jednokrotnym. Jest to jedy­ny znany szyfr całkowicie bezpieczny. bo nie przenoszący żadnych informacji o kluczu i o tekście jawnym. Szyfr z kluczem jednokrotnym stosowali Rosjanie w okresie zimnej wojny. Szyfrowali wiadomości na całym świecie używając ciągów losowych, ale ilość depesz i punktów między którymi należało je przesłać była tak duża, że tych ciągów losowych zaczęło im po prostu brakować. Używali więc tych samych ciągów loso­wych więcej niż raz do szyfrowańia depesz w odległych ód siebie miejscach. Po­zwoliło to Amerykanom na odczytanie, około 2 % wszystkich rosyjskich depesz. Wymagało bardzo żmudnej pracy, ale otrzymano konkretne rezultaty. Na tym przykładzie możemy zalIważyć dwie rzeczy:

1. Generowanie ciągów losowych nie jest takie łatwe, bo wszystkie generatory pseudolosowe mają jakiś skończony okres

2. Użycie tego samego ciągu losowego więcej niż raz (wystarczy dwa razy),

daje już pewną możliwość odczytania zaszyfrowanych wiadomości, co

udowodnili Amerykanie.

Ale wróćmy do szyfrów strumieniowych. Otóż jak przekonaliśmy się na przykładzie szyfru z kluczem bieżącym, szyfrowanie strumieniowe polega na szy­frowaniu informacji kluczem złożonym ze strumienia danych (bitów lub znaków), nie krótszym od szyfrowanej informacji. Szyfry strumieniowe dzielą tekst M na znaki lub bity
a następnie każdy ity element
jest szyfrowany kluczem
należącym do strumienia kluczy
czyli
Szyfr strumieniowy jest okresowy, jeśli strumień klucza powtarza się po d znakach, dla danego, ustalonego d. W przeciwnym razie szyfr jest nieokresowy. Do okresowych szyfrów strumieniowych należą szyfry generowane przez maszyny rotorowe (Enigma z okresem większym niż
, gdzie k oznacza liczbę rotorów. Oryginalnie k = 3 oraz k = 4) i maszyny Hagelina. Natomiast szyfr jednokrotny i szyfry z kluczem bieżącym są nieokresowymi szyframi strumieniowymi. Szyfr strumieniowy o małym d możemy uznać za szyfr blokowy o długości bloku równej d. Granica między szyframi strumieniowymi,- a blokowymi jest dość płynna i zależy od wielkości d i interpretacji np. Enigmę mo­żemy uważać za szyfr blokowy o długości bloku większej niż
lub też za okre­sowy szyfr strumieniowy o okresie ponad
(zwłaszcza wtedy gdy informacja szyfrowana jest krótsza od tego okresu). Szyfr może więc być uważany za szyfr blokowy, gdy każde
jest blokiem d liter:

jak również może być uważany za szyfr strumieniowy (okresowy), gdy każdy element
jest jedną literą, a strumień klucza K jest powtarzany:

K K K

Gdy okresy są krótkie, wówczas szyfr jest bardziej podobny do słabego szyfru blo­kowego niż do szyfru strumieniowego, a jego słabość wynika stąd, że zaszyfrowane znaki nie wpływają na szyfrowanie wszystkich znaków w bloku. Natomiast, gdy długość okresu wzrasta, wówczas szyfr staje się bardziej podobny do szyfru stru­maieniowego.Istnieją dwie różne metody realizacji szyfrowania strumieniowego: szyfry synchroniczne i szyfry samosynchronizujące się. My powiemy o tych pierwszych, a nastepnie przejdziemy do szyfrów blokowych. A więc synchroniczny szyfr strumieniowy jest to szyfr, w którym strumień klu­cza
jest generowany niezależnie od strumienia znaków szyfrowanego tekstu. Algorytm generowania klucza musi być algorytmem deterministycznym, aby klucz mógł być odtworzony przy deszyfrowaniu (nie jest to konieczne, jeśli klucz K jest zapamiętywany, ale przy długich strumieniach kluczy jest to niepraktyczne). Faza startu generatora klucza jest inicjowana przez wartość początkową
. Popatrzmy na dokładny schemat strumieniowego szyfru synchronicznego:

Zauważyliśmy poprzednio, że szyfry strumieniowe łatwo można złamać, gdy łańcuch klucza się powtarza lub gdy zawiera redundancje. Aby były one niemożliwe do przełamania, sekwencja kluczy musi być losowa dla całego tekstu podlegającemu szyfrowaniu. Intuicyjnie losowość oznacza, że każdy element z alfabetu klucza powinien być równomiemie rozmieszczony w całym łańcuchu klucza i nie powinno być długich, powtarzających się ciągów ani też innych wzorców. Żaden algorytm skończony nie może generować prawdziwie losowych ciągów. Nie wyklucza to jednak możliwości generowania kluczy przy użyciu genera­torów liczb pseudolosowych. Strumień bitów wiadomości
jest szyfrowany przez obliczanie
, przy czym
są kolejnymi elementami strumienia klucza, który został wygenerowany. Deszyfrowanie jest realizowane w ten sam sposób,czyli na podsta­wie wygenerowanego strumienia klucza jest obliczany tekst pierwotny według wzoru
. Wartość
jest wartością początkową generatora klucza zarówno dla szyfratora jak i deszyfratora. Pętla sprzężenia zwrotnego opisana niżej w pewnym sensie symuluje metodę klucza jednorazowego przez przekształcenie krótkiego klucza lo na pseudolosowy długi klucz K. Niestety jest to słabe przybliżenie szyfru z kluczem jednokrotnym. Jako generatora liczb pseudolosowych do szyfrowania strumieniowego wykorzystuje się liniowy rejestr przesuwny ze sprzężeniem zwrot­nym. I to tyle jeśli chodzi o takie ogólnikowe omówienie tego rodzaju szyfrów. Teraz natomiast przejdziemy do szyfrów blokowych. Szyfr blokowy jest to funkcja, która odwzorowuje n bitowy tekst jawny w n bitowy tekst tajny. n jest nazywane długością (wielkością) bloku. Funkcja jest parametryzowana przez k bitowy klucz K, biorący wartości z podzbioru K (przestrzeń klucza) zbioru wszystkich k-bitowych wektorów
. Najczęściej klucz jest wybierany losowo. Dla zapewnienia unikalności szyfrowania funkcja szyfrująca musi być odwracalna (1-1). Dla n bitowego tekstu jawnego, tekstu tajnego i stałego klucza, funkcja szyfrująca jest bijekcją na zbiorze n bitowych wektorów. Liczba kluczy wynosi
, a efektywny rozmiar klucza jest równy
(logarytm naturalny). Oto, jak wygląda schemat działania algorytmu:

Wyróżniamy kilka bloków pracy szyfrów blokowych. My natomiast omówimy takie dwa. Pierwszy z nich nosi nazwę elektronicznej książki kodowej (ECB). Tutaj każdy blok tekstu jawnego jest szyfrowany osobno:
. A oto, jak wygląda deszyfrowanie:
.Poniższy rysunek ilustruje prace w tym trybie:

Wadą tego trybu jest to, że jednakowe bloki szyfrogramu
odpowiadają jednakowym blokom tekstu jawnego
. Kolejny tryb pracy to wiązanie bloków zaszyfrowanych (CBC). Każdy blok tekstu jawnego jest przed szyfrowaniem sumowany z poprzednim blokiem szyfrogramu:
.Deszyfrowanie odbywa się tak:
. Wartość początkowa IV nie musi być tajna. Jednakowe bloki tekstu jawnego przechodzą w różne bloki szyfrogramu. Występuje mała propagacja błędów. Jeśli
odebrano z błędem to tylko bloki
będą odszyfrowane niepoprawnie. I to tyle jeśli chodzi o tryby pracy szyfrów blokowych. Przejdźmy teraz do omówienia standardu szyfrowania danych DES. DES (Data Encryption Standard), czyli Standard Szyfrowania Danych był najpopularniejszym szyfrem blokowym właśnie dlatego, że był standardem przez 24 lata. Jego historia datuje się od początku lat siedemdziesiątych. Opatentowany przez firmę IBM algorytm Lucifer został zmodyfikowany przez NSA (National Security Agency), czyli amerykańską Narodową Agencję Bezpieczeństwa. Między innymi skrócono długość klucza. Powstały w ten sposób szyfr został zatwierdzony w 1977 roku przez NBS (National Bureau of Standards), czyli Narodowe Biuro Standardów i jako standard federalny otrzymał nazwę DES. Od tego czasu DES co pięć lat był ponownie zatwierdzany jako standard. Ostatni raz w roku 1992, w roku 1997 był ponownie rozważany. W roku 2000 po rozstrzygnięciu konkursu AES (Advanced Encryption Standard) został zatwierdzony, jako nowy standard algorytm RIJNDAEL. DES jest szyfrem blokowym, który operuje na 64 bitowych blokach danych używając 56 bitowego klucza. Przeważnie jest to liczba zapisana na 64 bitach, przy czym co ósmy bit jest bitem parzystości i jest pomijany. Wśród wszystkich 256 kluczy istnieją klucze słabe, lecz mogą zostać one z łatwością pominięte. Całe bezpieczeństwo szyfru spoczywa na kluczu. Jest to szyfr symetryczny, tzn. ten sam klucz jest używany zarówno do szyfrowania jak i deszyfrowania. Na najniższym poziomie algorytm jest kombinacją dwóch podstawowych technik: mieszania i rozpraszania. Składa się on z dwóch głównych funkcji:

1. Permutacji klucza, która przygotowuje szesnaście 48 bitowych podkluczy. Podklucz jest wybrany z 56 bitów klucza. Służy do tego tablica permutacji podkluczy.

2. Funkcji szyfrującej, składającej się z 16 iteracji zwanych cyklami lub rundami. W każdym cyklu wykorzystuje się kombinację wyżej wymienionych technik z udziałem podkluczy. Algorytm wykorzystuje standardową arytmetykę i operacje logiczne (XOR, przesunięcia logiczne) na liczbach 64 bitowych. 64 bitowy tekst jawny P jest permutowany zgodnie z odwzorowaniem IP zwanym permutacją początkową. Permutacja IP jest bijekcją, dokonującą transpozycji bloku wejściowego zgodnie z poniższą tablicą permutacji początkowej IP:

Tablicę należy czytać w następujący sposób: Bit 58 zostaje przestawiony na bit 1, 50 na pozycję 2 i tak dalej. W podobny sposób należy czytać i inne tablice. Permutowany blok wejściowy jest następnie dzielony na 32 bitowe połowy. Lewa połowa jest zwana L0, a prawa R0. Permutacje początkowa IP i końcowa IP 1 nie zależą od danych ani od klucza. W związku z tym w żaden sposób nie wpływają na bezpieczeństwo algorytmu. Ponieważ permutacja na poziomie pojedynczych bitów jest trudna do zrealizowania programowego (chociaż jest łatwa w realizacjach sprzętowych) i jest czasochłonna, wiele aplikacji pomija permutacje IP i IP 1. Bezpieczeństwo nowego algorytmu nie jest mniejsze od bezpieczeństwa DES. Algorytm ten nie jest zgodny jednak ze standardem DES i nie powinien być nazywany DES.
. Następnie wykonywane są 16 razy jednakowe operacje, zwane funkcją f, w czasie których dane łączone są z kluczem. Można je opisać następująco:
,
, gdzie 1 ≤ i ≤ 16, a f jest funkcją szyfrującą. Oto, jak wygląda taka pojedyncza runda algorytmu DES:

I popatrzmy teraz jak wygląda taki schemat blokowy tego algorytmu:

Ponieważ funkcje szyfrujące DES używają 56 bitowego klucza, początkowy klucz 64 bitowy jest redukowany, przez usunięcie co 8 bitu. Są one wykorzystywane jako bity parzystości. Usunięcia dokonuje permutacja PC 1 zwana permutacją klucza:

Następnie dla każdego cyklu DES jest generowany 48 bitowy podklucz na podstawie 56 bitowego klucza K. Rysunek poniższy przedstawia schemat generowania podkluczy dla poszczególnych cykli:

56 bitowy klucz jest dzielony na 28 bitowe połowy, C0 i D0. Następnie połowy te są przesuwane cyklicznie w lewo o jeden lub dwa bity, zależnie od numeru cyklu, zgodnie z tabelą

poniżej:

Po wykonaniu przesunięcia jest wybieranych 48 z 56 bitów, wykorzystując permutację PC 2, zwaną permutacją wyboru lub kompresji:

Proces obliczania podkluczy dla cyklu i, gdzie 1≤ i ≤ 16, przedstawiają wyrażenia:

,
. Funkcja LS(x,i) jest przesunięciem cyklicznym x w lewo o liczbę pozycji podaną w tabeli przesunięć klucza. Podklucz Ki powstaje według wzoru

Na następnej stronie przedstawiony został schemat funkcji szyfrującej f algorytmu DES:

Funkcja szyfrująca f (przedstawiona na rysunku wyżej) tworzy 32 bitowy blok wyjściowy z 32 bitowego bloku wejściowego R i 48 bitowego podklucza K:
.32 bitowy blok danych jest rozszerzany do 48 bitów za pomocą permutacji z rozszerzeniem E danej tablicą poniżej. Operacja ma dwa cele: dostarczenie ciągu o tej samej długości co sumowany z nim klucz i ciągu wydłużonego, który może być poddany kompresji przy operacji podstawiania. Pozwalając jednemu bitowi wpływać na dwa podstawienia, uzyskuję się to, że zależność bitów wyjściowych od bitów wejściowych szybciej się rozprzestrzenia.

Wynik rozszerzenia - 48 bitowy blok E(R), jest sumowany modulo 2 z 48 bitowym podkluczem K, rezultatem czego jest 48 bitowy blok wejściowy poddawany operacji podstawiania. Podstawienia dokonywane są przez 8 skrzynek podstawieniowo -permutacyjnych zwanych krótko S skrzynkami lub po prostu skrzynkami. Ciąg o długości 48 bitów jest dzielony na osiem 6 bitowych bloków. Każdy 6 bitowy blok jest przetwarzany przez oddzielną skrzynkę. Każda skrzynka jest opisana przez tablicę złożoną z 4 wierszy i 16 kolumn, o 4 bitowych elementach. S skrzynka odwzorowuje sześciobitowy blok wejściowy w blok 4 bitowy. Ich struktura została przedstawiona w podanej literaturze. Skrzynki są nieliniowe i są najbardziej znaczącymi elementami bezpieczeństwa szyfru. Wartość bloku wyjściowego S-skrzynki jest opisana następującymi regułami:

• Bity 0 i 5 bloku wejściowego są łączone i określają wiersz skrzynki (liczba całkowita 0,1,2 lub 3).

• Środkowe 4 bity (1,2,3,4) określają kolumnę skrzynki (liczba całkowita z przedziału 0 do 15).

• 4 bitowa liczba leżąca na przecięciu wiersza i kolumny wyznaczonej w wyżej podany sposób określa wartość wyjściową.

Wynikiem fazy podstawień jest 32 bitowy blok powstały z konkatenacji ośmiu 4 bitowych bloków. Jest on następnie permutowany przy pomocy permutacji P. Permutacja P odwzorowuje każdy bit wejściowy w jeden bit wyjściowy. Żaden bit nie jest pomijany ani nie jest używany dwukrotnie (jest to bijekcja). Tabela poniżej pokazuje tą permutację:

Wynik permutacji P jest blokiem wyjściowym funkcji f. Deszyfrowanie DES odbywa się przy wykorzystaniu tego samego algorytmu co szyfrowanie. Jedyna różnica polega na kolejności użycia podkluczy. Są one pobierane w odwrotnej kolejności. Oznacza to, że jeśli kluczami szyfrującymi dla poszczególnych cykli są K1, K2, ..., K16 to kluczami deszyfrującymi są K16, K15, ... , K1. Od chwili stworzenia w 1977 roku DES podlegał intensywnej analizie. Istniało wiele spekulacji dotyczących długości klucza, liczby cykli i projektu skrzynek. Szczególnie tajemnicze były skrzynki. Nikomu nie znane były zasady ich stworzenia. Istniało podejrzenie istnienia tzw. zapadni, dzięki czemu NSA miałoby możliwość łatwego łamania DES. Przez ponad 20 lat badań nie znaleziono jednak praktycznych metod szybkiego łamania DES. Dostępne implementacje programowe umożliwiają na komputerze z zegarem 33 MHz przeszyfrowanie 40 600 bloków na sekundę. Bezpieczeństwo DES polega na tym, że najlepszym sposobem złamania tego szyfru jest tzw. atak brutalny, czyli przejrzenie całej przestrzeni klucza. Mając blok wejściowy i jego zaszyfrowany odpowiednik, czyli stosując tzw. atak ze znanym tekstem jawnym, aby znaleźć klucz tego szyfrowania należy sprawdzić wszystkie 256 klucze. Jest to więc 7 * 1016 szyfrowań co przy szybkości 40 600 bloków/s zajęłoby aż 56 tys. lat. Ale stosując szybsze komputery i wykorzystując obliczenia równoległe można to zrobić o wiele szybciej. W 1993 roku Michael Wiener stwierdził, że komputer, który złamałby DES, czyli przejrzał całą przestrzeń klucza w 3,5 godziny kosztowałby 1 milion USD. Takie urządzenie zostało zbudowane w roku 1997 w ramach programu EFF (Electronic Frontier Foundation). Właśnie dlatego uważa się, że DES nie jest już szyfrem bezpiecznym i nie został zatwierdzony ponownie jako standard.Alternatywą dla DES są szyfry blokowe o dłuższym kluczu. Jednym z nich jest potrójny DES. Jego działanie polega na trzykrotnym użyciu szyfru DES z dwoma różnymi kluczami. Daje to dużo lepsze efekty niż DES tradycyjny. Ponieważ DES nie tworzy grupy, zatem tekst tajny jest znacznie trudniej złamać metodą brutalnego ataku. Rozmiar przestrzeni klucza wynosi 2112 zamiast 256. Tekst jawny jest najpierw szyfrowany z kluczem K1, następnie jest deszyfrowany z kluczem K2 i ponownie szyfrowany z kluczem K1. Deszyfrowanie polega na zamianie procesu szyfrowania na deszyfrowanie z tym samym kluczem. Inną modyfikacją jest użycie DES z niezależnymi podkluczami. Zamiast generowania podkluczy 48 bitowych z 56 bitów używa się klucza o długości 768 bitów (16 cykli razy 48 bitów podklucza). Przestrzeń klucza wynosi 2768 co jest wielkością trudną do porównania z czymkolwiek (liczba atomów we Wszechświecie wraz z czarną materią szacowana jest na 2265). Wariant ten znacznie zwiększa złożoność DES. Biham i Shamir pokazali jednak, że tak zmodyfikowany szyfr może być złamany przy użyciu 261 wybranych tekstów jawnych. Występują ponadto warianty DES ze zmienioną kolejnością skrzynek i ich wartościami, które są zależne od klucza - przykładowo CRYPT(3).

I to tyle, jeśli o algorytm DES. Kolejną rzeczą będize omówienie przez nas specyfikacji algorytmu blokowego szyfrowania danych Rijndael zaprojektowanego przez Joana Daemena i Vincenta Rijmena z uniwersytetu Leuven w Belgii. Algorytm ten jest zwycięzcą konkursu AES i został zatwierdzony w październiku 2000 roku jako federalny standard szyfrowania danych w USA. Algorytm pewnie z czasem stanie się powszechnie stosowanym na całym świecie. Omówmy jego podstawy matematyczne, jednak najprawdopodobniej na następnych zajęciach.

---