Elementy  zabezpieczeń

Tytułem wstępu

Strona powstała na konkurs "Zobaczyć Matematykę" i pragnę dzięki niej zapoznać Państwa z praktycznym wykorzystaniem zagadnień matematycznych w kryptologii i zabezpieczeniach informatycznych. Kryptologia (z gr. kryptos – „ukryty” i logos – „rozum”, „słowo”) jest dziedziną wiedzy o przekazywaniu zabezpieczonych informacji przed niepowołanym dostępem. Wszystkie poniższe działy mają swoje określone zadania. Zawierają niezbędne definicje, teorie, przykłady i wizualizacje, których przyswojenie ułatwi nam zrozumienie działania kryptosystemu RSA, który jest nieodłącznym elementem w ochronie informacji w globalnej sieci.

Wstęp do algorytmów

Na początku przybliżmy sobie dział algorytmów. "Algorytm jest to zestaw kroków, jakie trzeba wykonać, by w sposób np. matematyczny rozwiązać zadany problem; opisuje, jak działa program." Tak brzmi słownikowa definicja tego słowa. Wielu nauczycieli przyrównuje algorytm do przepisu kulinarnego, aby pojęcie zostało łatwiej przyswojone przez uczniów. Jednym z najpopularniejszych algorytmów jest algorytm Euklidesa. Jest to metoda wyznaczania największego wspólnego dzielnika liczb całkowitych. Co ciekawe, nie wymaga on rozkładania podanych liczb na czynniki pierwsze. Zaskakującym faktem jest również to, że najgorszy przypadek danych wejściowych stanowią liczby ciągu Fibonacciego. Istnieje również rozszerzona wersja tego algorytmu, która dodatkowo oblicza całkowitoliczbowe współczynniki x i y:

$$ NWD(a, b) = ax + by $$

Euklides był greckim matematykiem pochodzącym z Aten, żyjącym ok. 365-300 p.n.e.. Jego największym dziełem były "Elementy", w którym sformułował 467 twierdzeń matematycznych. Nie bez powodu wspominam o tej pracy, ponieważ to w niej opisał najstarszy algorytm na świecie. Jego zrozumienie przyda nam się przy omawianiu kolejnych działów znajdujących się na stronie. Zanim przanalizujmy krok po kroku omawiany algorytm, musimy dowiedzieć się co to jest procedura rekurencyjna. Rekurecja (inaczej rekursja) jest to specyficzna sytuacja, kiedy funkcja lub definicja wywołuje samą siebie. Zastąpienie iteracyjnej techniki może nieco spowolnić tworzony program, ale ułatwić rozwiązanie. Poniżej znajduje się algorytm Euklidesa w postaci listy kroków z wykorzystaniem reszty z dzielenia oraz techniki odejmowania.

  Skierowanie kursora myszy na elementy algorytmu wyświetli wyjaśnienie.

EUKLIDES ( a, b )
1  
if b == 0
2     return a
3   else return EUKLIDES ( b, a mod b )
EUKLIDES ( a, b )
1  
if a == b
2     return a
3   if a > b
4     return EUKLIDES ( a - b, b )
5   else return EUKLIDES ( a, b - a )

Algorytmy i maszyny liczące miały swój wielki udział podczas II Wojny Światowej. Alan Turing był brytyjskim matematykiem, który prawdopodobnie skrócił wojnę o co najmniej 2 lata. Zawdzięczamy to jego maszynie do łamania kodów niemieckiej maszyny szyfrującej Enigmy. Nie jest to całkowicie jego zasługa, ponieważ Polacy, z Marianem Rejewskim na czele, złamali kod Enigmy miesiąc przed dojściem Hitlera do władzy.

Teoria złożoności obliczeniowej

Teoria złożoność algorytmów jest bardzo specyficznym działem teorii liczbowej. Określa ilość potrzebnych zasobów do rozwiązania problemów obliczeniowych. Algorytmy wykorzystywane do tworzenia różnego rodzaju oprogramowania użytkowego muszą być jak najszybsze i wydajniejsze. Wynik działania instrukcji zależny jest od ilości danych wejściowych. W tym dziale porównamy kilka przykładów złożoności czasowej dla poszczególnych wielkości danych wejściowych. Przywołując algorytm Euklidesa z poprzedniego działu, została określona następująca złożoność obliczeniowa: dla dowolnych liczb m > n >= 0 algorytm Euklidesa zwraca wartość NWD(m, n) po co najwyżej...

$$ 2*log_2(m+n)$$

...przebiegach pętli. Poniżej zostały zestawione wykresy złożoności czasowej dla danych wejściowych wpisanych przez użytkownika. Na wykresie najlepiej uda się porównać ze sobą złożoności i zobaczyć, że dla coraz większej ilości danych, wartości tych funkcji zaczynają się znacznie różnić.

  Klikając na poszczególne wzory podane w legendzie można włączyć lub wyłączyć dany wykres.

  Wpisz dowolną liczbę (z przedziału od 0 do 1023) danych wejściowych w rubryce "n", po czym kliknij "Wykonaj".

$$n\ -\ liczba\ danych\ wejściowych\\ x\ -\ stała\ większa\ od\ 2$$

Złożoność stała - algorytm wykonuje się w stałej ilości operacji, niezależnie od liczby danych wejściowych. Jest uważana za najszybszą złożoność.

$$ O(1) $$

Złożoność logarytmiczna - algorytm wykonuje logarytmiczną ilość operacji w stosunku do liczby danych wejściowych. Podstawą logarytmu zazwyczaj jest liczba 2.

$$ O(log_2 (n)) $$

Złożoność liniowa - algorytm wykonuje wprost proporcjonalną ilość operacji w stosunku do liczby danych wejściowych.

$$ O(n) $$

Złożoność liniowo-logarytmiczna - mimo większej złożoności w stosunku do powyższych przykładów nadal zapisuje się do kategorii szybkich.

$$ O(n*log_2 (n)) $$

Złożoność kwadratowa - ilość operacji algorytmu jest wprost proporcjonalna do liczby danych wejściowych podniesionej do potęgi drugiej. Zaliczamy go do kategorii niezbyt szybkich.

$$ O(n^2) $$

Złożoność wielomianowa - ilość operacji algorytmu jest wprost proporcjonalna do liczby danych wejściowych podniesionej do potęgi x. Niepożądana złożoność.

$$ O(n^x) $$

Złożoność wykładnicza - ilość operacji algorytmu jest wprost proporcjonalna do stałej x większej lub równej 2, podniesionej do potęgi równej liczbie danych wejściowych. Niepożądana złożoność.

$$ O(x^n) $$

W tym miejscu należy wspomnieć o użytecznym wykorzystaniu złożoności pesymistycznej. Do zaszyfrowania wiadomości służą nam algorytmy, których złamanie stanowi ogromne wyzwanie nawet dla najszybszych komputerów. Faktoryzacja, czyli rozkład liczby na czynniki pierwsze i wszystkie stworzone jej implementacje działają w czasie wykładniczym wobec rozkładanej liczby. Można zatem stwierdzić, że proces rozkładania kilkuset cyfrowych liczb jest niemożliwy. Mnożenie dwóch kilkusetcyfrowych liczb trwa ułamki sekund, gdzie faktoryzacja może zająć tysiące lat. Jest to dla nas kluczowa informacja, ponieważ na wykładniczej (najbardziej pesymistycznej) złożoności obliczeniowej opiera się kryptosystem RSA (o którym będzie mowa w ostatnim rozdziale).

Funkcja Eulera

Autorem omawianej funkcji jest żyjący w XVIII w. szwajcarski matematyk i fizyk - Leonhard Euler. Uważany jest za jednego z najbardziej produktywnych matematyków w historii. Jego praca wniosła wiele w rozwój analizy matematycznej oraz terminologii i notacji matematycznej. Przejdźmy do omówienia samego zagadnienia. Funckja Eulera ("Funkja φ") bada ile jest liczb całkowitych mniejszych lub równych N nie mających z nią wspólnych dzielników. Swoje zastosowanie odnajduje w kryptografii w badaniach nad złożonością szyfrów. Funkcja Eulera dana jest dla każdej liczby naturalnej 'n' wzorem:

$$ \varphi (n) = n\left( 1 - \frac{1}{P_1}\right)\left( 1 - \frac{1}{P_2}\right)\left( 1 - \frac{1}{P_3}\right)\cdots\left( 1 - \frac{1}{P_k}\right)$$

Przeanalizujmy przykład dla n = 16. Na początku musimy rozłożyć naszą liczbę na czynniki pierwsze. Dla małych liczb, proces ten nie będzie skomplikowany. A zatem 16 dzielimy przez liczbę 2 cztery razy. Następnie podstawiamy do wzoru każdy z powtarzających się dzielników tylko raz. W naszym przypadku pod P1 podstawimy 2 tylko raz.

$$ \begin{align} 16 \div 2 & = 8 \\ 8 \div 2 & = 4 \\ 4 \div 2 & = 2 \\ 2 \div 2 & = 1 \end{align} $$

$$ \varphi (16) = 16*\left( 1 - \frac{1}{2}\right) = 16 *\left(\frac{1}{2}\right) = 8 $$

Obliczanie funkcji fi jest trudne dla ogromnych liczb oprócz liczb pierwszych. Euler doszedł do następującego wniosku: aby znaleźć wartość funkcji φ dla każdej liczby pierwszej P, liczymy P-1. Wyprowadźmy ten wzór i wykonajmy przykład.

$$ \begin{align} \varphi (p) & = p\left(1 - \frac{1}{p}\right) \\ \varphi (p) & = p\left(\frac{p}{p} - \frac{1}{p}\right) \\ \varphi (p) & = p\left(\frac{p - 1}{p}\right) \\ \varphi (p) & = p - 1 \end{align} $$

$$ np. \ \varphi (13) = 13 - 1 = 12 $$

  Niebieskie punkty są wartościami funkcji dla argumentów będącymi liczbami pierwszymi.

$$ \varphi (n), \ dla \ n \ \in <1, 100> $$

Wartą zapamiętania zależnością funkcji Eulera jest multiplikatywność. Swoje zastosowanie znajdzie podczas omawiania działania algorytmu szyfrującego RSA.

$$ \begin{align} a \ i \ b & - liczby \ pierwsze \\\\ n & = a * b \\\\ \varphi(a*b) & = \varphi(a) * \varphi(b) \\\\ \varphi(n) & = (a - 1) * (b - 1) \end{align}$$

Arytmetyka modularna

Po II wojnie światowej przemysł komputerowy zaczął być coraz istotniejszy w dziale bezpieczeństwa. Państwa starały się półautomatyzować swoje systemy do sterowania rakietami z głowicami jądrowymi. Pomysł łączenia komputerów do szybkiego przesyłania informacji rozprzestrzeniał się coraz bardziej niosąc tym samym narastający problem. Wprowadzenie przelewów pieniężnych między dwiema osobami był jednym z wielu oczywistych powodów do stworzenia systemów kryptograficznych.

W 1976 roku Whitfield Diffie i Martin E. Hellman w opublikowanej pracy "New Directions in Cryptography" opisali pomysł do uzgadniania wspólnego klucza między dwiema stronami, które się nie znają. Komunikacja była tajna i nikt nie mógł przechwycić uzgodnionego klucza, ponieważ technika opierała się na funkcji jednokierunkowej. Procedura jest łatwa do przeprowadzona w pierwszą stroną i trudna w drugą. Możliwość odwrócenia funkcji zaistnieje, jeśli będziemy posiadać informację zwaną kluczem lub zapadką. Dla ogromnych, nawet kilkuset cyfrowych liczb, połączona moc obliczeniowa najszybszych komputerów na świecie nie jest w stanie odwrócić tego działania. Oryginalna wersja wykorzystuje arytmetykę multiplikatywnych grup modulo p, gdzie p jest liczbą pierwszą, a g pierwiastkiem pierwotnym modulo p. Przeanalizujmy najpierw przykład z kolorami, aby wstępnie przybliżyć jego działanie.

Prywatny kolor pierwszej osoby

Prywatny kolor drugiej osoby

Publiczny kolor

Mieszanina koloru prywatnego 1. osoby z kolorem publicznym

Mieszanina koloru prywatnego 2. osoby z kolorem publicznym

Mieszanina koloru prywatnego 1. osoby z mieszaniną osoby 2.

Mieszanina koloru prywatnego 2. osoby z mieszaniną osoby 1.

Przykład z kolorami był tylko wstępem, aby zrozumieć mechanikę protokołu. Teraz przedstawię jak wygląda procedura numeryczna oparta na arytmetyce modularnej.

  Ogólny sposób postępowania.

Krok 1.   Wygenerowanie liczby pierwszej (p) i generatora (q), który jest pierwiastkiem pierwotnym z naszej liczby pierwszej.

Krok 2.   Losowanie prywatnej liczby osoby pierwszej (P1) i prywatnej liczby osoby drugiej (P2).

Krok 3.   Wysłanie publicznie drugiej osobie wyniku obliczeń pierwszej osoby.

$$ q^{P_1} \mod p \equiv c_1 $$

Krok 4.   Wysłanie publicznie pierwszej osobie wyniku obliczeń drugiej osoby.

$$ q^{P_2} \mod p \equiv c_2 $$

Krok 5.   Obliczenie wspólnego, tajnego klucza (s) przez obie osoby.

$$ c_2^{P_1} \mod p \equiv s $$

$$ c_1^{P_2} \mod p \equiv s $$

RSA

Algorytmy teorioliczbowe wykorzystywane są współcześnie do systemów kryptograficznych. Codziennie są wysyłane miliardy maili czy wykonywanych przelewów bankowych. Nie dostrzegamy tego, a w rzeczywistości o pewne i pomyślne zakończenie operacji dbają kryptosystemy, które są trudne do złamania. Jednym z najlepszych przykładów jest RSA. Szyfr RSA to najczęściej używany asymetryczny algorytm z kluczem publicznym. W szyfrach asymetrycznych używa sie dwóch kluczy - publicznego do zaszyfrowania wiadomości i prywatnego do odszyfrowania. Jego siła opiera się na trudności rozkładania ogromnych liczb na czynniki pierwsze. W 1973 roku brytyjski matematyk Clifford Cocks opracował pomysłowe rozwiązanie będące powiązaniem potęgowania modularnego oraz teorii Eulera. Daje nam ono wzór, z którego łatwo odszyfrujemy wysłaną wiadomość posiadając odpowiednie dane. Podsłuchiwacz, który posiada publiczenie wysyłane dane, nie jest w stanie odnaleźć zaszyfrowanego m, czyli oryginalnej wiadomości. Jak wspomniałem w dziale o złożoności obliczeniowej, złożoność wielomianowa dla dostatecznie dużych liczb będzie trwała setki lat. Można zaznaczyć, że dotychczas najdłuży rozłożony na czynniki pierwsze klucz jest 768-bitowy. Nastąpiło to 12 grudnia 2009 roku, a informacje o operacji opublikowano niecały miesiąc później. Współczesne systemy banków przeważnie posiadają klucze o długości 1024-bitów. Trzeba wspomnieć, że posiadanie rozkładu publicznie wysłanej liczby na czynniki pierwsze jest jedyną metodą odszyfrowania wiadomości przez niepożądane osoby.

Metoda wyznaczania kluczy została utajniona po publikacji, lecz w 1979 odkryli ją Ron Rivest, Adi Shamir oraz Leonard Adleman. Od akronimów ich nazwisk powstała nazwa algorytmu RSA. Sprawdźmy jak Clifford Cocks powiązał wszystkie elementy opisane powyżej.

Aby zaszyfrować wiadomość należy podnieść liczbę m do potęgi e, gdzie e jest publicznym wykładnikiem, liczbą nieparzystą oraz nie posiadającą wspólnych dzielników z φ(n). Następnie dzielimy przez losową liczbę n. Wynikiem jest liczba c. Zasada ta pojawiła się w dziale o arytmetyce modularnej.

$$ m^e\mod n \equiv c $$

W odwrotną stronę, jeśli znamy zaszyfrowaną wiadomość c, dzielnik n i liczbę szyfrujacą e, znalezienie m staje się niemożliwe. Dochodzimy do wniosku, że takie równanie staje się zamkiem, który chroni naszą wiadomość. Aby odszyfrować wiadomość m musimy obliczyć wykładnik d, który jest liczbą deszyfrującą. Przyrównując te dwa wzory uzyskujemy zależność.

$$ \begin{align} m^e\mod n & \equiv c \\ c^d\mod n & \equiv m \\ m^{e^{d}}\mod n & \equiv m \\ m^{e*d}\mod n & \equiv m \\ \end{align} $$

Aby wygenerować liczbę deszyfrującą (d) musimy odwołać się do twierdzenia Euklidesa, które dowodzi, iż każda liczba ma dokładnie jeden rozkład na czynniki pierwsze. Kolejnym elementem, którego użył Cocks było pomnożenie dwóch losowych liczb pierwszych. W tym miejscu matematyk skorzystał z funkcji i teorii Eulera znajdującego się poniżej. Etapy przekształceń: Podniesienie obu stron do potęgi k. Po prawej stronie nie nastąpi zmiania, ponieważ 1^k = 1. Pomnożenie obu stron przez m. Jedno m przechodzi do wykładnika jako 1. Porównanie ze wzorem na szyfrowanie wiadomości m. Ostateczne wyznaczenie d.

$$ m^{\varphi(n)} \equiv 1\mod n \ - \ twierdzenie \ Eulera $$

$$ \begin{align} m^{k* \varphi(n)} & \equiv 1 \mod n \\\\ m*m ^ {k * \varphi (n)} & \equiv m\mod n \\\\ m^ {k * \varphi (n) + 1} & \equiv m\mod n \\\\ m^{e*d} & \equiv m\mod n \\\\ ed & = k * \varphi(n) + 1 \\\\ d & = \frac {k * \varphi (n) + 1}{e} \end{align} $$

Mając pełny zbiór potrzebnych, wytłumaczonych i wyprowadzonych wzorów, przejdźmy do omówienia przykładu działania algoytmu RSA.

Etap 1. Wygenerowanie liczb pierwszych P1 i P2.
Etap 2. Obliczenie n i φ(n).
Etap 3. Wygenerowanie e.
Etap 4. Obliczenie klucza deszyfrującego d.

$$ \begin{align} P_1 & = 31 \\ P_2 & = 37 \\ n & = 1147 \\ \varphi (1147) & = 1080 \\ e & = 7 \\ d & = \frac {3 * 1080 + 1}{7} = 463 \end{align} $$

Etap 5. Odebranie publicznie wysłanego n i e od pierwszej osoby.
Etap 6. Zamiana wiadomości m na liczbę i zaszyfrowanie jej.
Etap 7. Wysłanie zaszyfrowanej wiadomości c do pierwszej osoby.

$$ \begin{align} m^e\mod n & \equiv c \\ m & = 89 \\ 89^7\mod 1147 & \equiv c \\ c & = 294 \end{align} $$

Etap 8. Odszyfrowanie wiadomości m przez pierwszą osobę.

$$ \begin{align} c^d \mod n & \equiv m \\ 294 ^ {463} \mod 1147 & \equiv m \\ m & = 89 \end{align} $$

  Sprawdź, jaki kod ASCII przypada poszczególnym literom. Kliknij generuj, aby wygenerować 'e', 'd' oraz 'n'.
Wpisując w pola wykładnik szyfrujący 'e', moduł 'n' i literę w postaci kodu ASCII, możemy zaszyfrować widomość.
Wpisując w pola wykładnik deszyfrujący 'd', moduł 'n' i poprzednio zaszyfrowaną literę, możemy odszyfrować widomość.

Podsumowanie

Dziękuję za zapoznanie się z treścią strony.
Mam nadzieję, że moja praca była ciekawa i w sposób przejrzysty przedstawiła twierdzenia, i zagadnienia metematyczne związane z kryptologią. Włożyłem ogrom pracy w przygotowanie tego kontentu, jednakże wiele godzin spędzonych na planowaniu i pisaniu kodu sprawiło mi wiele przyjemności oraz wzbogaciło mnie o nowe doświadczenie.
Pozdrawiam serdecznie,
Sebastian Urwan

Użyte oprogramowanie i technologie:

  · HTML
  · CSS3
  · JavaScript
  · Bootstrap 3
  · MathJax
  · Animate.css
  · jQuerry
  · Chart.js
  · Brackets
  · Gimp
  · GeoGebra
  · InkScape

Źródła:

  · www.it-szkola.edu.pl
  · www.youtube.com/user/MiroslawZelent
  · www.khanacademy.org
  · www.wikipedia.org
  · www.math.edu.pl
  · www.cpp0x.pl
  · Encyklopedia "EUREKA"
  · "Wprowadzenie do algorytmów" Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
  · Zdjęcie - Euklides (link)
  · Zdjęcie - Leonhard Euler (link)
  · Zdjęcie - Whitfield Diffie i Martin E. Hellman (link)
  · Zdjęcie - Clifford Cocks (link)
  · Zdjęcie - Adi Shamir, Ron Rivest i Leonard Adleman (link)

Informacje dodatkowe:

  · Strona powstała na 9. edycję konkursu "Zobaczyć Matematykę".
  · Czcionki pochodzą ze strony fonts.google.com
  · Obrazki na stronie tytułowej i stopce są darmowe oraz pochodzą z dodatku do czasopisma "Komputer Świat".
  · Pozostałe grafiki są mojego autorstwa.
  · Do prawidłowego wyświetlania strony potrzebne jest połączenie z internetem.
  · Wykorzystany skrypt Chart.min.js opiera się na licencji MIT
  · Wykorzystany plik animate.css opiera się na licencji MIT
  · Testowanie strony odbyło się na przeglądarkach: Google Chrome wersja 55.0.2883.87 m; Firefox wersja 50.1.0; Opera wersja 42.0.2393.94

Copyright © 2016/2017 · Sebastian Urwan