71584 Str112

220 fi. Krzywo diptyc/nc

ciągu, istnieją algorytmy probabilistyczne o bardzo małym prawdopodobieństwie niepowodzenia. l^ło drugie, nic wystarczy generować losowych punktów na krzywej F: aby zakodować dużą liczbę możliwych tekstów otwartych m musimy umieć generować w systematyczny sposób punkty związane jakoś z /», na przykład tak, by współrzędna ,v takiego punktu była związana jakąś prostą zależnością z liczbą m.

Podamy teraz jeden z możliwych probabilistycznych sposobów kodowania tekstów otwartych za pomocą punktów krzywej eliptycznej zdefiniowanej nad ciałem F₄, przy czym o liczbie q = p^r zakładamy, że jest duża (oraz nieparzysta; por. ćwiczenie 8 poniżej dla przypadku q = 2^r). Niech x będzie wystarczająco dużą liczbą naturalną, by prawdopodobieństwo niepowodzenia wynoszące 1/2" mogło nas zadowolić, gdy próbujemy zakodować jednostkę tekstu otwartego m\ w praktyce x = 30 lub w najgorszym przypadku x = 50 powinno wystarczyć. Przypuśćmy, że jednostki tekstu m są liczbami z przedziału 0 ^ m < A/. Zakładamy także, że nasze ciało skończone jest dobrane tak, by q > Mx. Liczby całkowite z przedziału od 1 do Mx zapisujemy w postaci mx + j_t gdzie 1 <7 < x, oraz ustalamy pewną wzajemnie jednoznaczną odpowiedniość między takimi liczbami i elementami ciała F_fl. Na przykład zapisujemy każdą taką liczbę jako liczbę r-cyfrową w systemie pozycyjnym o podstawie p i uważamy te r cyfr, traktując je jako elementy Z//?Z, za współczynniki wielomianu stopnia r — 1, odpowiadającego pewnemu elementowi

r— 1

ciała F_f. Zatem liczba {a_r._la_r_₂...a₁a₀)p odpowiada wielomianowi £ a0ł_t

1=0

który, gdy rozpatrujemy go modulo pewien wielomian nicrozkładalny nad F_p, stopnia r, określa element dała F_?.

Zatem dla danej liczby m i dowolnej liczby 7=1,2,x, otrzymujemy element x dała F_flł odpowiadający liczbie mx + j. Dla takiego elementu x obliczamy prawą stronę równania

y¹=f(x) = x³ + ax + b

i próbujemy znaleźć pierwiastek kwadratowy z f(x), korzystając z metody opisanej w końcu podrozdziału 2.2. (Chodaż ten algorytm był opisany tylko dla dała prostego F_p, przenosi się on bez zmian na dowolne ciało skończone F_q. Aby go zastosować, musimy mieć pewien element g, nie będący kwadratem w tym ciele; taki element łatwo znajdujemy za pomocą algorytmu probabilistycznego). Jeśli znajdziemy taki element y, że y² = /(*), to bierzemy P_m = = (x, y). Jeśli okaże się, że element /(x) nie jest kwadratem, to zwiększamy x o 1 i próbujemy od nowa. Jeśli uda się znaleźć x taki, że f(x) jest kwadratem, zanim j stanie się większe od x, to będziemy umieli odtworzyć m ze współrzędnych punktu (x, y) za pomocą wzoru m = [(5ć — l)/x], gdzie x jest liczbą odpowiadającą elementowi x w opisanej wyżej wzajemnie jednoznacznej odpo-wiedniości między liczbami całkowitymi a elementami ciała F_fl. Ponieważ f (x) jest kwadratem dla około 50% wszystkich możliwych x, prawdopodobieństwo

fi.2. Systemy kryptograficzne, w których używa się krzywych eliptycznych 221

tego, że za pomocą tej metody nie Skonstruujemy punktu P_m, którego współrzędna x odpowiada liczbie i zawartej między my. + 1 i my. + x, wynosi około 2"*. (Dokładniej, prawdopodobieństwo tego, że f(x) jest kwadratem, wynosi NI2q\ ale N)2q jest bardzo bliskie 1 /2.)

Logarytm dyskretny na krzywej E. W podrozdziale 4.3 omawialiśmy systemy kryptograficzne z publicznym kluczem oparte na problemie logarytmu dyskretnego w grupie multyplikatywnej ciała skończonego. Teraz zrobimy to samo w grupie (addytywnej) punktów krzywej eliptycznej E zdefiniowanej nad ciałem skończonym F_f.

Definicja. Jeśli E jest krzywą eliptyczną nad ciałem i B jest punktem tej krzywej, to problem logarytmu dyskretnego na krzywej E (przy podstawie B) polega na znalezieniu dla danego punktu PeE liczby całkowitej xgZ, takiej że xB = P, jeśli taka liczba x istnieje.

Możliwe jest, że problem logarytmu dyskretnego na krzywych eliptycznych okaże się trudniejszy do rozwiązania niż problem logarytmu dyskretnego w ciałach skończonych. Wydaje się, że najmocniejsze metody opracowane dla ciał skończonych nie działają w przypadku krzywych eliptycznych. Jest tak zwłaszcza dla charakterystyki 2. Jak jest pokazane w przeglądowym artykule Odlyzki, cytowanym w bibliografii, specjalne metody rozwiązywania problemu logarytmu dyskretnego w grupie F*- pozwalają względnie prosto obliczać loga-rytmy dyskretne, a więc i łamać szyfry opisane w podrozdziale 4.3, chyba że liczba r jest dość duża. Wydaje się, że analogiczne systemy używające krzywych eliptycznych zdefiniowanych nad F_2r (patrz niżej) będą bezpieczne już dla znacznie mniejszych wartości r. Ponieważ powody praktycznej natury (odnoszące się zarówno do oprogramowania, jak i do sprzętu komputerowego) przemawiają za używaniem arytmetyki ciał F₂r, systemy kryptograficzne z publicznym kluczem opisane niżej mogą okazać się wygodniejsze w użyciu niż systemy oparte na problemie logarytmu dyskretnego w grupie F*.

Do roku 1990 jedynymi algorytmami znajdującymi logarytm dyskretny na krzywej eliptycznej były algorytmy działające w dowolnej grupie, nie korzystające ze szczególnej struktury danej grupy. Są to algorytmy działające w czasie wykładniczym, przy założeniu, że rząd grupy jest podzielny przez dużą liczbę pierwszą. Ale Menezes, Okamoto i Vanstone odkryli nowy sposób podejścia do problemu logarytmu dyskretnego na krzywej eliptycznej E zdefiniowanej nad ciałem F.. Mianowicie wykorzystali oni pary Weila (por. §111.8 książki Silvermana cytowanej w bibliografii do podrozdziału 6.1), aby zanurzyć grupę E w grupę multyplikatywną pewnego rozszerzenia F₄* ciała F_f. To zanurzenie redukuje problem logarytmu dyskretnego na krzywej E do problemu logarytmu dyskretnego w grupie FJL.

Jednakże, aby redukcja za pomocą par Weila mogła być przydatna, ważne jest to, by stopień k rozszerzenia był mały. W zasadzie jedynymi krzy-