Metody kryptograficzne stosowane w PKI

Daniel Rychcik
14-04-2001

0. Wstęp

Dokument ten opisuje zasady działania podstawowych metod kryptograficznych stosowanych w obrębie protokołu SSL i infrastruktury kluczy publicznych (PKI)

1. Kryptografia kluczy prywatnych

Ten sposób szyfrowania danych (zwany również kryptografią symetryczną lub kryptografią z kluczem tajnym) znany jest od dawna. Najprostsze jego rodzaje to szyfry oparte o przestawianie liter według pewnego, z góry ustalonego schematu. Dane szyfrowane były w ten sposób już w starożytności - np. Juliusz Cezar używał szyfru opartego na tym schemacie do przekazywania rozkazów swoim odległym oddziałom.

Ogólny schemat wszystkich tego typu algorytmów jest następujący:

Strony uzgadniają klucz(e) służące do szyfrowania/deszyfrowania danych
(Najczęściej ten sam klucz służy zarówno do szyfrowania jak i deszyfrowania, ale nie jest to regułą)
W późniejszym czasie strony używają uzgodnionych kluczy do wymiany danych, ewentualnie zmieniając je co jakiś czas.

Bardziej zaawansowane szyfry symetryczne używane dzisiaj opierają się na manipulacji bitami danych. Najbardziej znany algorytm to DES używany m.in. do szyfrowania haseł w systemach UNIX-owych. Używa on skomplikowanych operacji na bitach danych, których kolejność i rodzaj zależy właśnie od bitów klucza. Inne znane algorytmy symetryczne to 3DES (mocniejsza wariacja DES), RC2 i RC4.

Największą zaletą algorytmów symetrycznych jest ich szybkość - odpowiednio stosowane, mogą tylko nieznacznie zmniejszać przepustowość kanału transmisyjnego.

2. Kryptografia kluczy publicznych

Odkrycia matematyczne drugiej połowy XX wieku umożliwiły powstanie kryptografii opartej o klucze publiczne. Podstawową wadą szyfrów symetrycznych jest bowiem konieczność uzgodnienia a priori tajnych kluczy używanych do wymiany danych. Często stawia to pod znakiem zapytania cały sens operacji, jeżeli np. strony znajdują się w dużym oddaleniu od siebie i potrzebują przesłać pilne dane.

Taka sytuacja wprowadzała poza tym problem związany z tajnością kluczy. Aby bowiem dwie strony mogły uzgodnić ze sobą tajne klucze, musiały najpierw przesłać je sobie drogą tajną - ale jak przesłać zaszyfrowane klucze nie mając kluczy używanych do szyfrowania ?...

Kryptografia kluczy publicznych zwana także kryptografią asymetryczną zakłada, że każda transmisja danych używa dwóch kluczy. Jeden z nich, klucz prywatny znany jest tylko jednej stronie, zaś drugi, klucz publiczny nie musi być tajny - jest on powszechnie dostępny i umożliwia przykładowo wysyłanie zaszyfrowanych informacji do właściciela klucza prywatnego.

Kryptografia asymetryczna ma tą własność, że cokolwiek zostało zaszyfrowane kluczem prywatnym może zostać odszyfrowane wyłącznie kluczem publicznym i odwrotnie: dane zaszyfrowane kluczem publicznym może odszyfrować tylko właściciel klucza prywatnego!

Matematyczne podstawy kryptografii asymetrycznej są oparte o "problemy asymetryczne", czyli takie, które jest o wiele łatwiej wymyśleć, niż rozwiązać. Typowy przykład to faktoryzacja liczb: łatwo jest pomnożyć przez siebie kilka liczb pierwszych, natomiast rozkład iloczynu na czynniki pierwsze jest już dużym problemem obliczeniowym. W przypadku naprawdę dużych liczb pierwszych problem jest praktycznie nierozwiązalny - właśnie taki schemat stosuje się w algorytmach asymetrycznych.

Najbardziej znany przykład algorytmu stosującego klucze publiczne to RSA stosowany np. w systemie bezpiecznej poczty PGP.

Jak widać kryptografia asymetryczna likwiduje wszystkie wady kryptografii symetrycznej. Jest to właściwie rozwiązania doskonałe, które ma tylko jedną wadę: szybkość. O ile algorytmy symetryczne (zwłaszcza blokow) doskonale nadają się do szyfrowania "w locie", lub nawet implementacji sprzętowej, to złożoność obliczeniowa szyfrowania/deszyfrowania danych z użyciem kluczy publicznych raczej wyklucza takie zastosowania.

Próbą połączenia najlepszych cech obydwu metod szyfrowania jest

3. Metoda mieszana

Kluczową obserwacją dla tej metody jest fakt, że niedogodność algorytmów symetrycznych nie polega na ich "słabości" - dobierając odpowiednio długi klucz możemy uzyskać zabezpieczenie właściwie dowolnie "silne". Problemem jest tylko uzgodnienie tych kluczy. Za to algorytmy symetryczne są o wiele szybsze.

Wymyślono więc następujący schemat bezpiecznego przesyłania danych:
(Zakładamy, że strony są już w posiadaniu swoich kluczy publicznych używanych w algorytmie asymetrycznym)

A generuje klucz K który będzie używany później przy przesyłaniu danych algorytmem symetrycznym
A wysyła klucz K do B szyfrując go kluczem publicznym B
B deszyfruje klucz K swoim kluczem prywatnym
Strony dalej komunikują się korzystając z szyfrowania symetrycznego z użyciem klucza K

Możliwe są różne wariacje tej metody umożliwiające na przykład:

Autentyfikację klienta/serwera:
Można to zrealizować na etapie nawiązywania połączenia - właściwie sytuacja jest tu taka, jakby używany był tylko algorytm asymetryczny.
Okresową wymianę kluczy
Strony mogą się umówić, że przykładowo co 15 minut niszczą i od nowa generują klucze symetryczne. Może to być ważne przy połączenia trwających wiele czasu i takich, po których przesyła się niewiele danych. Ktoś posiadający odpowiednio szybki komputer i będący w stanie podsłuchać szyfrowaną transmisję mógłby pokusić się wtedy o złamanie klucza.

4. Funkcje skrótu

Opisane dotąd metody działają lepiej lub gorzej w przypadku szyfrowania danych przesyłanych w sieci. Nie sprawdzają się jednak dobrze w sytuacji, w której mamy wygenerować tylko podpis pewnej porcji danych - konieczne jest w takiej sytuacji zaszyfrowanie całego dokumentu kluczem prywatnym, co jest operacją czasochłonną.

Aby temu zapobiec stosuje się funkcje skrótu (message digest). Działają one w ten sposób, że dla komunikatu o dużej długości liczona jest wartość (znacznie krótsza - coś na zasadzie sumy kontrolnej) pewnej funkcji i dopiero wynik tej funkcji jest szyfrowany przy użyciu algorytmu asymetrycznego.

Oczywiście nie można zagwarantować, że funkcja przekształcająca kilkunastoklilobajtowy komunikat w kilkudziesięciobajtowy skrót będzie różnowartościowa, jednak funkcje skrótu są tak dobrane, że prawdopodobieństwo przypadkowego skonstruowania dwóch komunikatów o tej samej wartości funkcji jest pomijalne.

5. Schematy stosowania algorytmów

W poniższych schematach będę stosował standardową konwencję stosowaną w książkach o kryptografii: ustalmy, że Alice i Bob to dwie osoby chcące się bezpiecznie komunikować, Charles zaś, to intruz chcący im w tym przeszkodzić.

5.1. Bezpieczne przesyłanie danych

Tu sytuacja jest klasyczna i najlepiej opisana. Załóżmy, że Alice chce przesłać poufne informacje do Boba i chce, żeby Charles nie mógł ich odczytać nawet, jeśli przechwyci wiadomość. Schemat postępowania jest następujący:

Bob generuje parę kluczy i umieszcza klucz publiczny w dostępnym miejscu
Alice pobiera klucz publiczny Boba
Alice szyfruje dane kluczem publicznym Boba i wysyła mu pocztą.
Dane są bezpieczne! Tylko Bob może je rozszyfrować (swoim kluczem prywatnym) - nawet Alice nie może tego zrobić, jeśli nie posiada oryginalnych danych! Zatem nawet jeżeli Charles będzie w stanie przechwycić list, to wiele się z niego nie dowie.

Oczywiście pojawia się pewien problem: skąd wiadomo, że Charles nie wygenerował sobie własnej pary kluczy, nie podpisał klucza publicznego jako "klucz Boba" i nie umieścił w publicznie dostępnym miejscu? Rozwiązaniem jest w tym momencie założenie, że Alice i Bob ufają pewnej ważnej instrytucji, która przechowuje klucze prywatne i zapewnia, że należą one rzeczywiście do tych osób, których imionami są podpisane.

(Ta instytucja to właśnie Certificate Authority z naszego projektu :-)

5.2. Podpisywanie wiadomości.

Załóżmy tym razem, że Alice chce przesłać Bobowi ważną informację, która co prawda nie musi pozostać tajna, ale ważne jest, aby Bob wiedział, że pochodzi rzeczywiście od Alice, a nie np. od Charlesa. Co robimy w takiej sytuacji? (zakładamy, że obie strony mają już swoje klucze publiczne)

Alice szyfruje komunikat swoim kluczem prywatnym
Bob deszyfruje otrzymany komunikat kluczem publicznym Alice
W tym momencie Bob ma pewność, że dane pochodzą od Alice - tylko ona mogła je zaszyfrować tak, że dały się odszyfrować jej kluczem publicznym!

Pewną wersją tej metody jest użycie funkcji skrótu. Schemat wygląda wtedy następująco:

Alice oblicza funkcję skrótu dla komunikatu
Alice szyfruje wynik swoim kluczem prywatnym i dołącza do przesyłki
Bob oblicza analogiczną funkcję skrótu dla przesyłki
Bob dekoduje załączony skrót kluczem publicznym Alice

kluczem publicznym Alice

Jeżeli wyniki się zgadzają, to Bob ma (prawie*) pewność, że dane pochodzą od Alice!

(*) prawie - ponieważ funkcja skrótu teoretycznie nie jest różnowartościowa. W praktyce jest to niewielki problem

Podpis cyfrowy dokonany tą drogą może być uważany za ekwiwalent podpisu "prawdziwego" - Alice nie może się wyprzeć, że podpisała wiadomość, ponieważ tylko właściciel jej klucza prywatnego mógł to zrobić!

Szczególnym przypadkiem podpisywania wiadomości jest

5.3. Autentyfikacja partnera

Polega ona na tym, że wysyłamy partnerowi krótki losowy komunikat i prosimy o podpisanie jego kluczem prywatnym. Jeżeli będziemy w stanie rozszyfrować odpowiedź jego kluczem publicznym (i wynik będzie zgodny z oryginałem), to znaczy, że autentyfikacja się powiodła.