Dwa slowa na poczatek

Szyfrowanie to, jak latwo sie domyslec, sposob ochrony informacji przed jej zinterpretowaniem przez osoby niepowolane. Moga one ja odczytywac, lecz zaszyfrowana tresc (kryptogram) nie stanowi dla nich zadnej wartosci, gdyz nie da sie go przeksztalcic na tekst jawny (otwarty) bez znajomosci odpowiedniego klucza.

A jakie informacje w systemach komputerowych najczesciej sie utajnia? Pomijajac oczywiscie dane personalne, czesto zdarza sie, ze autor lub uzytkownik systemu potrzebuje zamiescic w nim , badz tez w zbiorach pomocniczych pewne cechy charakterystyczne, majace sluzyc do porownywania wlasciwego srodowiska programu ze stanem aktualnym. Takimi informacjami sa najczesciej: hasla, procedury uwierzytelniania, numer seryjny programu, nazwa programu, informacje o producencie, dlugosc programu, data jego powstania, sumy kontrolne, niektore informacje o srodowisku komputera (np. fragmenty BIOS-u), cechy kluczy (dyskietek kluczowych czy tez kluczy sprzetowych).

Dziedzine wiedzy i badan zajmujaca sie utajnionym zapisywaniem danych nazywamy kryptografia, zas termin kryptoanaliza obejmuje dziedzine wiedzy badajaca metody przelamywania szyfrow. Rozrozniamy dwa podstawowe rodzaje szyfrow: przestawieniowe i podstawieniowe. Z nich tez wywodza sie dalsze, niejako pochodne rodzaje.

Dalsze podrozdzialy w tej czesci pracy opisuja kolejno:

• szyfry przestawieniowe

• szyfry podstawieniowe

• szyfry kaskadowe

• szyfry wykladnicze

• szyfry plecakowe

Szyfry przestawieniowe

Szyfry te zmieniaja uporzadkowanie bitow lub znakow w danych wedlug pewnego schematu. Zazwyczaj dokonuje sie przestawienia za pomoca pewnej figury geometrycznej. Szyfrowanie przebiega wiec w dwoch krokach: tekst jawny wpisuje sie do figury w sposob okreslony pewna tzw. sciezka zapisu, a nastepnie odczytuje sie go wedlug okreslonego porzadku (sciezki odczytu) otrzymujac tekst zaszyfrowany. Klucz obejmuje wiec figure geometryczna oraz sciezki zapisu i odczytu.

Jako pierwszy przyklad wezmy prosty szyfr plotowy. Litery tekstu jawnego zapisuje sie tu tak, aby tworzyly ksztalt przypominajacy wierzcholek plotu zbudowanego ze sztachet. Tekst zaszyfrowany otrzymujemy odczytujac kolejne wiersze tak utworzonej konstrukcji. Proces szyfrowania mozemy przedstawic na prostym przykladzie.

Bardzo czesto uzywana figura geometryczna jest macierz dwuwymiarowa. Jako przyklad szyfru wezmy tzw. przestawienie kolumnowe. Tekst jawny zapisuje sie do macierzy wierszami. Kryptogram powstaje jako odczyt kolumn w okreslonym porzadku. W naszym przykladzie wyglada to tak ...

Spora czesc szyfrow przestawieniowych zmienia kolejnosc znakow tekstu jawnego przy zastosowaniu stalego okresu t. Sa to tzw. szyfry okresowo-permutacyjne. Mozna je implementowac jako przestawienie kolumn macierzy, do ktorej tekst jawny wpisano wierszami. Kryptogram odczytywany jest tu rowniez wierszami. Metoda ta daje lepsze rezultaty, gdy uzywa sie komputerow, poniewaz kazdy wiersz moze tu byc szyfrowany i deszyfrowany niezaleznie.

Kryptoanalitycy moga latwo rozpoznac, czy zastosowany szyfr jest szyfrem przestawieniowym, poniewaz czestosc wystepowania liter tekstu zaszyfrowanego bedzie zblizona do czestosci ich wystepowania w tekscie jawnym. Dlatego wlasnie tego rodzaju szyfry moga byc w prosty sposob lamane metoda anagramowa, polegajaca na odtworzeniu wlasciwej kolejnosci przemieszanego zestawu znakow.

Szyfry podstawieniowe

Ich idea jest zastepowanie bitow, znakow lub blokow znakow ich ustalonymi zamiennikami. Istnieja cztery typy szyfrow podstawieniowych:

• monoalfabetyczne

• homofoniczne

• wieloalfabetyczne

• poligramowe

Przyjrzyjmy sie im w oddzielnych paragrafach.

Szyfry podstawieniowe monoalfabetyczne

Zamieniaja one kazdy znak tekstu jawnego na odpowiedni znak kryptogramu, przy czym w calej wiadomosci do zamiany kazdego znaku jawnego na zaszyfrowany stosuje sie odwzorowanie typu jeden do jednego.

Jako przyklad szyfru monoalfabetycznego moze nam posluzyc prosty szyfr Cezara (jako pierwszy uzyl go Juliusz Cezar). Polega on na przyporzadkowaniu kazdej literze alfabetu lacinskiego odpowiedniego numeru identyfikacyjnego (np. A=0, B=1 itd.) i dokonaniu przesuniecia numeru kazdej litery tekstu jawnego o k = 3 pozycje (ma tu miejsce tzw. przewijanie - gdy konczy sie alfabet przesuwamy sie do jego poczatku). Zakres szyfrowania mozna oczywiscie rozszerzyc na zbior znakow ASCI (numery od 0-255) lub jakis inny skonczony zbior n znakow. Funkcja szyfrujaca bedzie sie wowczas wyrazala wzorem:

Mozna dokonywac przeksztalcen wyzszego rzedu korzystajac z przeksztalcen wielomianowych stopnia t. Wtedy zamiana kazdego znaku tekstu jawnego na kryptogram przebiega zgodnie z ogolnym wzorem:

Widzimy wiec, ze szyfr Cezara to przeksztalcenie wielomianowe stopnia zerowego.

W niektorych szyfrach podstawieniowych monoalfabetycznych do kokodowania sluzyly rowniez niestandardowe alfabety szyfrowe. Przykladem moze tu byc slynny szyfr cmentarny, ktorego klucz utworzono za pomoca rysunkow stosowanych w grze w kolko i krzyzyk. Znane sa rowniez przypadki szyfrowania poprzez zamiane liter na nuty (np. J.S. Bach uzyl swojego nazwiska w Propozycjach muzycznych oraz Sztuce fugi).

Na koniec omawiania szyfrow monoalfabetycznych nalezy wspomniec, ze wiekszosc z nich jest w prosty sposob lamana na podstawie analizy czestosci wystepowania liter lub znakow (nawet przy ataku bez tekstu jawnego). Z tego powodu ich praktyczne znaczenie jest znikome.

Szyfry podstawieniowe homofoniczne

Szyfry te, podobnie jak poprzednio omowiome szyfry monoalfabetyczne, zamieniaja kazdy znak tekstu jawnego na odpowiedni znak kryptogramu, z ta jednak roznica, ze odwzorowanie ma tu charakter jeden do wielu i kazdy znak moze byc zaszyfrowany jako jeden z pewnej grupy znakow alfabetu szyfrowego.

Jako przyklad wezmy prosty szyfr, w ktorym litery alfabetu lacinskiego sa szyfrowane jako liczby calkowite z przedzialu (0, 99), przy czym ilosc liczb calkowitych przydzielonych danej literze jest proporcjonalna do wzglednej czestosci jej wystepowania i zadna z tych liczb nie jest przydzielona do wiecej niz jednej litery. Oto odnosnik do konkretnego przykladu.

Szyfry homofoniczne moga byc znacznie trudniejsze do zlamania, gdy liczba homofonow przydzielona danej literze jest proporcjonalna do wzglednej czestosci jej wystepowania, poniewaz rozklad czestosci wystepowania symboli jest wtedy prawie jednostajny, co utrudnia analize. Dodatkowa zaleta tych szyfrow jest mozliwosc kodowania rownolegle z autentyczna wiadomoscia, ktora chce sie przekazac, wiadomsci falszywej (zmylkowej).

Istnieja rowniez bardziej skomplikowane szyfry tego rodzaju (wyzszych stopni). Mozna tu wspomniec o legendarnych juz szyfrach Beale'a.

Szyfry podstawieniowe wieloalfabetyczne

Stosuje sie w nich wiele odwzorowan znakow tekstu jawnego na znaki kryptogramu, przy czym kazde odwzorowanie jest z reguly typu jeden do jednego, podobnie jak w szyfrach monoalfabetycznych. Jak wiec widzimy szyfry wieloalfabetyczne ukrywaja rozklad czestosci przez uzycie wielu podstawien.

Wiekszosc szyfrow tej grupy to szyfry okresowe o okresie d znakow. Klasycznym przykladem moze tu byc powstaly w XVI wieku szyfr Vigenere'a.

Szyfrowanie wiadomosci przebiega tu na podstawie dowolnie wybranego slowa kluczowego (hasla). W przypadku znakow ASCI moze to byc dowolny ich ciag. Do numeru kazdego kolejnego znaku tekstu jawnego dodajemy numer odpowiadajacego mu znaku slowa kluczowego i uzyskujemy znak kryptogramu. Gdy slowo kluczowe sie skonczy, bierzemy je kolejny raz od poczatku. Dla znakow ASCI szyfr Vigenere'a mozna przedstawic za pomoca ponizszej funkcji:

Funkcja deszyfrujaca bedzie oczywiscie wygladala tak:

Rowniez tutaj mozna sie pokusic o konkretny przyklad.

Latwo zauwazyc, ze im dluzsze i bardziej skomplikowane jest haslo, tym trudniej odszyfrowac tekst utajniony. Z kolei rownie latwo jest zauwazyc, ze gdy nasze haslo bedzie jednoznakowe otrzymamy prosty szyfr monoalfabetyczny. Dla okreslonego zbioru znakow, bedacego dziedzina dzialan na tekstach mozemy stworzyc tzw. tablice Vigenere'a, ktora okresla nam przesuniecia dla dowolnej kombinacji znakow.

Zalanczam tu rowniez Pascalowa implementacje szyfrowania z wykorzystaniem omowionej metody. Jako haslo mozna tu podac dowolny ciag znakow ASCI (rozrozniane sa zatem male i duze litery). Program deszyfrujacy wykorzystuje te same funkcje, rozni sie jedynie drobnym szczegolem wyjasnionym w jednym z komentarzy.

Okresowe szyfry wieloalfabetyczne rowniez nie naleza do najbezpieczniejszych. Po wyznaczeniu okresu takiego szyfru jest on w zasadzie bez problemow przelamywany. Do wyznaczania okresu szyfru sluza dwie metody: wskaznika zgodnosci i Kasiskiego.

Szyfry podstawieniowe poligramowe

Szyfry tego typu, w odroznieniu od wyzej przedstawionych innych rodzajow szyfrow podstawieniowych, "obrabiaja" jednoczesnie wieksze grupy liter. Zlamanie takiego szyfru jest zatem duzo trudniejsze dzieki odebraniu znaczenia czestosci wystepowania liter lub znakow.

Dobrym, choc dosyc prostym, przykladem szyfru poligramowego jest szyfr Playfaira, wykorzystywany przez Anglikow w czasie I wojny swiatowej. Kluczem jest tu macierz o wymiarach 5x5, w ktorej sklad wchodza wszystkie litery alfabetu lacinskiego z wyjatkiem J. Wyglada to tak jak na ponizszym rysunku.

Litery szyfruje sie tu parami (m₁m₂) wedlug nastepujacych zasad:

1. Jesli m₁ i m₂ znajduja sie w tym samym wierszu, to c₁ i c₂ (czyli litery kryptogramu) sa znakami z prawej strony m₁ i m₂, przy czym pierwsza kolumne traktuje sie jako polozona na prawo od ostatniej kolumny.
2. Jesli m₁ i m₂ znajduja sie w tej samej kolumnie, to c₁ i c₂ sa znakami polozonymi ponizej m₁ i m₂, przy czym pierwszy wiersz traktuje sie jako lezacy pod ostatnim wierszem.
3. Jesli m₁ i m₂ znajduja sie w roznych wierszach i kolumnach, to c₁ i c₂ sa brane z przeciwleglych rogow prostokata wyznaczonego przez m₁ i m₂, przy czym c₁ pochodzi z wiersza zawierajacego m₁, a c₂ z wiersza zawierajacego m₂.
4. Jesli m₁ = m₂, to do tekstu jawnego miedzy te litery wstawia sie litere nieznaczaca (np. X), co eliminuje powtorzenia.
5. Jesli tekst jawny ma nieparzysta liczbe znakow, to na jego koncu rowniez dopisuje sie litere nieznaczaca.

I znow krociutki przyklad.

Szyfry kaskadowe

Szyfry kaskadowe to zlozenia wielu funkcji (szyfrow), w ktorych kazda funkcja moze byc podstawieniem lub permutacja (przestawieniem).

Wazna podgrupa szyfrow kaskadowych sa szyfry podstawieniowo-permutacyjne. Tworca tej koncepcji przeksztalcenia mieszajacego jest Shannon. Jako przyklad jej praktycznej implementacji moze posluzyc urzadzenie szyfrujace LUCIFER, zaprojektowane przez jednego z pracownikow firmy IBM. Zastosowano w nim na przemian podstawienia i przestawienia. Mozna to zatem przedstawic za pomoca ponizszego wzoru:

gdzie: C - kryptogram, M - tekst jawny, S_i - i-te podstawienie, P_i - i-te przestawienie.

Uklad podstawiajacy S_i podzielono tu na 4 mniejsze uklady (S_i1, S_i2, S_i3, S_i4) dzialajace na 3-bitowych fragmentach bloku, co ma na celu uproszczenie ukladow mikroelektronicznych. Mozna rowniez zauwazyc, ze skoro permutacje P_i mieszaja wszystkie 12 bitow bloku, to kazdy bit tekstu jawnego ma wplyw na kazdy bit tekstu zaszyfrowanego.

Szyfry wykladnicze

Stanowia one nieco bardziej skomplikowany, lecz przez to bezpieczniejszy, rodzaj szyfrow. Opieraja sie na wykonywaniu potegowania w ciele skonczonym.

Przykladem moze tu byc szyfr RSA (od nazwisk autorow: Rivest, Shamir, Adleman). Modulem obliczen jest tu liczba n, bedaca iloczynem dwoch liczb pierwszych p i q. Blok tekstu jawnego M oraz kryptogram C musza zawierac sie w zbiorze liczb calkowitych [0, n-1]. Szyfrowanie przebiega tu zgodnie ze wzorem:

Natomiast deszyfrowanie wedlug:

Liczby calkowite dodatnie d i e nalezy dobrac wedlug nastepujacych wskazowek:

1. d jest liczba z przedzialu [max(p,q)+1,n-1] i pierwsza wzgledem E(n) - funkcji Eulera dla n (najlepiej niech to bedzie dowolna liczba pierwsza z tego przedzialu).
2. Wartosc e oblicza sie na podstawie rownania: e = inv(d,E(n)). Najlepiej zastosowac tu tzw. rozszerzony algorytm Euklidesa.
3. Jezeli na podstawie obliczen otrzymamy e takie, ze e < log₂n, to, aby zapewnic, ze dla kazdego kryptogramu wystapi przy odczycie redukcja modulo n, nalezy wybrac nowa wartosc d i jeszcze raz obliczyc e.

Przyklad liczbowy

Szyfry plecakowe

Jest to grupa szyfrow oparta na NP - zupelnym zagadnianiu plecakowym. Jego rozwiazanie deterministyczne (systematyczne) wymaga czasu wykladniczego, dlatego wlasnie jest ono zagadnieniem NP - zupelnym.

Istota NP - zupelnego zagadnienia plecakowego jest nastepujaca. Dla danego zbioru n liczb calkowitych A = (a₁,...,a_n) oraz liczby calkowitej S^* nalezy ustalic, czy istnieje podzbior zbioru A, taki, ze suma jego elementow daje w wyniku liczbe S^*. Majac dany taki podzbior mozna latwo sprawdzic, czy rownosc zachodzi, jednak znalezienie tego wlasciwego, jest wysoce czasochlonne, poniewaz istnieje 2ⁿ mozliwych podzbiorow, gdzie nalezy prowadzic poszukiwania (trzeba je po prostu sprawdzic).

Szyfry oparte na tym zagadnieniu to tzw. szyfry z kluczem jawnym (bedzie to wyjasnione przy omawianiu szyfru Merklego-Hellmana). Niektorych z nich mozna uzywac do ukrycia tresci wiadomosci, lecz nie do kontroli tozsamosci ich nadawcy. Wynika to z faktu, ze przeksztalcenie deszyfrujace nie odwzorowuje calej przestrzeni wiadomosci na siebie. Nie jest wiec mozliwe "podpisanie" dowolnej wiadomosci przez wykonanie na niej przeksztalcenia deszyfrujacego. Innymi szyframi mozna posluzyc sie w celu identyfikacji nadawcy, ale nie do ukrycia tresci wiadomosci. Problem jest tu bowiem odwrotny: przeksztalcenie deszyfrujace mozna wykonywac na wszystkich wiadomosciach, lecz szyfrujace - nie. Istnieja wprawdzie szyfry spelniajace obie te funkcje (ukrywanie tresci wiadomosci i identyfikacja nadawcy), ale sa one malo praktyczne, gdyz mozna je przelamywac za pomoca technik wielomianowych.

Jako przyklad szyfru omawianego typu moze nam posluzyc szyfr plecakowy Merklego- -Hellmana, sluzacy do ukrywania tresci wiadomosci. Opiera sie on na dwojkowym zagadnieniu plecakowym. Mamy dodatnia liczbe C i wektor dodatnich liczb calkowitych A = (a₁,...,a_n). Nalezy znalezc podzbior elementow wektora A, ktorych suma wynosi C. Nalezy zatem znalezc wektor dwojkowy M = (m₁,...,m_n) spelniajacy rownanie: C = A * M. Jest to zagadnienie NP - zupelne. Najlepszy znany algorytm jego rozwiazania wymaga 2^n/2 czasu i 2^n/4 pamieci (w jednostkach potrzebnych na wykonanie jednego takiego sprawdzenia).

Istnieje jednak pewna szczegolna klasa zagadnien plecakowych, zwanych prostymi, ktorych czas rozwiazania liniowo zalezy od liczby elementow. Merkle i Hellman pokazali, jak przeksztalcic proste zagadnienie plecakowe w zagadninie plecakowe z tajnym przejsciem, trudne do rozwiazania bez dodatkowych informacji. Przeksztalcenie to sklada sie z nastepujacych krokow.

1. Wybieramy wektor prostego zagadnienia plecakowego A' = (a₁',...,a_n'). Korzystajac z tego wektora rozwiazanie zagadnienia C' = A' * M jest proste.
2. Wybieramy liczbe calkowita u, wieksza od sumy elementow wektora A'.
3. Wybieramy liczba calkowita w taka, ze najwiekszy wspolny dzielnik liczb u i w wynosi 1 (NWD(u,w) = 1).
4. Obliczamy w^-1 (odwrotnosc w mod u) wedlug wzoru: w^-1 = inv(w,u). Skorzystac tu mozna z rozszerzonego algorytmu Euklidesa.
5. Przeksztalcamy wektor A' w wektor zlozonego zagadnienia plecakowego A wedlug wzoru: A= w * A' mod u. Dla poszczegolnych elementow jest to wzor: a_i = w * a_i' mod u.

Rozwiazanie rownania C = A * M jest trudne, lecz mamy "tajne przejscie" w postaci liczb w^-1 i u. Mozemy zatem przeksztalcic zagadnienie w prosta postac: C' = A' * M.

Klucz jawny to wektor zlozonego zagadnienia plecakowego A. Klucz tajny to wektor prostego zagadnienia plecakowego A' oraz opis "tajnego przejscia", czyli liczby u i w^-1(A' mozna obliczyc majac A, u i w^-1 wedlug wzoru: A' = w^-1 * A mod u). Przeksztalcenie szyfrujace przy uzyciu opublikowanego klucza A oznaczmy jako E_A, natomiast przeksztalcenie deszyfrujace przy uzyciu tajnego klucza (A', u, w^-1) - jako D_A. Podczas szyfrowania tekst jawny dzieli sie na n-bitowe bloki M = (m₁,...,m_n) i kazdy blok szyfruje sie obliczajac:

Kryptogram C deszyfruje sie natomiast wedlug wzoru:

Przyklad liczbowy