Rozdział Elementy teorii złożoności



Pobieranie 1,74 Mb.
Strona1/19
Data23.02.2018
Rozmiar1,74 Mb.
  1   2   3   4   5   6   7   8   9   ...   19




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),




  1. podpis cyfrowy,




  1. uwierzytelnienie (potwierdzanie tożsamości),




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




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




  1. dzielenie sekretów,




  1. 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).



    1. 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).

    2. 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.













  1   2   3   4   5   6   7   8   9   ...   19


©operacji.org 2017
wyślij wiadomość

    Strona główna