Porovnání ECDSA vs RSA

Úvod

V poslední době došlo k četným diskusím o kladech a záporech RSA[01]
a ECDSA[02], v krypto komunitě. Pro nezasvěcené jsou to dva
nejpoužívanější algoritmy digitálního podpisu, ale i pro technologičtější
důvtipný, může být docela obtížné držet krok s fakty. Tento článek je
pokus o zjednodušení srovnání obou algoritmů. I když to tak není
V hlubokém technickém eseji může netrpělivější čtenář zkontrolovat konec
článek pro rychlou TL; DR tabulku se shrnutím diskuse.

ECDSA vs RSA

ECDSA a RSA jsou algoritmy používané kryptografie veřejného klíče[03] systémy,
poskytnout mechanismus pro ověření pravosti. Kryptografie veřejného klíče je
věda o navrhování kryptografických systémů využívajících páry klíčů: na veřejnosti
klíč (odtud jméno), které lze volně distribuovat komukoli, společně s
odpovídající soukromý klíč, která je známa pouze jejímu majiteli. Ověřování
odkazuje na proces ověřování, že zpráva podepsaná soukromým klíčem byla
vytvořené držitelem konkrétního soukromého klíče. Algoritmy použité pro
autentizace je souhrnně označována jako algoritmy digitálního podpisu [04].

Takové algoritmy se spoléhají na složité matematické problémy, které jsou relativně jednoduché
spočítat jednu cestu, i když docela nepraktické couvat. To znamená, že pro
útočník vytvořil digitální podpis, aniž by znal soukromý
klíč, musí vyřešit nevyřešitelné matematické problémy, jako je celé číslo
faktorizace, pro které neexistují žádná známá účinná řešení [05].

Z tohoto důvodu, protože neexistují žádná efektivní řešení pro internet
základní matematické problémy, hodnocení kryptografických algoritmů může
vyskytují se pouze s ohledem na jejich prováděcí podrobnosti ve spojení s
úroveň zabezpečení, které poskytují. Za tímto účelem tato část představuje a
porovnání RSA a ECDSA pomocí pěti (nebo šesti) kvantifikujících metrik. Každá metrika
je představen ve své vlastní sekci, spolu s jeho významem pro kohokoli, kdo to je
snaží se rozhodnout mezi dvěma algoritmy.

Přijetí

RSA je průmyslovým standardem pro kryptografii veřejných klíčů po mnoho let
Nyní. Většina SSL /TLS certifikáty byly (a stále jsou) podepsány pomocí RSA klíčů.
Ačkoli většina CA dosud implementovala podporu pro ECDSA
certifikáty, toto dlouhodobé přijetí vedlo pouze k mnoha starým systémům
podporující RSA. Proto, pokud dodavatel vyžaduje zpětnou kompatibilitu se starými
klientského softwaru, jsou nuceni používat certifikáty podepsané RSA. Dnes,
většina moderních klientů však implementovala podporu pro ECDSA, což bude
pravděpodobně toto omezení kompatibility v blízké budoucnosti odstraníte.

Standardní splatnost

RSA byla poprvé standardizována pro SSL /TLS v roce 1994 [06], zatímco byl představen ECDSA
ve specifikaci TLS v1.2 v roce 2008 [07]. Tento věkový rozdíl naznačuje a
rozdíl ve splatnosti standardů, které popisují osvědčené postupy pro
každý algoritmus. Přestože byly standardy RSA rozsáhle prozkoumány a
auditovaný, ECDSA neviděl tolik pozornosti. V poslední době, obhajování tohoto
algoritmus hlavních CA a jeho přijetí ve většině moderních SSL /TLS klienti
vyústilo v publikování rozsáhlejšího výzkumu, ale stále zůstává a
relativně nový systém. To ponechává prostor pro neobjevené konstrukční nedostatky nebo
v budoucnu budou zveřejněny chybné implementace.

Poměr velikosti klíče k úrovni zabezpečení

Úroveň zabezpečení [08] je metrika v kryptografii, odkazující na sílu
kryptografického primitivu nebo funkce. To se běžně měří v „bitech“
označují počet operací, které musí útočník provést, aby ohrozil jeho
bezpečnostní. Tato metrika může poskytnout kvantifikační metodu pro porovnání účinnosti
různých kryptosystémů. Je třeba zdůraznit, že velikost veřejného klíče je také
měřeno v bitech, ale jedná se o zcela odlišný koncept, odkazující na
fyzická velikost klíče.

V tomto ohledu poskytuje společný RSA 2048bitový veřejný klíč úroveň zabezpečení
112 bitů. ECDSA však vyžaduje pouze veřejné klíče s velikostí 224 bitů
stejná úroveň zabezpečení 112 bitů. Tento pozoruhodný rozdíl ve velikosti klíče má dvě
významné důsledky. Menší velikosti klíčů vyžadují menší šířku pásma pro nastavení
SSL /TLS stream, což znamená, že certifikáty ECDSA jsou ideální pro mobilní zařízení
aplikace. Kromě toho lze takové certifikáty uložit do zařízení s velkým množstvím
omezující omezení paměti, skutečnost, která umožňuje m /TLS hromádky být
implementováno v zařízeních IoT bez přidělení mnoha zdrojů. Publikováno
výzkum dokonce ukazuje, že ECDSA je efektivnější implementovat do vestavěných
zařízení.

Výkon a časová složitost

Algoritmy jsou abstraktní recepty popisující metodu k dosažení určitého cíle.
V informatice se jejich výkon měří počítáním počtu
elementární operace, které jsou nezbytné pro dosažení tohoto předem určeného konce
stav. Taková metrika se nazývá časová složitost. Od jiného vstupu
velikosti vyžadují různý počet operací, časová složitost je obvykle
vyjádřeno jako funkce vstupní velikosti.

Oba tyto algoritmy provádějí zhruba stejnou časově náročnou práci
matematické operace, například dělení a násobení. Tedy vstupní velikost
(což je v tomto případě velikost jejich klíčů) zůstává nejvýznamnější
faktor ovlivňující jejich výkon. Porovnání těchto dvou algoritmů musí být
rozlišuje mezi podepsáním zprávy a ověřením podpisu. Ve většině
Po praktických implementacích se zdá, že RSA je výrazně rychlejší než ECDSA v roce XNUMX
ověřování podpisů, i když je při podpisu pomalejší.

Věci se komplikují pro vyšší úroveň zabezpečení. Například ve většině
běžná konfigurace úrovně zabezpečení 112 bitů, RSA vyžaduje 2048bitové
versus ECDSA, která potřebuje 224bitové klíče. V další společné úrovni 128 bitů, RSA
vyžaduje 3072bitový klíč, zatímco ECDSA pouze 256 bitů. To má za následek RSA
výkonnost dramaticky poklesne, zatímco ECDSA je ovlivněna jen nepatrně. Tak jako
důsledek tohoto problému se škálováním, i když se RSA zdá být výkonnější na internetu
Ve chvíli, kdy by se neustále zvyšovaly požadavky na bezpečnost, by se mohlo velmi dobře stát
ECDSA de-facto řešení v budoucnosti.

Postkvantová rezistence

Shorův algoritmus [10] je dobře známý algoritmus pro použití klíčů RSA
kvantové počítače. Protože neexistují (veřejné) praktické implementace a
takový stroj, následující je dohad o budoucnosti veřejného klíče
kryptografie. V okamžiku psaní tohoto článku je nejlepší implementace Shora
Algoritmus může porazit 15bitové šifrování RSA klíčů. I když to nezní
o tom, jak se stále více výzkumu zaměřuje na kvantové výpočty, RSA
kdykoli se mohl dostat do vážných problémů.

Zastánci ECDSA by však neměli být slavnostní, protože eliptické
kryptografie křivek je také zranitelný [11] k upravené verzi Shor's
algoritmus. Pokud tedy lze oba šifry rozbít kvantovým počítačem,
jedinou objektivní metrikou je složitost potřebná k provedení takovéto
Záchvat. Podle veřejného výzkumu vyžaduje 2048bitové klíče RSA 4098 bitů
(a 5.2 bilionů tofoliových bran), které mají být poraženy, zatímco ECDSA 256bitové klíče
vyžadují pouze 2330 qubits (a 126 miliard tofolli bran). RSA je tedy více
drahé zlomit, používat teoretický kvantový stroj.

Proč investovat do čističky vzduchu?

Ačkoli toto srovnání není v žádném případě komplexní, je zřejmé, že
RSA si právem získala pozici vedoucího digitálního podpisu
algoritmus pro většinu aplikací certifikátů. Nicméně, protože technologie je vždy
postupuje se nepředvídatelnějším způsobem, bezpečnostní povědomí a potřeby jsou také
vzrůstající. Před více než deseti lety bylo zabezpečení vestavěného zařízení
fikce a v dnešní době bezpečná komunikace je nutností pro jakýkoli skutečný svět
aplikace. Výsledkem je, že i když je ECDSA relativně mladá, je kdokoli
hádejte, jestli nahradí RSA jako standard pro autentizaci v SSL /TLS
implementace.

Pokud se vy, čtenář, stále nemůžete rozhodnout, který algoritmus zvolit, existuje
řešení pro podporu ECDSA a RSA (jako záložní mechanismus), až do
krypto komunita se usadí na vítěze. Podívejte se do budoucna v této části článku
průvodce.

TL; DR tabulka

Reference

• [01] Algoritmus RSA
• [02] Algoritmus ECDSA
• [03] Kryptografie veřejných klíčů
• [04] Algoritmy digitálního podpisu
• [05] Složitost NP
• [06] SSL v.0.0 RFC
• [07] TLS v.1.2 RFC
• [08] Úroveň zabezpečení
• [09] RSA vs ECC pro vestavěné systémy
• [10] Shorův algoritmus
• [11] Kvantové odhady zdrojů pro ECDL