Elliptic Curve Diffie-Hellman: Zmiana Klucza na Krzywej

Co to jest rzeczywiście krzywa eliptyczna?

Krzywa eliptyczna używana w kryptografii nie jest elipsą. Jest to zbiór punktów spełniających równanie postaci y do kwadratu równe x do sześcianu plus a razy x plus b, oceniane nad polem skończonym zamiast nad zwykłymi liczbami rzeczywistymi. Pole skończone oznacza, że arytmetyka jest wrogą modulo pewnej dużej liczby pierwszej, więc krzywa to rzeczywiście skończona siatkę dyskretnych punktów, a nie gładka kontynuowana forma, choć pomaga zilustrować ją jako gładką krzywą. Każda poprawna kombinacja współrzędnych x i y spełniających to równanie, plus jeden dodatkowy specjalny punkt nazywany punktem nieskończonościowym, tworzy zbiór punktów krzywej. Punkt nieskończonościowy działa jako element neutralny, odgrywając rolę taką jak zero w zwykłej dodawaniu. Protokole kryptograficzne wybierają konkretne standardowe krzywe, razem z określonym punktem początkowym na tych krzywych nazywanym generatorem, często oznaczanym jako G. Popularne wyborze to krzywe nazwane P-256, Curve25519 i secp256k1, każda zdefiniowana przez określone stałe a, b oraz określony rozmiar pola pierwszego. bezpieczeństwo wszystkiego opartego na krzywej zależy od rozmiaru tego podstawowego pola i braku znanych słabości strukturalnych. To, co sprawia, że te krzywe są przydatne w kryptografii, to to, że ich punkty mają wbudowaną zasady dodawania geometrycznego, które przekształca zbiór punktów na matematyczną grupę. Struktura tej grupy umożliwia zdefiniowanie i obliczenie efekcji mnożenia skalarowego, równoważnego potęgowaniu w przypadku krzywych eliptycznych. Wszystko, co nastąpi od generowania par kluczowych do wyznaczania wspólnego sekretu, opiera się na jednym pojęciu: punkty na odpowiednio wybranej krzywej można łączyć za pomocą dobrze zdefiniowanej operacji dodawania, a ta operacja zachowuje wystarczająco przewidywalny charakter, aby umożliwić budowę pełnego protokołu kryptograficznego na jej podstawie, choć jest wystarczająco nieprzewidywalna, że odwrotna operacja dodawania wielokrotnych razy jest obliczeniowo niewykonalna dla obserwatora z zewnątrz.

Dodawanie punktów: Geometriczny Motyw

Dodawanie dwóch różnych punktów P i Q na krzywej ma elegancką opis geometriczny przed tym, jak staje się puro algebra. Aby dodać te dwa punkty, wyobraź sobie rysowanie prostej przechodzącej przez oba punkty. Z powodu sześciennego równania krzywej, ta prosta przecina krzywą dokładnie w jednym dodatkowym punkcie. Odbijanie tego trzeciego punktu przecięcia symetrycznie względem osi poziomej daje wynik, nazywany P plus Q. Podwójne dodawanie pojedynczego punktu P oznacza obliczenie P plus P, co działa podobnie, ale używa prostej styczennej w punkcie P zamiast prostej przechodzącej przez dwa oddzielne punkty, znów znajdując miejsce, gdzie ta styczna przecina krzywą drugi raz i odbijając wynik. W przypadku liczb rzeczywistych wszystko to ma fizyczną ilustrację z liniami i krzywymi; nad polem skończonym te same formuły algebraiczne są stosowane, tylko z koordynatami obliczonymi przy użyciu arytmetyki modularnej zamiast zwykłej arytmetyki, więc geometriczna ilustracja staje się modelem mentalnym zamiast czegoś, co można rzeczywiście narysować. Krytycznie, ta operacja dodawania jest zamknięta, co oznacza, że dodanie dwóch punktów na krzywej zawsze daje inny punkt na krzywej, a przestrzega tych samych zasad associative i komutatywnych, które regularne dodawanie podlega. To dokładnie pozwala na spójne powtarzane dodawanie punktu do siebie, napisane jako mnożenie skalarny, niezależnie od sposobu grupowania lub kolejności dodawań. Specjalne przypadki uzupełniają definicję: dodanie punktu do punktu w nieskończoności zwraca ten sam punkt bez zmian, a dodanie punktu do jego własnej odbicia symetrycznego względem osi poziomej, nazywanego odwrotnością, daje punkt w nieskończoności. Te zasady razem sprawiają, że zbior punktów na krzywej, połączony z tą operacją dodawania, tworzy matematyczną grupę, to samo struktura, która całkowite liczby modulo pierwsza tworzą pod mnożeniem w klasycznym Diffie-Hellman, ale zbudowaną z geometrii zamiast arytmetyki potęgowania.

Mnożenie skalarny i metoda dodawania-duplikacji

Mnożenie skalarny polega na wybraniu punktu P oraz liczby całkowitej k, a następnie obliczeniu punktu osiągającego poprzez dodanie P do siebie k razy, co jest zapisane jako k razy P. Dodawanie P jeden raz po drugim byłoby niepraktycznie wolne dla wielu wartości k używanych w kryptografii, które mogą mieć setki bitów długości. Praktycznym rozwiązaniem jest algorytm dodawania-duplikacji, który jest bezpośrednim odpowiednikiem techniki mnożenia i potęgowania szybkiego użytej do szybkiego potegowania modularnego w klasycznym Diffie-Hellman. Algorytm sprawdza reprezentację binarną liczby k i przetwarza ją bit po bitu, powtarzając dodawanie punktu do siebie (duplikowanie) oraz dodawanie punktu bazowego P wtedy, gdy bieżący bit jest równy jedynce. Ponieważ mnożenie punktu przez dwa razy zajmuje około tyle samo czasu jak dodawanie dwóch różnych punktów, a liczba bitów w k rosnie tylko logarytmicznie z jej długością, algorytm dodawania-duplikacji oblicza k razy P używając około tylu operacji ile ma bitów k, zamiast k osobnych dodawań. Dla skalaru o 256 bitach to znaczy około kilku setek operacji punktowych zamiast niepraktycznie duży liczbę indywidualnych dodawania, co sprawia, że mnożenie skalarny jest praktyczne nawet na małych systemach sprzętowych. Ta efektywność jest to, co pozwala elliptic curve key generation i wymiana kluczy być wystarczająco szybkie do codziennego użytku w przeglądarkach, aplikacjach mobilnych i protokołach sieciowych. Elegancja metody dodawania-duplikacji polega na tym, że dokładnie odzwierciedla sposób, w jaki ludzie obliczają duże potęgi efektywnie poprzez powtarzane kwadraty, tylko przetłumaczonej na język dodawania punktów. Szybkość w kierunku przodu jest kluczowa, ponieważ obie strony w ECDH muszą regularnie wykonywać mnożenie skalarny, ale jak wyjaśnia kolejna sekcja, ta sama szybkość nie rozszerza się na nikogo próbującego odwrotnie przeanalizować wyniku do pierwotnego skalaru.

Problem dyskretnego logarytmu eliptycznego

Cała bezpieczność ECDH opiera się na jednej asymetrii: podanym punkcie bazowemu G i skalarze k, obliczenie wynikowego punktu Q, równego k razy G, jest szybkie, ale dany tylko G i Q, odtworzenie skalarza k uważane jest za obliczeniowo niemożliwe do rozwiązania dla dobrze wybranych krzywych i wystarczających rozmiarów pola. To nazywa się problemem dyskretnego logarytmu eliptycznego, często skrócone jako ECDLP, a odgrywa on tą samą strukturalną rolę, jak problem dyskretnego logarytmu klasycznego w tradycyjnym Diffie-Hellmanie nad polem pierwszym. Kluczowa różnica polega na tym, jak trudne są te problemy w stosunku do rozmiaru liczb, które one obejmują. Najlepsze znane algorytmy dla rozwiązywania problemu dyskretnego logarytmu klasycznego nad poliem pierwszym działają w czasie pod-eksponencjalnym, co oznacza, że są szybsze niż brute force, ale nadal wolne, co zmusza do użycia bardzo dużych liczb pierwszych, zwykle około trzech tysięcy i siedemdziesięciu dwóch bitów, aby pozostawać bezpiecznymi. Najlepsze znane ogólne algorytmy dla rozwiązywania problemu dyskretnego logarytmu eliptycznego, na odwrót, działają w pełni eksponencjalnym czasie względem rozmiaru pola, bez znanych skrótu podobnego do ataków sub-eksponencjalnych, które działają przeciwko klasycznemu problemowi. Ta silniejsza gwarancja trudności oznacza, że mniejsze pole eliptyczne, zwykle około dwustu pięćdziesięciu sześciu bitów, zapewnia podobną odporność na atak. Przysłuchujący, który zablokował zarówno publiczne punkty wymienione podczas ECDH, widzi G i oba publiczne punkty stron, co oznacza, że widzi Q jeden i Q dwa, ale wydzielanie żadnego z prywatnych skalarnych z tych informacji wymaga rozwiązania ECDLP, problemu dla którego nie znane jest żaden efektywny algorytm nawet przy duzych zasobach obliczeniowych. To rozbieżność między łatwym przodu a trudnym odwracaniem jest dokładnie tym, co konwertuje proste arytmetykę punktów na zaufany element kryptograficzny.

Pchnięcie rąk i dlaczego mniejsze klucze są ważne

Podsumowując, pchnięcie rąk ECDH rozgrywa się w kilku prostych krokach. Obie strony z góry ustalają wspólną krzywą i punkt bazowy G, które są publiczne i standardowe. Każda strona potem losowo wybiera skalar prywatny, pełniąc rolę klucza prywatnego: oznaczmy go jako skalar A dla pierwszej strony i skalar B dla drugiej. Każdy oblicza swój własny punkt publiczny mnożąc punkt bazowy przez swój własny skalar, dając punkt publiczny A równy skalar A razy G, a punkt publiczny B równy skalar B razy G. Obie strony wymieniają te punkty publiczne otwarcie, nawet poprzez kanał, który atakujacy może obserwować. Ostatecznie każda strona mnoży punkt publiczny drugiej strony przez swój własny skalar prywatny. Pierwsza strona oblicza skalar A razy punkt publiczny B, a druga strona oblicza skalar B razy punkt publiczny A. Ponieważ mnożenie skalarnego jest asocjatywne i komutatywne w podstawowej grupie, obie obliczenia są równe skalarowi A razy skalar B razy G, co oznacza, że obie strony docierają do dokładnie tego samego wspólnego sekretu bez wysyłania swoich skalarnych kluczy prywatnych. Ten punkt wspólny, lub wartość wywodząca się z jego współrzędnych poprzez funkcję wygenerowania klucza, staje się symetryczny klucz używany do dalszej komunikacji szyfrowanej. Praktyczne korzyści wynikające z wybierania krzywych nad polami pierwszymi polegają na rozmiarze: 256-bitowy klucz krzywej elliptycznej oferuje bezpieczenstwo porównywalne z 3072-bitowym kluczem Diffie-Hellmana nad poliem skończonym, co przekłada się na mniejsze komunikaty, szybsze generowanie kluczy, mniej pamięci i wykorzystanie CPU oraz niższy zużycie energii. Ta zalety efektywności są dokładnie tym, dla czego ECDH, a nie klasyczne Diffie-Hellmana, służy jako podstawa wymiany kluczy w współczesnych połączeniach TLS i HTTPS, protokolu Signal używanym w aplikacjach do bezpiecznej komunikacji, oraz protokołu WireGuard, który jest protokołem prywatnego sieci wirtualnej, wszystko to zależy od szybkiego, lighweight i powtarzalnego zgadzania się na klucz.

Często zadawane pytania