Kryptografia asymetryczna
Z Wikipedii
Kryptografia asymetryczna to rodzaj kryptografii, w którym używa się zestawów dwu lub więcej powiązanych ze sobą kluczy, umożliwiających wykonywanie różnych czynności kryptograficznych.
Najważniejsze zastosowania kryptografii asymetrycznej – szyfrowanie i podpisy cyfrowe – zakładają istnienie 2 kluczy – prywatnego i publicznego, przy czym klucza prywatnego nie da się łatwo odtworzyć na podstawie publicznego, w niektórych innych zastosowaniach kluczy może być więcej.
Kryptografia asymetryczna została oficjalnie wynaleziona przez cywilnych badaczy Martina Hellmana, Whitfielda Diffie i niezależnie przez Ralpha Merkle w 1976 roku. 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. 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.
Algorytmy mające zastosowanie w kryptografii asymetrycznej wykorzystują operacje, które da się łatwo przeprowadzić w jedną stronę a bardzo trudno w drugą. Np. mnożenie jest łatwe, a faktoryzacja trudna (na czym opiera się RSA). Albo potęgowanie modulo jest łatwe, a logarytm dyskretny jest trudny (na czym opierają się ElGamal, DSA i ECC).
[edytuj] Szyfrowanie
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 odczytać informację. 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.
[edytuj] Podpisywanie cyfrowe
Liczony jest hasz wiadomości. Jest on następnie szyfrowany przez osobę uwierzytelniającą jej kluczem prywatnym i jako podpis elektroniczny dołączana do oryginalnej wiadomości. Dowolna osoba posiadająca klucz publiczny może sprawdzić autentyczność podpisu, poprzez odszyfrowanie hasza za pomoca klucza publicznego nadawcy, oraz porównanie go z osobiście wyliczonym na podstawie wiadomości.
W przypadku RSA klucz prywatny i publiczny są symetryczne, i podpisy cyfrowe są implementowane na bazie szyfrowania, tylko z odwrotnym zastosowaniem klucz – hasz wiadomości jest szyfrowany kluczem prywatnym, i żeby zweryfikować wiadomość, odszyfrowuje się go kluczem publicznym i porównuje z wiadomością.
W innych kryptosystemach takich jak 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 jest możliwe istnienie wielu podpisów jednej wiadomości. Jest to ważna cecha dla niektórych zastosowań.
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 "bezpośrednich" metod takich jak RSA i ElGamal.
[edytuj] 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. Para kluczy d, e jest generowana na podstawie rozkładu dużej liczby n na czynniki pierwsze p i q, który to rozkład jest kasowany w procesie generacji kluczy na podstawie równania (d jest losowane, e obliczane lub odwrotnie):
Klucze to (e,n) i (d,n).
W systemie ElGamal wybierana jest liczba pierwsza p, generator g, następnie losowana jest liczba x. Kluczem prywatnym jest (p,g,x), kluczem publicznym zaś (p,g,gx), 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 o logarytm dyskretny, takich jak kryptografia krzywych symetrycznych, tyle że zamiast liczby pierwszej wyznaczającej odpowiednią grupę liczb całkowitych modulo p wybiera się jakąś inną grupę, np. grupę punktów krzywej eliptycznej.
