Porównanie ECDSA z RSA

Wprowadzenie

Ostatnio odbyło się wiele dyskusji na temat zalet i wad RSA[01]
i ECDSA[02], w społeczności kryptograficznej. Dla niewtajemniczonych jest ich dwóch
najczęściej używane algorytmy podpisu cyfrowego, ale nawet dla bardziej zaawansowanych technologii
bystry, nadążanie za faktami może być dość trudne. Ten artykuł to
próba uproszczenia porównania dwóch algorytmów. Chociaż tak nie jest
głęboko techniczny esej, tym bardziej niecierpliwy czytelnik może sprawdzić koniec
artykuł do szybkiej tabeli TL; DR z podsumowaniem dyskusji.

ECDSA kontra RSA

ECDSA i RSA są algorytmami używanymi przez kryptografia klucza publicznego[03] systemy,
zapewnić mechanizm dla Uwierzytelnianie. Kryptografia klucza publicznego to
nauka projektowania systemów kryptograficznych wykorzystujących pary kluczy: publiczny
klucz (stąd nazwa), które można dowolnie dystrybuować wraz z
odpowiedni prywatny klucz, który jest znany tylko jego właścicielowi. Poświadczenie
odnosi się do procesu weryfikacji, czy została podpisana wiadomość podpisana kluczem prywatnym
utworzony przez posiadacza określonego klucza prywatnego. Algorytmy stosowane do
uwierzytelnianie jest ogólnie znane jako algorytmy podpisu cyfrowego [04].

Takie algorytmy opierają się na skomplikowanych problemach matematycznych, które są stosunkowo proste
obliczyć w jedną stronę, chociaż odwrócenie jest dość niepraktyczne. Oznacza to, że dla
atakujący w celu sfałszowania podpisu cyfrowego, bez wiedzy prywatnej
klucz, muszą rozwiązać nierozwiązywalne problemy matematyczne, takie jak liczba całkowita
faktoryzacja, dla której nie są znane skuteczne rozwiązania [05].

Z tego powodu, ponieważ nie ma wydajnych rozwiązań dostępnych dla
leżące u podstaw problemów matematycznych, ocena algorytmów kryptograficznych może
występują tylko w odniesieniu do szczegółów ich realizacji w połączeniu z
poziom bezpieczeństwa, jaki zapewniają. W tym celu w tej sekcji przedstawiono
porównanie RSA i ECDSA przy użyciu pięciu (lub sześciu) wskaźników ilościowych. Każda metryka
jest wprowadzony we własnej sekcji, wraz z jego znaczeniem dla każdego, kto jest
próba wyboru między dwoma algorytmami.

Przyjęcie

RSA jest od wielu lat standardem w branży kryptografii z kluczem publicznym
teraz. Większość SSL /TLS certyfikaty były (i nadal są) podpisywane kluczami RSA.
Chociaż do tej pory większość urzędów certyfikacji wdrożyła obsługę systemów opartych na ECDSA
certyfikaty, ta długotrwała adopcja doprowadziła tylko do wielu starszych systemów
wspieranie RSA. Dlatego jeśli dostawca wymaga zgodności z poprzednimi wersjami
oprogramowanie klienckie, są zmuszeni do korzystania z certyfikatów podpisanych za pomocą RSA. Dzisiaj,
jednak większość współczesnych klientów wdrożyła obsługę ECDSA, która to zrobi
prawdopodobnie usunie to ograniczenie kompatybilności w najbliższej przyszłości.

Standardowy termin zapadalności

RSA został po raz pierwszy ustandaryzowany dla SSL /TLS w 1994 r. [06], kiedy wprowadzono ECDSA
w specyfikacji TLS v1.2 w 2008 [07]. Ta różnica wieku wskazuje a
rozbieżność w dojrzałości standardów opisujących najlepsze praktyki
każdy algorytm. Chociaż standardy RSA zostały szeroko zbadane i
skontrolowany ECDSA nie zwrócił tak dużej uwagi. Ostatnio rzecznictwo tego
algorytm przez główne CA i jego przyjęcie w większości nowoczesnych SSL /TLS klienci mają
spowodowało opublikowanie szerszych badań, ale nadal pozostaje
stosunkowo nowy program. Pozostawia to miejsce dla nieodkrytych wad projektowych lub
błędne implementacje zostaną ujawnione w przyszłości.

Stosunek wielkości klucza do poziomu bezpieczeństwa

Poziom bezpieczeństwa [08] to metryka w kryptografii, odnosząca się do siły
prymitywu kryptograficznego lub funkcji. Jest to zwykle mierzone w „bitach”
oznacza liczbę operacji, które atakujący musi wykonać, aby skompromitować tę operację
bezpieczeństwo. Ta metryka może dostarczyć metodę ilościową do porównania skuteczności
różnych kryptosystemów. Należy podkreślić, że rozmiar klucza publicznego również jest
mierzony w bitach, ale jest to zupełnie inna koncepcja, odnosząca się do
fizyczny rozmiar klucza.

Pod tym względem wspólny klucz publiczny RSA 2048 bitów zapewnia poziom bezpieczeństwa wynoszący
112 bitów. Jednak ECDSA wymaga tylko 224-bitowych kluczy publicznych, aby zapewnić
ten sam 112-bitowy poziom bezpieczeństwa. Ta uderzająca różnica w wielkości klucza ma dwa
znaczące implikacje. Mniejsze rozmiary kluczy wymagają mniejszej przepustowości do skonfigurowania
SSL /TLS stream, co oznacza, że ​​certyfikaty ECDSA są idealne dla telefonów komórkowych
Aplikacje. Co więcej, takie certyfikaty mogą być przechowywane w urządzeniach z dużą ilością
bardziej ograniczające ograniczenia pamięci, fakt, który pozwala m /TLS stosy
zaimplementowane w urządzeniach IoT bez alokacji wielu zasobów. Opublikowany
badania pokazują nawet, że ECDSA jest bardziej wydajna [09] we wdrażaniu wbudowanym
urządzeń.

Wydajność i złożoność czasowa

Algorytmy to abstrakcyjne przepisy opisujące metodę osiągnięcia określonego celu.
W informatyce ich wydajność jest mierzona poprzez zliczenie liczby
elementarne operacje niezbędne do osiągnięcia tego z góry określonego zakończenia
stan: schorzenie. Taka metryka nazywa się złożoność czasu. Ponieważ różne dane wejściowe
rozmiary wymagają różnej liczby operacji, zwykle złożoność czasu
wyrażone jako funkcja wielkości wejściowej.

Oba omawiane algorytmy działają mniej więcej tak samo czasochłonnie
operacje matematyczne, takie jak podziały i mnożenia. Zatem wielkość wejściowa
(która w tym przypadku jest wielkością ich kluczy) pozostaje najważniejsza
czynnik wpływający na ich wydajność. Konieczne jest porównanie dwóch algorytmów
rozróżnia się między podpisaniem wiadomości a weryfikacją podpisu. W większości
praktyczne wdrożenia, RSA wydaje się być znacznie szybszy niż ECDSA w
weryfikacja podpisów, choć jest wolniejsza podczas podpisywania.

Sprawa się komplikuje w przypadku wyższych poziomów bezpieczeństwa. Na przykład w większości
powszechna konfiguracja poziomu bezpieczeństwa 112 bitów, RSA wymaga 2048 bitów
w porównaniu z ECDSA wymagającym 224-bitowych kluczy. W kolejnym wspólnym poziomie 128 bitów RSA
wymaga klucza 3072-bitowego, podczas gdy ECDSA tylko 256 bitów. Powoduje to RSA
wydajność dramatycznie spada, podczas gdy ECDSA ma tylko niewielki wpływ. Tak jak
konsekwencja tego problemu ze skalowaniem, chociaż RSA wydaje się bardziej wydajna w
moment ciągłego wzrostu wymagań bezpieczeństwa mógłby bardzo dobrze renderować
ECDSA to de facto rozwiązanie w przyszłości.

Opór post kwantowy

algorytm faktoryzacji shora [10] to dobrze znany algorytm łamania kluczy RSA przy użyciu
komputery kwantowe. Ponieważ nie ma (publicznych) praktycznych wdrożeń
taka maszyna, to przypuszczenie o przyszłości klucza publicznego
kryptografia. W chwili pisania tego tekstu najlepsza realizacja Shora
algorytm może pokonać 15-bitowy klucz RSA. Chociaż to nie brzmi
dotyczący, ponieważ coraz więcej badań jest ukierunkowanych na obliczenia kwantowe, RSA
może mieć poważne kłopoty w dowolnym momencie.

Zwolennicy ECDSA nie powinni jednak szybko świętować, ponieważ są eliptyczne
kryptografia krzywych jest również wrażliwy [11] do zmodyfikowanej wersji Shora
algorytm. W konsekwencji, jeśli oba szyfry mogą zostać złamane przez komputer kwantowy,
jedyną obiektywną miarą jest złożoność wymagana do wdrożenia takiego
atak. Według badań publicznych klucze RSA 2048 bitów wymagają 4098 kubitów
(i 5.2 bln bram Tofolli) do pokonania, podczas gdy klucze 256-bitowe ECDSA
wymagają tylko 2330 kubitów (i 126 miliardów bramek Tofolli). Dlatego RSA to więcej
drogi do zerwania, przy użyciu teoretycznej maszyny kwantowej.

Wnioski

Chociaż porównanie to w żadnym wypadku nie jest wyczerpujące, widać to
RSA słusznie zyskało pozycję wiodącego podpisu cyfrowego
algorytm dla większości aplikacji certyfikatów. Ponieważ jednak technologia jest zawsze
postęp w bardziej nieprzewidywalny sposób, świadomość bezpieczeństwa i potrzeby również
wzrastający. Nieco ponad dziesięć lat temu bezpieczeństwo urządzeń wbudowanych było
fikcja, a obecnie bezpieczna komunikacja to obowiązkowy element każdego świata rzeczywistego
podanie. W rezultacie, nawet jeśli ECDSA jest stosunkowo młoda, należy do kogokolwiek
zgadnij, czy zastąpi RSA jako standard uwierzytelniania w SSL /TLS
wdrożenia.

Jeśli czytelnik nadal nie może zdecydować, który algorytm wybrać, istnieje
rozwiązania wspierające zarówno ECDSA, jak i RSA (jako mechanizm rezerwowy), aż do
Społeczność kryptograficzna decyduje się na zwycięzcę. Zapoznaj się z sekcją tego artykułu w przyszłości
Poradnik Jak to zrobić.

Tabela TL; DR

Referencje

• [01] Algorytm RSA
• [02] Algorytm ECDSA
• [03] Kryptografia klucza publicznego
• [04] Algorytmy podpisu cyfrowego
• [05] Złożoność NP
• [06] SSL wersja 0.0 RFC
• [07] TLS wersja 1.2 RFC
• [08] Poziom bezpieczeństwa
• [09] RSA vs ECC dla systemów wbudowanych
• [10] Algorigthm Shora
• [11] Szacunki zasobów kwantowych dla ECDL