Porównanie wybranych systemów kryptograficznych


W artykule tym zamierzam przybliżyć i porównać z sobą symetryczne i asymetryczne systemy kryptograficzne początku XX wieku oraz lat 70. Za przykłady po obu stronach tej konfrontacji posłużą mi algorytm Vernama i algorytm RSA. Krótko opiszę każdy z nich, podam ich najważniejsze zalety i wady. Czuję się też zobowiązany do tego, by wspomnieć o metodach kryptografii, jakie znano w znacznie odleglejszych nam czasach, bo nawet przed naszą erą. Skupiam się tu na kryptografii klasycznej i problemach trudnych matematycznie. Pomijam świat wielowymiarowy oraz czynniki mechaniczne. Temat kryptografii kwantowej pozostawiam sobie na przyszłość.

 

 

  1. Rys historyczny

 

Zanim przejdę do głównej części tematu, muszę wspomnieć o sposobach szyfrowania wiadomości w czasach najdawniejszych. Jednym z nich jest metoda stosowana przez spartan, o nazwie Skytale. Polega on na naniesieniu znaków na pas skóry, a następnie nałożeniu go na odpowiednią włócznię w celu odczytania. Problem polega na połączeniu paska z kształtem włóczni. Trzon musi być odpowiednio wyrzeźbiony, aby można było ową wiadomość odczytać.

 

Kolejnym przykładem jest szyfr Cezara. Dziś może się wydawać trywialny, lecz w tamtych czasach spełniał swoją rolę. Bazuje on na systemie podstawieniowym, co oznacza, że pojedynczym znakiem zastępujemy pojedynczy inny znak. Korzystając więc z określonego klucza, który przeważnie jest liczbą, przesuwamy litery alfabetu w celu odkodowania wiadomości. Modelowo ciąg znaków KXRHX z kluczem 3 po odczytaniu da nam słowo NAUKA.

 

 

  1. Szyfr Vernama – stary, ale ciągle niezawodny

 

Twórcą tego szyfru, a właściwie maszyny go generującej, jest Gilbert Vernam. Za rok utworzenia przyjmuje się 1917. Należy do grupy algorytmów symetrycznych, w których zaszyfrowanej wiadomości odpowiada dokładnie jeden tajny klucz. W pewnym sensie przypomina szyfr Cezara, jednak jest bardziej skomplikowany. Różnica polega na przestawianiu znaku o losowy wolumen oraz nurt. Maszyna ta umożliwia korzystanie zawsze z klucza oryginalnego i jednokrotnego. Daje nam to pewność, że sekwencja zabezpieczająca nie rozpowszechni się.

Przełóżmy sprawę na mózg elektronowy. Jak wiadomo, komputer działa zero-jedynkowo. Nie inaczej w przypadku omawianego algorytmu: każdy element szyfru jest dobrany dokładnie z pięcioma sygnałami łączności telegraficznej lub ich braku. Logicznie będzie to „tak” lub „nie”, czyli 1 albo 0. Przykładowo słowo „nauka” odpowiadać będzie kodowi binarnemu

 

         N               A                U               K               A

          01101110  01100001  01110101  01101011  01100001

 

Mamy już zatem naszą wiadomość. Teraz potrzebujemy strumienia szyfrującego. Załóżmy, że wylosowaliśmy następujący:

 

11111110 11010101 01010101 10101010 00011100

 

Pozostało nam utworzyć szyfrogram. Aby to uczynić, musimy zastosować logiczny funktor zdaniotwórczy, inaczej alternatywę wyłączającą lub różnicę symetryczną. W skrócie XOR. Oznacza to, że wynik będzie prawdziwy (1) wtedy i tylko wtedy, jeśli jeden i tylko jeden z argumentów będzie prawdą (1).

 

Wróćmy do szyfrowania. Wykonując operację XOR na wiadomości i szyfrogramie, tj.:

 

01101110 01100001 01110101 01101011 01100001

11111110 11010101 01010101 10101010 00011100

 

uzyskamy:

 

10010000 10110100 00100000 11000001 01111101

 

i to jest nasz tajny kod dostępny dla obu stron komunikacji.

 

Jeśli bylibyśmy stroną odbierającą szyfr i mającą wykonać deszyfrowanie, wykonujemy powyższe operacje tak samo z tą różnicą, że algorytm XOR przeprowadzamy na tajnym kodzie oraz strumieniu szyfrującym.

 

 

  1. Algorytm RSA- klasyka w nowoczesnym wydaniu

 

RSA powstał w roku 1977. Stworzyli go Ronald Linn Rivest, Adie Shamir oraz Leonard Adleman. Od pierwszych liter nazwisk profesorów MIT  (Massachusetts Institute of Technology) pochodzi również nazwa szyfru. Należy do grona szyfrów niesymetrycznym, czyli takich, który posiada dwa klucze. Jeden tajny, a drugi publiczny. Pierwszy służy do odszyfrowania komunikacji, natomiast drugi do jej zakodowania. W tym miejscu należy zaznaczyć, że pomimo upublicznienia klucza nie ułatwia to w żaden sposób deszyfryzacji. Ażeby nieco rozjaśnić tę sprawę, posłużę się przykładem. Robiąc zakupy przez internet i wybierając cyfrową formę płatności, mimowolnie bierzemy udział w działaniu algorytmu RSA. Podstawową cechą omawianego szyfru i jego bezpieczeństwa jest faktoryzacja liczb, tzn. trudny problem matematyczny rozkładu dużych liczb na czynniki pierwsze.

 

a.) Generowanie kluczy

 

W celu skorzystania z omawianego schematu musimy zacząć od wygenerowania obu kluczy.

Znajdujemy liczby np. 128 bitowe. Określamy je jako dowolne litery alfabetu. Domyślnie przyjmuje się „p” i „q”. Pomijam tu zewnętrzne algorytmy sterujące losowaniem tych cyfr (np. Test Millera-Rabina). Pamiętamy o ścisłej ochronie wybranych atrybutów.

Następnie obliczamy funkcję Eulera φ (wyliczanie liczb względnie pierwszych, nie większych od określonej liczby naturalnej) oraz moduł „n”. Odpowiednio korzystamy tu ze wzorów

φ = (p-1) * (q-1) i n = p * q. Teraz czas na znalezienie liczby względnie pierwszej z uwzględnieniem wyniku funkcji Eulera tj. 1 = (e, φ) zgodnie z warunkiem nieparzystości i

1 < e < n.

Teraz odnajdujemy przeciwną liczbę (d) modulo (reszta z dzielenia) φ do liczby e

1 = d * e mod φ.

 

W tym miejscu mamy już potrzebne klucze. Klucz tajny (d, n) oraz klucz publiczny (e, n).

 

b.) Szyfrowanie

 

Pierwszym krokiem jest otrzymanie od adresata wiadomości klucza publicznego pod postacią dwóch liczb „e” i „n”. Następnie, korzystając z nierówności 0 < t < n, znajdujemy odpowiednie liczby naturalne (t). Teraz na owych liczbach stosujemy szyfrowanie do postaci c = t e modulo  n, gdzie „c” oznacza liczby analogiczne do liczb „t”, z tym że w postaci utajnionej. Ostatnim krokiem jest odesłanie ich do adresata. Warto zaznaczyć, że klucz publiczny nie umożliwia ich rozszyfrowania, a tylko kodowanie.

 

c.) Deszyfrowanie

 

Sytuacja odwrotna. Wysyłamy wygenerowany klucz publiczny w postaci liczb „e” i „n” do docelowego korespondenta, który je szyfruje i odsyła z powrotem w postaci liczb naturalnych ( c ) spełniających nierówność 0 < c < n.

Następnie stosując wzór t = cd modulo n wyznaczamy wartość liczb ( t ).  Teraz wystarczy odczytać wiadomość, korzystając z domyślnego systemu.

 

d.) Przykład

 

Do utworzenia kluczy posłużę się małymi liczbami pierwszymi. Domyślnie powinny być bardzo duże, ale chciałbym ułatwić zrozumienie działania algorytmu.

 

Mamy zatem p = 7 i q = 5.

 

Obliczamy funkcję Eulera

 

φ = (7 – 1) * (5 – 1) = 24

 

Teraz n, czyli moduł

 

n = 7 * 5 = 35

 

Kolejno wykładnik publiczny(e), czyli liczba względnie pierwsza do 35 (największy wspólny dzielnik to 1)

 

e = 11

 

Wykładnik prywatny liczymy ze wzoru:

 

d * 11 modulo 35 = 1

 

Warunek spełnia liczba 51, ponieważ 51 * 11 = 561 ——— 561 mod 35 =1.

 

W ten sposób wygenerowaliśmy klucze

 

Publiczny (11, 35)

Prywatny (51, 35)

 

 

Czas na szyfrowanie. Załóżmy, że otrzymaliśmy wcześniej wyliczony klucz publiczny (11,35)

 

Wybieramy liczbę „t” spełniającą nierówność w naszym przypadku 0 < t < 35, czyli np. 13

Używamy wzoru:

 

c = 1311 mod 35 = 4194304 mod 35 = 27

 

Liczba 27 jest zaszyfrowaną liczbą 13.

 

 

Czas na rozszyfrowanie. Przyjmijmy inny wariant. Dostaliśmy tajną komunikację o wartości 7. Posiadamy klucz prywatny (103, 143) i możemy przejść do zadania, czyli znalezienia pierwotnej wartości liczby „t”.

 

t = 7103 mod 143

 

W celu ułatwienia możemy zastosować metodę podobną do zamiany liczb binarnych do formatu dziesiętnego, czyli po prostu wykorzystanie kolejnych potęg dwójki.

 

7103 mod 143 = 764 + 32 + 4 + 2 + 1 mod 143 = (764mod 143) * (732 mod 143)  * (72 mod 143) * (71 mod 143)

 

764 mod 143 = (732 mod 143)2 mod 143 = 162 mod 143 = 113

 

732 mod 143 = (716mod 143)2 mod 143 = 482 mod 143 = 16

 

74 mod 143 = (72 mod 35)2 mod 143 = 492 mod 143 = 113

 

72 mod 143 = (71 mod 35)2 mod 35 = 49 mod 143 = 49

 

71 mod 143 = 7

 

t = 113 * 16 * 113 * 49 * 7 mod 143 = 70076272 mod 143 = 123

 

Liczba 123 jest odtajnioną wiadomością.

 

 

  1. Podobne, a jednak inne – porównanie

 

a.) Zalety

 

Szyfr Vernama

 

  • w przypadku stosowania zawsze jednorazowego, losowego klucza zapewnia absolutne bezpieczeństwo
  • nieskomplikowany i szybki w stosowaniu

 

Algorytm RSA

 

  • swobodna możliwość udostępniania klucza publicznego bez ryzyka odtajenia wiadomości
  • ze względu na oparcie bezpieczeństwa o trudności rozkładu ogromnych liczb na czynniki pierwsze umożliwia komunikację danych w środowisku narażonym na liczne nadużycia

 

b.) Wady

 

Szyfr Vernama  

 

  • rozmiar klucza jest równy długości wiadomości
  • wymóg klucza jednorazowego, w przeciwnym wypadku istnieje ryzyko odnalezienia ciągu logicznego

 

Algorytm RSA

 

  • długi czas szyfrowania wiadomości
  • różnica w wydajności w przypadku dużych wolumenów danych

 

 

Jak widać, główne różnice polegają na koszcie czasowym i wydajności działania w określonych przypadkach. Szybkość i prostota wypadają na korzyść szyfru symetrycznego, za to większa swoboda i elastyczność jest po stronie RSA. Trzeba jednak nadmienić, że w erze obecnej technologii i zastosowaniu jednorazowego, losowego klucza szyfru Vernama mamy zagwarantowane stuprocentowe bezpieczeństwo.

 

Tak długo jak obecna technologia nie wykona nieprzewidywalnie wyjątkowo ogromnego skoku do przodu, obecne systemy kryptograficzne zapewniają satysfakcjonujące efekty i przede wszystkim niemal całkowitą ochronę wymienianych danych.

 

 

  1. Źródła

 

Thomas H. Cormen. Rozdział 31. Algorytmy Teorioliczbowe we Wprowadzenie do algorytmów. Wyd. VII. Warszawa, 2005 WNT, s. 902 – 909

 

David Kahn: The Codebreakers – The Story of Secret Writing. Scribner, 1996


Mateusz Rogala

O Mateusz Rogala

Ukończyłem studia podyplomowe na Politechnice Gdańskiej z kierunkiem Programowanie i bazy danych. Interesuję się tematem materii, fizyką i informatyką kwantową. W wolnych chwilach zajmuję się kalisteniką oraz czytam książki fantastyczne.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *