35600 Str113

222    6. Krzywe tiilptyranc

wvm! eliptycznymi, dla których stopień k jest mały, są tzw. krzywe eliptyczne ..superosobliwc”, których najhardziej znanymi przykładami są krzywe postaci y¹»jr* + fl.v, gdy charakterystyka p ciała F_f przystaje do -1 modulo 4, oraz krzywe postaci y^l - v³ + ó, gdy p » -1 (mod 3). Ogromna większość krzywych eliptycznych to krzywe, które nie są superosobliwc. Dla tych krzywych redukcja prawic nigdy nic prowadzi do algorytmu pod wykład niczego (por. moją pracę w Journal of Cryptology, cytowaną w bibliografii).

Zatem zasadniczą zaletą systemów kryptograficznych korzystających z krzywych eliptycznych jest to, że nic jest znany żaden algorytm podwykład-niczy, który łamie te systemy, przy założeniu, że będziemy unikać krzywych supcrosobliwych i krzywych, których rząd nic ma dużego dzielnika pierwszego.

Opiszemy teraz systemy kryptograficzne analogiczne do systemów z publicznym kluczem opisanych w podrozdziale 4.3, oparte na problemie logarytmu dyskretnego na krzywej eliptycznej E zdefiniowanej nad ciałem skończonym F_ę.

System analogiczny do systemu wymiany kluczy Diffiego-Hellmana. Przypuśćmy, że Aida i Bernardo chcą uzgodnić klucz, którego będą używać razem z pewnym klasycznym systemem kryptograficznym. Najpierw wybierają (nic robiąc z tego tajemnicy) skończone ciało F_q i krzywą eliptyczną E nad tym ciałem. Ich klucz będzie skonstruowany z pewnego losowego punktu P na tej krzywej. Jeśli na przykład wybiorą losowy punkt PeE, to jego współrzędna x będzie losowym elementem ciała F. i mogą ją wtedy przekształcić w r-cyf-rową liczbę całkowitą, zapisaną w systemie pozycyjnym o podstawie p (gdzie q = p^r), która z kolei będzie kluczem w ich klasycznym systemie kryptograficznym. (Słowo „losowy” ma tu niezbyt precyzyjne znaczenie; chcemy nim wyrazić to, że dokonany wybór klucza jest całkowicie dowolny i nie sposób przewidzieć, który z wielu możliwych kluczy zostanie wybrany). Ich zadaniem będzie wybranie punktu P w taki sposób, by cała korespondenta mogła odbywać się w sposób jawny, a mimo to nikt inny oprócz nich nie mógł dowiedzieć się, jakim punktem jest P.

Aida i Bernardo najpierw w sposób jawny wybierają punkt BeE, będący „podstawą”. Punkt B odgrywa rolę generatora g grupy multyplikatywnej ciała skończonego w systemie Diffiego-Hellmana. Nie będziemy jednak żądać, by punkt B był generatorem grupy punktów krzywej E. W rzeczywistości ta grupa może nie być cykliczna. Nawet jeśli jest cykliczna, to chcemy uniknąć wysiłku związanego ze sprawdzaniem, czy B jest generatorem (lub nawet obliczania liczby N punktów, której w ogóle nie musimy znać). Chcemy jednak, by podgrupa generowana przez B była duża, najlepiej jeśli jej wielkość będzie tego samego rzędu co wielkość całej grupy E. Tą kwestią zajmiemy się później. Na razie przypuśćmy, że B jest ustalonym, znanym powszechnie punktem krzywej E, którego rząd jest bardzo duży (albo jest równy N, albo jest dużym dzielnikiem liczby W).

Aby wygenerować klucz, Aida najpierw wybiera losową liczbę całkowitą a, która ma rząd wielkości q (czyli w przybliżeniu jest tak samo duża jak M), i zachowuje ją w tajemnicy. Oblicza następnie aBeE i wynik ogłasza publicznie. Bernardo robi to samo: wybiera losową liczbę b i ogłasza publicznie hBeE. Tajnym kluczem, którego będą teraz używać, jest P — abBeE. Oboje umieją wyznaczyć ten klucz. Na przykład Aida zna hB (gdyż wszyscy to znają) i zna swoją tajną liczbę a. Natomiast osoby trzecie znają tylko aB i bB. Wydaje się, że bez rozwiązania problemu logarytmu dyskretnego - znalezienia a, gdy znamy B i aB (lub znalezienia ó, gdy znamy B i bB) ~ nie potrafimy znaleźć abB na podstawie tylko aB i bB.

System analogiczny do systemu Masseya-Onwry. Tak samo jak w systemie korzystającym z ciał skończonych, będzie to system kryptograficzny z publicznym kluczem do przesyłania jednostek tekstu /n, które tym razem będą zakodowane za pomocą punktów P_m pewnej ustalonej (i znanej powszechnie) krzywej eliptycznej E nad ciałem F, (przy czym liczba q jest duża). Zakładamy też, że liczba N punktów na krzywej E została obliczona (i też jest powszechnie znana). Każdy użytkownik systemu w tajemnicy wybiera losową liczbę całkowitą e między 1 i N taką, że NWD{e, N) — 1, a następnie za pomocą algorytmu Euklidesa oblicza liczbę odwrotną d = e~^l mod N, tzn. liczbę d taką, że de = 1 (mod N). Jeśli Alicja chce przesłać Bolkowi wiadomość P_m, to najpierw przesyła mu punkt e_AP_m (gdzie indeks A oznacza Alicję). To nic nie mówi Bolkowi, który nie zna ani d_A, ani e_A i nie może wobec tego odtworzyć P_m. Nie próbując zatem dociekać sensu w tej wiadomości, mnoży ją przez swoją liczbę e_B i odsyła wynik e_Be_AP_m z powrotem do Alicji. Trzeci krok należy do Alicji. Odsłania ona częściowo tajemnicę, mnożąc otrzymaną liczbę e_Be_AP_m przez d_A. Ponieważ NP_m = O i d_Ae_A = 1 (mod N), otrzyma ona w wyniku punkt e_BP_m, który teraz zwraca Bolkowi, a on umie już odczytać wiadomość, mnożąc ten punkt przez d_B.

Zauważmy, że osoby trzecie znają tylko e_AP_m, e_Be_AP_m i e_BP_m. Jeśli ktoś z nich potrafi rozwiązać problem logarytmu dyskretnego na krzywej £, to potrafi wyznaczyć e_B z pierwszych dwóch punktów, obliczyć wtedy d_B = e_B^l mod N i wreszcie odczytać wiadomość P_m = d_B(e_BPJ.

System analogiczny do systemu EIGamala. Jest to kolejny system kryptograficzny z publicznym kluczem do przesyłania wiadomości P_m. Tak samo, jak w opisanym wyżej systemie wymiany kluczy, zaczynamy od wyboru ustalonego ciała skończonego F., krzywej eliptycznej E nad tym dałem i punktu BeE (są one powszechnie znane). Nie musimy znać liczby N punktów krzywej. Każdy użytkownik systemu wybiera losową liczbę całkowitą a, którą trzyma w tajemnicy oraz wyznacza i powszechnie ogłasza punkt aB.

Aby wysłać Bartkowi wiadomość P_m, Anita wybiera losową liczbę całkowitą k i wysyła parę punktów (kB, P_m + k(a_BB)), gdzie a_BB jest powszechnie znanym kluczem Bartka. Aby odczytać wiadomość, Bartek mnoży pierwszy punkt przez swój tajny klucz a_B i odejmuje otrzymany wynik od drugiego punktu:

P_m + k(a_BB)-a_a(kB) = P_m.