WY3.DOC

LITERATURA

1.       Denning D. Kryptografia i ochrona danych, Wydawnictwa Naukowo-Techniczne, Warszawa, 1992.

2.       Koblitz N. Wykład z teorii liczb i kryptografii, Wydawnictwa Naukowo-Techniczne, Warszawa, 1995.

3.       Koblitz N. Algebraiczne aspekty kryptografii, Wydawnictwa Naukowo-Techniczne, Warszawa, 2000.

4.       Kutyłowski M, Strothmann W. Kryptografia. Teoria i praktyka zabezpieczania systemów komputerowych, Wydawnictwa Read Me, Warszawa, 1999.

5.       Welschenbach M. Cryptography in C and C++, Wydawnictwa Apress L.P., 2001.

6.       www.accessdata.com

7.       www.password-crackers.com/crack.html

8.       www.10pht.com/10phtcrack

TERMINOLOGIA

Najważniejsze pole zainteresowań kryptografii to szyfrowanie dokumentów i danych. Kryptografia udostępnia narzędzia, które stosowane w sposób rozważny i z pełną świadomością ich ewentualnych słabości chronią skutecznie gromadzone i przesyłane dane. Narzędzia te obejmują szyfry służące zapewnianiu poufności danych, funkcje skrótu stosowane dla weryfikacji integralności danych, podpisy cyfrowe, protokoły uwierzytelniania i protokoły zarządzania kluczami. Z oryginalnego dokumentu (może to być tekst, zakodowany cyfrowo obraz albo sygnał dźwiękowy ) zwanego tekstem jawnym (otwartym) można utworzyć zaszyfrowaną wersję, którą nazywamy kryptogramem (szyfrogramem). Tekst jawny zawiera (na przykład):

Alfabet - - 32 litery alfabety polskiego i odstęp

Alfabet binarny -

Alfabet - - symboli  ASCII

Alfabet - - 26 liter alfabety łacińskiego bez dodatkowych symboli dla znaków interpunkcyjnych, cyfr, dużych liter itp.

Do zaszyfrowania i deszyfrowania potrzebny jest dodatkowo klucz lub klucze (Rys. 1).

Rys. 1

Algorytm szyfrowania i deszyfrowania stanowi kryptosystem czyli szyfr. Przykłady:

Szyfr Cezara (100-44 r. do n.e.). Litery alfabetu można utożsamić z liczbami. W systemie Cezara używanych jest 26 symboli (26 liter alfabetu łacińskiego) odpowiadających liczbom od 0 d0 25. Szyfr polega na permutacji: 0 (a) ® 3 (d); 1 (b) ® 4 (e); 2 (c) ® 5 (f);...; 25 (z) ® 2 (c). Oznacza to, że w szyfrogramie zastępujemy każdą literę tekstu literą położoną w alfabecie o trzy pozycje dalej. Mówiąc współczesnym językiem Rzymianie używali operacji dodawania 3 modulo 26 : . Dla przykłady słowu imperium odpowiada kryptogram lpshulxp albo teksty Veni vidi vici odpowiada kryptogram yhql  ylgl  ylfl.

Szyfr częstokołu: Np. słowo kryptografia zapisujemy w postaci i otrzymujemy kryptogram rporfakytgai .Tutaj wysokość częstokołu równa 2. Dla wysokości 3 mamy: i otrzymujemy kryptogram ygirporfakta. Długość permutacji albo wysokość częstokołu jest kluczem szyfrowania i deszyfrowania.

Tekst jawny P zaszyfrowany za pomocą klucza K oznaczać będziemy , tekst jawny uzyskany z kryptogramu C za pomocą klucza K oznaczać będziemy . Notacja ta zakłada, że wiemy, jaką metodę szyfrowania lub deszyfrowania mamy na myśli.

Ze względu na własności kluczy jest dwie metody szyfrowania:

Algorytmy symetryczne: klucz do szyfrowania oraz do deszyfrowania jest ten sam (Rys. 2):

Rys. 2

Algorytmy asymetryczne: (algorytmy z kluczem jawnym lub kluczem publicznym) klucze do szyfrowania i deszyfrowania są różne; praktycznie nie powinno być możliwe wyprowadzenie z jednego z nich drugiego.

WPROWADZENIE

Niech A oraz B będą alfabetami skończonymi. Zauważmy, że każdy alfabet można zakodować korzystając z alfabetu binarnego {0,1}. W tym rozdziale symbolem Å ozna­czamy sumę modulo 2 odpowiednich bitów, a symbolem v\\w konkatenację słów (bloków) v i w o tej samej długości.

Niech M oznacza zbiór nazywany zbiorem wiadomości jawnych, a C - zbiór zwany zbiorem wiadomości tajnych. Zbiór M składa się z symboli o skończonej długości wziętych z pewnego alfabetu A. Zbiór C składa się z symboli o skończonej długości z pewnego alfabetu B. Dowolny element mÎM nazywa się wiadomością jawną, a dowolny element cÎC nazywa się wiadomością tajną (wiadomością zaszyfrowaną, szyfrogramem). Jeśli M (odpowiednio C) składa się z wiadomości o ustalonej długości wyrażonej w bitach, powiedzmy o długości r>0, to taki zbiór oznaczamy przez M(r) (odpowiednio C(r)).

Niech K oznacza zbiór kluczy kryptograficznych. Dowolny element kÎK nazywa­my kluczem kryptograficznym lub po prostu kluczem. Dla każdego klucza definiujemy funkcję (algorytm) Ek: M®C i funkcję (algorytm) Dk: C®M. Funkcję Ek nazywa się funkcją szyfrującą (algorytmem szyfrującym), a funkcję Dk, jeśli istnieje, to nazywa się funkcją deszyfrującą (algorytmem deszyfrującym).

Zbiór {Ek: M®C½kÎK} nazywa się schematem szyfrowania, a zbiór {Dk: C®M½ kÎK} schematem deszyfrowania, jeśli Dk = Ek-1.

Funkcję f: X®Y nazywa się jednokierunkową, jeśli dla wszystkich xÎX wy­znaczenie jej wartości f(x) jest łatwe (można to wykonać w czasie wielomianowym w sposób deterministyczny), natomiast jest trudne obliczeniowo (tj. możliwe do wyko­nania tylko w czasie wykładniczym w sposób deterministyczny) znalezienie xÎX, takiego że dla prawie wszystkich yÎY spełniona jest zależność f(x)=y.

Systemem szyfrowania nazywamy uporządkowaną parę:

SZYFR = ({Ek: M®C ½ kÎK}, {Dk*: C®M½ k*ÎK })

taką, że {Ek: M®C ½ kÎK } jest schematem szyfro­wania, a {Dk*: C®M ½ k*ÎK} jest schematem deszyfrowania, a ponadto Ek oraz Dk* są permutacjami. Jeśli M = C, to wówczas taki system szyfrowania nazywa się endomorficznym.

Jeśli k* = k lub k* ≠ k i jest obliczeniowo łatwe wyznaczenie klucza k* na podstawie znajomości klucza k, to taki system szyfrowania nazywamy symetrycznym. Natomiast jeśli k* ≠ k i jest trudne obliczeniowo wyznaczenie klucza k* na podstawie znajomości klucza k, to taki system szyfrowania nazywamy asymetrycznym (także systemem z kluczem publicznym); w takim systemie klucz k* nazywamy kluczem prywatnym, a klucz k - kluczem publicznym.

Symetryczny system szyfrowania BLOK = ({Ek: M(r) ®C(r) ½ k Î K(s)}, {Dk*(r): C(r) ®M(r) ½ k*ÎK(r)}) nazywamy szyfrem blokowym. Przetwarzane bloki mają długość r bitów, a stosowane klucze kryptograficzne - s bitów. Zatem dla każdego klucza k i wiadomości m1½½ m2½½...½½mt złożonej z t bloków, każdy o długości r bitów, spełniona jest równość

...