Krzywe eliptyczne w kryptografii

Tak zwana "kryptografia krzywych eliptycznych" to bardzo modne i popularne pojęcie, które rzeczywiście jest ważne, ale - niestety - o którym mówi się najczęściej niezwykle powierzchownie, bez wchodzenia w "detale matematyczne". Niniejszy artykuł próbuje pójść takiemu podejściu pod prąd - chcemy w elementarny sposób objaśnić, o co tak naprawdę chodzi z tymi krzywymi eliptycznymi.

1. Bestiariusz algebraika

Wybierzmy i ustalmy sobie jakąś liczbę pierwszą $p,$ na przykład $|13.$ Na początku będziemy zajmować się zbiorem:

F13 = {0,1,2,...,12} (ogólniej: Fp = {0,1,2,...,p − 1}).

W tym zbiorze wykonywać będziemy działania dodawania i mnożenia, ale nie klasycznie, lecz zgodnie z arytmetyką modulo, czyli po prostu reszt z dzielenia. To znaczy, w naszym świecie będziemy mieli:

5+ 10 = 2 czy 4⋅7 = 2.

Co ciekawe, w tak dziwacznej strukturze zaskakująco wiele własności zwykłych liczb rzeczywistych jest zachowanych. Znane jeszcze ze szkoły podstawowej prawa łączności, przemienności czy rozdzielności mnożenia względem dodawania są prawdziwe także w $|F13$ z działaniami modulo. Możemy nawet sensownie określić odejmowanie i dzielenie jako operacje odwrotne do (odpowiednio) dodawania i mnożenia. Przykładowo określmy:

a b = x wtedy i tylko wtedy, gdy b ⋅x = a.

Możemy łatwo sprawdzić, że - przy powyższej definicji - zachodzi $|8 3 = 7$ czy $|7 5 = 4.$ Więcej, okazuje się, że jeśli tylko nie próbujemy dzielić przez $|0,$ to wynik zawsze istnieje i to jednoznaczny.

Pójdźmy krok dalej i zacznijmy badać równania w świecie $F . 13$ Zapytajmy chociażby o rozwiązania następującego równania kwadratowego:

2 x +3x + 8 = 0.

Możemy sprawdzić, że rozwiązania są dokładnie dwa: $3$ oraz $7.$ Ba, działają nawet klasyczne wzory z deltą, o ile tylko określimy sensownie pierwiastkowanie modulo.

Oczywiście, ma sens pytanie o zbiory, których definicja kojarzy nam się z obiektami klasycznej geometrii. Chociażby popatrzmy na zbiór:

O = {(x,y) ∈ F13 ×F13 x2 + y2 = 9}.

Możemy po prostu obliczyć, że

O = {(0, 3),(0,10),(3,0),(5,6), (5,7),(6, 5),(6,8),(7,5),(7,8),(8,6),(8,7),(10, 0)},

a otrzymany zbiór $|O$ nazwać okręgiem nad $|F13,$ choć to przecież żaden prawdziwy okrąg, a tylko 12 punktów iloczynu kartezjańskiego $|F13 ×F13.$ Niemniej tego typu obiekty są bardzo użyteczne i intensywnie badane przez dziedzinę matematyki zwaną geometrią algebraiczną. W tym artykule chcemy przybliżyć przykład takiego obiektu - tak zwane krzywe eliptyczne, czyli punkty spełniające równanie:

KF13 = {(x,y) ∈F13× F13 y2 = x3 + ax + b},

dla pewnych ustalonych $|a,b∈ F13.$

Zanim powrócimy do właśnie przedstawionych krzywych eliptycznych nad ciałem $F13,$ przyjrzyjmy się jeszcze ich rzeczywistym odpowiednikom, tzn. krzywym typu

K = {(x,y) ∈R × R y2 = x3 + ax + b},

$(a,b ∈ R),$ których przykład możemy obejrzeć na rysunku 1. Udziwnijmy świat punktów tej krzywej. Dorzućmy do $K$ jeden nowy punkt specjalny: $|∞$ (nieskończoność), a w powstałym zbiorze $K¯ = K ∪ {∞ }$ zdefiniujmy następujące dodawanie punktów (tzn. pewną operację $¯ ¯ ¯ + K ×K K$ ):

dla dowolnego $P ∈ ¯K$ mamy $P + ∞ = ∞ +P = P$ ;
Jeśli dwa różne punkty $P ,Q ∈ K$ mają tę samą pierwszą współrzędną (jak na rysunku 2), to $P + Q =∞$ ;
Jeśli dwa różne punkty $|P,Q ∈K$ mają różną pierwszą współrzędną, to rysujemy prostą przechodzącą przez $|P$ i $Q,$ zaznaczamy trzeci punkt przecięcia z krzywą $(R),$ a ostatecznym wynikiem dodawania $P$ i $|Q$ jest odbicie symetryczne $|R$ względem osi $OX$ (Rys. 3). Może się zdarzyć, że dorysowana prosta nie przetnie się w żadnym dodatkowym punkcie (jak na rysunku 4). Wówczas dorysowana prosta na pewno będzie styczna do naszej krzywej i jako punkt $R$ należy przyjąć punkt styczności.
Jeśli liczymy $|P +P ,$ to rysujemy styczną do $K$ w punkcie $P .$ Jeśli ta styczna nie przecina się z $K$ w żadnym innym punkcie, to $P + P = ∞ ,$ w przeciwnym razie (prosta przecina się jeszcze w punkcie $|R$ ) $P + P = R ′,$ gdzie $R ′$ jest odbiciem symetrycznym $R$ względem osi $OX$ (zob. Rys. 5).

Jak widać, dodawanie punktów jest zdefiniowane w pełni geometrycznie. Jednakże możemy to samo działanie (sprawdź! - jest to żmudne, ale proste) opisać analitycznie. Gdy $P = (x1,y1),Q = (x2,y2)$ i $P + Q = W = (x3,y3),$ dla $|x1≠ x2,$ mamy

$pict$

a gdy $x = x 1 2$ oraz $y = y , 1 2$ wzory są następujące:

$pict$

Forma analityczna dodawania punktów jest wygodniejsza, ponieważ pozwala na zdefiniowanie dodawania punktów również w zbiorze $|K¯F13 = KF13∪ {∞ } ,$ poprzez zwykłą analogię. To znaczy umawiamy się, że powyższe wzory analityczne (mające sens również w arytmetyce modulo 13) na $x 3$ i $y 3$ określają dodawanie punktów również w $¯ KF13 .$

Dodawanie punktów na krzywej (zarówno w $|¯K ,$ jak i w $K¯ F13$ ) jest działaniem o ładnych własnościach: jest łączne, ma element neutralny (tutaj $|∞$ ) oraz własność, że każdy element $P$ ma element odwrotny $P ′$ (czyli taki, że $|P +P ′= ∞$ ). Struktury o takich własnościach zwyczajowo nazywamy grupą. Przykładem grupy innej niż te dwie opisane wyżej może być też $Fp ∖ {0}$ z działaniem mnożenia modulo $|p$ (warto samemu sprawdzić). Dla nas te grupy będą mieć jednak jeszcze jedną bardzo ważną własność, związaną z trudnością obliczeniową. O tym już za chwilkę.

2. Bestia na usługach kryptografii

Wiele protokołów szyfrowania w kryptografii opiera się na trudności obliczeniowej różnych problemów. Pewnie najsłynniejsze jest szyfrowanie RSA, którego bezpieczeństwo gwarantowane jest przez trudność faktoryzacji dużych liczb. Są jednak i inne protokoły (np. szyfr El-Gamal), których bezpieczeństwo opiera się na innym założeniu, mianowicie na trudności obliczania logarytmu dyskretnego. Na czym to polega? Chodzi o problem znalezienia w danej grupie $|G$ z mnożeniem dla danych $a,b ∈G$ takiego $|k,$ że

ak = b

bądź w wersji z grupą z dodawaniem takiego $k,$ że:

a +a + ⋯ + a = b. krazy

Oczywiście, nie dla każdej grupy problem logarytmu dyskretnego jest trudny. Dla grupy $F p$ z dodawaniem jest on banalny (dlaczego?), ale dla tego samego $|Fp,$ tylko z mnożeniem - już uchodzi za trudny. Konkretnie, najszybszy znany algorytm dla tego problemu działa w czasie

-------- 2O 3ln plnln2p ,

co dla $p$ rozsądnie dużych rozmiarów jest już poza zasięgiem współczesnych komputerów.

Po co więc te całe krzywe eliptyczne? Po prostu najszybsze algorytmy rozwiązujące logarytm dyskretny dla losowej krzywej postaci $|KFp$ są jeszcze wolniejsze niż algorytmy dla grupy $F p$ podobnego rozmiaru. Konkretnie dla krzywych eliptycznych wszystkie znane ogólne algorytmy rozwiązujące problem logarytmu dyskretnego działają w czasie

3 -------- 2O lnp ≫ 2O lnplnln2p .

Oznacza to, że każdy protokół kryptograficzny, oparty o problem logarytmu dyskretnego, staje się bezpieczniejszy bez zwiększenia $p$ (a więc bez zwiększenia rozmiaru kluczy), jeśli tylko zmienimy grupę, z którą pracujemy, z $|F p$ z mnożeniem na $|K Fp$ z dodawaniem punktów. Dokładnie z tego powodu już nie jest popularne używanie podpisu cyfrowego DSA (z roku 1991), a powszechnie używa się podpisu ECDSA (z roku 1999) - czyli jego odpowiednika, ale opartego o krzywe eliptyczne.

A jednak ta geometria algebraiczna gdzieś się przydaje!