Kryptografia asymetryczna

Idea

Kryptografię asymetryczną wynaleźli w 1976 Martin Hellman i Whitfield Diffie (do tego czasu znane były wyłącznie szyfry symetryczne). Polega na użyciu pary uzupełniających się kluczy: publicznego i prywatnego. Wykorzystuje się operacje matematyczne, które bardzo łatwo przeprowadzić w jedną stronę, ale trudno w drugą.

W przeciwieństwie do szyfrów symetrycznych używa się innych kluczy do szyfrowania, a innych do odszyfrowania. W najczęściej spotykanych zastosowaniach jest to para razem generowanych i powiązanych ze sobą matematycznie kluczy: jeden szyfruje, a drugi odszyfrowuje informacje - klucz, którym zaszyfrowano daną wiadomość, nie umożliwia odczytania szyfrogramu, konieczny jest klucz drugi z pary.

Dzięki temu treść zaszyfrowana jednym z tych kluczy może zostać rozszyfrowana tylko drugim z nich - nie ma więc potrzeby przesyłania tajnych kluczy - nadawca szyfruje wiadomość kluczem publicznym odbiorcy i tak zaszyfrowana wiadomość nie może zostać odszyfrowana żadnym innym, jak tylko kluczem prywatnym odbiorcy, który - takie jest założenie - jest w jego wyłącznym posiadaniu.

Schemat:

tekst jawny >--[klucz publiczny]--> szyfrogram >--[klucz prywatny]--> tekst jawny

Założenia:

  • zaszyfrowaną kluczem publicznym informację można odszyfrować tylko kluczem prywatnym (a nie publicznym) i odwrotnie: jeśli do zaszyfrowania użyje się klucza prywatnego, to tylko używając klucza publicznego (a nie prywatnego), będzie można odszyfrować informację
  • z klucza publicznego nie da się wyprowadzić klucza prywatnego (lub jest to trudniejsze niż atak brute force) i na odwrót: znajomość klucza prywatnego nie pozwala odtworzyć klucza publicznego (z tym samym zastrzeżeniem)
  • jeden z kluczy (domyślnie: prywatny) jest w wyłącznej dyspozycji właściciela, dla większego bezpieczeństwa chroniony jest hasłem; drugi klucz (domyślnie: publiczny) jest dostępny dla wszystkich chcących wysyłać do właściciela kluczy zaszyfrowane informacje
  • szyfr jest odporny na atak polegający na porównaniu jawnego tekstu z szyfrogramem (atak ze znanym tekstem jawnym)

Właściwości kluczy:

  • publiczny: mniej złożony; dostępny dla wszystkich; szyfrujący i weryfikujący podpis, skonstruowany tak, że stosunkowo łatwo wykryć jego podmianę
  • prywatny: bardziej złożony; dostępny tylko dla właściciela; deszyfrujący i podpisujący; nie da się go odtworzyć na podstawie klucza publicznego

Szyfry asymetryczne opierają się na istnieniu pewnych trudnych do odwrócenia problemów matematycznych. Np. o wiele łatwiej jest pomnożyć przez siebie dwie duże liczby, niż rozłożyć dużą liczbę na czynniki (opiera się na tym system RSA). Jednak ta trudność faktoryzacji wynika z braku znajomości odpowiedniej metody, sama trudność nie została matematycznie udowodniona.

Drugim popularnym systemem jest ElGamal, opierający się na trudności logarytmu dyskretnego.

Typowe rozmiary kluczy są rzędu 3072-15360 bitów dla np. RSA lub ok. 512 bitów dla kryptografii na krzywych eliptycznych. W przypadku RSA złamane zostały klucze rozmiarów do ok. 500 bitów.

Zastosowania

Wynalezienie kryptografii asymetrycznej (1976) umożliwiło nowe zastosowania takie jak podpisy cyfrowe i uwierzytelnianie. Obecnie metody kryptograficzne są stosowane nie tylko do utajnienia informacji - cztery najważniejsze zastosowania:

  • poufność (tajność) - tylko autoryzowany odbiorca jest w stanie odczytać wiadomość z szyfrogramu
  • integralność - odbiorca może stwierdzić czy wiadomość nie została naruszona/zmieniona w czasie transmisji
  • uwierzytelnienie (notorycznie i błędnie nazywane autentykacją) - odbiorca jest w stanie potwierdzić tożsamość nadawcy i zweryfikować czy to podpisany nadawca rzeczywiście wysłał wiadomość
  • niezaprzeczalność (ang. non-repudiation) - nadawca nie będzie w stanie zaprzeczyć, że wysłał wiadomość (niezaprzeczalność nadania), odebrał (niezaprzeczalność odbioru) itd...

Kryptografia asymetryczna dała zupełnie nowe możliwości: np. mechanizm podpisu cyfrowego, dzięki którym można zapewnić z dużą pewnością (przy założeniu, że odpowiedni prywatny klucz nie został w żaden sposób "skompromitowany"), że wiadomość została wysłana przez nadawcę, który się pod nią podpisał. Właściwie użyte mechanizmy pozwalają uzyskać stopień pewności porównywalny lub większy niż podpis fizyczny. Przykładami protokołów podpisów cyfrowych są DSA i ElGamal. Podpisy cyfrowe używane są głównie w PKI i mechanizmach bezpieczeństwa sieci (nawiązywanie połączenia SSL).

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), mechanizmów bezpieczeństwa sieci (Kerberos, VPN itp.) itd.

Ze względu na wydajność najczęściej stosowane są metody hybrydowe. Ponieważ szyfrowanie asymetryczne jest dużo wolniejsze od symetrycznego, prawie nigdy nie stosuje się go do przesyłania dłuższych wiadomości. Samej kryptografii asymetrycznej używa się do utworzenia i wymiany kluczy symetrycznych, używanych do szyfrowania samej komunikacji w trakcie danej sesji. Podobnie w podpisie cyfrowym - podpisywana jest nie sama wiadomość, ale jej skrót. Kryptografia krzywej eliptycznej może przełamać ten schemat.

Znaczenie

Istnienie tylko kryptografii symetrycznej - z jednym kluczem, który szyfruje i odszyfrowuje - ogranicza w istotny sposób możliwość stosowania tego rodzaju szyfrów do osób lub instytucji, które się nawzajem znają i posiadają niezależny, bezpieczny kanał wymiany kluczy. A nawet i w tym wypadku, przy większej ilości uczestników komunikacji i konieczności regularnej wymiany kluczy (np. systemy bankowe) dystrybucja kluczy staje się olbrzymim problemem logistycznym.

Kryptografia asymetryczna pozwala na rozwiązanie tych problemów, nawiązanie szyfrowanej komunikacji między nieznającymi się uprzednio osobami oraz stworzenie całego systemu publicznie dostępnych rozwiązań kryptograficznych dodając do tego niemożliwe uprzednio zastosowania takie jak podpis cyfrowy czy niezaprzeczalność. Jest obecnie podstawą technik zabezpieczania zarówno kanałów wymiany danych, jak i samych informacji.

Inaczej mówiąc: bez kryptografii asymetrycznej nie byłoby większości współczesnych zastosowań technik kryptograficznych, bez których internet nie mógłby być miejscem wymiany poufnych informacji. Nawet jeśli sami nie używamy takich technik jak PGP, SSL czy SSH to, tak czy inaczej korzystamy z internetu, gdzie te techniki mają fundamentalne znaczenie przy zastosowaniach biznesowych, w e-commerce i samym zarządzaniu serwerami.

Czyli gdyby nie kryptografia asymetryczna nie byłoby internetu takim, jakim go znamy.

Zastosowania

Szyfrowanie

tekst jawny >--[klucz publiczny]--> szyfrogram >--[klucz prywatny]--> tekst jawny
  1. Bob chce, żeby Alice (i inni ludzie) mogli mu wysyłać zaszyfrowane wiadomości. W tym celu generuje parę powiązanych ze sobą kluczy: trzymany w ukryciu i dostępny tylko jemu klucz prywatny oraz klucz publiczny, który udostępnia (na swojej stronie internetowej, serwerze kluczy lub za pośrednictwem key signing party).
  2. Alice pobiera klucz publiczny Boba i używając go, szyfruje wiadomość; ponieważ odszyfrować ją można tylko kluczem prywatnym Boba, może przesłać ją niezaufanym kanałem łączności i tylko Bob po otrzymaniu szyfrogramu używając swojego klucza prywatnego (utrzymywany w sekrecie od czasu utworzenia i znany tylko mu) może odszyfrować i przeczytać wiadomość. Dzięki temu wiadomość jest strzeżona przed nieautoryzowanymi osobami, a Bob i Alice nie potrzebują bezpiecznego tunelu do wymiany współdzielonego klucza.

Podpis cyfrowy

Podpis cyfrowy to dodatkowa informacja dołączona do wiadomości służąca do weryfikacji jej źródła. Służy uwierzytelnieniu cyfrowej informacji analogicznie do podpisu na zwyczajnym papierze, ale przy użyciu technik kryptograficznych. Podpisy cyfrowe korzystają z kryptografii asymetrycznej - tworzona jest para kluczy, klucz prywatny i klucz publiczny - klucz prywatny służy do podpisywania wiadomości, klucz publiczny natomiast do weryfikowania podpisu.

Najważniejszymi kryptosystemami umożliwiającymi podpisywanie cyfrowe są RSA, ElGamal i DSA, ECDSA. Najpopularniejsze standardy pozwalające na złożenie podpisu elektronicznego to X.509 oraz PGP. Dopóki są możliwe kolizje w haszu, można sfałszować podpis cyfrowy, który go stosuje.

Mechanizm podpisu cyfrowego zawiera trzy algorytmy:

  • tworzenia klucza
  • podpisywania
  • weryfikacji

Mechanizmy podpisu cyfrowego mają kilka uprzednich warunków, bez których taki podpis nic nie znaczy ani w sensie prawnym, ani kryptograficznym.

  • Dobrej jakości algorytm, nie wszystkie używane algorytmy asymetryczne nie są bezpieczne, są znane ataki na nie.
  • Dobrej jakości implementacja, implementacja dobrego algorytmu (lub protokołu) z błędami nie działa.
  • Klucz prywatny musi pozostać rzeczywiście tajny - każdy, kto ma do niego dostęp może tworzyć tak samo autentyczne podpisy cyfrowe.
  • Dystrybucja kluczy publicznych musi się dokonywać tak, że klucz publiczny przypisany dla Boba rzeczywiście do niego należy i na odwrót. Jest to zapewniane przez PKI (operator to CA).
  • Użytkownicy (i ich oprogramowanie) musi używać protokołu prawidłowo.

Dopiero, jeśli wszystkie powyższe warunki są spełnione, podpis cyfrowy jest dowodem na to, kto wysłał wiadomość. Do prawidłowego działania całej infrastruktury podpisu cyfrowego konieczne jest również ustawodawstwo, dzięki któremu może mieć skutki prawne.

Jak wiadomo wiadomość zaszyfrowana kluczem publicznym może zostać odszyfrowana tylko kluczem prywatnym. Ten mechanizm może też działać w drugą stronę - jeżeli zostanie zaszyfrowana kluczem prywatnym, to tylko używając klucza publicznego, będzie można ją odszyfrować. Jaka wyniknie korzyść z zastosowania szyfru, który każdy będzie mógł odczytać?

Będzie można określić, którym kluczem prywatnym została zaszyfrowana wiadomość, a ściśle rzecz biorąc potwierdzić czy została zaszyfrowana konkretnym kluczem. Szyfrowanie kluczem prywatnym (a więc normalnie przeznaczonym do odszyfrowania) staje się podpisem elektronicznym.

tekst jawny >-[klucz prywatny]-> szyfrogram >-[klucz publiczny]-> tekst jawny |
                                                                              |-porównanie
tekst jawny >-                 [kanał łączności]               -> tekst jawny |
  1. Bob chce wysłać wiadomość do Alice, tak, żeby zagwarantować, że wiadomość pochodzi od niego (ale nie przejmuje się czy ktoś inny będzie mógł ją przeczytać). Wysyła więc do Alice niezaszyfrowaną wiadomość razem z tą samą wiadomością zaszyfrowaną swoim kluczem prywatnym.
  2. Dzięki temu Alice (lub ktokolwiek inny) będzie w stanie dowieść pochodzenia wiadomości, po prostu rozszyfrowując wiadomość kluczem publicznym i porównując ją z wiadomością niezaszyfrowaną. Jeśli obie będą identyczne, oznacza to, że wiadomość rzeczywiście pochodzi od Boba, ponieważ do utworzenia tego podpisu był potrzebny prywatny klucz Boba, a tylko on ma do niego dostęp.

Zaszyfrowana wersja wiadomości jest cyfrowym podpisem Boba do wiadomości ponieważ każdy może użyć klucza publicznego, by potwierdzić, że rzeczywiście Bob jest jej autorem.

Zazwyczaj jednak Bob po prostu stosuje funkcję haszującą do wiadomości i aby ją uwierzytelnić, szyfruje otrzymany w ten sposób skrót, używając klucza prywatnego, dzięki temu podpis jest dużo krótszy, co oszczędza i czas (ponieważ haszowanie jest dużo szybsze niż szyfrowanie kluczem publicznym) i miejsce (ponieważ zaszyfrowany skrót wiadomości jest dużo mniejszy niż szyfrogram powstały z całej wiadomości).

Potem jako swój podpis elektroniczny dołącza do oryginalnej wiadomości - dowolna osoba posiadająca klucz publiczny może sprawdzić autentyczność podpisu, poprzez odszyfrowanie hasza za pomocą klucza publicznego nadawcy, oraz porównanie go z osobiście wyliczonym na podstawie wiadomości. Programy do podpisów elektronicznych automatyzują te czynności.

W tym przykładzie Alice odszyfrowuje skrót kluczem publicznym Boba i porównuje wynik z haszem odebranego jawnego tekstu.

Certyfikat tożsamości

Problem: Alice udostępniła swój klucz publiczny i każdy używając go, może jej wysłać tajne wiadomości. Niestety Mallory również może udostępnić swój klucz publiczny (posiadając powiązany z nim klucz prywatny) twierdząc, że należy do Alice i jeśli wprowadzi kogoś w błąd, będzie mógł odczytać część tajnych wiadomości wysłanych do niej. Ale jeśli Alice wbuduje swój klucz publiczny w certyfikat i jest tam podpis cyfrowy złożony przez zaufanego Trenta, każdy kto ufa Trentowi, będzie mógł w prosty sposób sprawdzić ten certyfikat, i zobaczyć czy Trent potwierdza, że ten wbudowany klucz należy do Alice.

Certyfikat klucza publicznego (inaczej nazwany certyfikatem tożsamości) jest blokiem bitów w określonym formacie, zawierającym publiczną połowę algorytmu klucza asymetrycznego (klucza publicznego) razem z informacją o tożsamości (dane personalne, adres mailowy, tytuł, numer telefonu itp.), podpisane cyfrowo przez pewną osobę lub instytucję - przypisując/wiążąc w ten sposób klucz publiczny do osoby (lub instytucji) opisanej atrybutami.

Certyfikat zwykle zawiera: podpisany klucz publiczny, nazwa, określająca osobę, komputer lub organizację, termin ważności, lokację (URL) centrum odwołań (ang. revocation center).

Istnieją dwa podstawowe mechanizmy uwierzytelniania kluczy:

  • scentralizowany PKI: podpis będzie pochodził od instytucji certyfikującej
  • zdecentralizowana sieć zaufania: podpis będzie pochodził od samego użytkownika (samopodpisany certyfikat) albo innych użytkowników (tzw. "wyrazy poparcia"; ang. endorsements)

W obu przypadkach autor podpisu zapewnia, że informacja o tożsamości i klucz publiczny odpowiadają sobie.

PKI (Public Key Infrastructure)

Firmy i instytucje, które mają handlować i zawierać umowy poprzez sieć, potrzebują bardziej wiarygodnego potwierdzenia autentyczności używanych kluczy kryptograficznych. Odpowiedzią na te potrzeby jest scentralizowana, hierarchiczna infrastruktura klucza publicznego, która świadczy usługi związane z zarządzaniem certyfikatami kluczy publicznych. Jest konieczna w zastosowaniach biznesowych, gdzie nie ma czasu na niezależne potwierdzanie własnych kluczy. Są potwierdzone przez niezależną instytucję, której ufają obie strony komunikacji.

PKI pozwala ona na zarządzanie certyfikatami przez ich generowanie, dystrybucję, aktualizację i unieważnianie oraz rejestrację wielu użytkowników dla różnych potrzeb. Opiera się na strukturze odwróconego drzewa, głównym urzędom certyfikacji (Root CA) mogą podlegać inne CA, stworzone specjalnie dla różnych zastosowań (np. handel elektroniczny, bankowość, administracja publiczna). W drzewie danego Root CA może się znajdować dowolna liczba podległych urzędów oraz użytkowników.

Prawdziwość podpisu można zweryfikować, mając klucz publiczny urzędu certyfikującego, który znajduje się w kolei w certyfikacie wystawionym dla tego urzędu przez organ wyższej instancji. Weryfikacja certyfikatu polega na prześledzeniu ścieżki zaufania, na końcu której znajduje się główny organ nadrzędny (root CA). Certyfikat wystawia on sam dla siebie, a wszyscy powinni mieć swobodny dostęp do jego klucza publicznego.

Konieczne stało się ujednolicenie wymagań i przepisów dotyczących certyfikatów, dostawców usług certyfikacyjnych oraz urządzeń służących do generowania i weryfikacji podpisu elektronicznego. Wszystkie zawierają takie pola jak: wersja, numer seryjny, nazwa wydawcy certyfikatu, data ważności, nazwa podmiotu, dla którego wystawiono certyfikat, jego klucz publiczny, oraz podpis cyfrowy organu wydającego certyfikat (CA - Certification Authority).

W typowym PKI Trent będzie CA (Certificate Authority), który jest zaufanym z konieczności przez wszystkich uczestników.

W rozwiązaniach tego typu Alice może nie znać CA Boba, więc certyfikat Boba może zawierać także certyfikat klucza publicznego jego CA podpisany przez CA2 "wyższego poziomu", który jest znany dla Alice. Taki proces prowadzi do hierarchii certyfikatów i jeszcze bardziej skomplikowanych związków zaufania.

PKI używa oprogramowania, które zarządza certyfikatami na wielką skalę, np. w systemie X.509 PKI hierarchia certyfikatów jest zawsze odwróconym drzewem z korzeniem certyfikacji na samej górze reprezentującym CA, który jest centralny dla całego systemu i nie potrzebuje być uwierzytelniany przez kogoś trzeciego.

Certyfikat może zostać odwołany, jeśli okaże się, że powiązany prywatny klucz został "skompromitowany", lub jeśli relacja (pomiędzy tożsamością a kluczem publicznym) wbudowana w certyfikat zostanie uznana za nieprawidłowa, lub zmieniona. Może to nastąpić, jeśli np. osoba zmienia pracę lub dane personalne. Odwołanie (revocation) zdarza się rzadko, użytkownik zawsze będzie mógł sprawdzić jego poprawność. Można to zrobić, porównując z listą odwołań certyfikatów (CRL: certificate revocation list) - listą odwołanych lub skasowanych certyfikatów. Podstawową funkcją scentralizowanego PKI jest zapewnienie, że ta lista jest aktualna i dokładna.

Innym sposobem jest zapytanie przy użyciu (OCSP: Online Certificate Status Protocol) co pozwala poznać status danego certyfikatu.

Rozwiązanie to pierwszy raz było zastosowane w PEM (Privacy Enhanced Mail), wcześniejszym od PGP systemie kryptograficznym dla poczty elektronicznej, który jednak nie zdobył większej popularności.

Istnieje kilka standardów certyfikatów, ale najpopularniejszy to X.509.

Większość najważniejszych standardów takich jak SSL/TLS, SSH, S/MIME, SET (Secure Electronic Transactions) czy IPSec została zaprojektowana z myślą o współdziałaniu w strukturach PKI.

Sieć zaufania (web of trust)

Wszystkie implementacje zgodne z OpenPGP, zawierają mechanizm sprawdzający nazwany siecią zaufania. Służy do ustanowienia i sprawdzenia autentyczności powiązania pomiędzy publicznym kluczem a użytkownikiem. Jest to w pewnym sensie odpowiednik scentralizowanego PKI opierającego się wyłącznie na autorytecie certyfikującym (lub na hierarchii takowych).

W sieci komputerowej może istnieć wiele niezależnych sieci zaufania i każdy użytkownik (przez swój certyfikat tożsamości) może być częścią takiej sieci lub powiązaniem pomiędzy sieciami. W sieci zaufania Trent może być każdym użytkownikiem i to czy warto zaufać jego potwierdzeniu, zależy od osoby chcącej wysłać wiadomość do Alice.

Certyfikaty tożsamości (zawierające publiczne klucze i informacje o tożsamości użytkowników) mogą zostać cyfrowo podpisane przez innych użytkowników, którzy w ten sposób gwarantują powiązanie klucza publicznego i osoby wymienionej w certyfikacie. Służą do tego keysigning parties.

Istnieje również mechanizm liczenia głosów powalający określić, które powiązanie klucz publiczny - właściciel będzie uważane za zaufane: np. jeśli trzech częściowo zaufanych gwarantów uwierzytelnia certyfikat (a więc i powiązanie osoby z kluczem), lub zrobi to jeden w pełni zaufany gwarant to powiązanie osoby i klucza w tym certyfikacie zostanie uznane za poprawne.

Mechanizm ten może zostać modyfikowany stosownie do potrzeb użytkowników, może też zostać wyłączony. Jest elastyczny i pozostawia decyzję o zaufaniu w rękach indywidualnego użytkownika, co wymaga zarówno uważności, jak i inteligentnego nadzoru.

Problemem w sieci zaufania jest sytuacja, w której klucz prywatny został utracony - ponieważ nie może zostać odwołany, wciąż jest traktowany jako prawidłowy, a wiadomości zaszyfrowane odpowiadającym mu kluczem publicznym nie mogą być odczytane (rozszyfrowane). Użytkownik powinien przygotować podpisany certyfikat odwołania na wypadek sytuacji utraty lub kompromitacji klucza prywatnego. Można również do tego celu zastosować datę wygaśnięcia.

Zagrożenia

Zagrożeniem dla klucza prywatnego są wirusy, malware itd., które mogą spowodować wykradzenie, skopiowanie lub zniszczenie klucza prywatnego.

Najbardziej prawdopodobny scenariusz takiego ataku polega na zdalnej instalacji trojana i keyloggera (może to być jeden wyspecjalizowany program), który kopiuje plik z kluczem prywatnym i wysyła go atakującemu, a dzięki możliwości rejestrowania zdarzeń systemowych (uruchomienie klienta PGP i naciskanie klawiszy) ujawnia również hasło.

Podpis elektroniczny, w którym zostanie zastosowany słaby algorytm haszujący, albo zbyt krótki skrót, jest wrażliwy na atak (szczególnie urodzinowy).

Podatność na atak MITM: chociaż wydawało się, że kryptografia asymetryczna jest rozwiązaniem problemu dystrybucji kluczy, szybko okazało się, że ktoś może się podszyć się pod tożsamość i wysłać podłożony klucz publiczny, wtedy oszust będzie mógł otrzymać informacje, odszyfrować je i czytać, potem zaszyfrować poprawnym kluczem publicznym i wysłać go do poprawnego celu. Oznacza to, że można spenetrować tajne dane bez łamania szyfru i nie angażując mocy obliczeniowej. Jest to poważne zagrożenie, bo oznacza, że nawet użycie "niełamliwych" szyfrów nie wystarczy do zagwarantowania prywatności.

Złożone procedury uwierzytelniania kluczy publicznych, komplikują stosowanie kryptografii asymetrycznej i powodują dodatkowe problemy bezpieczeństwa.

Z tego powodu zarówno przy weryfikacji podpisu, jak i przy szyfrowaniu wiadomości istotne jest upewnienie się, czy dany klucz publiczny rzeczywiście należy do adresata. PGP umożliwia umieszczenie w dystrybuowanych kluczach użytkowników 'certyfikatów tożsamości' tak skonstruowanych, że podmiana lub przypadkowe zniekształcenie są łatwo wykrywalne. Ale sam fakt, że każde zniekształcenie certyfikatu jest łatwe do wykrycia, nie jest wystarczającym zabezpieczeniem, ponieważ zapobiega "kompromitacji" dopiero po utworzeniu certyfikatu, a nie przedtem. Użytkownicy powinni użyć także innych metod, by potwierdzić prawidłowość klucza. Mechanizmem, który to umożliwia jest tzw. "sieć zaufania". PGP posiada również możliwość odwołania certyfikatu tożsamości, który stał się nieprawidłowy oraz określenie daty wygaśnięcia.

Siła obecnie używanych szyfrów asymetrycznych (np. RSA) polega na trudności przeprowadzenia faktoryzacji (czyli odnalezienia składników: dużych liczb pierwszych, których użyto do utworzenia klucza). Jak na razie nikt nie udowodnił, że faktoryzacja jest rzeczywiście trudna, po prostu nie są znane szybkie metody na jej przeprowadzenie. Możliwe, że ktoś takie metody wymyśli i wtedy wszystkie metody używające takich szyfrów będą zagrożone, a sam szyfr bezużyteczny. Możliwe również, że trudność przeprowadzenia faktoryzacji zostanie udowodniona i wtedy metoda uzyskałaby gwarancję bezpieczeństwa.

Szyfry

Diffie-Hellman

Protokół uzgadniania kluczy Diffie'ego-Hellmana to protokół kryptograficzny, w którym dwie strony mogą wylosować pewną liczbę (tajny klucz), taką, że obie strony po wykonaniu protokołu będą ją znały, za to nie będzie jej znał nikt z podsłuchujących wymianę wiadomości. Liczba ta może być potem używana jako klucz symetryczny do szyfrowania komunikacji.

Protokół nie zabezpiecza przed ingerencjami w komunikację (atak MITM), jedynie przed pasywnym podsłuchem. Dlatego należy go uzupełnić o zabezpieczenia przed atakiem aktywnym.

Była to pierwsza praktyczna metoda ustanowienia wspólnej tajemnicy przez niechroniony kanał komunikacji. Szyfr złamany w 1980. Patent wygasł.

ElGamal

ElGamal to jeden z dwóch najważniejszych systemów kryptografii asymetrycznej (drugim jest RSA). Zapewnia szyfrowanie oraz podpisy cyfrowe. Wiele modyfikacji ElGamala (podobnie jak z modyfikacjami RSA) zapewnia różne inne usługi. Autor: Taher ElGamal

Używany w GPG, obecnych wersjach PGP i innych kryptosystemach;

RSA

RSA to pierwszy i obecnie jeden z dwóch najpopularniejszych (obok ElGamal) systemów kryptografii asymetrycznej. Stworzony w roku 1978 przez zespół: Ronald Rivest, Adi Shamir, Leonard Adelman (wówczas pracownicy MIT). RSA jest akronimem utworzonym z pierwszych liter nazwisk jego twórców. Pierwszy główny system klucza publicznego.

Trudność RSA opiera się na trudności faktoryzacji dużych liczb - znalezienie szybkiej metody faktoryzacji doprowadziłoby do złamania RSA, aczkolwiek nie ma dowodu, że nie da się złamać RSA w inny sposób. Klucz RSA musi być około 10 razy większy od klucza tajnego, by zapewnić podobne bezpieczeństwo.

Dużo wolniejszy od DES i innych szyfrów symetrycznych, więc najczęściej Bob szyfruje tajną wiadomość algorytmem symetrycznym, tajny klucz (relatywnie krótki) szyfruje RSA i przesyła zarówno zaszyfrowany RSA klucz symetryczny, jak i zaszyfrowaną nim wiadomość do Alice. Ta procedura wymaga użycia silnego generatora liczb przypadkowych dla klucza symetrycznego, ponieważ w przeciwnym wypadku Eve będzie mogła ominąć RSA, zgadując klucz symetryczny. Podatny na MITM.

Zasada działania: dwie liczby pierwsze (p i q) są podstawą dla wyznaczenia wartości n i e.

  • n to iloczyn p i q (n=pq)
  • e to liczba względnie pierwsza (czyli niemająca wspólnych podzielników oprócz 1) do iloczynu (p-1)(q-1) mniejsza od n
  • klucz publiczny to wartości(n, d) a prywatny (n, d)

RSA jest trudny do złamania pod warunkiem użycia dużych liczb pierwszych, w praktyce wybierane są liczby prawdopodobnie pierwsze (duże losowe, nieparzyste liczby, na których przeprowadza się testy mające wykluczyć parzystość)

  • szyfrowanie - uzyskanie wiadomości c z tekstu m - c=memod n (mod - dzielenie modulo)
  • odszyfrowanie - m=cd mod n
  • sygnatura s na wiadomości m - s=md mod n
  • sprawdzenie autentyczności podpisu s - obliczenie wartości se mod n (jeśli wynikiem jest wiadomość m, podpis jest prawidłowy)

Patent MIT w USA (1983) wygasł we wrześniu 2000, gdzie indziej nie jest możliwe jego opatentowanie.

RSA (ang), RSA (kryptografia)

DSA (Digital Signature Algorithm)

Obowiązujący w USA federalny standard podpisu cyfrowego, zaproponowany przez NIST (National Institute of Standards and Technology) w sierpniu 1991 do użycia w DSS (Digital Signature Standard). Patent wygasł i algorytm jest udostępniany przez NIST bez opłat (royalty-free).

Algorytm DSA do podpisu dokumentu wykorzystuje wartość jednokierunkowej funkcji skrótu SHA-1. Długość kluczy używanych w tym algorytmie jest zmienna w zakresie 512 - 1024 bitów. Są one adekwatne do aktualnych mocy obliczeniowych. Za wystarczające do większości cywilnych zastosowań uważane są klucze o długości przynajmniej 768 bitów. DSA jest używany w OpenSSL, OpenSSH i GnuPG.

Tworzenie klucza

  • wybierz liczbę pierwszą p o długości L-bit gdzie 512 ≤ L ≤ 1024, i L jest podzielne przez 64
  • wybierz 160-bitową liczbę pierwszą q, taką, że p - 1 = qz, gdzie z jest dowolną liczbą naturalną
  • wybierz h, gdzie 1 < h < p - 1 taką, że_g = hz mod p > 1_
  • wybierz x w sposób przypadkowy tak, że 0 < x < q
  • oblicz y = gx mod p
  • klucz publiczny to (p, q, g, y) a prywatny x

zauważ, że (p, q, g) mogą być współdzielone pomiędzy różnymi użytkownikami systemu jeśli jest to potrzebne

Składanie podpisu

  • wybierz dla danej wiadomości przypadkową wartość s (called a nonce), gdzie 1 < s < q
  • oblicz s1 = (gs mod p) mod q
  • oblicz s2 = (H(m) + s1*x)s-1 mod q, gdzie H(m) jest funkcją haszującą SHA-1 zastosowaną do wiadomości m
  • podpis to (s1,s2)

Weryfikacja

  • oblicz w = (s2)-1 (mod q)
  • oblicz u1 = H(m)*w (mod q)
  • oblicz u2 = s1*w (mod q)
  • oblicz v = [gu1*yu2 mod p] mod q
  • podpis jest prawidłowy jeśli v = s1

DSA jest podobny do Elgamal.

Odnośniki