Kryptografia

Podstawowe pojęcia

Kryptografia – nauka o sposobach przesyłania wiadomości w zmienionej postaci tak, by tylko adresat mógł odczytać wiadomość.

Tekst jawny (otwarty)– wiadomość, którą chcemy przesłać.

Tekst zaszyfrowany (kryptogram) – wiadomość w zmienionej postaci.

Alfabet– sposób, w jaki zapisany jest tekst jawny i kryptogram; zwykle alfabet składa się z pewnej liczby N liter.

Szyfrowanie– proces przekształcania tekstu jawnego w kryptogram.

Rozszyfrowywanie (deszyfrowanie lub dekodowanie)– proces przekształcania tekstu zaszyfrowanego w otwarty.

Przekształcenie szyfrujące– funkcja przyporządkowująca jednostce tekstu otwartego jednostkę tekstu zaszyfrowanego.

Przekształcenie rozszyfrowujące (deszyfrujące)– przekształcenie odwrotne, które odtwarza tekst jawny z tekstu zaszyfrowanego.

System kryptograficzny – układ .

Łamanie szyfru (kryptoanaliza) – czytanie zaszyfrowanych wiadomości bez znajomości metody szyfrowania i rozszyfrowywania.

Jednostki tekstu – pojedyncze litery, pary liter (diagram), trójki (trigram) czy bloki 10, 20 itd. liter, na które dzielimy tekst jawny i kryptogram.

Klucz (klucz szyfrujący lub klucz szyfrowania)- parametry lub parametry pozwalające zaszyfrować tekst jawny w oparciu o ustaloną formułę systemu kryptograficznego.

Od wielu wieków ludzkość stosowała przeróżne sposoby ukrywania przekazywania informacji. Tradycyjnie kryptografię stosowano do celów wojskowych i korespondencji dyplomatycznej. W ostatnich latach zastosowanie tej dziedziny matematyki rozciągnęło się na wiele nowych obszarów, w których podstawową rolę odgrywają systemu komunikacji – zbieranie i przechowywanie danych, elektroniczne transakcje itd. Znaleźliśmy się w sytuacji, gdy jeden z użytkowników obszernej sieci chce przesłać do innego wiadomość tak, by nikt inny nie mógł jej odczytać. Przed laty problem stanowiło nie tylko rozszyfrowanie tekstu, ale również jego przechwycenie. Bez względu jednak na sposób zdobycia przesyłanej wiadomości, rzadko kiedy stosowano czysto matematyczne sposoby łamania kodów. Zwykle wykorzystywano dodatkowe informacje, które ułatwiały pierwsze kroki rozkodowywania. Na przykład, w trakcie krucjat niewierni rozszyfrowali przesyłany list wykorzystując prostą informację: jak zacznie list chrześcijanin? Oczywiście „W imię Ojca i Syna, i Ducha Świętego”. Jednym z niewielu przykładów „matematycznego” złamania kodu jest Enigma. W trakcie II wojny światowej matematycy polscy zdołali tylko i wyłącznie matematycznymi metodami (mieli przy okazji nieco szczęścia) rozpracować niemiecką maszynę. Później, kiedy Niemcy skomplikowali nieco sposób kodowania, do pracy zaprzężono kilka połączonych ze sobą maszyn Turinga, które poradziły sobie z tym problemem (niektórzy uważają, że urządzenie zbudowane na potrzeby łamania Enigmy było pierwszym komputerem). Można się domyślić, że wraz z rozwojem matematyki pojawiały się coraz to bardziej skomplikowane sposoby szyfrowania, niemal niemożliwe do złamania. Do zaawansowanych metod należą m.in. te oparte na wykorzystaniu krzywych eliptycznych, a także (już nieco z innego powodu) systemy z publicznym kluczem.

Tworzenie systemu kryptograficznego rozpoczyna się od „ponumerowania” wszystkich możliwych jednostek tekstu, czyli – w najprostszym przypadku – „ponumerowanie” wszystkich liter alfabetu. W przypadku 26-literowego alfabetu będą to najczęściej liczby od 0 do 25, a więc literze „A” przypadnie liczba 0, „B” – 1 „C” – 2 itd. Czasem również odstępowi (tzw. spacji) przypisuje się jakąś liczbę, choćby 26. W przypadku, gdy za jednostkę tekstu weźmiemy jeden znak, sprawa jest oczywista. Jeśli jednak mamy do czynienia z diagramem, to możemy danemu blokowi dwuliterowemu przypisać liczbę: , gdzie . Teraz diagramowi „ON” dopowiadać będzie liczba 27 14 + 13 = 391. Podobnie sprawa ma się z trigramami, z tym że będziemy je numerować w sposób następujący:

Bloki k-literowe w alfabecie składającym się z N liter możemy ponumerować liczbami od 0 do Nk – 1. Będziemy więc taki blok traktować jako k-cyfrową liczbę w systemie pozycyjnym o podstawie N.

Szyfr Cezara

Poniższego systemu kryptograficznego używał w Rzymie Juliusz Cezar (podobno sam go wymyślił).

Mamy 26-literowy alfabet A-Z o odpowiadających mu liczbach 0-25. Niech litera L (należąca do zbioru {0, 1, …, 25}) oznacza jednostkę tekstu jawnego. Definiujemy funkcję f ze zbioru {0, 1, …, 25} w ten sam zbiór:

Inaczej mówiąc, f po prostu dodaje 3 modulo 26: f(L) L + 3 (mod 26). Ogólnie tę metodę nazywamy przesunięciem, definiując f wzorem C = f(L) L + b (mod N), dla b ustalonej liczby całkowitej. W systemie Juliusza Cezara mieliśmy N = 26, b = 3. Chcąc rozszyfrować zakodowaną tym szyfrem wiadomość po prostu obliczamy L = f-1(C) Cb (mod N).

Do złamania systemu kryptograficznego potrzebujemy przede wszystkim ogólnej struktury tegoż systemu, a więc na przykład informacji, że opiera się on na przesunięciu liter 0-25 alfabetu A-Z. Ponadto musimy również posiadać wartości pewnych parametrów związanych z systemem – choćby znać wartość parametru przesunięcia b. Kiedy zdobędziemy te informacje, łatwo będzie nam złamać kod.

Zwykle osoby korzystające z systemów kryptograficznych posiadają urządzenia (tym pojęciem obejmujemy również program komputerowy) do szyfrowania i rozszyfrowywania informacji. Konstrukcja tych mechanizmów umożliwia stosowanie jednego systemu kryptograficznego. Bardzo prawdopodobne jest, że informacja o używanym przez nich systemie wydostanie się na zewnątrz. Dlatego też, by zwiększyć bezpieczeństwo, często zmieniają oni wykorzystywane parametry. Na przykład – spotykając się raz na jakiś czas – ustalają listę 50 wyborów parametru b.

Jednym z najprostszych sposobów łamania zaszyfrowanych metodą przesunięcia wiadomości jest analiza częstości. Opiera się ona na informacji o częstości występowania danej litery w języku, w którym przekazywane są teksty. Wszyscy zapewne wiedzą, że chociażby w języku angielskim najczęściej występującą literą jest „E”. Jeśli teraz zauważymy, że „U” jest najczęściej występującą w tekście zakodowanym literą, to dochodzimy do prostego wniosku, iż „U” to „E”. W przypadku, gdy szyfrujemy tekst wraz z odstępami, to zwykle najczęściej występującym znakiem będzie ten, który odpowiada właśnie odstępowi.

Odkrycie, iż przesunięcie przeprowadza „E” = 4 na „U” = 20, pozwala nam znaleźć w prosty sposób klucz b: 20 4 + b (mod 26), czyli b = 16.

Chcąc ulepszyć systemu przesunięć, można wykorzystać bardziej ogólne przekształcenie zwane przekształceniem afinicznym. W tym przypadku będziemy potrzebować już dwóch informacji dotyczących częstości, a więc poznać dwie najczęściej powtarzające się litery. W przypadku angielskiego po „E” najczęściej występuje „T”, gdy więc odkryjemy, że w tekście zakodowanym najczęściej pojawiają się odpowiednio „K” i „D”, to sprawa będzie prosta.

Również diagramy dwuliterowe można szyfrować wykorzystując przekształcenia afiniczne. W tym przypadku wpierw dzielimy jednak tekst jawny na fragmenty dwuliterowe, a jeśli składa się on z nieparzystej liczby liter, do na końcu dopisujemy dodatkowy znak. Oczywiście wybieramy do tego znak, który nie utrudni poprawnego odczytania (np. odstęp, jeśli takowy występuje). Następnie, w znanym nam już sposób, przypisujemy diagramowi liczbę, a potem dokonujemy przekształcenia. Aby złamać taki kod, badamy częstość występowania bloków dwuliterowych w danym języku. W przypadku angielskiego będą to „TH” i „HE”. Znajomość dwóch odpowiadających sobie diagramów zwykle wystarcza do znalezienia klucza.

Przekształcenie afiniczne to przekształcenie Z/NZ opisane wzorem CaL + b (mod N), gdzie a i b są ustalonymi liczbami całkowitymi, które razem tworzą klucz szyfrowania (w przypadku diagramów będzie to przekształcenie Z/NZ zdefiniowane CaL + b (mod N2)). Zakładając, że „E” = 4 to po zaszyfrowaniu „K” = 10, a „T” = 19 to „D” = 3, możemy zapisać 10a + b 4 (mod 26) i 3a + b 19 (mod 26). Mamy więc dwie kongruencje z dwiema niewiadomymi. Z algebry liniowej wiadomo, że n równań liniowych o n niewiadomych można rozwiązać tylko wtedy, gdy te równania są niezależne. W naszym przypadku tak właśnie jest i po odjęciu tych dwóch kongruencji stronami i podstawieniu otrzymujemy wzór rozszyfrowujący: K 9C + 18 (mod 26).

UWAGA: W tym przypadku a nie może mieć wspólnych dzielników z N. Inaczej nie będzie istniało przekształcenie odwrotne umożliwiające rozszyfrowanie.

Afiniczne systemy kryptograficzne kodujące diagramy są lepsze od tych, w których używa się pojedynczych liter. Mają one jednak pewną wadę, a mianowicie druga litera każdego diagramu kryptogramu zależy tylko od drugiej litery tekstu jawnego. Można więc wiele informacji uzyskać z analizy częstości liter występujących w kryptogramie na miejscach parzystych. Podobnie ma się sprawa z przekształceniami afinicznymi modulo Nk bloków k-literowych.

Szyfr VignŔre’a

Ten szyfr był przez wiele stuleci jedynym z najpopularniejszych, a opisuję się go w następujący sposób:

Dla ustalonego k bloki k‑literowe traktujemy jak wektory przestrzeni (Z/NZ)k. Wybieramy ustalony wektor b należący do tej przestrzeni (zwykle jest to łatwe do zapamiętania słowo kluczowe) i szyfrujemy za pomocą przesunięcia o wektor b: C = K + b, gdzie K i C to ciągi k liczb modulo N. System ten jest jednak tak łatwy do złamania jak systemy oparte na przesunięciu pojedynczych liter. Znając bowiem (lub odgadując) N i k rozbijamy tekst zaszyfrowany na bloki k‑literowe i stosując analizę częstości pierwszych liter wszystkich bloków ustalamy pierwszą literę b, a następnie podobnie ustalamy drugą literę b itd.

Diagramom można również przypisywać wektory (x, y), na przykład „NO” odpowiadać będzie wektor (13, 14). Do szyfrowania tym razem stosuje się macierz A o dwóch kolumnach i dwóch wierszach, a rozszyfrowywania macierzy odwrotnej A–1. Do złamania tego rodzaju kodów wystarczy znajomość dwóch par diagramów tekstu otwartego i kryptogramu, którą to informację można zdobyć w oparciu o analizę częstości diagramów lub zdobywając z innego źródła informację, że pewien czteroliterowy fragment tekstu odpowiada czeteroliterowemu kryptogramowi.

Niech naszą macierzą szyfrującą będzie macierz A = , gdzie N = 26. Korzystając z niej możemy zaszyfrować wektor diagramu „NO” w następujący, oczywisty sposób: AK = , a więc nasz diagram będzie odpowiadał diagramowi „QV”.

Jeśli spełniamy warunki potrzebne do złamania zaszyfrowanej informacji, a więc znając dwie pary diagramów tekstu otwartego C1 = AK1 oraz C2 = AK2, to możemy znaleźć macierze A i A–1 (czyli szyfrującą i deszyfrującą). W tym celu składamy kolumny K1 oraz K2, otrzymując macierz K wymiaru 2 x 2, oraz wektory kryptogramu C1 oraz C2, otrzymując macierz C również wymiaru 2 x 2. Następnie tworzymy równanie macierzowe C = AK o znanych macierzach C i K, a macierz A niewiadomą, które możemy rozwiązać: A = CK–1. Podobnie z równania K = A–1C otrzymujemy macierz A–1 = KC–1.

Przez wszystkie stulecia kryptograficznej historii (czyli m.in. we wcześniejszych przykładach) algorytm szyfrowania nie wymagał podawania klucza szyfrującego tekst jawny i oddzielnego klucza rozszyfrowującego. Oznaczało to, że każda osoba posiadająca wystarczająco dużo informacji by rozszyfrować wiadomość, mogła również bez problemu otrzymać klucz szyfrujący. Tylko niezwykle naiwni mogli sądzić, że ten, kto złamał szyfr, mógłby nie znać klucza szyfrującego. Dopiero w 1976 roku W. Diffie i M. Hellman odkryli zupełnie nowy typ systemów kryptograficznych – powstały systemy z kluczem publicznym. Idea tych systemów kryptograficznych jest prosta: rozpowszechnia się klucz szyfrujący i algorytm szyfrowania tak, że każdy ewentualny użytkownik go otrzyma, jednakże do rozszyfrowania zakodowanej informacji potrzeba zupełnie innego klucza deszyfrującego. Innymi słowy osoba, która wie, w jaki sposób szyfrować wiadomość nie może wykorzystać klucza szyfrującego do tego, by znaleźć klucz rozszyfrowujący bez niezwykle długich obliczeń.

Idea systemów z kluczem publicznym opiera się na istnieniu prostego przekształcenia szyfrującego , które łatwo obliczyć mając klucz szyfrujący, ale dla którego obliczenie funkcji odwrotnej jest bardzo trudne. Innymi słowy, funkcja f nie jest odwracalna bez znajomości klucza rozszyfrowującego. Taką funkcję f nazywamy funkcją progową lub funkcją jednokierunkową z kluczem. Bliskie tych funkcji są tzw. funkcje jednokierunkowe (bez klucza), nazywane też jednostronnymi. Charakteryzują się one tą cechą, że ich wartości łatwo obliczyć, ale odwrotność niezwykle trudne. Jeszcze w 1974 roku G. Purdy opublikował pierwszą funkcję jednokierunkową, której wartości łatwo obliczało się korzystając z komputera, ale odwrotności nie.

Często jednym z najważniejszych fragmentów przesyłanej informacji jest podpis. Wszyscy wiemy, że typowy dla nadawcy charakter pisma daje nam pewność, iż list przyszedł od niego. W przypadku szczególnie ważnych informacji może zajść potrzeba potwierdzenia tożsamości nadawcy, zwłaszcza w przypadku elektronicznego przesyłania wiadomości. Systemy z publicznym kluczem umożliwiają to w sposób niezwykle prosty.

Agnieszka i Michał są dwoma użytkownikami systemu. Przez fA oznaczać będziemy przekształcenie szyfrujące, które używa się przesyłając informację do Agnieszki, a przez fM oznaczać analogiczne przekształcenie, tyle że dla Michała. Niech teraz PA będzie podpisem Agnieszki, która chce wysłać Michałowi opatrzoną nim wiadomość (w końcu wszyscy mogą się pod nią podszyć). Agnieszka opatrzy więc list informacją fM fA–1(PA). Michał rozszyfruje tą wiadomość korzystając ze swojej funkcji fM–1 i otrzyma tekst jawny oraz fragment „bełkotu”, którym jest podpis Agnieszki fA–1(PA). Michał wie do kogo pochodzi list, wykorzysta powszechnie znane przekształcenie szyfrujące Agnieszki fA do „bełkotu” i otrzyma PA. Ponieważ oczywiście nikt poza Agnieszką nie mógł wykorzystać przekształcenia fA–1, więc jej podpis jest automatycznie potwierdzeniem nadawcy.

Większość systemów kryptograficznych jest deterministyczna, innymi słowy tekst otwarty będzie za każdym razem szyfrowany w ten sam sposób. Systemy te mają niestety swoje wady. Po pierwsze, jeśli osoba trzecia wie, że teksty otwarte należą do małego zbioru (wiadomością jest choćby „tak” lub „nie”), to może ona zaszyfrować wszystkie wiadomości i stwierdzić, która z nich jest interesującą tajną informacją. Po drugie, trudna jest udowodnić jakiekolwiek twierdzenia dotyczące bezpieczeństwa systemów deterministycznych. Między innymi z tych właśnie powodów wprowadzono tzw. szyfrowanie probabilistyczne, które niweluje te dwie wady.

System RSA

Jest to jeden z najbardziej rozpowszechnionych systemów z publicznym kluczem i do tego najstarszym. Jego nazwa pochodzi od nazwisk trzech twórców: Rivesta, Shamira i Adlemana. W przypadku RSA wykonuje się wiele dość skomplikowanych operacji matematycznych, które komputer wykonuje niezwykle szybko. Cała zaś idea tego szyfru opiera się na trudności związanej z rozkładem dużej liczby na czynniki pierwsze. Osoba, która pragnie, by przesyłano do niej zakodowane informacje, rozpowszechnia stosunkowo dużą liczbę, która jest iloczynem dwóch liczb pierwszych o liczbie cyfr rzędu 100. Do zaszyfrowania informacji wystarczy tylko rozpowszechnienia wartość iloczynu tych liczb, jednakże do rozszyfrowania – te liczby. Dla ukazania złożoności problemu rozłożenia dużej liczby na czynniki pierwsze proponuję, by Czytelnik spróbował zrobić to dla iloczynu dwóch liczb trzycyfrowych – iloczynem jakich liczb pierwszych jest liczba 343171?

Odpowiedź: 571 i 601

Napis w toalecie University of Washington

Czy zauważyliście, by ktoś kiedykolwiek szukał naprawdę dużych liczb, które nie są pierwsze? To znaczy, czy chciałbyś kiedykolwiek przeczytać wiadomość, że „dziś Widział Informatyki University of Washington ogłosił, że liczba 258 111 625 031 + 8 jest parzysta; jest to największa dotychczas znaleziona liczba złożona”.

W 1991 roku rządowy instytut Stanów Zjednoczonych, Nationa Institute of Standards and Technology, zaproponował standard podpisów cyfrowych (Digital Signature Standard - DSS). Jego rola ma być analogiczna do standardowego szyfrowania danych (Data Encryption Standard - DES), a więc zakładało się, że stanie się on metodą cyfrowego podpisywania korespondencji między organizacjami rządowymi i handlowymi. O ile jednak DES był klasycznym systemem kryptograficznym (z tzw. prywatnym kluczem), o tyle podpisy cyfrowe wymagają użycia systemów z kluczem publicznym. DSS został tak opracowany, że osiągnął dość wysoki poziom bezpieczeństwa i działał dość szybko, a jednocześnie przechowywanie podpisu nie wymagało dużej pamięci. I może dzięki temu rozpowszechnił się dość znacznie.

Nie chcąc zanudzać czytelnika zbyt długimi matematycznymi wykładami, które wiążą się z bardziej zaawansowanymi systemami kryptograficznymi, pominąłem wiele niezwykle interesujących tematów, takich jak funkcje skrótu, wymiana kluczy, logarytm dyskretny, system wymiany kluczy Diffiego-Hellmana, system kryptograficzny Masseya-Omury, system kryptograficzny ElGamala czy pakowanie plecaka (co ciekawe, istnieje dotychczas niezłamany system plecakowy, opracowany przez Chora i Rivesta). Mam jednak nadzieję, że ciekawi sięgnął po tzw. „lektury dodatkowe”.

Miłego szyfrowania…

więcej...