Krok 1: Alice przesyła do Boba swój klucz publiczny

Kroki 2 i 3: Bob szyfruje wiadomość kluczem publicznym Alice, która to następnie otrzymuje zaszyfrowaną wiadomość i rozszyfrowuje ją kluczem prywatnym

Kryptografia klucza publicznego (kryptografia asymetryczna) – rodzaj kryptografii, w którym jeden z używanych kluczy jest udostępniony publicznie. Każdy użytkownik może użyć tego klucza do zaszyfrowania wiadomości, ale tylko posiadacz drugiego, tajnego klucza może odszyfrować taką wiadomość. Istnieją również bardziej zaawansowane algorytmy wykorzystujące więcej kluczy i inne zależności między kluczami.

Kryptografia asymetryczna opiera się na funkcjach jednokierunkowych – takich, które da się łatwo wyliczyć w jedną stronę, ale bardzo trudno w drugą. Np. mnożenie jest łatwe, a rozkład na czynniki (z ang. faktoryzacja) trudny (na czym przykładowo opiera się RSA). Potęgowanie modulo jest łatwe, a logarytmowanie dyskretne jest trudne (na czym opierają się ElGamal, DSA i ECC).

Historia

Kryptografia asymetryczna została oficjalnie wynaleziona przez cywilnych badaczy Martina Hellmana, Whitfielda Diffie w 1976 roku. Prawie równolegle prototyp podobnego systemu stworzył Ralph Merkle – w 1974 roku zaproponował algorytm wymiany kluczy nazwany puzzlami Merkle’a^[1]. Dopiero pod koniec XX wieku brytyjska służba wywiadu elektronicznego GCHQ ujawniła, że pierwsza koncepcja systemu szyfrowania z kluczem publicznym została opracowana przez jej pracownika Jamesa Ellisa już w 1965 roku, a działający system stworzył w 1973 roku Clifford Cocks, również pracownik GCHQ^[2]. Odkrycia te były jednak objęte klauzulą tajności do 1997 roku. Obecnie kryptografia asymetryczna jest szeroko stosowana do wymiany informacji poprzez kanały o niskiej poufności, jak np. Internet. Stosowana jest także w systemach elektronicznego uwierzytelniania, obsługi podpisów cyfrowych, do szyfrowania poczty (OpenPGP) itd.

Szyfrowanie

Klucz publiczny używany jest do zaszyfrowania informacji, klucz prywatny do jej odczytu. Ponieważ klucz prywatny jest w wyłącznym posiadaniu adresata informacji, tylko on może ją odczytać. Natomiast klucz publiczny jest udostępniony każdemu, kto zechce zaszyfrować wiadomość.

Ponieważ kryptografia asymetryczna jest o wiele wolniejsza od symetrycznej, prawie nigdy nie szyfruje się wiadomości za pomocą kryptosystemów asymetrycznych. Zamiast tego szyfruje się jedynie klucz jakiegoś szyfru symetrycznego, takiego jak np. AES. Takie protokoły, łączące elementy kryptografii symetrycznej i asymetrycznej, nazywa się hybrydowymi.

Podpisy cyfrowe

Strona uwierzytelniająca wylicza skrót (ang. hash) podpisywanej wiadomości. Następnie szyfruje ten skrót swoim kluczem prywatnym i jako podpis cyfrowy dołącza do oryginalnej wiadomości. Dowolna osoba posiadająca klucz publiczny może sprawdzić autentyczność podpisu poprzez odszyfrowanie skrótu za pomocą klucza publicznego nadawcy i porównanie go z własnoręcznie wyliczonym na podstawie wiadomości.

W przypadku RSA klucz prywatny i publiczny można zamienić miejscami. Podpisy cyfrowe są implementowane na bazie szyfrowania, tylko z odwrotnym zastosowaniem kluczy – skrót wiadomości jest szyfrowany kluczem prywatnym, a żeby zweryfikować wiadomość, odszyfrowuje się go kluczem publicznym i porównuje z wiadomością.

W innych kryptosystemach (np. w ElGamal) podpisywanie cyfrowe jest zupełnie niezależne od szyfrowania. Niektóre, jak DSA, umożliwiają tylko podpisywanie, nie da się w nich zaś w oczywisty sposób szyfrować. Podpis tej samej wiadomości w RSA jest zawsze identyczny. W ElGamalu i DSA każdy kolejny podpis tej samej wiadomości zwykle jest inny – co ma znaczenie w niektórych zastosowaniach.

Rząd Stanów Zjednoczonych usiłował swego czasu ograniczyć stosowanie silnej kryptografii do szyfrowania, jednak musiał pozwolić na silne podpisy cyfrowe. RSA nie dawała możliwości udostępnienia tylko jednej z tych funkcji, dlatego promowany był system podpisów cyfrowych DSA. Jak się jednak okazało, losowość tych podpisów można wykorzystać do implementacji „ukrytego kanału komunikacji” i silnego szyfrowania za pomocą DSA (jak również w podpisach ElGamala, ale ElGamal udostępnia też normalne szyfrowanie). Jest to jednak metoda bardzo powolna i nie jest stosowana ze względu na dostępność szybszych „pośrednich” metod takich jak RSA i ElGamal.

Zależności między kluczem publicznym i prywatnym

We wszystkich kryptosystemach uzyskanie klucza prywatnego na podstawie publicznego musi być obliczeniowo trudne.

W RSA zależność między kluczem publicznym i prywatnym jest symetryczna – uzyskanie klucza publicznego na podstawie prywatnego jest równie trudne, jak uzyskanie prywatnego na podstawie publicznego. Składowe kluczy ${\displaystyle d}$ i ${\displaystyle e}$ obliczane są przy użyciu dwóch dużych i zbliżonych długością liczb pierwszych (${\displaystyle p}$ i ${\displaystyle q}$), generowanych w sposób możliwie przypadkowy. ${\displaystyle d}$ i ${\displaystyle e}$ otrzymuje się na podstawie równania (${\displaystyle d}$ jest losowane, ${\displaystyle e}$ obliczane lub odwrotnie):

${\displaystyle d\cdot e\equiv 1{\pmod {(p-1)(q-1)}}.}$

Iloczyn ${\displaystyle p}$ i ${\displaystyle q}$ jest częścią klucza oznaczaną przez ${\displaystyle n.}$

Klucz publiczny i prywatny tworzą odpowiednio pary ${\displaystyle (e,n)}$ i ${\displaystyle (d,n).}$ Liczby ${\displaystyle p}$ i ${\displaystyle q}$ nie są potrzebne poza procesem generowania kluczy i zwykle są kasowane, jednakże istnieje wariant algorytmu, w którym wchodzą one w skład klucza prywatnego (są wykorzystywane w celu zwiększenia szybkości działania kryptosystemu).

W systemie ElGamal wybierana jest liczba pierwsza ${\displaystyle p,}$ generator ${\displaystyle g,}$ następnie losowana jest liczba ${\displaystyle x.}$ Kluczem prywatnym jest ${\displaystyle (p,g,x),}$ kluczem publicznym zaś ${\displaystyle (p,g,g^{x}),}$ w grupie multiplikatywnej liczb całkowitych modulo p. Klucz publiczny może być obliczony na podstawie prywatnego, co zresztą ma miejsce podczas generacji kluczy.

Bardzo podobnie wygląda sytuacja w innych systemach opartych na logarytmie dyskretnym, takich jak kryptografia krzywych eliptycznych. W tych metodach grupę Zp zastępuje się inną grupą, np. utworzoną z punktów leżących na krzywej eliptycznej.

Zobacz też

• algorytm symetryczny
• kryptologia kwantowa
• PKI
• SSH
• Transport Layer Security

Przypisy