Zastosowanie współczesnej matematyki w kryptografii z kluczem jawnym.doc

30

„Zastosowanie współczesnej matematyki

w kryptografii z kluczem jawnym”

Spis treści

Wstęp ......................................................................................................................  3

Rozdział 1 Elementy teorii złożoności obliczeniowej.............................................  6

-         Złożoność obliczeniowa algorytmów ..........................................................  6

-         Klasy problemów P i NP .............................................................................  8

-         Problem łamania dla kryptosystemu z kluczem jawnym ............................. 11

-         Funkcje jednokierunkowe ........................................................................... 12

Rozdział 2 Elementy algebry i teorii liczb ............................................................ 15

-         Algorytm Euklidesa .................................................................................... 15

-         Rozkład kanoniczny liczb naturalnych ....................................................... 16

-         Kongruencje ................................................................................................ 17

-         Pierwiastki kwadratowe modulo n .............................................................. 20

-         Generatory grup multiplikatywnych ........................................................... 21

-         Testy pierwszości ........................................................................................ 24

-         Test Fermata ..................................................................................... 24

-         Test Millera – Rabina ....................................................................... 26

Rozdział 3 Protokoły szyfrujące ........................................................................... 28

-         Podstawowe własności protokołów szyfrujących ....................................... 28

-         Kryptosystem RSA ...................................................................................... 28

-         Kryptosystem ElGamala .............................................................................. 32

Rozdział 4 Podpisy cyfrowe .................................................................................. 34

-         Funkcje skrótu ............................................................................................. 34

-         Funkcja Chaum-van Heijst-Pfitzmann ............................................. 35

-         Ataki przeciwko funkcjom skrótu .................................................... 37

-         Podstawowe własności podpisów cyfrowych ............................................. 39

-         Algorytm DSA ............................................................................................ 40

-         „Ślepe” podpisy .......................................................................................... 41

Rozdział 5 Zastosowanie krzywych eliptycznych w kryptografii .......................... 42

-         Równanie krzywej eliptycznej ..................................................................... 42

-         Reguła dodawania punktów krzywej eliptycznej ........................................ 44

-         Protokół Diffiego-Hellmana ........................................................................ 49

Bibliografia ............................................................................................................ 51

Wstęp

Kryptografia oznacza ogół zagadnień związanych z bezpieczeństwem informacji w trakcie ich przesyłania i przechowywania.

Kryptosystemem nazywamy odwzorowanie, które jednostkom tekstu jawnego (szyfrowanej wiadomości) przyporządkowuje jednostki tekstu zakodowanego (szyfrogramu). Pierwszy kryptosystem powstał już w starożytnym Rzymie za czasów Juliusza Cezara (stąd jego nazwa – szyfr Cezara). Oczywiście był on bardzo prymitywny, jednak jego udoskonalone odmiany były stosowane jeszcze w pierwszej połowie XX wieku. Przez wiele stuleci korzystano z różnych kryptosystemów. Do ich konstruowania rzadko jednak używano osiągnięć matematyki. Jeszcze w połowie XX wieku do tego celu wykorzystywano zaledwie elementarną algebrę i teorię liczb [1]. Dopiero pojawienie się kryptosystemów z kluczem publicznym (jawnym) pozwoliło zastosować od dawna znane teorie matematyczne, które wcześniej wydawały się bezużyteczne.

Do połowy lat siedemdziesiątych ubiegłego wieku w celu szyfrowania danych używano kryptosystemów z kluczem tajnym (kryptosystemów symetrycznych). W tym przypadku zarówno nadawca wiadomości jak i jej odbiorca powinni znać pewne sekretne klucze, które umożliwiają kodowanie/dekodowanie informacji. Przed rozpoczęciem korespondencji trzeba więc dokonać bezpiecznej wymiany tajnych kluczy, które nie mogą dostać się w niepowołane ręce.

W 1976 roku W. Diffie i M. E. Hellman wynaleźli całkiem nowy system szyfrowania oparty na kluczach publicznych (kryptosystem asymetryczny), w którym do szyfrowania wiadomości zastosowana została tzw. funkcja jednokierunkowa. W kryptosystemach asymetrycznych wymiana kluczy nie jest konieczna, ponieważ jeden z nich może być jawny. Był to początek nowoczesnej kryptografii.

Nasuwa się jednak pytanie: dlaczego kryptosystemy asymetryczne powstały dopiero w 1976 roku?  Można podać dwa powody:

1)      Wcześniej nie było potrzeby korzystania z kluczy jawnych – kryptografii używano prawie wyłącznie do celów wojskowych i dyplomatycznych a w tym przypadku doskonale nadawały się kryptosystemy z kluczem tajnym.

2)      Brak możliwości wykonywania skomplikowanych obliczeń na bardzo dużych liczbach.

Wielkie znaczenie kryptografii z kluczem publicznym wiąże się z rozprzestrzenieniem się potężnej techniki komputerowej.

Oczywiście współczesnej kryptografii nie stosuje się wyłącznie do szyfrowania wiadomości. Oto jej główne zastosowania:

1)     poufny przekaz informacji (kodowanie/dekodowanie wiadomości),

2)     podpis cyfrowy,

3)     uwierzytelnienie (potwierdzanie tożsamości),

4)     bezpieczna wymiana tajnych kluczy (np. poprzez jawny kanał informacyjny),

5)     zobowiązanie bitowe (tzw. rzut monetą na odległość),

6)     dzielenie sekretów,

7)     dowody interakcyjne i dowody z wiedzą zerową (np. ktoś chce kogoś przekonać, że rozwiązał pewne trudne zadanie nie zdradzając informacji o sposobie jego rozwiązania).

Powyższe problemy rozwiązuje się za pomocą tzw. protokołów (procedur ustalających kolejność komunikacji poszczególnych osób uczestniczących w wymianie informacji).

Celem niniejszej pracy jest matematyczne uzasadnienie niektórych ważnych z praktycznego punktu widzenia algorytmów kryptograficznych. W rozdziale 1 przedstawione są (w sposób nieformalny) elementy teorii złożoności obliczeniowej, która jest niezbędna między innymi dla precyzyjnego zdefiniowania funkcji jednokierunkowych. Rozdział 2 zawiera wybrane zagadnienia algebry i teorii liczb użyteczne w kryptografii z kluczem jawnym. W rozdziale 3 znajduje się opis i uzasadnienie matematyczne dwóch stosowanych w praktyce asymetrycznych kryptosystemów szyfrujących – RSA i algorytmu ElGamala.  Następnie w rozdziale 4 poruszona jest problematyka podpisu cyfrowego. Wreszcie w rozdziale 5 znajdują się podstawowe wiadomości o krzywych eliptycznych i ich zastosowaniu w kryptografii.

Rozdział 1

Elementy teorii złożoności obliczeniowej

Złożoność obliczeniowa algorytmów

Złożoność obliczeniową dowolnego algorytmu charakteryzują dwie funkcje: T(n) i S(n), gdzie argument n oznacza długość danych wejściowych - ilość bitów potrzebnych do ich zapisania (jeżeli x jest pewną daną, to jej długość oznaczamy |x|). T(n) określa złożoność czasową algorytmu (ilość wykonywanych operacji), natomiast S(n) złożoność przestrzenną (ilość potrzebnych do obliczeń komórek pamięci). Wielkości te mogą być wyrażane za pomocą następującej notacji „O”.

Definicja 1.1

Załóżmy, że dla wszystkich argumentów n większych od pewnego n0 funkcje f(n) i g(n) są określone, przyjmują wartości dodatnie i dla pewnej stałej cÎR zachodzi  f(n) £ c×g(n). Wówczas oznaczamy f = O(g).

Dużą zaletą wyznaczania w ten sposób złożoności czasowej jest uniezależnienie wyniku od szybkości maszyny, na którym badany algorytm jest wykonywany. Dla algorytmów o dużej złożoności obliczeniowej (a takie występują w kryptografii) przestają być istotne parametry techniczne komputera. Wtedy ogromne znaczenie ma rząd wielkości złożoności obliczeniowej algorytmu.

Algorytmy można sklasyfikować w zależności od ich złożoności czasowej lub przestrzennej. Tabela 1.0 przedstawia kilka przykładowych klas algorytmów oraz dla porównania czasy obliczeń dla danych długości jednego miliona bitów, przy założeniu że jedna operacja wykonywana jest w 10–6 sekundy [6].

Tabela 1.1