Rozdział Elementy teorii złożoności



Pobieranie 1,74 Mb.
Strona19/19
Data23.02.2018
Rozmiar1,74 Mb.
1   ...   11   12   13   14   15   16   17   18   19
Rozdział 5

Zastosowanie krzywych eliptycznych w kryptografii
Przedstawione do tej pory protokoły kryptograficzne wykorzystywały właściwości grup multiplikatywnych Zp*. Istnieją jednak inne struktury algebraiczne, które mogą okazać się w praktyce lepsze.
Poziom bezpieczeństwa systemu kryptograficznego zależy od wielkości stosowanych w nim liczb. Jednak operacje na zbyt dużych liczbach są kosztowne i czasochłonne. Skonstruowany kryptosystem może okazać się nieopłacalny. Jak więc istotnie zmniejszyć rząd wielkości zastosowanych liczb bez zmniejszenia poziomu bezpieczeństwa systemu?
W połowie lat osiemdziesiątych ubiegłego wieku zainteresowano się właściwościami krzywych eliptycznych, ponieważ są one źródłem ogromnej liczby grup skończonych. Okazało się, że grupy punktów krzywych eliptycznych są w wielu aspektach podobne do grup multiplikatywnych ciał skończonych. Co więcej wydaje się, że kryptosystemy skonstruowane za pomocą krzywych eliptycznych są tak samo bezpieczne przy wykorzystaniu liczb o znacznie mniejszej długości. Krzywe eliptyczne znalazły więc zastosowanie w konstrukcji systemów kryptograficznych. Opracowano również algorytmy rozkładu liczb na czynniki pierwsze i testy pierwszości oparte na tych krzywych [3].
Równanie krzywej eliptycznej
Definicja 5.1

Niech F będzie dowolnym ciałem. Jeżeli ciało K jest większe od F i zawiera F to K nazywa się rozszerzeniem ciała F.


Często stosowanym sposobem otrzymywanie rozszerzeń ciał jest dołączanie do nich elementów. Na przykład jeżeli F jest ciałem to K = F() jest rozszerzeniem ciała F zawierającym wszystkie wyrażenia wymierne utworzone z i elementów ciała F.
Definicja 5.2

Jeżeli każdy wielomian o współczynnikach z ciała F rozkłada się na czynniki liniowe, to F nazywamy ciałem algebraicznie domkniętym.



Warunek z definicji 5.2 jest równoważny żądaniu, aby każdy wielomian o współczynnikach w ciele F miał pierwiastek w F. Przykładem ciała algebraicznie domkniętego jest ciało liczb zespolonych.
Definicja 5.3

Najmniejsze algebraicznie domknięte rozszerzenie ciała F nazywamy domknięciem algebraicznym F i oznaczamy.
Na przykład domknięciem algebraicznym ciała liczb rzeczywistych jest ciało liczb zespolonych.
Definicja 5.4

Jeżeli wielokrotne dodawanie elementu neutralnego mnożenia 1 w ciele F daje po pewnej ilości sumowań wynik 0, to istnieje jedyna liczba pierwsza p taka, że = 0. Wtedy mówimy, że ciało F ma charakterystykę p i oznaczamy char(F) = p. Jeżeli natomiast sumowanie elementu 1 nigdy nie da zera, to piszemy char(F) = 0.
Przykładowo ciało skończone Zp ma charakterystykę p natomiast ciało liczb wymiernych ma charakterystykę 0.
W ciele F nie musi być zdefiniowana odległość lub topologia, dlatego pochodną wielomianu jednej zmiennej lub pochodną cząstkową wielomianu wielu zmiennych definiuje się bezpośrednio: (xn)’ = n(xn–1).
Definicja 5.5

Niech F będzie ciałem oraz dane będzie równanie:



y2 + a1xy + a3y = x3 + a2x2 + a4x + a6, (1)
gdzie aiF. Oznaczmy przez E(F) zbiór złożony z punktów (x, y)F2, których współrzędne spełniają równanie (1) oraz z „punktu w nieskończoności” O. Jeśli K jest pewnym rozszerzeniem ciała F, to E(K) jest zbiorem punktów (x, y)K2, których współrzędne spełniają równanie (1) wraz z punktem O. Krzywą zadaną równaniem (1) nazywamy krzywą eliptyczną jeśli jest ona gładka tzn. nie istnieje punkt w zbiorze E(), w którym znikają obie pochodne cząstkowe równania (1).
Tak więc krzywa zadana równaniem (1) jest krzywą eliptyczną, jeśli układ równań

nie ma rozwiązania w E().
Jeżeli char(F)  2 oraz char(F)  3, to bez straty ogólności możemy zakładać, że krzywa eliptyczna dana jest równaniem postaci
y2 = x3 + ax + b, (2)
gdzie a, bF. Istotnie, w tym przypadku poprzez liniową zamianę zmiennych można wyzerować współczynniki a1, a3 i a2 [2]. Warunek gładkości krzywej (2) jest równoważny żądaniu, aby 4a3 + 27b2  0.
W dalszej części tego rozdziału będziemy przyjmować, że krzywa eliptyczna jest zadana równaniem (2). Na rysunku 5.1 przedstawiona została krzywa eliptyczna nad ciałem liczb rzeczywistych opisana wzorem y2 = x3x.
Reguła dodawania punktów krzywej eliptycznej
Aby uzasadnić, że zbiór punktów krzywej eliptycznej ma strukturę grupy przemiennej, zdefiniujmy działanie dodawania tych punktów.

Rys. 5.1. Krzywa eliptyczna zadana równaniem y2 = x3x.


Niech E będzie krzywą eliptyczną nad ciałem liczb rzeczywistych oraz P = (x1, y1) i Q = (x2, y2) będą dwoma dowolnymi punktami tej krzywej różnymi od O. Wprowadźmy następujące reguły:


  1. Jeżeli O jest punktem w nieskończoności, to definiujemy –O jako O.




  1. Przyjmujemy, że P + O = O + P = P.




  1. –P = (x1, –y1) tzn. punkt przeciwny do P jest punktem o tej samej współrzędnej x co P, ale przeciwnej współrzędnej y. Z równania (2) wynika, że jeżeli (x, y) jest punktem krzywej eliptycznej, to (x, –y) też jest punktem tej krzywej.




  1. Przyjmujemy, że P + (–P) = O.




  1. Jeżeli P jest punktem krzywej eliptycznej E, to niech l będzie styczną do tej krzywej w punkcie P oraz punkt R będzie jedynym punktem przecięcia prostej l z krzywą E różnym od P. Definiujemy wtedy P + P = –R. Może się zdarzyć, że prosta l jest pionowa i przecina krzywą E tylko w punkcie P. Wtedy P + P = O.


Rys. 5.2. Reguła dodawania P + P.




  1. Jeżeli x1x2, to prosta l przechodząca przez punkty P i Q przecina krzywą E w jeszcze jednym punkcie R (jeżeli l jest styczna do krzywej E w punkcie P, to przyjmujemy R = P, analogicznie jeżeli l jest styczna do krzywej E w punkcie Q, to R = Q). Wtedy definiujemy P + Q jako –R.

Rys. 5.3. Reguła dodawania P + Q.



Na mocy powyższych reguł każdy element krzywej eliptycznej ma element przeciwny oraz punkt w nieskończoności O jest elementem neutralnym dodawania punktów krzywej eliptycznej. Okazuje się, że dodawanie to jest łączne, co ilustruje rysunek 5.4.

Rys. 5.4. Łączność dodawania punktów krzywej eliptycznej.


Niech E będzie krzywą eliptyczną nad ciałem Zp. Wtedy krzywa E jest zbiorem punktów (x, y) takich, że x, yZp oraz x i y spełniają kongruencję y2x3 + ax + b mod p. Na rysunku 5.5 przedstawiona jest krzywa y2 = x3x nad ciałem Z257. Oczywiście krzywe eliptyczne nad ciałem Zp znacznie różnią się od krzywych eliptycznych nad R ale wzory definiujące operacje dodawania punktów są w obu przypadkach takie same.
Największymi zaletami stosowania krzywych eliptycznych w kryptografii są:


  • duża elastyczność w wyborze grupy (jest wiele krzywych eliptycznych nad ciałem Zp, natomiast istnieje tylko jedna grupa multiplikatywna Zp*),

  • dla odpowiednio wybranej krzywej eliptycznej E do tej pory nie istnieją algorytmy, które łamały by system kryptograficzny w rozsądnym czasie.



Rys. 5.5. Krzywa y2 = x3x nad ciałem Z257.


Szczególnie ten drugi argument ma ogromne znaczenie. Postęp jaki miał miejsce w ostatnich latach w znajdowaniu logarytmów dyskretnych w ciałach skończonych oraz w metodach faktoryzacji liczb wymusił (w celu utrzymania bezpieczeństwa kryptosystemów) konieczność wydłużania kluczy. Użycie krzywych eliptycznych do konstrukcji systemów kryptograficznych jest więc rozsądnym rozwiązaniem.
Bardzo dobrym zastosowaniem kryptosystemów z kluczem jawnym jest wymiana tajnego klucza, którym można posłużyć się do wymiany zaszyfrowanych wiadomości w innym kryptosystemie z kluczami tajnymi. Zaskakujące jest to, że dzięki zastosowaniu funkcji jednokierunkowej wymiany takiej można dokonać przesyłając niezaszyfrowane wiadomości poprzez otwarty (dostępny dla każdego) kanał informacyjny. Protokół Diffiego – Hellmana (pierwszy kryptosystem z kluczem jawnym) realizuje właśnie taką wymianę klucza. Najpierw rozpatrzmy pierwotną wersję tego algorytmu bazującą na trudności obliczenia logarytmu dyskretnego w grupie Zp*.

Protokół Diffiego – Hellmana.
Załóżmy, że osoba A i osoba B chcą uzgodnić pewien tajny klucz (dużą liczbę naturalną) poprzez otwarty kanał komunikacyjny. Treść wszystkich wiadomości przesyłanych przez nich jest znana osobie C, która próbuje wykraść uzgadniany klucz.

Osoba A i osoba B wykonują następujące czynności:




  • jawnie uzgadniają pewną dużą liczbę pierwszą p oraz generator Zp* g,

  • osoba A losuje w tajemnicy liczbę kA < p i przesyła osobie B liczbę gkA mod p,

  • osoba B losuje w tajemnicy liczbę kB < p i przesyła osobie A liczbę gkB mod p,

  • uzgodnionym kluczem będzie gkAkB mod p.

Osoba A i osoba B łatwo mogą obliczyć uzgodniony klucz: gkAkB  (gkA)kB  (gkB)kA mod p.



Rys. 5.6. Schemat Diffiego – Hellmana w Zp*.


Załóżmy, że osoba C chce obliczyć uzgodniony klucz znając wartości liczb: p, g, gkA mod p i gkB mod p. Gdyby potrafiłaby rozwiązać problem logarytmu dyskretnego, znalazła by liczbę gkAkB mod p.
Do tej pory nie udowodniono równoważności problemu logarytmu dyskretnego i złamania systemu Diffiego – Hellmana. Wiadomo, że jeżeli ktoś potrafi rozwiązywać problem logarytmu dyskretnego to również potrafi złamać ten system. Może się jednak zdarzyć (choć jest to mało prawdopodobne), że ktoś znajdzie inny sposób na złamanie protokołu Diffiego – Hellmana. W praktyce można założyć, że protokół ten jest bezpieczny, dopóki problem logarytmu dyskretnego uważany jest za trudny.
Rozważmy teraz problem logarytmu dyskretnego dla grupy punktów krzywej eliptycznej.

Definicja 5.6

Niech G będzie grupą punktów krzywej eliptycznej E. Problem logarytmu dyskretnego na krzywej eliptycznej E o podstawie QE polega na znalezieniu dla danego punktu PE liczby całkowitej n takiej, że P = nQ (o ile taka liczba istnieje), gdzie nQ oznacza n – krotną sumę punktu Q.


Protokół Diffiego – Hellmana łatwo zaadoptować do krzywych eliptycznych. Niech E będzie krzywą eliptyczną nad ciałem Zp. Osoba A i osoba B wykonują następujące czynności:


  • jawnie ustalają punkt Q na krzywej eliptycznej E,

  • osoba A w tajemnicy losuje liczbę kA, oblicza punkt kAQ i tak wyznaczony punkt przesyła osobie B,

  • osoba B w tajemnicy losuje liczbę kB, oblicza punkt kBQ i tak wyznaczony punkt przesyła osobie A,

  • uzgodnionym kluczem jest punkt P = kAkBQ.

Osoba A wylicza uzgodniony klucz mnożąc otrzymany od osoby B punkt przez wylosowaną przez siebie tajną liczbę. Analogicznie postępuje osoba B. Osoba C, która stara się przechwycić uzgadniany klucz, musi wyznaczyć punkt P = kAkBQ na podstawie znajomości Q, kAQ i kBQ. Jeżeli potrafi ona rozwiązać problem logarytmu dyskretnego w grupie punktów krzywej eliptycznej E, jest też wstanie wyznaczyć punkt P.


W podobny sposób można modyfikować inne kryptosystemy oparte na trudności znalezienia logarytmu dyskretnego. Na przykład istnieje wersja algorytmu DSA, która opiera się na krzywych eliptycznych [2]. Oznacza się ją jako ECDSA (ang. elliptic curve digital signature algorithm). Algorytm ECDSA może w niedługim czasie być uznany za alternatywny standard podpisu cyfrowego względem DSA.


Bibliografia
[1] Kippenhahn R., „Tajemne przekazy”, Prószyński i S-ka, Warszawa 2000.
[2] Koblitz N., „Algebraiczne aspekty kryptografii”, Wydawnictwa Naukowo Techniczne, Warszawa 2000.
[3] Koblitz N., „Wykład z teorii liczb i kryptografii”, Wydawnictwa Naukowo Techniczne, Warszawa 1995.
[4] Kutyłowski M., Strothmann W. B., „Kryptografia. Teoria i praktyka zabezpieczania systemów komputerowych”, Oficyna Wydawnicza Read Me, Warszawa 1999.
[5] Marzantowicz W., Zarzycki P., „Elementy teorii liczb”, Wydawnictwo Naukowe UAM, Poznań 1999.
[6] Schneier B., „Kryptografia dla praktyków”, Wydawnictwa Naukowo Techniczne, Warszawa 1995.




1   ...   11   12   13   14   15   16   17   18   19


©operacji.org 2017
wyślij wiadomość

    Strona główna