Kryptografia krzywych eliptycznych: Szybko do przodu, Trudnie wstecz

Krzywa, ciało i zasada geometrycznego dodawania

Elipsa krzywa używana w kryptografii to zbiór punktów (x, y) spełniających równanie y² = x³ + ax + b, które jest oceniane nie przez liczby rzeczywiste, lecz w ciele skończonym liczb całkowitych modulo dużą liczbę pierwszą p – więc "krzywa" to naprawdę skończony zbiór par dyskretnych (x, y) oraz jeden dodatkowy punkt na nieskończenie oddalonym, który działa jako element neutralny. Użyteczność tej krzywej dla kryptografii wynika z faktu, że ten skończony zbiór punktów może być wyposażony w strukturę grupy: istnieje dobrze zdefiniowany sposób "dodawania" dwóch punktów na krzywej i uzyskania trzeciego punktu również leżącego na krzywej.

Dodawanie punktów: cięć i styczna, nad skończonym ciałem

Geometrycznie (łatwiej to sobie wyobrazić na płaszczyźnie zespolonej przed redukcją mod p): aby dodać dwa różne punkty P i Q, narysuj prostą przez nie, znajdź jej trzecie przecięcie z krzywą i odbij ten punkt względem osi x, aby otrzymać P + Q. Aby dodać punkt do samego siebie (podwojenie), użyj stycznej do tego punktu zamiast cięcia. W każdym kroku arytmetyka modulo p zastępuje arytmetykę liczb rzeczywistych, ale wzory algebraiczne są takie same:

Podwojenie P = (x, y), P ≠ O, y ≠ 0: λ = (3x² + a) / (2y) mod p x³ = λ² - 2x mod p y³ = λ(x - x³) - y mod p

Dodawanie P=(x1,y1), Q=(x2,y2), x1 ≠ x2: λ = (y2 - y1) / (x2 - x1) mod p x³ = λ² - x1 - x2 mod p y³ = λ(x1 - x³) - y1 mod p Dzielenie tutaj oznacza mnożenie przez odwrotność modularną, obliczoną przy użyciu rozszerzonego algorytmu Euklidesa; każdy krok zachodzi w skończonym ciele i zamkniętość tego ciała pod działaniami jest tym, co gwarantuje, że P + Q zawsze wraca na krzywą, nigdy z niej odpływa.

doubling P = (x, y), P ≠ O, y ≠ 0:
  λ = (3x² + a) / (2y)   mod p
  x3 = λ² − 2x        mod p
  y3 = λ(x − x3) − y   mod p

adding P=(x1,y1), Q=(x2,y2), x1 ≠ x2:
  λ = (y2 − y1) / (x2 − x1)   mod p
  x3 = λ² − x1 − x2         mod p
  y3 = λ(x1 − x3) − y1          mod p

Iloczyn skalarny: łatwy kierunek

Klucz prywatny jest przypadkową liczbą całkowitą k; odpowiadający mu klucz publiczny to punkt kG — punkt początkowy G dodany do siebie k razy — obliczony wydajnie za pomocą podwojenia i dodawania: aby obliczyć kG, zapisz k w systemie binarnym i, skanując bity, wielokrotnie podwajaj bieżący punkt i dodawaj G, gdybie aktualny bit był równy 1. Zajmuje to tylko około log₂(k) podwójnych i operacji dodawania, więc nawet klucz prywatny o długości 256 bitów wymaga jedynie kil sta dobrych punktów, a każdy z nich jest sam w sobie tylko kilkoma mnożeniami modularnymi — wystarczająco szybki, aby uruchomić na karcie smart.

double_and_add(k, G):
  R = O                      // point at infinity, the identity
  for bit in binary(k), most significant first:
    R = R + R                // double
    if bit == 1: R = R + G   // add
  return R                   // = kG, computed in O(log k) steps

Dlaczego jego odwracanie jest trudne: problem logarytmu dyskretnego

Rozwiązanie k, dane G i publiczny klucz Q = kG, to Problem Logarytmu Dyskretnego na Krzywej Eliptycznej (PLDE), a żaden znany algorytm nie rozwiązuje go szybciej niż mniej więcej √p kroków dla krzywej wybranej nad polem o rozmiarze p (najlepsze ogólne ataki, takie jak Pollard's rho, działają w czasie proporcjonalnym do pierwiastka kwadratowego z porządku grupy). W przeciwieństwie do tego, zwykła potegowanie modularna, którego problem logarytmiczny dyskretny jest analogiczny, podpada pod ataki o złożoności sub-wykładową w zakresie indeksowania; grupy krzywych eliptycznych nie mają znanych odpowiedników skrótów, co właśnie powoduje, że klucz eliptyczny o rozmiarze 256 bitów oferuje mniej więcej taką samą praktyczną ochronę jak klucz RSA o rozmiarze 3072 bity — mniejsze klucze, szybsze operacje, dla tego samego poziomu odporności na ataki.

Co właściwie robi ECC

ECDH (Elliptic Curve Diffie-Hellman) umożliwia dwóm stronom wymianę jedynie publicznych punktów, kG i jG, a następnie niezależne obliczenie tego samego sekretu współdzielonego kjG bez konieczności przesyłania k lub j, zabezpieczając transfer klucza w niemal każdej nowoczesnej połączeniu HTTPS. ECDSA (Elliptic Curve Digital Signature Algorithm) wykorzystuje ten sam trudny do odwrócenia mnożnik skalarny, aby osoba posiadająca prywatny klucz k mogła wygenerować podpis, który każdy z publicznym kluczem kG może zweryfikować, ale nikt bez k mógłby go wygenerować – mechanizm leży u podstaw Bitcoinowych transakcji i weryfikacji certyfikatów TLS.

Oba opierają się na tym samym asymetrycznym zachowaniu, które obserwujemy w symulacji: szybkie jest poruszanie się po krzywej k razy, ale ustalenie wartości k z miejsca lądowania nie jest możliwe.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Elliptic Curve Cryptography i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.