0Pricing
Cryptology Academy · Lekcja

Mnożenie skalarne i ECDLP

Zrozumieć wielokrotne dodawanie punktów i wyjaśnić, dlaczego odwrócenie tej operacji jest trudne

Mnożenie skalarne i ECDLP to bezpłatna lekcja Cryptology Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Cryptology Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Cryptology Academy zawiera 4 lekcji w sumie.

Wprowadzenie

Mnożenie skalarne to podstawowa operacja EC: obliczanie k×P przez wielokrotne stosowanie prawa grupowego. ECDLP — znalezienie k na podstawie k×P — to trudny problem zapewniający bezpieczeństwo całej kryptografii opartej na krzywych eliptycznych.

Definicja mnożenia skalarnego

k×P = P + P + ... + P (k razy). Dla k=4: 4P = P+P = 2P; 2P+2P = 4P. Dla k=2^256 bezpośrednie iterowanie jest niewykonalne. Potrzebujemy wydajnego algorytmu.

Algorytm podwajania i dodawania

Analogicznie do podnoszenia do kwadratu i mnożenia: Dla każdego bitu k od MSB do LSB: R = 2R (podwajanie) jeśli bit ma wartość 1: R = R + P (dodawanie) O(log k) operacji grupowych ≈ O(256) dla P-256.

Przykład: 13×P

13 = 1101 w systemie binarnym Początek: R = P 1: R = 2P+P = 3P (dla bitu 1) 0: R = 6P 1: R = 12P+P = 13P ✓ 4 podwojenia + 2 dodawania dla k=13.

Problem logarytmu dyskretnego na krzywych eliptycznych (ECDLP)

Mając punkty G i Q = k×G na krzywej, należy znaleźć k. W przód: łatwe (O(log k) operacji) Wstecz: dla krzywych kryptograficznych nie jest znany algorytm wielomianowy Najlepszy algorytm ogólny: algorytm rho Pollarda w O(√n) ≈ 2^128 dla P-256.

Dlaczego ECDLP jest trudniejszy niż DLP

Klasyczny DLP (g^k mod p): algorytmy rachunku indeksów działają w czasie podwykładniczym. ECDLP: dla ogólnych krzywych eliptycznych nie jest znany odpowiednik rachunku indeksów. Ta sama długość klucza oznacza znacznie trudniejszy problem.

Atak Pohliga-Hellmana

Jeśli rząd grupy ma małe czynniki pierwsze, ECDLP można wydajnie rozwiązać w każdej podgrupie. Obrona: należy używać krzywych o pierwszym lub prawie pierwszym rzędzie grupy i unikać krzywych z małymi podgrupami.

Atak MOV

Atak MOV odwzorowuje ECDLP na DLP w ciele skończonym za pomocą parowania Weila. Działa wyłącznie dla krzywych supersingularnych (stopień zanurzenia k=1,2). Wszystkie krzywe NIST są odporne na atak MOV.

Stałoczasowe mnożenie skalarne

Naiwne podwajanie i dodawanie ujawnia k przez czas wykonania (warunkowy etap dodawania). Należy używać drabiny Montgomery’ego lub algorytmów comb, które wykonują te same operacje niezależnie od bitów klucza. Jest to niezbędne w bezpiecznych implementacjach.

Poziomy bezpieczeństwa ECDLP

P-192: 96-bitowe bezpieczeństwo (wycofane przez NIST) P-224: 112-bitowe bezpieczeństwo P-256: 128-bitowe bezpieczeństwo (obecny standard) P-384: 192-bitowe bezpieczeństwo P-521: 260-bitowe bezpieczeństwo Curve25519: 128-bitowe bezpieczeństwo

Od bezpieczeństwa ECDLP do bezpieczeństwa ECDH

Bezpieczeństwo ECDH sprowadza się do ECDLP: jeśli można rozwiązać ECDLP (znaleźć a na podstawie A=a×G), można obliczyć wspólny sekret. Założenie obliczeniowego Diffiego-Hellmana (CDH) przyjmuje, że jest to trudne.

Szybkie sprawdzenie

Jaka jest złożoność czasowa najlepszego algorytmu ogólnego (rho Pollarda) dla ECDLP przy rzędzie grupy n?

Podsumowanie

Mnożenie skalarne i ECDLP są już znane. Następnie porównamy standardowe krzywe: P-256, Curve25519 i secp256k1.

Często zadawane pytania

Czy lekcja „Mnożenie skalarne i ECDLP” jest bezpłatna?

Tak — pełny tekst „Mnożenie skalarne i ECDLP” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Cryptology Academy, przejdź na CoddyKit PRO. Kurs Cryptology Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Mnożenie skalarne i ECDLP”?

Zrozumieć wielokrotne dodawanie punktów i wyjaśnić, dlaczego odwrócenie tej operacji jest trudne Ćwiczysz Cryptology Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Cryptology Academy?

Nie wymagamy żadnego doświadczenia. Cryptology Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.

Ile czasu zajmuje lekcja „Mnożenie skalarne i ECDLP”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Cryptology Academy?

Tak. Każda lekcja Cryptology Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Prawo grupy krzywej eliptycznej
  2. Mnożenie skalarne i ECDLP
  3. Standardowe krzywe: P-256, Curve25519 i secp256k1
  4. ECC a RSA: kompromisy między bezpieczeństwem a wydajnością
← Powrót do Cryptology Academy