Na czym polega wymiana kluczy Diffiego-Hellmana
Przez tysiące lat wysłanie tajnej wiadomości oznaczało, że najpierw trzeba było przekazać tajny klucz osobiście lub przez kuriera. W 1976 roku dwóch badaczy ze Stanfordu pokazało, że dwie strony mogą stworzyć wspólny klucz z niczego, wymieniając wiadomości na oczach wszystkich. Ten pomysł otworzył erę kryptografii klucza publicznego i wciąż działa za każdym razem, gdy przeglądarka pokazuje kłódkę.
Problem dystrybucji kluczy
Szyfr taki jak AES jest tak bezpieczny jak jego klucz, a obie strony potrzebują tego samego klucza. Przed 1976 rokiem klucz trzeba było dostarczyć potajemnie: pocztą dyplomatyczną, przez zaufanego kuriera albo w wydrukowanych wcześniej książkach kodów. Dla dwóch nieznajomych, którzy chcą bezpiecznie porozmawiać od razu, na przykład sklepu i klienta w internecie, jest to niemożliwe. Praca Whitfielda Diffiego i Martina Hellmana „New Directions in Cryptography” rozwiązała ten problem metodą, która w ogóle nie wymaga wcześniejszego sekretu.
Arytmetyka na tarczy zegara
Wymiana wykorzystuje arytmetykę modularną: obliczenia na zegarze o p godzinach, gdzie p jest dużą liczbą pierwszą. Potęgi na takim zegarze zachowują się niezwykle. Jeśli g jest pierwiastkiem pierwotnym, liczby g, g², g³, … mod p skaczą po tarczy i odwiedzają każdą godzinę od 1 do p − 1, zanim zaczną się powtarzać, w kolejności, która wygląda na losową. Obliczenie gᵃ mod p jest szybkie i wymaga mniej więcej tylu mnożeń, ile cyfr binarnych ma a. Odwrócenie tego – nie.
Wymiana krok po kroku
Alice i Bob jawnie uzgadniają p i g. Alice wybiera sekret a i wysyła A = gᵃ mod p; Bob wybiera sekret b i wysyła B = gᵇ mod p. Alice oblicza Bᵃ = (gᵇ)ᵃ, a Bob oblicza Aᵇ = (gᵃ)ᵇ, oba mod p. Ponieważ kolejność wykładników nie ma znaczenia, oboje otrzymują g^(ab) mod p. W klasycznym małym przykładzie p = 23, g = 5, a = 6 i b = 15 Alice wysyła 8, Bob wysyła 19, a oboje dochodzą do wspólnego sekretu 2.
Problem logarytmu dyskretnego
Eve widzi p, g, A i B. Gdyby potrafiła znaleźć a na podstawie A = gᵃ mod p, mogłaby obliczyć sekret tak samo jak Alice. To jest problem logarytmu dyskretnego. Najlepsze znane algorytmy klasyczne, takie jak sito ciała liczbowego, są znacznie szybsze niż wypróbowywanie każdego wykładnika, ale wciąż potrzebują czasu, który rośnie szybciej niż jakakolwiek potęga liczby cyfr. Przy liczbach pierwszych o długości 2048 bitów problem jest poza zasięgiem każdego istniejącego komputera. Nie wiadomo, czy możliwe jest coś szybszego, a bezpieczeństwo wymiany opiera się na przekonaniu, że nie.
Atak man-in-the-middle
Diffie-Hellman chroni przed podsłuchującym, ale nie przed oszustem. Mallory, siedząc między Alice a Bobem, może przeprowadzić osobną wymianę z każdym z nich i przekazywać wiadomości dalej, czytając wszystko. Obroną jest uwierzytelnianie: w HTTPS serwer podpisuje swoją część wymiany kluczem poświadczonym przez zaufany urząd certyfikacji, więc przeglądarka wie, że naprawdę rozmawia z właściwą witryną. Wymiana kluczy i podpisy zawsze idą w parze.
Kto to wymyślił?
Diffie i Hellman opublikowali metodę w 1976 roku, opierając się na pomysłach Ralpha Merkle’a – Hellman poprosił później, by także jemu przypisywano zasługę. W 1997 roku brytyjska agencja wywiadowcza GCHQ ujawniła, że jej matematycy byli pierwsi: James Ellis wpadł na pomysł kryptografii klucza publicznego w 1970 roku, Clifford Cocks znalazł system podobny do RSA w 1973 roku, a Malcolm Williamson odkrył tę samą wymianę kluczy w 1974 roku – wszystko to utrzymywano w tajemnicy przez ponad dwadzieścia lat.
Diffie-Hellman dziś
Współczesne połączenia używają przeważnie wymiany Diffiego-Hellmana na krzywych eliptycznych, która daje to samo bezpieczeństwo przy znacznie krótszych liczbach, na przykład krzywej X25519 w TLS 1.3, Signal i WhatsApp. Używanie nowej pary sekretów dla każdego połączenia zapewnia utajnianie z wyprzedzeniem (forward secrecy): nawet jeśli długoterminowy klucz serwera zostanie później skradziony, wcześniejsze rozmowy pozostaną bezpieczne. Słabe parametry wciąż są zagrożeniem, co w 2015 roku pokazał atak Logjam na stare 512-bitowe liczby pierwsze, a duży komputer kwantowy z algorytmem Shora złamałby zarówno klasyczną, jak i eliptyczną wersję Diffiego-Hellmana, dlatego obok nich wdraża się teraz postkwantowe metody wymiany kluczy.
Wypróbuj
Otwórz wizualizację Diffiego-Hellmana, aby prześledzić pięć kroków na tablicy pokazującej, co wiedzą Alice, kanał publiczny i Bob, jako farby i jako liczby. Wybieraj liczby pierwsze od 23 do 2 147 483 647, ustaw własne sekrety i pozwól Eve zaatakować, próbując każdego wykładnika: zobacz, jak od razu wygrywa przy małych liczbach pierwszych i jak szacowany czas przeszukiwania rośnie, gdy liczba pierwsza się wydłuża.
Często zadawane pytania
Czy Diffie-Hellman to to samo co RSA?
Nie, choć oba są metodami klucza publicznego z lat 70. XX wieku. RSA, opublikowany w 1977 roku, potrafi szyfrować i podpisywać za pomocą klucza publicznego i prywatnego i opiera się na trudności rozkładu dużych liczb na czynniki. Diffie-Hellman służy tylko do uzgodnienia wspólnego sekretu i opiera się na problemie logarytmu dyskretnego.
Jak duże są liczby w praktyce?
Klasyczny Diffie-Hellman używa liczb pierwszych o długości co najmniej 2048 bitów, czyli około 617 cyfr dziesiętnych, a często 3072 lub 4096 bitów. Wersje na krzywych eliptycznych używają kluczy około 256-bitowych przy porównywalnym bezpieczeństwie.
Dlaczego każdy dodatkowy bit podwaja pracę Eve?
Liczba pierwsza o jeden bit dłuższa jest mniej więcej dwa razy większa, więc wykładników do wypróbowania jest mniej więcej dwa razy więcej. Prawdziwe ataki są sprytniejsze niż sprawdzanie każdego wykładnika, ale ich koszt i tak rośnie bardzo szybko wraz z rozmiarem liczby pierwszej.
Dlaczego Alice i Bob potrzebują liczby pierwszej?
Przy module będącym liczbą pierwszą każda liczba od 1 do p − 1 ma odwrotność i istnieją pierwiastki pierwotne, więc potęgi g obejmują wszystkie możliwości. Często wybiera się bezpieczne liczby pierwsze, dla których (p − 1)/2 też jest liczbą pierwszą, aby wykluczyć skróty korzystające z małych dzielników p − 1.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Otwórz wizualizację Diffiego-Hellmana