Str115

22fi 6. Krzywe eUptywlw

blisko /wiązane z następującym pytaniem dotyczącym grup multyplikatyw-nych ciał skończonych: dla danej liczby h, jaka jest szansa na to, by dla różnych p liczba h była generatorem grupy FJJ? To pytanie było badane zarówno dla grup multyplikatywnych ciał skończonych, jak i dla grup punktów krzywych eliptycznych. Dalsze informacje na ten temat można znaleźć w pracy Gupty i Murty’cgo, cytowanej w bibliografii.

Jak już wspomnieliśmy wcześniej, dla bezpieczeństwa powyższych systemów kryptograficznych nic jest niezbędne, by punkt B był generatorem. Potrzebne jest tylko to, by w podgrupie cyklicznej generowanej przez B problem logarytmu dyskretnego był trudny do rozwiązania. Tak będzie - tzn. wszystkie znane metody rozwiązywania problemu logarytmu dyskretnego będą bardzo wolne - jeśli rząd B będzie podziclny przez bardzo dużą liczbę pierwszą, np. taką, której rząd wielkości będzie prawie tak duży jak N.

Pewnym sposobem zagwarantowania, że wybór B jest właściwy - oraz że punkt B generuje krzywą eliptyczną - jest wybranie naszej krzywej eliptycznej i ciała skończonego w taki sposób, by liczba N punktów krzywej była liczbą pierwszą. Wtedy każdy punkt B # O będzie generatorem. Zatem, jeśli użyjemy pierwszej z opisanych wyżej metod, to dla ustalonego ciała ¥_ą możemy tak długo szukać par (£, B), aż znajdziemy taką parę, dla której liczba punktów krzywej £ jest liczbą pierwszą (co możemy stwierdzić za pomocą któregoś testu pierwszości z podrozdziału 5.1). Jeśli użyjemy drugiej metody, to dla ustalonej globalnej krzywej eliptycznej £ nad ciałem Q tak długo szukamy liczb pierwszych /?, aż znajdziemy taką, dla której liczba punktów krzywej £ mod p jest liczbą pierwszą. Jak długo musimy szukać? To pytanie jest analogiczne do następującego pytania dotyczącego grup F*: czy liczba (p — l)/2 jest pierwsza, tzn. czy każdy element i=- ± 1 jest albo generatorem, albo kwadratem generatora (por. ćwiczenie 13 z podrozdziału 2.1)? Żadne z tych pytań, tzn. ani dla ciał skończonych, ani dla krzywych eliptycznych, nie doczekało się jeszcze odpowiedzi, ale przypuszcza się, że w obu przypadkach prawdopodobieństwo tego, że dana liczba pierwsza p ma żądaną własność, jest rzędu 0(1/log/?).

Uwaga. Aby grupa punktów krzywej £ mod p dla dużej liczby pierwszej p mogła mieć rząd N będący liczbą pierwszą, konieczne jest, by grupa punktów krzywej £ była grupą beztorsyjną, tzn. by nie miała punktów skończonego rzędu z wyjątkiem punktu 0. W przeciwnym razie liczba N jest podzielna przez rząd podgrupy torsyjnęj.

Ćwiczenia

1.    Skonstruuj algorytm probabilistyczny znajdujący element F_fl nic będący kwadratem.

2.    Znajdź wielomianowy algorytm deterministyczny kodujący jednostki tekstu otwartego m za pomocą punktów krzywej eliptycznej w następujących przypadkach:

(a) krzywa E ma równanie y² • x³ -- x oraz ^ ~ 3 (mod 4);

(b) krzywa E ma równanie y² -f y -- x³ oraz q * 2 (mod 3).

3.    Niech £ będzie krzywą eliptyczną o równaniu ;^I+yax^,-x₎ zdefiniowaną nad ciałem mającym p = 751 elementów. (Zamiana zmiennych postaci y' = y + 376 doprowadzi to równanie do postaci (i) z podrozdziału 6.1). Ta krzywa zawiera W = 727 punktów. Przypuśćmy, źe jednostkami tekstu otwartego są cyfry 0-9 i litery A-Z, których odpowiednikami liczbowymi są liczby od 10 do 35. Weź x = 20.

(a)    Użyj metody opisanej w tekście do zapisania wiadomości „STDP007” jako ciągu siedmiu punktów krzywej.

(b)    Przetłumacz ciąg punktów (361,383), (241,605), (201,380), (461,467), (581, 395) na wiadomość będącą odpowiedzią.

4.    Niech £ będzie krzywą eliptyczną zdefiniowaną nad dałem Q i niech p będzie wystarczająco dużą liczbą pierwszą, by redukcja równania y¹ = x³ -f + ax + b modulo p dała krzywą eliptyczną nad ciałem f_r Pokaż, że

(a)    jeśli wielomian trzeciego stopnia x³ + ax + b rozkłada się na czynniki liniowe modulo p, to grupa punktów krzywej £ mod p nie jest cykliczna;

(b)    jeśli ten wielomian ma pierwiastek modulo p, to liczba N elementów £ mod p jest parzysta.

5.    Niech £ będzie krzywą eliptyczną z przykładu 5 w podrozdziale 6.1. Niech q = 2^r i niech N_r będzie liczbą F₂r-punktów krzywej £.

(a)    Pokaż, że dla żadnego r > 1 liczba N_r nie jest pierwsza.

(b)    Dla liczb r podzielnych przez 4 znajdź warunki równoważne temu, by liczba N_r była podzielna przez liczbę pierwszą (r/4)-bitową lub (r/4 + l)-bitową.

6.    Niech £ będzie krzywą eliptyczną zdefiniowaną nad ciałem F_p i niech N_r oznacza liczbę F_pr-punktów krzywej £.

(a)    Udowodnij, że jeśli p > 3, to dla żadnego r > 1 liczba N_r nie jest pierwsza.

(b)    Daj kontrprzykład do punktu (a), gdy p = 2 { gdy p = 3.

7.    (a) Znajdź krzywą eliptyczną £ zdefiniowaną nad ciałem F₄ mającą tylko

jeden F₄-punkt (punkt w nieskończoności 0).

(b)    Pokaż, że liczba F_4r-punktów krzywej z punktu (a) jest kwadratem liczby Mersenne’a V — 1.

(c)    Znajdź prosty wzór na podwojenie F₄,‘punktu tej krzywej eliptycznej.

(d)    Udowodnij, że jeśli 2^r - 1 jest liczbą pierwszą Mersenne’a, to każdy F₄r-punkt (z wyjątkiem punktu O) ma rząd dokładnie 2' -1.

8.    Niech r będzie liczbą nieparzystą i niech K oznacza dało F_r. Dla ze A'

(r-l}/2

niech g(z) oznacza sumę £ z²¹¹ i niech /r(z) („tracę” = ślad) oznacza

r-l    J=0

sumę Yj /= o

(a) Udowodnij, że /r(z)eF₂; lr(z_x + z₂) = /r(z_t) + tr(z₂)\ tr( 1) = 1 »£(z) + g(z)² = z + fr(z).