Wymiana kluczy Diffiego-Hellmana
Jak dwie osoby, które nigdy się nie spotkały, mogą uzgodnić tajny klucz, gdy ktoś słucha każdego ich słowa? W 1976 roku Whitfield Diffie i Martin Hellman znaleźli odpowiedź, która dziś chroni niemal każde bezpieczne połączenie w internecie. Prześledź z Alice i Bobem pięć kroków, raz jako mieszanie farb, a raz na prawdziwych liczbach, a potem pozwól podsłuchującej Eve zaatakować: przy małych liczbach wygrywa w mgnieniu oka, przy rozmiarach stosowanych w praktyce potrzebowałaby więcej czasu, niż wynosi wiek wszechświata. Naciśnij „Następny krok”, aby śledzić, jak Alice i Bob uzgadniają sekret, podczas gdy Eve czyta wszystko, co wysyłają; „Wstecz” cofa o jeden krok. Każda wartość jest pokazana jako farba i jako liczba. Zablokowane wartości nigdy nie opuszczają właściciela. Wybierz po prawej większą liczbę pierwszą lub inne sekrety albo naciśnij „Nowe sekrety”. W ostatnim kroku przycisk „Niech Eve zaatakuje” sprawia, że Eve próbuje każdego wykładnika, aż któryś pasuje: łatwe dla małych liczb pierwszych, beznadziejne dla prawdziwych.
Jak to działa
- Naciśnij „Następny krok”, aby prześledzić wymianę: publiczne ustalenia, sekrety, wiadomości i wspólny wynik.
- Obserwuj każdą wartość jako farbę i jako liczbę i zobacz, które pozostają prywatne, a które Eve może odczytać.
- W ostatnim kroku naciśnij „Niech Eve zaatakuje”, potem wybierz większą liczbę pierwszą i zobacz, jak szybko jej szanse znikają.
Jak działa wymiana
Alice i Bob najpierw publicznie uzgadniają liczbę pierwszą p i liczbę g. Następnie każde z nich wybiera tajną liczbę, a dla Alice i b dla Boba, i zachowuje ją dla siebie. Alice wysyła Bobowi A = gᵃ mod p, a Bob wysyła Alice B = gᵇ mod p. Na koniec Alice oblicza Bᵃ mod p, a Bob oblicza Aᵇ mod p. Oba wyniki są równe g do potęgi a·b mod p, więc oboje mają teraz wspólną liczbę, która nigdy nie przeszła przez łącze. Eve, która widziała p, g, A i B, nie ma takiego skrótu.
Dlaczego Eve jest bezradna
Obliczenie gᵃ mod p jest szybkie, nawet dla liczb o setkach cyfr, dzięki wielokrotnemu podnoszeniu do kwadratu. Droga powrotna, czyli znalezienie wykładnika a na podstawie wyniku, to problem logarytmu dyskretnego, a dla dobrze dobranych liczb pierwszych nie jest znana żadna szybka metoda. Dla małych liczb pierwszych w tym demo Eve może po prostu wypróbować każdy wykładnik; aplikacja liczy jej próby i szacuje, ile trwałoby pełne przeszukanie. Każdy dodatkowy bit liczby pierwszej podwaja pracę, więc 2048-bitowe liczby pierwsze używane w internecie stawiają atak siłowy daleko poza zasięgiem. Wersja z farbami oddaje tę samą ideę: mieszanie kolorów jest łatwe, ale rozdzielenie mieszaniny z powrotem na kolory jest praktycznie niemożliwe.
Często zadawane pytania
Dlaczego analogia z farbami działa?
Mieszanie farb jest łatwe i nie da się go cofnąć, tak jak podniesienie g do potęgi mod p jest łatwe do wykonania i trudne do odwrócenia. Alice i Bob dodają każde swój tajny kolor do wspólnego koloru i wymieniają się mieszaninami; potem każde dodaje swój tajny kolor do otrzymanej mieszaniny. Oboje kończą ze wspólnym kolorem i oboma sekretami, a Eve widzi tylko dwie mieszaniny dwóch kolorów i nie potrafi ich rozdzielić. Farby miesza się tu w równych częściach, więc kolejność nie ma znaczenia, tak jak (gᵃ)ᵇ = (gᵇ)ᵃ.
Czym jest g i dlaczego musi być pierwiastkiem pierwotnym?
g jest generatorem: jego potęgi g¹, g², …, g^(p−1) mod p przebiegają wszystkie liczby od 1 do p − 1. Dzięki temu wartości publiczne rozkładają się na wszystkie możliwości, więc Eve dowiaduje się z nich jak najmniej. Aplikacja wybiera dla każdej liczby pierwszej najmniejszą taką liczbę, na przykład g = 5 dla p = 23.
Czy Diffie-Hellman szyfruje moje wiadomości?
Nie. Służy tylko do uzgodnienia wspólnego sekretu. Ten sekret jest następnie używany jako klucz szybkiego szyfru symetrycznego, takiego jak AES, który szyfruje właściwe dane. Tak działa każde połączenie HTTPS: wymiana kluczy, zwykle na krzywych eliptycznych, a po niej szyfrowanie symetryczne.
Czy Eve może podszyć się pod Boba?
Przy samej wymianie – tak. Pośrednik (man in the middle) mógłby przeprowadzić jedną wymianę z Alice, a drugą z Bobem i przekazywać wszystko dalej. Prawdziwe protokoły zapobiegają temu, wymagając od serwera udowodnienia tożsamości podpisem cyfrowym i certyfikatem, dzięki czemu wymiana jest uwierzytelniona.
Czy coś jest wysyłane na serwer?
Nie. Wszystkie liczby, mieszanie farb i atak Eve są obliczane w twojej przeglądarce, a twoje ustawienia pozostają w pamięci lokalnej tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora