O kryptografii słów kilka
Posted by Michał ‘mina86’ Nazarewicz on 12th of February 2008
Każdy człowiek ma jakieś tajemnice, których nie chce nikomu zdradzać. Równocześnie każdy ma sekrety, którymi chce się z kimś podzielić, ale tak, żeby nikt więcej ich nie poznał. Sytuacje takie mogą się zdarzać w codziennym życiu przeciętnego obywatela, w życiu dużej firmy lub całego państwa. Utrzymanie w tajemnicy pewnych tajemnic może się przyczynić do czyjegoś sukcesy lub porażki. Winston Churchill (1874-1965) przyznał, że złamanie kodów Enigmy przez trzech polskich matematyków (Mariana Rejewskiego (1905-1980), Jerzego Różyckiego (1906-1942) i Henryka Zygalskiego (1906-1978)) pozwoliło w znacznym stopniu skrócić czas wojny (i co za tym idzie, zmniejszyć liczbę ofiar).
Oznaczenia
W artykule tym (oraz kolejnych artykułach o kryptografii) będę używał następujących oznaczeń:
M
- niezaszyfrowana wiadomość
mi
i
ty fragment niezaszyfrowanej wiadomości (niektóre algorytmy wymagają podzielenia wiadomości na części przed zaszyfrowaniem)C
- zaszyfrowana wiadomość
ci
i
ty fragment zaszyfrowanej wiadomościE()
- funkcja szyfrująca
- jeżeli przyjmuje dwa parametry, to drugim parametrem jest klucz
D()
- funkcja deszyfrująca
- jeżeli przyjmuje dwa parametry, to drugim parametrem jest klucz
H()
- funkcja skrótu (tzw. hash)
- jeżeli przyjmuje dwa parametry, to drugim parametrem jest klucz
k
- klucz
kpub
- klucz publiczny
kpriv
- klucz prywatny
Zasada działania
Zasada działania szyfrowania jest bardzo prosta. Mamy dwie funkcje E()
i D()
, które spełniają następujący warunek: dla każdego M zachodzi M = D( E( M ) )
. W przypadku niektórych algorytmów D = E
, jednakże nie ma to istotnego znaczenia dla mocy szyfru. Jest to jedynie ułatwienie implementacji algorytmu, bo zamiast pisać dwie funkcję wystarczy napisać jedną, którą będzie można szyfrować i deszyfrować.
Szyfrowanie symetryczne
Przy takim zapisie widać, że wystarczy poznać funkcje deszyfrującą, żeby móc rozszyfrowywać zaszyfrowane wiadomości i żeby uniemożliwić to musielibyśmy zmieniać cały algorytm szyfrowania. Z tego powodu do algorytmów wprowadzono klucze, dzięki czemu jednym algorytmem można szyfrować na różne sposoby zależnie od klucza i równocześnie nie znając klucza nie da się wiadomości rozszyfrować. Algorytmy z kluczem powinny spełniać następujący warunek: dla każdego M, k1, k2 zachodzi: jeśli k1 = k2 to C = E(M, k1) = E(M, k2) i M = D(C, k1) = D(C, k2)
. Należy zauważyć, że warunkiem jest implikacja, ale kożystnie jest jeżeli zachodzi równoważność.
Przy takich założeniach algorytm szyfrowania może być znany każdemu, a jedynie klucz jest rzeczą, która nie może się dostać w niepowołane ręce. Szyfrowaniem, w którym ten sam klucz służy do szyfrowania i deszyfrowania wiadomości nazywamy szyfrowaniem symetrycznym i ma ono pewne wady.
Szyfrowanie asymetryczne
Problem jest taki, że jeżeli dwie osoby chcą bezpiecznie komunikować się ze sobą, to muszą ustalić jakiś klucz. Problem w tym, jak to zrobić żeby nikt inny go nie poznał. Nie dość, że zmniejsza to bezpieczeństwo to jeszcze wydłuża czas przekazywania informacji. Sytuacji, w których zwykłe szyfrowanie symetryczne nie wystarcza jest oczywiście więcej.
Na pomoc przychodzi nam szyfrowanie asymetryczne, które korzysta z pary kluczy, klucza publicznego (kpub
), który możemy dawać każdemu i da się nim jedynie szyfrować wiadomości; oraz z klucza prywatnego (kpriv
), który służy jedynie do rozszyfrowywania wiadomości i powinien być w posiadaniu tylko i wyłącznie jednej osoby. Bardziej matematycznie można zapisać, że szyfrowanie asymetryczne musi spełniać następujący warunek: dla każdego M, kpub, kpriv zachodzi jeśli kpub i kpriv stanowią parę to M = D( E( M, kpub ), kpriv)
.
Oczywiście algorytm szyfrowania asymetrycznego musi być tak obmyślony, żeby nie dało się odtworzyć klucza prywatnego na podstawie klucza publicznego. Gdyby było to możliwe, to algorytm straciłby cały swój sens.
Logowanie z kluczem
Algorytmy szyfrowania asymetrycznego mogą zostać wykorzystane w systemie logowania. Zapobiega to przesyłaniu hasła pomiędzy komputerami i właściwie uniemożliwia zalogowanie się bez znajomości klucza prywatnego. Proces logowania z kluczem wygląda następująco:
- serwer losuje sobie jakąś liczbę
n
, - szyfruje ją kluczem publicznym (
C = E( n, kpub )
), - zaszyfrowaną liczbę wysyła klientowi,
- klient deszyfruje liczbę kluczem prywatnym (
m = D( C, kpriv )
), - wysyła otrzymaną liczbę serwerowi,
- serwer porównuje obie liczby (wysłaną przez klienta i wylosowaną w pierwszym kroku) (
n =? m
):- jeśli obie liczby są równe, to logowanie się powiodło,
- jeśli są one różne, to logowanie się nie powiodło.
Podpis cyfrowy
Algorytmy szyfrowania asymetrycznego mogą dodatkowo spełniać jeszcze jeden warunek. Mianowicie: dla każdego M, kpub,kpriv zachodzi kpub i kpriv stanowią parę ⇒ M = D( E( M, kpriv ), kpub)
. Czyli, że szyfrując wiadomość kluczem prywatnym będzie można ją rozszyfrować kluczem publicznym. Własność taką posiada algorytm RSA i dzięki temu jest wykorzystywany w podpisie cyfrowym. Tuż przed wysłaniem wiadomości, zostaje wyliczony jej hash (lub bardziej po polsku skrót), który jest następnie szyfrowany przy użyciu klucza prywatnego (matematycznie jest to wynik operacji: ep = E( H(M), kpriv )
). Osoba, która odbiera wiadomość rozszyfrowuje tenże hash i porównuje go z hashem przez siebie wyliczonym. Jeżeli są one różne, wiadomość została zmodyfikowana po podpisaniu.
Hash
Przybliżmy więc pojęcie hasha. Jest to taka funkcja, która z łańcucha o dowolnej długości generuje łańcuch o określonej długości. Dodatkowo algorytm generowania tego hasha powinien być taki, że przy zmianie jednego bitu wiadomości hash się zmienia w dość dużym stopniu (tzn. każdy bit wiadomości wpływa na conajmniej kilka bitów hasha). Co więcej powinno być praktycznie niemożliwe stworzenie dwóch różnych łańcuchów o takim samym hashu.
Funkcja skróty jest często wykorzystywana w systemach logowania. Hasło użytkownika jest hashowane i w takiej postaci zapisywane. W momencie logowania oblicza się hash z podanego hasła i porównuje z zapisanym hashem (zapisany hash = H( podane hasło ) ⇒ użytkownik podał poprawne hasło
).
Trzeba pamiętać, że nieprawdą jest, iż dla każdego x, y zachodzi H( x ) = H( y ) ⇒ x = y
. Jednakże nieścisłość tą można bez żadnych obaw pominąć. Po prostu jeżeli chcemy mieć większą pewność to używamy innego algorytmu, np. zamiast MD5 to SHA1…