Wizualizator krzywych eliptycznych

Jak używać: ustaw a, b i liczbę pierwszą p, kliknij Rysuj i wybieraj punkty na wykresie

Wizualizator krzywych eliptycznych pokazuje zbiór punktów spełniających równanie y² = x³ + ax + b (mod p), czyli w arytmetyce reszt z dzielenia przez p. Wszystko, co potrzebne do pracy, masz na jednym ekranie: trzy pola i przycisk „Rysuj”.

1. Ustaw współczynniki a i b. Domyślnie są to 2 i 3.
2. Wpisz liczbę pierwszą p z zakresu od 3 do 199. Domyślnie 97.
3. Kliknij „Rysuj”. Po wczytaniu strony narzędzie wykonuje to samo polecenie automatycznie, więc od razu widzisz wykres dla wartości domyślnych.
4. Klikaj punkty na wykresie. Pierwszy klik zaznacza punkt P, drugi punkt Q.
5. Odczytaj wynik z tabeli: pojawi się suma P + Q, a gdy oba kliknięcia dotyczą tego samego punktu — wynik 2P.

Każde kliknięcie punktu go zaznacza. Po dwóch kliknięciach kolejny klik zaczyna wybór od nowa, więc możesz od razu sprawdzić inną parę punktów. Obliczenia wykonują się w Twojej przeglądarce i nigdzie nie są wysyłane.

Jak czytać wzór y² = x³ + ax + b (mod p) i tabelę wyników

Zapis „(mod p)” znaczy, że liczymy reszty z dzielenia przez p. Punkt (x, y) należy do krzywej, gdy reszta z dzielenia y² przez p jest równa reszcie z dzielenia x³ + ax + b przez p. Współrzędne x i y to liczby od 0 do p − 1.

Kwadrat liczby y i kwadrat liczby p − y dają tę samą resztę, dlatego punkty układają się symetrycznie względem poziomej osi. Dla każdego x sprawdzasz więc, czy prawa strona równania jest kwadratem jakiejś reszty modulo p. Jeśli nie jest, przy tym x nie ma żadnego punktu.

Tabela wyników pokazuje dwa wiersze: „Krzywa: y² = x³ + ax + b (mod p)” z aktualnymi wartościami a, b i p oraz „Liczba punktów (z punktem w nieskończoności)”. Ta liczba obejmuje również punkt O, czyli jest o jeden większa niż liczba kropek widocznych na wykresie.

Dla wartości domyślnych: a = 2, b = 3 i p = 97. Krzywa ma postać y² = x³ + 2x + 3 (mod 97), a liczba punktów wynosi 100 razem z punktem w nieskończoności.

Dodawanie punktów na krzywej: cięciwa, podwojenie 2P i punkt w nieskończoności O

Na punktach krzywej określa się dodawanie — nie jest to zwykłe dodawanie współrzędnych.

Geometrycznie dla dwóch różnych punktów P i Q prowadzisz prostą przez nie. Prosta przecina krzywą w trzecim punkcie, a wynik P + Q to odbicie tego punktu względem poziomej osi symetrii. Gdy P = Q, zamiast cięciwy bierzesz styczną w punkcie P; taki wynik oznaczamy 2P.

Algebraicznie, wszystko modulo p. Dla P = (x₁, y₁) i Q = (x₂, y₂), gdzie P ≠ Q, nachylenie λ = (y₂ − y₁) ÷ (x₂ − x₁). Dla podwojenia λ = (3x₁² + a) ÷ (2y₁). Potem x₃ = λ² − x₁ − x₂ (mod p) i y₃ = λ·(x₁ − x₃) − y₁ (mod p), a wynikiem jest punkt (x₃, y₃).

Punkt w nieskończoności O pełni rolę zera: O + Q = Q, P + O = P. Suma punktów o tej samej współrzędnej x, dla których y₁ + y₂ ≡ 0 (mod p), czyli punktów symetrycznych względem poziomej osi, daje O — w tabeli zobaczysz wtedy punkt w nieskończoności zamiast pary liczb.

Przykład dla wartości domyślnych (a = 2, b = 3, p = 97). Na krzywej y² = x³ + 2x + 3 (mod 97) leżą P = (0, 10) i Q = (3, 6). Nachylenie λ = (−4) · 65 ≡ 31 (mod 97), bo 3 · 65 ≡ 1. Wtedy x₃ = 31² − 0 − 3 ≡ 85 i y₃ = 31 · (0 − 85) − 10 ≡ 71, czyli P + Q = (85, 71). Dla tego samego P podwojenie daje 2P = (65, 32).

Dlaczego p musi być pierwsze i krzywa nieosobliwa (4a³ + 27b² ≠ 0 mod p)

Wzory na dodawanie punktów wymagają dzielenia: przez x₂ − x₁ albo przez 2y₁. Dzielenie modulo p to mnożenie przez odwrotność, czyli liczbę, która pomnożona przez dzielnik daje resztę 1. Gdy p jest liczbą pierwszą, każda niezerowa reszta ma odwrotność, więc dzielenie zawsze ma sens. Dla p złożonego część liczb odwrotności nie ma i rachunek się nie domyka.

Warunek 4a³ + 27b² ≢ 0 (mod p) mówi, że krzywa nie jest osobliwa. Gdy to wyrażenie daje resztę 0, równanie opisuje krzywą z ostrzem albo z przecięciem samej siebie. W takim punkcie styczna nie jest jednoznaczna, wzór na 2P przestaje działać, a zbiór punktów nie tworzy poprawnej grupy.

Zakres p od 3 do 199 wynika ze sposobu liczenia punktów: sprawdzane są wszystkie pary x, y od 0 do p − 1. Dzięki temu obraz krzywej jest kompletny i mieści się na jednym wykresie.

Ograniczenia i czego narzędzie nie liczy

Narzędzie jest demonstratorem arytmetyki na małych krzywych. Ogranicza się do liczb pierwszych p nie większych niż 199, bo tylko wtedy pokazuje wszystkie punkty na jednym wykresie i pozwala klikać je pojedynczo. Krzywe kryptograficzne mają p o długości setek cyfr — takich zbiorów nie da się narysować ani przejrzeć wzrokiem.

Czego tu nie znajdziesz:

• gładkiej linii krzywej — widzisz zbiór punktów, a nie ciągły przebieg równania;
• rzędu grupy, rzędu pojedynczego punktu ani rzędu podgrupy; tabela podaje tylko łączną liczbę punktów razem z O;
• generatora grupy i sprawdzenia, czy dany punkt nim jest;
• mnożenia skalarnego, czyli wielokrotności typu kP — dodajesz dwa punkty naraz;
• zastosowań kryptograficznych: uzgadniania klucza, podpisu cyfrowego, szyfrowania;
• oceny, czy krzywa nadaje się do konkretnego zastosowania — to wymaga wiedzy o strukturze grupy.

Trzeci klik na wykresie zaczyna nowy wybór, więc nie zsumujesz trzech punktów w jednym kroku. Chcesz prześledzić dłuższy rachunek? Zapisz wynik pośredni i użyj go jako kolejnego punktu.

Najczęstsze pytania

Narzędzie liczy wyłącznie lokalnie w przeglądarce na bardzo małych ciałach pierwszych i służy celom dydaktycznym — nie nadaje się do weryfikacji parametrów kryptograficznych ani nie zawiera żadnych opłat (waluta $ nie jest używana).