O kryptografii słów kilka

Michał ‘mina86’ Nazarewicz | 12 lutego 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
ity fragment niezaszyfrowanej wiadomości (niektóre algorytmy wymagają podzielenia wiadomości na części przed zaszyfrowaniem)
C
zaszyfrowana wiadomość
ci
ity fragment zaszyfrowanej wiadomości
E()
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:

  1. serwer losuje sobie jakąś liczbę n,
  2. szyfruje ją kluczem publicznym (C = E( n, kpub )),
  3. zaszyfrowaną liczbę wysyła klientowi,
  4. klient deszyfruje liczbę kluczem prywatnym (m = D( C, kpriv )),
  5. wysyła otrzymaną liczbę serwerowi,
  6. 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 (aka podpisie elektronicznym, aka e-podpisie). Tuż przed wysłaniem wiadomości, zostaje wyliczony jej hash (aka 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…