Kryptografia krzywych eliptycznych
- Autor metody
- Neal Koblitz
- Rok
- 1985
- Typ
- asymmetric encryption and key agreement
- Rodzina
- Public-key cryptography
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Kryptografia krzywych eliptycznych (ECC) to system kryptograficzny z kluczem publicznym oparty na algebraicznej strukturze krzywych eliptycznych nad ciałami skończonymi.
Zaproponowana niezależnie przez Neala Koblitz i Victora Millera w 1985 r., ECC oferuje porównywalne bezpieczeństwo do RSA przy znacznie mniejszych rozmiarach kluczy. Współczesna kryptografia coraz częściej preferuje ECC ze względu na jej wydajność: 256-bitowy klucz ECC zapewnia bezpieczeństwo porównywalne z 2048-bitowym kluczem RSA, co czyni ją idealną dla środowisk o ograniczonych zasobach i systemów o wysokiej wydajności.
Intuicja stojąca za metodą
ECC opiera się na problemie dyskretnego logarytmu na krzywej eliptycznej: znając równanie krzywej i dwa punkty, łatwo jest obliczyć ich sumę, korzystając z właściwości geometrycznych krzywej, ale niezwykle trudno jest odwrócić tę operację i ustalić, ile razy jeden punkt musi być dodany do siebie, aby osiągnąć inny punkt. Ta asymetria umożliwia bezpieczne generowanie i wymianę kluczy. W przeciwieństwie do RSA, które opiera się na problemie faktoryzacji, trudność ECC wynika ze struktury grupy krzywej eliptycznej.
Historia
ECC zostało niezależnie wynalezione przez Neal Koblitz i Victora Millera w latach 1985-1987. Początkowo adopcja była powolna ze względu na obawy patentowe i ugruntowaną dominację RSA. Jednak od lat 2000 ECC zyskało na znaczeniu jako lepsza alternatywa, szczególnie po tym, jak National Security Agency (NSA) zaleciła krzywe eliptyczne dla informacji niejawnych. Nowoczesne protokoły, takie jak TLS 1.3, Signal i systemy blockchain, w dużej mierze ustandaryzowały krzywe ECC, takie jak Curve25519 i P-256.
Kiedy stosować
ECC jest idealna do zastosowań wymagających silnego bezpieczeństwa przy ograniczonych zasobach, takich jak urządzenia mobilne, systemy IoT i systemy wbudowane. Jest standardem w nowoczesnych protokołach internetowych (TLS 1.3 używa ECDHE), systemach blockchain (Bitcoin i Ethereum używają ECDSA) oraz aplikacjach do przesyłania wiadomości (Signal używa Curve25519). ECC powinna być preferowana nad RSA dla nowych systemów ze względu na lepszą wydajność i porównywalne bezpieczeństwo.
Ograniczenia i uwagi
- Bardziej złożone podstawy matematyczne niż RSA, co utrudnia implementację i analizę
- Wymaga starannego doboru parametrów krzywej eliptycznej; słabe krzywe (takie jak te o niskim stopniu zanurzenia) są podatne na ataki
- Bezpieczeństwo silnie zależy od użytej krzywej; preferowane są krzywe standardowe, ale ich wybór wiąże się z pewnymi kontrowersjami
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Znacznie mniejsze rozmiary kluczy niż RSA dla porównywalnych poziomów bezpieczeństwa, co zmniejsza narzut związany z przechowywaniem i transmisją
- Szybsze generowanie kluczy, szyfrowanie i deszyfrowanie w porównaniu do RSA przy tej samej sile bezpieczeństwa
- Dobrze nadaje się do urządzeń o ograniczonych zasobach, takich jak telefony komórkowe, urządzenia IoT i karty inteligentne
- Coraz częściej standaryzowana i wspierana w nowoczesnych bibliotekach kryptograficznych i protokołach
Zastosowania
- Szyfrowanie TLS/SSL dla HTTPS i nowoczesnego bezpieczeństwa sieciowego przy użyciu wymiany kluczy ECDHE
- Systemy blockchain i kryptowalut (Bitcoin używa ECDSA na secp256k1, Ethereum na secp256k1)
- Wiadomości i bezpieczna komunikacja (Signal Protocol używa Curve25519 i X25519)
- Uwierzytelnianie i podpisy cyfrowe w kartach inteligentnych, sprzętowych modułach bezpieczeństwa i poświadczeniach rządowych
- Bezpieczeństwo IoT i systemów wbudowanych, gdzie zasoby obliczeniowe są ograniczone
- Badania nad kryptografią postkwantową, badanie krzywych hiperbolicznych dla algorytmów odpornych na komputery kwantowe
Jak to działa
Jak to działa
Wybierz równanie krzywej eliptycznej (zazwyczaj y^2 = x^3 + ax + b nad ciałem skończonym), punkt generatorowy G na krzywej oraz rząd n (liczbę punktów na krzywej). Klucz prywatny d jest losową liczbą całkowitą, a klucz publiczny Q = d × G jest obliczany przez mnożenie punktów.
Punkty na krzywej eliptycznej tworzą grupę w ramach geometrycznej operacji dodawania. Aby dodać dwa różne punkty, należy narysować linię przechodzącą przez nie, znaleźć punkt przecięcia z krzywą i odbić wynik względem osi x. Podwajanie punktu wykorzystuje linię styczną.
Aby zaszyfrować wiadomość dla klucza publicznego Q, należy wygenerować losowe k i obliczyć dwie wartości: punkt (x, y) = k × G oraz zaszyfrowaną wiadomość, która łączy wiadomość z haszem k × Q.
Odbiorca używa swojego klucza prywatnego d do obliczenia d × (k × G) = k × (d × G) = k × Q, odzyskując wspólny sekret i deszyfrując wiadomość.
Częste pułapki
- Implementacja mnożenia punktów bez ochrony przed atakami bocznymi może ujawnić klucz prywatny poprzez analizę czasu lub zużycia energii
- Używanie słabych lub niestandardowych krzywych eliptycznych, które mogą mieć słabości matematyczne zmniejszające bezpieczeństwo do zerowego poziomu
- Niewłaściwe użycie kryptograficznie bezpiecznego generatora liczb losowych dla klucza efemerycznego k w podpisach ECDSA, co czyni podpisy możliwe do podrobienia
Najczęściej zadawane pytania
Dlaczego 256-bitowy klucz ECC jest tak bezpieczny jak 2048-bitowy klucz RSA?
Problem dyskretnego logarytmu na krzywych eliptycznych jest trudniejszy niż problem faktoryzacji liczb całkowitych. Rozwiązanie ECDLP wymaga czasu wykładniczego nawet przy użyciu komputerów kwantowych z algorytmem Shora, podczas gdy faktoryzacja liczb całkowitych staje się problemem czasu wielomianowego na komputerach kwantowych.
Jakie są najczęściej używane krzywe eliptyczne?
Krzywe standardowe NIST P-256, P-384 i P-521. Krzywa Curve25519 Bernsteina jest preferowana w nowoczesnych systemach ze względu na jej odporność na ataki implementacyjne. Bitcoin używa secp256k1, a Ethereum również używa secp256k1 do podpisów kont i transakcji.
Czy ECC jest podatne na komputery kwantowe?
Tak, algorytm Shora może rozwiązać problem dyskretnego logarytmu na krzywej eliptycznej na komputerach kwantowych, czyniąc zarówno ECC, jak i RSA podatnymi. Badania nad kryptografią postkwantową rozwijają alternatywy oparte na kratach, kodach i wielomianach.
Jaka jest różnica między ECDH a ECDSA?
ECDH (Elliptic Curve Diffie-Hellman) to protokół uzgadniania kluczy służący do ustanawiania wspólnych sekretów przez niezabezpieczone kanały. ECDSA (Elliptic Curve Digital Signature Algorithm) służy do tworzenia i weryfikacji podpisów cyfrowych.
Czy mogę używać tego samego klucza do ECDH i ECDSA?
Jest to technicznie możliwe, ale niezalecane. Używanie oddzielnych kluczy do operacji szyfrowania i podpisywania jest zgodne z zasadą separacji kluczy i zmniejsza ryzyko subtelnych luk bezpieczeństwa.
Pokrewne metody
Źródła
Miller, V. S. (1985). Use of Elliptic Curves in Cryptography. In Proceedings of the Advances in Cryptology - CRYPTO 1985, LNCS 218, pp. 417-426.
Otwórz odnośnik DOISkopiowano.Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177), 203-209.
Otwórz odnośnik DOISkopiowano.