38566 Str111
218 A. Krzvwc eliptyczni
(r) Wyra* współrzędne punktów /’ i 2 V zti pomocą współrzędnych punktu P.
(b) Pokaż, żc jeśli q 16, to każdy punkt PeEmtk rząd 3.
(c) Pokaż, żc każdy punkt krzywej E o współrzędnych z ciała F16 w rzeczywistości ma współrzędne w ciele F4. Skorzystaj wtedy z twierdzenia Hassego dla q = 4 i q = 16, hy określić liczbę punktów tej krzywej.
10. Wyznacz (-funkcje krzywych z ćwiczenia 8 nad ciałem Fp dla p => 5, 7, 11,13.
11. Wyznacz (-funkcję krzywej y2 + y = .v3 — x + 1 nad ciałem Fp dla p = 2 i p * 3. (Pokaż po pierwsze, że w obu przypadkach Nx = 1). Oznacz przez N(jt) = jr • x normę liczby zespolonej, a następnie znajdź prosty wzór na Nr
Bibliografia
1. Ful ton W.: Algebraic Cumes. Benjamin 1969.
2. Husemóller D.: Ettiptic Cumes. Springer-Vcrlag 1987.
3. Kohlitz N.: Inlroduction to Elliptic Cumes and Modular Forms. Wyd. 2, Springer-Verlag 1993.
4. Koblilz N.: Why study equations over flnite fields? Math. Magazine, 1982, 55, s. 144-149.
3. Lang S.: Elliptic Cumes: Diophantine Analysis. Springer- Verlag 1978.
6. Si!vcrman J.: The Ańthmetic of Elliptic Cumes. Springer-Yerlag 1986.
6.2. Systemy kryptograficzne, w których używa się
krzywych eliptycznych
W podrozdziale 4.3 zobaczyliśmy, w jaki sposób skończona grupa abe-lowa FJ - grupa multyplikatywna ciała skończonego - może być wykorzystana do stworzenia systemu kryptograficznego z publicznym kluczem. Mówiąc dokładniej, to trudności związane z rozwiązaniem problemu logarytmu dyskretnego w ciałach skończonych pozwoliły na stworzenie systemów kryptograficznych omówionych w podrozdziale 4.3. Celem tego podrozdziału jest opisanie analogicznych systemów z publicznym kluczem, wykorzystujących skończone grupy abelowe punktów krzywej eliptycznej E zdefiniowanej nad ciałem F.
Zanim jednak opiszemy same systemy kryptograficzne, musimy przedstawić kilka tematów wprowadzających.
Wielokrotności punktów. Operacją analogiczną do mnożenia dwóch ele-' mentów grupy FJ jest w grupie punktów krzywej eliptycznej E zdefiniowanej nad ciałem F dodawanie punktów. Zatem operacją analogiczną do podnoszenia do k~tej potęgi w FJ jest mnożenie punktu PeE przez liczbę całkowitą k. Podnoszenie do k-tej potęgi w ciele skończonym może być wykonane za pomocą algorytmu iterowanego podnoszenia do kwadratu i wymaga O (log k log3 q) operacji na bitach (por. twierdzenie 2.1.9). Podobnie pokażemy, że wielokrotność kPeEmoie być znaleziona za pomocą 0(logklog3ąr) operacji na bitach, przy zastosowaniu metody iterowanego podwajania.
Przykład 1. Aby znaleźć 100P, piszemy 100 P = 2(2(P -f 2(2(2(P + 2/0)))) i stwierdzamy, źe wystarczy 6 podwojeń i 2 dodawania punktów krzywej.
Twierdzenie 6.2.1. Przypuśćmy, źe krzywa eliptyczna E jest zdefiniowana za pomocą równania Welerstrassa (równanie (1), (2) lub (3) w poprzednim podrozdziale) nad ciałem skończonym Vq. Wtedy dla dowolnego punktu PeE współrzędne punktu kP mogą być obliczone za pomocą 0(\ogk\og3q) operacji na bitach.
Dowód. Zauważmy, źc potrzebujemy mniej niż 20 działań w Fq (dodawań, odejmowań, mnożeń i dzieleń), by obliczyć współrzędne sumy dwóch punktów, korzystając ze wzorów (4)-(5) (lub z analogicznych wzorów z ćwiczenia 6 do podrozdziału 6.1). Zatem na podstawie twierdzenia 2.1.9 każde takie dodawanie (lub podwojenie) punktów może być wykonane w czasie 0(log3^). Ponieważ metoda iterowanego podwajania wymaga 0(\ogk) kroków (por. dowód twierdzenia 1.3.6), więc stąd wynika, że do obliczenia współrzędnych punktu kP wystarczy O (log k log3 q) operacji na bitach.
Uwagi:
1. Oszacowanie czasu w twierdzeniu 6.2.1 nie jest najlepsze, zwłaszcza gdy nasze ciało skończone ma charakterystykę p = 2. Zadowolimy się jednak tym oszacowaniem, wynikającym z najprostszych algorytmów wykonywania działań w ciałach skończonych.
2. Jeśli przypadkiem znamy liczbę N punktów naszej krzywej eliptycznej E i jeśli k > Nj to ponieważ NP = O, możemy przed obliczeniem kP zastąpić liczbę k jej resztą z dzielenia przez N\ w takim przypadku możemy zastąpić dotychczasowe oszacowanie czasu przez 0(log*q) (przypomnijmy, że Nśq + 1 +2<Jq = 0(qj). Istnieje algorytm, pochodzący od Rene Scho-ofa, obliczający N za pomocą 0(log8<?) operacji na bitach.
Kodowanie tekstów otwartych. Chcemy kodować nasze teksty otwarte za pomocą punktów na pewnej krzywej eliptycznej E zdefiniowanej nad dałem skończonym Ffl. Chcemy robić to zgodnie z pewną ustaloną regułą tak, by tekst otwarty m (który możemy uważać za liczbę naturalną z pewnego przedziału) mógł być łatwo odtworzony ze współrzędnych odpowiadającego mu punktu Pm. Zauważmy, że to kodowanie nie jest tym samym co szyfrowanie. W dalszym ciągu będziemy omawiać sposoby szyfrowania punktów Pm odpowiadających tekstom otwartym. Ale upoważniony użytkownik systemu musi być w stanie odtworzyć m po rozszyfrowaniu punktu odpowiadającego kry-p to gram owi.
Trzeba tu wspomnieć o dwóch rzeczach. Po pierwsze, nie znamy dotychczas żadnego deterministycznego algorytmu działającego w czasie wielomianowym (względem log q), umożliwiającego wypisanie dużej liczby punktów dowolnej krzywej eliptycznej E nad ciałem Fq. Jednakże, jak zobaczymy w dalszym
Wyszukiwarka
Podobne podstrony:
Wykaz współrzędnych punktów osnowy pomiarowej Nr punktu osnowy Współrzędna X Współrzędna
2. Szkic rozmieszczenia punktów 1, 2 i 3. LU / / 3. Obliczenie współrzędnych 0 i X punktu 3 za pomoc
Metoda biegunowa obliczania współrzędnych?nych punktów Obliczenie współrzędnych punktu zdjętego meto
geo1 x X2=? X! Y, Y2=? Zad. 2 Obliczenie współrzędnych punktu Wyznaczyć: współrzędne X2, Y2 punktu 2
skanuj0007 (364) Zadanie 1.8. Wykorzystując współrzędne punktu A określone w tabeli 1.1., wykreśl rz
skanuj0113 (24) 206 B. Cieślar Funkcja naprężeń:(D gdzie: x, y - współrzędne punktu, w którym oblicz
IMGP3579 Obliczyć wartość siły parcia na powierzchnię płaską F. Wyznaczyć współrzędne punktu przyłoż
skanuj0001 (442) 1. RZUTY PROSTOKĄTNE - RZUTY MONGE’ Zadanie 1.1. Mając dane współrzędne punktu A (t
skanuj0010 (163) Obliczenie współrzędnych punktu 14 metodą
45838 SNC00431 (2) Obliczyć współrzędne punktu 200 A-, wedxcc te **4 00 2000 ?asho
Kartkowka 10 2011 zimowy`0x800 Kartkówka 2 z algebry liniowej 1 A. Wariant II. I J2 pkt
więcej podobnych podstron