Krzywe eliptyczne – przyszłość kryptologii czy nieunikniona konieczność, którą będziemy musieli podjąć ze względów bezpieczeństwa. Po co właściwie one są? Dlaczego działają? Jak wykorzystać ich implementacje w środowisku .net?

Źródło: hakin9.org
Autor: Grzegorz Zielono

Dlaczego działają? Jak wykorzystać ich impelemntacje w środowisku .net?
Krzywa eliptyczna to nic nadzwyczajnego. To krzywa opisana równaniem y2 + a1xy + a3y = x3 + a2x2 + a4x + a6. Wykres przedstawiony został na Rysunku 1. Jak widać nic nadzwyczajnego. Dlaczego więc krzywe zyskały takie uznanie w dziedzinie kryptologii? Mają jedną bardzo docenianą i cenną własność – zbiór punktów przy ciałach skończonych tworzy grupę, tzn. m.in. to że operacje typu dodawanie, mnożenie, zwielokrotnianie punktów w efekcie da punkt, który również znajduje się na tej krzywej. Mówimy o takim działaniu – działanie wewnątrzgrupowe.
Krzywe używane w kryptologii trochę różnią się od podanej wyżej. Należy zacząć od tego, że ich wzór jest zazwyczaj trochę prostszy i wygląda tak: y2 + a1xy = x3 + a2x2 + a6. Jednak znacznie ważniejszą cechą jest to, że krzywe te są opisane nad ciałami Galois (ciałami skończonymi). Z wizualnego punktu widzenia krzywa taka nie jest ciągła – jest zbiorem punktów. Mówimy, że krzywa jest nad ciałem Zq .Oznacza to, że elementy, punkty tej krzywej, są obliczane modulo q.
Wszystkie wartości dzielone są przez pewną wartość q, a wynik operacji liczba modulo q jest resztą z dzielenia liczby przez q. Dla przykładu rozważmy q=2, czyli będziemy wykonywać operacje modulo 2. Spójrzmy na kolejne liczby naturalne:
Jak widać operacja ta daje w wyniku 1, gdy liczba jest nieparzysta i 0, gdy liczba jest parzysta. Ponieważ np. reszta z dzielenia 3/2 jest równa 1.
W naszym charakterystycznym przypadku q będzie równe jakiemuś wielomianowi nierozkładalnemu stopnia 2n. Po co? Bo jak wiemy komputer działa w systemie dwójkowym, ale że w przypadku q=2 (nazywamy to charakterystyką 2) mielibyśmy jedynie wartości 1 i 0 dla dowolnej liczby to podnosimy 2 do jakiejś znacznej potęgi i nazywamy to dzieleniem modulo wielomian stopnia n. Normy FIPS (Federal Information Processing Standards) mówią o wymogu, aby n było pierwsze, ale niesie to za sobą wiele konsekwencji dotyczących implementacji w strukturach programowalnych.
Pojawia się pytanie, jak z liczb naturalnych przejść do wielomianów? Nie jest to trudne! Weźmy dla przykładu liczbę 9 i zapiszmy ją w systemie dwójkowym – czyli 9 = 1001. Odpowiada to wielomianowi x3 + 1, a np. liczba 7 = 0111 odpowiada wielomianowi x2 + x + 1. Jak widać każda kolejna pozycja w rozwinięciu binarnym odpowiada kolejnej potędze x: Dla liczby 9:
Czyli 1*x3 + 0*x2 + 0* x1 + 0*x°, co w wyniku daje nam x3 + 1.
Aby opisać wszystko wyczerpująco należy jeszcze wyjaśnić co to znaczy, że wielomian jest nierozkładalny. Znaczy to, że wielomian taki nie ma dzielników. Dla przykładu podam wielomian rozkładalny x3 + 1 = (x+1)*(x2 + x + 1) oraz nierozkładalny x + 1. Tego wielomianu nie jesteśmy w stanie sprowadzić do iloczynu dwóch innych w tym ciele.
Rozważmy teraz większy przykład operujący już na liczbach zapisywanych jako wielomiany oraz wykonujący dzielenie modulo wielomian nierozkładalny stopnia 6 (np. wielomian x6 + x+ 1).
Weźmy dla przykładu liczbę 100 = 1100100. Wyobraźmy sobie tę liczbę jako wielomian x6 + x5 + x2.
Aby wykonać działanie modulo wielomian dokonujemy dzielenia wielomianu x6 + x5 + x2 przez x6 + x + 1, a wynikiem jest reszta z dzielenia tych wielomianów, w tym przypadku x5 + x2 + x+ 1.
Większość operacji jakie są wykonywane na krzywych eliptycznych w zastosowaniach kryptograficznych są wykonywane właśnie na wielomianach (w bazie wielomianowej) z uwagi na to, że jest to najbardziej naturalna dla komputera struktura liczb – zer i jedynek.
Wybierając krzywą decydujemy się na jej parametry. Przyjęło się określać 5 specyficznych parametrów koniecznych przy obliczeniach (p,a,b,G,n,h). Parametry a i b to a2 i a6 ze wzoru krzywej, G jest punktem bazowym (punkt ten jest analogiem dla liczby g, będącej generatorem jakiejś grupy – G generuje wszystkie punkty na krzywej), p to stopień naszego wielomianu, n jest rzędem grupy punktów na krzywej (ilością punktów, a h = #E(Fq)/n.
Dodawanie i zwielokrotnianie punktów jest ściśle określone wzorami, które są różne dla wybranej charakterystyki. Wypiszę tu jedynie wzory dla interesującej nas charakterystyki 2:
x, =,\:+A+<i
P —P
dl
jj=A!+A+o y,=(jf, +jci}A+xi+y,
Jak widzimy operacje te są wyjątkowo złożone jak na proste podwajanie i dodawanie punktów. Można je przyspieszyć wprowadzając współrzędne rzutowe, które spowodują, że operację dzielenia wykonamy jedynie raz – w chwili przejścia ze współrzędnych rzutowych znów do afinicznych. Dlaczego to tak bardzo przyspiesza? Operacja dzielenia w tym ciele nie istnieje, dlatego musimy wykonać operację mnożenia przez element odwrotny czyli X-1. Aby znaleźć element odwrotny musimy posłużyć się Rozszerzonym Algorytmem Euklidesa, który wymaga znaczącej ilości mnożeń i jest wyjątkowo czasochłonny. Z tego prosty wniosek: im mniej znajdywania elementów odwrotnych tym wydajniejsze operacje.
Algorytm ten można z łatwością zaimplementować w dowolnym języku np. C należy jednak pamiętać, aby operację mnożenia zdefiniować jako mnożenie wielomianów, a dodawanie jako prosty XOR (czyli dodawanie wielomianów modulo 2). Czemu? Wystarczy sobie wyobrazić dwa wielomiany np. x4 + x3 + x2 oraz x5 + x4 + x3 +1 po dodaniu tych wielomianów otrzymamy x5 + 2×4 + 2×3 + x2 + 1, ale że jesteśmy w Z2 to istnieją jedynie wartości 0 lub 1, dlatego też ten wielomian wygląda następująco x5 + x2 + 1.

Logarytm dyskretny na krzywej eliptycznej

Z problemem logarytmu dyskretnego spotkaliśmy się już przy protokole Diffiego-Hellmana. W tym protokole był on nie lada problemem – tutaj jest jeszcze bardziej złożony choć jasny i spójny w sensie działań.
Jak to działa? Bierzemy jakiś punkt na krzywej, niech to będzie dla przykładu punkt bazowy G i zwielokrotniamy go o daną wartość x, otrzymując w ten sposób punkt Q. Czyli Q=x*G. Problemem trudnym obliczeniowo jest znalezienie wartości x przy znajomości Q i G. Ten problem nazywamy logarytmem dyskretnym na krzywej eliptycznej.
Istnieją metody ataku na logarytm dyskretny typu metoda małych i dużych kroków, ale ich skuteczność jest mierna dla samego logarytmu dyskretnego, nie wspominając już o logarytmie dyskretnym na krzywej eliptycznej.

Tabela 1. Tabela1. Przykład działania modularnego „mod(2)”

Tabela 2. Tabela 2. Zapis binarny wielomianu x3 + 1

Tabela 3. Tabela 3. Schemat protokołu DH na krzywej eliptycznej.

Tabela 4. Tabela przedstawia porównanie długości kluczy (przy zachowaniu podobnego bezpieczeństwa) dla poszczególnych metod szyfrowania.

Protokół Diffiego-Hellmana na krzywej eliptycznej

Pierwszym krokiem, jaki strony dokonują, jest wybór parametrów krzywej. Aby bezpieczeństwo było zapewnione należy wybrać dobrą krzywą – taką o odpowiednich parametrach. Jak dokonać tego wyboru? Najprościej wybrać jedną z proponowanych krzywych w normie SEC2. W opisywanym przypadku będziemy korzystać ze zdefiniowanych w środowisku .net krzywych zgodnych z normami FIPS.
Po dokonaniu wyboru znane jest już 5 koniecznych parametrów (p,a,b,G,n,h) strony mogą przystąpić do uzgadniania klucza. Skupimy się na stronie A, strona B będzie dokonywać analogicznych operacji.
Strona A losuje d z przedziału od 1 do n-1 i oblicza Q=d*G. Czyli dokonuje zwielokrotnienia punktu bazowego G. Po zakończeniu tej operacji kluczem publicznym strona A jest Q, a kluczem prywatnym d. Proste, ale czy szybkie? Działanie to wygląda pozornie prosto, ale jak to wcześniej opisałem operacje na krzywej są operacjami bardzo złożonymi i dlatego ta pozornie szybka i łatwa czynność wymaga sporo czasu. Jak to działa?
Można łatwo sprawdzić, że QB = dB*G, czyli QB = dA*dB*G oraz QA = dA*G i QA = dB*dA*G.
Popatrzmy teraz jak to zaimplementować w C# na przykładzie Alice i Boba będącymi stronami w naszym działaniu. Biblioteka, której użyjemy to System.Security.Criptography jest ona ogólnie dostępna w środowisku .net.
Na Listingu 1 widać, że klucz będzie zapisany w tablicy bytów, aby zobaczyć go (jeśli nas to interesuje) w jakiejś czytelnej dla nas formie należy skorzystać z konwersji na Base64String jak przedstawiono na Listingu 2.
W C# mamy możliwość wyboru trzech wartości klucza: 256, 384, 521 każdy oczywiście daje inne bezpieczeństwo, choć właściwie dla każdej z tych wartości możemy już być pewni tajności naszego klucza.
Możemy również wybrać metodę pozyskiwania klucza. Do naszej dyspozycji są 3 metody: Hash, Hmac, Tls. Dla osób związanych z tematem hasła te nie są obce, więc pominę ich wyjaśnienia.
Nie muszę chyba wspominać, że jeśli chcemy żeby wszystko działało, wybór długości klucza dla obu stron musi być taki sam.

DSA na krzywej eliptycznej

Znów pierwszym krokiem jest wybór parametrów krzywej. Co więcej drugi krok również jest identyczny jak w DH, mianowicie należy wybrać d z przedziału od 1 do n-1 i obliczyć Q=d*G. Kluczem publicznym będzie Q zaś prywatnym d. Metoda działania:

• Wyliczamy e = Hash(m), gdzie hash jest funkcją skrótu. Najlepiej, aby była to sprawdzona funkcja skrótu, czyli przynajmniej z funkcji 2 generacji (np. SHA256). Wybieramy Ln lewych bitów e i zapisujemy jako z.
• Wybieramy losowe k z przedziału [1,n-1] (n jest oczywiście rzędem grupy punktów na wybranej krzywej).
• Obliczamy punkt P(x,y) = k*G. Obliczamy r = x mod(n). Jeśli wynik jest 0 (n dzieli r) wracamy do punktu 2.
• Obliczamy s = k-1 (z + r*dA) mod(n). Jeśli wynik 0 (n dzieli s) wracamy do punktu 2.
• Podpisem jest para (r,s).

Jak sprawdzić podpis:

• Ze względu na własności krzywych sprawdzamy poprawność klucza publicznego (jeśli nie ufamy sprawdzanemu):
  • czy Q jest równe od 0,
  • czy Q leży na krzywej,
  • czy nQ jest równe 0.
• Sprawdzamy podpis:
  • czy r i s są z przedziału [1,n-1], obliczamy e = Hash(m) i wybieramy Ln lewych bitów e i zapisujemy jako z, obliczamy w = s-1 mod(n),
  • obliczamy u = zw mod(n) i l = rw mod(n),
  • obliczamy P(x,y) = u*G + l*Q, podpis jest prawidłowy jeśli r = x mod(n). Implementacja w C# pokazana została na Listingu 3.

Rysunek 1. Wykres Krzywej eliptycznej y2 + xy = x3 + x2 + 1 nad ciałem liczb rzeczywistych

Funkcja skrótu na krzywej eliptycznej

W obecnej chwili toczy się jeszcze konkurs SHA3 na nową funkcję skrótu. Niestety już w pierwszej rundzie odpadła jedyna funkcja oparta o krzywe eliptyczne ECOH. Prawdopodobnym powodem niezakwalifikowania się do rundy drugiej była prędkość.
Funkcja ta również opiera się na wyznaczaniach kolejnych punktów dla bloków i finalnego obliczenia skrótu z ich sumy. Dokładny opis oraz implementację w C możemy znaleźć na stronach NISTu.

Inne zastosowania krzywych

Znana jest metoda faktoryzacji liczb przy użyciu krzywych eliptycznych, choć jest ona jedynie wydajna dla liczb mających około 100 cyfr dziesiętnych, więc jego przydatność przy dzisiejszych kluczach RSAjest raczej znikoma. Jednak metoda istnieje – polega na wyborze odpowiedniej krzywej. Ma duży związek z tzw. liczbami gładkimi i metodą p-1 Pollarda, czy też algorytmem Lenstry. Dociekliwych odsyłam do wyszukania więcej informacji o tej właśnie metodzie. Dla przykładu link do strony z apletem, realizującym faktoryzację na krzywych eliptycznych oraz dokładny opis przykładowego algorytmu:

• http://www.alpertron.com.ar/ECM.HTM
• http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization

Krzywe eliptyczne można również znaleźć w algorytmie SSL, dociekliwych odsyłam do strony z artykułem, gdzie rozpatrywana jest wydajność tegoż algorytmu w oparciu o krzywe eliptyczne.
W artykule można znaleźć dokładnie przedstawiony SSL Handshake, oparty o RSA,jak i ECC:

• http://research.sun.com/projects/ crypto/performance.pdf

Krzywe eliptyczne nie są jeszcze dokładnie zbadane i wciąż znajduje się ich nowe zastosowania. Ostatnim głośnym odkryciem, właściwego wykorzystania krzywych, było udowodnienie Dużego Twierdzenia Fermata na podstawie krzywych eliptycznych.

Podsumowanie

Krótkie podsumowanie plusów i minusów
krzywych eliptycznych.
Plusy:

• duże bezpieczeństwo już przy krótkich kluczach,
• uzgadnianie klucza, podpis, szyfr blokowy oparte na tej samej idei: zwielokrotniania punktu na krzywej.

Minusy:

• duża ilość wymaganych obliczeń – co za tym idzie dłuższe czasy obliczeń, duże i trudne implementacje sprzętowe.

Właściwie największym problemem krzywych jest to, że są wolne. Wystarczy sobie wyobrazić protokół DH na krzywych eliptycznych. Tutaj uzgadnianie klucza musi być maksymalnie szybkie, niestety krzywe eliptycznie tego warunku nie spełniają i nigdy spełniać nie będą.

W Sieci
Standardy krzywych eliptycznych i definicje algorytmów na krzywych eliptycznych:
• http://www.secg.org/download/aid-385/sec1_final.pdf,
• http://csrc.nist.gov/publications/nistpubs/800-56A/SP800-56A_Revision1_Mar08-
2007.pdf.

Grzegorz Zielono
Autor zajmuje się bezpieczeństwem systemów
informatycznych, przesyłanych danych i informacji.
Pracuje jako informatyk w prywatnej firmie. Kontakt z
autorem: gzielono@gmail.com.


Listing 1. Przedstawia użycie algorytmu ECDH zaimplementowanego w
bibliotekach .net
ECDiffi eHellmanCng Alice= new ECDiffi eHellmanCng(521); //Strona A wybiera długość
klucza a co za tym idzie również krzywą
Alice.KeyDerivationFunction = ECDiffi eHellmanKeyDerivationFunction.Hash;
Alice.HashAlgorithm = CngAlgorithm.Sha256;
byte[] Key = Alice.DeriveKeyMaterial(Bob.PublicKey); //Na podstawie publicznego
klucza strony B strona A wyznacza wspólny klucz

Listing 2. Sposób przekonwertowania klucza do formy znakowej
string strSecretA = Convert.ToBase64String(Key);

Listing 3. Przedstawia użycie algorytmu ECDSA zaimplementowanego w
bibliotekach .net
ECDsaCng Ecdsa = new ECDsaCng(key); //klucz podajemy jako CngKey
byte[] signed_hash = Ecdsa.SignHash(hash); //tak wygląda podpisywanie hash'a za
pomocą podpisu zadanego przy konstruktorze
Ecdsa.VerifyHash(key, hash); //Tutaj weryfi kowanie podpisu