Protokół Diffiego-Hellmana

Protokół Diffiego-Hellmana – protokół uzgadniania kluczy szyfrujących, opracowany przez Witfielda Diffiego oraz Martina Hellmana w 1976 roku. Jego siła oparta jest na trudności obliczenia logarytmów dyskretnych w ciałach skończonych. Klucz uzgodniony za pomocą tego algorytmu może zostać wykorzystany do szyfrowania komunikacji. Algorytm pozwala bezpiecznie uzgodnić klucz, nawet jeżeli istnieje osoba, która podsłuchuje proces uzgadniania klucza, nie chroni jednak przed atakami typu man in the middle. Algorytm nie nadaje się do szyfrowania i deszyfrowania wiadomości.

Opis protokołu

Protokół Diffiego-Hellmana służy do ustalenia wspólnego tajnego klucza przy użyciu publicznych środków komunikacji. Następujący diagram przedstawia ogólną ideę uzgodnienia klucza na przykładzie kolorów zamiast liczb. Kluczowe dla procesu jest to, że Alicja i Bob używają jedynie prostej operacji mieszania kolorów. Operacja ta powinna być możliwie trudna do odwrócenia (być funkcją jednokierunkową). Wygenerowany klucz jest praktycznie niemożliwy do odtworzenia przez osobę podsłuchującą. Kolor żółty jest znany Alicji i Bobowi:

Illustration of the Diffie-Hellman Key Exchange

Poniżej znajduje się wyjaśnienie zawierające nieco matematyki:

Najprostsza, oryginalna wersja protokołu wykorzystuje arytmetykę multiplikatywnych grup modulo Szablon:Mvar, gdzie Szablon:Mvar jest liczbą pierwszą, a Szablon:Mvar [[Pierwiastek pierwotny|pierwiastkiem pierwotnym modulo Szablon:Mvar]]. Poniżej przykład, gdzie publicznie znane wartości oznaczono kolorem Szablon:Kolor, a tajne Szablon:Kolor:

Alicja Bob Tajne Publiczne Obliczane Wysyłane Obliczane Publiczne Tajne Szablon:Mvar Szablon:Mvar, Szablon:Mvar Szablon:Mvar,Szablon:Mvar → Szablon:Mvar Szablon:Mvar Szablon:Mvar, Szablon:Mvar, Szablon:Mvar Szablon:MvarSzablon:Mvar mod Szablon:Mvar = Szablon:Mvar Szablon:Mvar → Szablon:Mvar, Szablon:Mvar Szablon:Mvar Szablon:Mvar Szablon:Mvar, Szablon:Mvar, Szablon:Mvar ← Szablon:Mvar Szablon:MvarSzablon:Mvar mod Szablon:Mvar = Szablon:Mvar Szablon:Mvar, Szablon:Mvar, Szablon:Mvar, Szablon:Mvar Szablon:Mvar Szablon:Mvar, Szablon:Mvar Szablon:Mvar, Szablon:Mvar, Szablon:Mvar, Szablon:Mvar Szablon:MvarSzablon:Mvar mod Szablon:Mvar = Szablon:Mvar Szablon:MvarSzablon:Mvar mod Szablon:Mvar = Szablon:Mvar Szablon:Mvar, Szablon:Mvar, Szablon:Mvar, Szablon:Mvar Szablon:Mvar, Szablon:Mvar

1. Alicja i Bob uzgadniają liczbę pierwszą Szablon:Kolor=Szablon:Kolor i podstawę Szablon:Kolor=Szablon:Kolor.
2. Alicja wybiera tajną liczbę całkowitą Szablon:Kolor=Szablon:Kolor, i wysyła Bobowi Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor
3. Bob wybiera tajną liczbę całkowitą Szablon:Kolor=Szablon:Kolor, i wysyła Alicji Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor
4. Alicja oblicza Szablon:Kolor = Szablon:Kolor ^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor
5. Bob oblicza Szablon:Kolor = Szablon:Kolor ^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor
6. Alicja i Bob współdzielą tajną liczbę: Szablon:Kolor = Szablon:Kolor. Jest tak, ponieważ Szablon:Kolor⋅Szablon:Kolor jest tym samym, co Szablon:Kolor⋅Szablon:Kolor. Więc jeśli ktoś znałby jednocześnie obie tajne wartości, mógłby także obliczyć Szablon:Kolor:
   • Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor mod Szablon:Kolor
   • Szablon:Kolor = Szablon:Kolor

Zarówno Alicja, jak i Bob posiadają tę samą wartość tajną, ponieważ $(g^a{)}^b$ oraz $(g^b{)}^a$ są przystające modulo Szablon:Mvar. Zauważmy, że jedynie Szablon:Mvar, Szablon:Mvar i $g^{ab}=g^{ba}modp$ są trzymane w sekrecie. Pozostałe wartości – Szablon:Mvar, Szablon:Mvar, $g^{a}modp$ oraz $g^{b}modp$ – są wysyłane jawnie. Gdy Alicja i Bob obliczą wspólną wartość, mogą użyć jej jako klucza, znanego tylko im, do wysyłania tajnych komunikatów poprzez ten sam otwarty kanał komunikacji. Oczywiście, o wiele większe wartości Szablon:Mvar, Szablon:Mvar i Szablon:Mvar powinny być użyte dla zapewnienia bezpieczeństwa, ponieważ łatwo jest przeprowadzić próbę dla tych kilku możliwych wartości $g^{ab}mod23$ (są tylko 23 wartości do sprawdzenia). Gdy Szablon:Mvar jest liczbą pierwszą długości około 300 cyfr dziesiętnych, a Szablon:Mvar oraz Szablon:Mvar mają po co najmniej 100 cyfr każda, wtedy nawet najlepszy znany obecnie algorytm nie znajdzie Szablon:Mvar mając jedynie Szablon:Mvar, Szablon:Mvar, $g^{b}modp$ i $g^{a}modp,$ nawet przy użyciu całej mocy obliczeniowej dostępnej ludzkości. Problem jest znany jako logarytm dyskretny. Zauważmy Szablon:Mvar nie musi być duże, i w praktyce wybiera się 2 lub 5.

Poniżej bardziej ogólny opis protokołu:

1. Alicja i Bob uzgadniają skończoną grupę cykliczną Szablon:Mvar oraz generator Szablon:Mvar w Szablon:Mvar (to się zwykle odbywa na długo przed pozostałą częścią protokołu; przyjmuje się, że Szablon:Mvar jest znane wszystkim napastnikom). Użyjemy dla grupy Szablon:Mvar notacji multiplikatywnej.
2. Alicja losuje naturalną liczbę Szablon:Mvar i wysyła $g^a$ Bobowi.
3. Bob losuje naturalną liczbę Szablon:Mvar i wysyła $g^b$ Alicji.
4. Alicja oblicza $(g^b{)}^a.$
5. Bob oblicza $(g^a{)}^b.$

Oboje posiadają teraz element $g^{ab},$ który może posłużyć jako tajny klucz.

W celu odszyfrowania wiadomości Szablon:Mvar z szyfrogramu $m{g}^{ab},$ Bob (lub Alicja) muszę najpierw obliczyć $(g^{ab}{)}^{-1}:$

Bob zna $|G|,b$ i $g^a.$ Z wartości konstrukcji grupy Szablon:Mvar, dla każdego Szablon:Mvar w Szablon:Mvar, $x^{|G|}=1.$

Bob oblicza $(g^a{)}^{|G|-b}=g^{a(|G|-b)}=g^{a|G|-ab}=g^{a|G|}{g}^{-ab}=(g^{|G|}{)}^a{g}^{-ab}=1^a{g}^{-ab}=g^{-ab}=(g^{ab}{)}^{-1}.$

Kiedy Alicja wysyła Bobowi szyfrogram $m{g}^{ab},$ Bob używa $(g^{ab}{)}^{-1}$ i odzyskuje wiadomość $m{g}^{ab}(g^{ab}{)}^{-1}=m(1)=m.$

„Karta danych”

Poniżej znajduje się tabela przedstawiająca w uproszczeniu, kto co wie. (Ewa podsłuchuje transmisję z nadzieją uzyskania klucza ustalanego przez Alicję i Boba, nie ma jednak możliwości modyfikacji czy podmiany wysyłanych wiadomości).

• Szablon:Kolor = wspólny klucz tajny. Szablon:Kolor = Szablon:Kolor
• Szablon:Kolor = publiczna podstawa. Szablon:Kolor = Szablon:Kolor
• Szablon:Kolor = publiczna (pierwsza) liczba. Szablon:Kolor = Szablon:Kolor
• Szablon:Kolor = tajna wartość Alicji. Szablon:Kolor = Szablon:Kolor
• Szablon:Kolor = publiczna wartość Alicji. Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor = Szablon:Kolor
• Szablon:Kolor = tajna wartość Boba. Szablon:Kolor = Szablon:Kolor
• Szablon:Kolor = publiczna wartość Boba. Szablon:Kolor = Szablon:Kolor^{Szablon:Kolor} mod Szablon:Kolor = Szablon:Kolor

Alicja wie nie wie Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:Kolor podstawa Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor Szablon:Kolor = Szablon:Kolor

Bob wie nie wie Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:Kolor podstawa Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor Szablon:Kolor = Szablon:Kolor

Ewa wie nie wie Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:Kolor podstawa Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor = Szablon:KolorSzablon:Kolor mod Szablon:Kolor

Uwaga: Powinno być trudno Alicji odgadnąć tajną wartość Boba (i vice versa). Ewa mogłaby bowiem podmienić własną parę wartości, kładąc publiczną wartość Boba w miejsce jej prywatnej, generując w ten sposób fałszywy współdzielony klucz tajny. Następnie mogłaby obliczyć tajną wartość Boba (oraz użyć jej do obliczenia tajnego klucza współdzielonego). Ewa może próbować wybrać parę wartości taką, że łatwo jej będzie obliczyć prywatną wartość Boba.

Uogólnienie na więcej niż dwie strony

Protokół Diffiego-Hellmana nie jest ograniczony do negocjowania klucza jedynie przez dwoje uczestników. W ustalaniu klucza może brać dowolna liczba uczestników, wykonując kolejne iteracje protokołu uzgadniania. W poniższym przykładzie Alicja, Bob i Cezary będą ustalać wspólny klucz. Jak poprzednio, wszystkie operacje są wykonywane mod $p:$

1. Uczestnicy uzgadniają parametry algorytmu: Szablon:Mvar oraz Szablon:Mvar.
2. Uczestnicy tworzą prywatne wartości, nazwane odpowiednio Szablon:Mvar, Szablon:Mvar oraz Szablon:Mvar.

1. Alicja oblicza $g^a$ i wysyła Bobowi.
2. Bob oblicza $(g^a{)}^b=g^{ab}$ i wysyła Cezaremu.
3. Cezary oblicza $(g^{ab}{)}^c=g^{abc}$ i używa jako klucza tajnego.
4. Bob oblicza $g^b$ i wysyła Cezaremu.
5. Cezary oblicza $(g^b{)}^c=g^{bc}$ i wysyła Alicji.
6. Alicja oblicza $(g^{bc}{)}^a=g^{bca}=g^{abc}$ i używa jako klucza tajnego.
7. Cezary oblicza $g^c$ i wysyła Alicji.
8. Alicja oblicza $(g^c{)}^a=g^{ca}$ i wysyła Bobowi.
9. Bob oblicza $(g^{ca}{)}^b=g^{cab}=g^{abc}$ i używa jako klucza tajnego.

Metoda ta wymaga jednak dużej liczby potęgowania modulo Szablon:Mvar.

Dystrybuowanie klucza na więcej uczestników metodą dziel i zwyciężaj

W naszym przykładzie występuje 8 uczestników: A, B, C, D, E, F, G i H. Podzielimy ich na dwie mniejsze grupy:

1. Uczestnicy A, B, C i D, wyznaczają jedną wspólną wartość, $g^{abcd};$ jest ona następnie wysyłana do drugiej grupy – uczestnicy E, F, G i H. W odpowiedzi otrzymują $g^{efgh}.$
2. Uczestnicy A oraz B wyznaczają $g^{efghab},$ która zostaje wysłana do C i D, podczas gdy oni robią to samo i wysyłają $g^{efgh(cd)}$ do A i B.
3. Uczestnik A oblicza $g^{efghcda}$ i wysyła do B. Podobnież czyni B i wysyła do A wartość $g^{efghcdb}.$ C i D czynią podobnie.
4. Uczestnik A wykonuje ostatnią operację, uzyskując tajny klucz $g^{efghcdba}=g^{abcdefgh};$ B oblicza tak samo. Znowu, C i D czynią podobnie.
5. Uczestnicy E, F, G i H jednocześnie wykonują analogiczne operacje, używając $g^{abcd}$ jako wyjściowej wartości.

Bezpieczeństwo

Protokół jest uważany za bezpieczny na ataki podsłuchowe, o ile Szablon:Mvar oraz Szablon:Mvar są wybrane poprawnie. Napastnik (Ewa) musi rozwiązać problem Diffiego Hellmana, by uzyskać Szablon:Mvar^{Szablon:MvarSzablon:Mvar}. Obecnie uważa się to za trudne. Efektywny algorytm rozwiązywania problemu logarytmu dyskretnego uczyniłby łatwym do obliczenia Szablon:Mvar lub Szablon:Mvar i rozwiązania problemu Diffiego-Hellmana, czyniąc ten oraz wiele innych schematów klucza publicznego bezużytecznymi.

Rząd grupy Szablon:Mvar powinien być liczbą pierwszą, lub posiadać duży czynnik pierwszy. Zapobiegnie to użyciu algorytmu Pohlinga-Hellmana do uzyskania Szablon:Mvar lub Szablon:Mvar. Z tego powodu liczba pierwsza Sophie Germain Szablon:Mvar jest czasami używana do obliczenia $p=2q+1,$ nazywanej „bezpieczną liczbą pierwszą”, gdyż rząd Szablon:Mvar jest wtedy podzielny jedynie przez 2 i przez Szablon:Mvar. Szablon:Mvar jest natomiast wybierane spośród generatorów podgrupy Szablon:Mvar rzędu Szablon:Mvar, zamiast całej Szablon:Mvar. To powoduje, że symbol Legendre’a Szablon:Mvar^Szablon:Mvar nie mówi nic o parzystości Szablon:Mvar.

Jeśli Alicja i Bob używają generatora liczb losowych, którego wyjście nie jest całkiem losowe i wyniki mogą być przewidywane w pewnym stopniu, to zadanie Ewy jest dużo łatwiejsze.

Tajne wartości Szablon:Mvar i Szablon:Mvar są porzucane po zakończeniu sesji. Stąd algorytm spełnia trywialnie warunek doskonałej tajności.

W oryginalnej koncepcji protokół Diffiego-Hellmana nie zapewnia uwierzytelniania uczestników, stąd jest podatny na atak Szablon:K. Osoba w środku ustanawia dwie sesje protokołu, podając się Alicji za Boba, a Bobowi za Alicję. Pozwala to jej odszyfrowywać (a także odczytywać i zapisywać) i reszyfrowywać wiadomości wysyłane między nimi. Do zapobieżenia tego typu atakowi niezbędna jest wykorzystanie innego algorytmu uwierzytelniającego. W tym celu również mogą zostać użyte inne warianty protokołu Diffiego-Hellmana (np. Szablon:Link-interwiki).

Inne zastosowania

Ustalanie klucza z uwierzytelnianiem

Gdy Alicja i Bob współdzielą hasło, mogą użyć protokołu Szablon:Link-interwiki (Password-Authentification Key Agreement) – forma protokołu zabezpieczająca przed atakami Szablon:K. Prosty schemat polega na wykorzystaniu Szablon:Mvar jako hasła. Korzyść jest taka, że napastnik może próbować odgadnąć hasło tylko raz dla każdej strony. To sprawia, że system jest dobrze zabezpieczony przy relatywnie słabych hasłach dostępu. To podejście zostało opisane w zaleceniu ITU-T X.1035 i znajduje zastosowanie w zabezpieczeniu sieci domowych w standardzie G.hn.

Klucz publiczny

Jest możliwym użycie protokołu Diffiego-Hellmana jako części infrastruktury klucza publicznego. Klucz publiczny Alicji to $(g^{a}modp,g,p).$ Aby wysłać wiadomość, Bob wybiera losowe Szablon:Mvar i wysyła Alicji $g^{b}modp$ (niezaszyfrowane) razem z wiadomością zaszyfrowaną kluczem symetrycznym $(g^a{)}^{b}modp.$ Tylko Alicja jest w stanie odszyfrować wiadomość, ponieważ tylko ona zna Szablon:Mvar. Wykorzystanie klucza publicznego zapobiega także atakom Szablon:K.

W praktyce, protokół Diffiego-Hellmana nie jest używany w ten sposób, z racji wykorzystania algorytmu RSA do podpisywania i weryfikacji certyfikatów. Protokół Diffiego-Hellmana nie może także zostać użyty do podpisywania certyfikatów, pomimo że algorytmy podpisywania ElGamal i DSA są z nim powiązane. Jednakże jest wykorzystywany w algorytmach Szablon:Link-interwiki, Szablon:Link-interwiki oraz IKE – składowej stosu protokołów IPsec zabezpieczającego komunikację IP.

Zobacz też

• arytmetyka modularna
• ElGamal
• kryptografia klucza publicznego
• kryptografia krzywych eliptycznych
• Secure Remote Password
• wymiana klucza