Str116

228    (t. Krzywe eliptyczne

(b)    Udowodnij, żc /;(;) = 0 dla dokładnie połowy elementów _t.;,i K i /r(z)» 1 dla drugiej połowy.

(c)    Znajdź algorytm probabilistyczny generujący F?,-punkty krzywej eljp

tycznej >•* + y &    + ax -i- b.

9.    Niech E będzie krzywą eliptyczną y² = *³ -I- ax *f b, gdzie a, /; e Z. Niech PtE. Niech p > 3 będzie liczbą pierwszą, która nie jest dzielnikiem anj 4a³ + 27/>\ ani mianowników współrzędnych x i y punktu P. Pokaż, j-c rząd punktu P mod p na krzywej eliptycznej E mod p jest najmniejszą liczbą całkowitą dodatnią k taką. że albo (1) kP = O na krzywej £, albo (2) liczba p dzieli mianowniki współrzędnych punktu kP.

10.    Niech Ebędzie krzywą eliptyczną.v² Ą-y- x² -Jzdefiniowaną nad ciałem Q i niech P = (0,0). Wyznaczając kolejne punkty 2^JP dla 7=1,2,... znajdź przykład liczby pierwszej p takiej, że grupa E mod p nie jest generowana przez P mod p. (Uwaga. Można pokazać, że punkt P generuje grupę punktów wymiernych krzywej E.)

11.    Użyj systemu analogicznego do systemu EIGamala, korzystającego z krzywych eliptycznych, by wysłać wiadomość z ćwiczenia 3(a), gdzie E i p są takie same jak w ćwiczeniu 3 i B = (0,0). Przypuśćmy, że kluczem Twojego korespondenta jest punkt (201,380), a Twoim ciągiem losowych liczb k (po jednej na każdą jednostkę tekstu) jest 386, 209, 118, 589,312,483,335. Jaki ciąg siedmiu par punktów wyślesz?

Zauważ, że w tym ćwiczeniu używamy małej wartości p\ bardziej realistyczny przykład, który moglibyśmy spotkać w praktyce, wymagałby liczb mających kilkadziesiąt cyfr dziesiętnych.

Bibliografia

I.    Agnew GMullin R., Vanstone SA.: An implemenlation of eUiplic curve cryplosystcms ovcr F₂iss. IEEE J. Selected Areas in Communications, 1993, 11, s. 804-813.

1 Gupta R., Murty M.R.: Primilive points onellipticcurves. Compositio Math., 1986,58, s. 13-44.

3.    Koblitz N.: EUiplic curve cryplosystcms. Math. Comp., 1987, 48, s. 203-209.

4.    Koblitz N.: Primalily of Ihe number of poinls on an elliptic curve over a finitc field Pacific J. Math., 1988,131, s. 157-165.

5.    Koblitz N.: Construding elliptic curve cryplosyslems in characlerislic 2. Aduances in Cryp-tology - Crypto ‘90, Springer-Verlag 1991, s. 156-167.

6.    Koblitz N.: EUiplic curve implemenlation of zero-knowledge blobs. J. Cryp tology, 1991, 4, 1207-213.

7.    Koblitz N.: CM-curves with good cryptographic properties. Aduances in Cryptology - Crypto VI, Springer-Verlag 1992, s. 279-287.

8.    Lenslra H.W., Ir.: Elliptic curves and number-theorelic algorithms. Report 86-19, Mathema-tisch Instituul, Universiteit van Amsterdam 1986.

9.    Menezes A.: Elliptic Curoe Public Key Cryplosyslems. Kluwer Acad. Publ. 1993.

10.    Menezes A., Okamoto T., Vanstone S.: Reducing elliptic curve logarithms to logaritkms in a finite field. IEEE Transactions on Information Theory IT-39, 1993, s. 1639-1646.

II.    Menezes A., Vanslone S., Zuccherato R.: Counting points on eUiplic curves over F₂m. Math. Comp., 1993, 60, s. 407-420.

12. MiUcr V.: Use of eUiptic curvcs in cryplography. Abstracis for Crypto 85, 1985.

13.    Odlyzko A M.: Discrcle logarflhm* m fmite field* and their cryptngraphic agnificance, Adoan-ces in Cryplołogy, Froceetiiną* of Kurnrrypi H4, Springer-Verlag 1985, «. 224-314.

14.    Schoof R.: Elliptic curves over fmite field* and the computati/m of «qoare roota mod p. Math. Comp., 1985, 44, s. 483-494.

6.3. Test pierwszości, w którym używa się krzywych eliptycznych

Test pierwszości, w którym używa się krzywych eliptycznych, wynaleziony przez S. Goldwassera, J. Kiliana i (w nieco innej postaci) przez A. O. L. Atkina, jest testem analogicznym do następującego testu pierwszości Pockłing-tona, w którym korzysta się z grupy (Z//zZ)*:

Twierdzenie 63.1. Niech n będzie dodatnią liczbą całkowitą. Załóżmy, że istnieje liczba pierwsza q, będąca dzielnikiem liczby n — l. większa niż -Jn — 1. Jeśli istnieje taka liczba całkowita a. że (i.) aⁿ~^l = 1 (mod n)\ i (ii) NWD(a ^ln~ ¹^^q — 1, ń) = 1, to liczba n jest pierwsza.

Dowód. Jeśli liczba n nie jest pierwsza, to istnieje dzielnik pierwszy p ^ n liczby n. Ponieważ q > p — 1, więc NWD(q, p — 1) = 1, a zatem istnieje taka liczba całkowita u, że uq = 1 (mod p — 1). Zatem z założenia (i) wynika, że _at»-i)/« _ _auą(n-V)/q __ _a«(n-i) = j (mod p), co przeczy założeniu (ii).

Uwagi. Ten test jest znakomity, pod warunkiem że liczba n — 1 jest podziełna przez liczbę pierwszą q > >/n — 1 oraz potrafiliśmy znaleźć liczbę q (i dowieść, że jest ona pierwsza). W przeciwnym razie nie mamy szczęścia. (Nie jest to całkiem prawdą — istnieje ogólniejsza wersja tego testu, mająca zastosowanie wówczas gdy znamy rozkład na czynniki pewnego dużego dzielnika liczby n — 1, por. ćwiczenie 2 poniżej.)

Zauważmy, że ten test jest testem probabilistycznym w tym tylko sensie, że losowo wybrana liczba a może spełniać lub też nie spełniać warunku (ii) (oczywiście, jeśli a nie spełnia warunku (i), to liczba n nie jest pierwsza). Jednak kiedy znajdziemy taką liczbę a (zazwyczaj wystarczy wziąć a = 2), wtedy test wykazuje z całą pewnością, że liczba n jest pierwsza. W przeciwieństwie do testów pierwszości opisanych w podrozdziale 5.1 (tzn. testów Solovaya-Stras-sena i Mi llera-Rabina) wniosek z testu Pocklingtona jest całkowicie pewny: liczba n jest pierwsza, a nie „prawdopodobnie pierwsza”.

Test pierwszości używający krzywych eliptycznych jest oparty na podobnym twierdzeniu, w którym zakładamy, że mamy do czynienia z równaniem y² = x³ -ł- ax -ł- b, rozpatrywanym modulo n. Liczby a i b są zatem nie-ujemnymi liczbami całkowitymi mniejszymi od n oraz E jest zbiorem wszystkich par liczb całkowitych x, yeZ./nŻ,, spełniających to równanie, wraz