ECDSAとRSAの比較

概要

最近、長所と短所について多くの議論がありました RSA【01]
& ECDSA[02]、暗号化コミュニティ。 初心者のために、彼らはのXNUMXつです
最も広く使用されているデジタル署名アルゴリズム、ただしより技術的な
精通している、それは事実に追いつくのはかなり難しい場合があります。 この記事は
XNUMXつのアルゴリズムの単純化した比較を試みます。 しかし、これは
深く技術的なエッセイである、より焦る読者は
ディスカッションの要約を含むクイックTL; DRテーブルの記事。

ECDSAとRSA

ECDSAとRSAは、 公開鍵暗号[03]システム、
のメカニズムを提供する 認証。 公開鍵暗号は
鍵のペアを使用する暗号化システムを設計する科学：a 公共
キー （したがって名前）は誰にでも自由に配布でき、
対応する 秘密鍵、それはその所有者だけが知っています。 認証
秘密鍵で署名されたメッセージがであったことを確認するプロセスを指します
特定の秘密鍵の所有者によって作成されます。 使用されるアルゴリズム
認証は総称して デジタル署名アルゴリズム [04]。

このようなアルゴリズムは、比較的単純な複雑な数学的問題に依存しています
逆に実行することは非常に非現実的ですが、一方向に計算します。 これは、
個人情報を知らずに、デジタル署名を偽造する攻撃者
キー、彼らは整数などの扱いにくい数学の問題を解決する必要があります
既知の効率的な解決策がない因子分解[05]。

そのため、利用可能な効率的なソリューションがないため、
基礎となる数学的問題、暗号アルゴリズムの評価
に関連してそれらの実装の詳細に関してのみ発生します
彼らが提供するセキュリティのレベル。 この目的のために、このセクションでは、
XNUMXつ（またはXNUMXつ）の定量化メトリックを使用したRSAとECDSAの比較。 各メトリック
独自のセクションで紹介されています。
XNUMXつのアルゴリズムを決定しようとしています。

養子縁組

RSAは、長年にわたって公開鍵暗号の業界標準でした
今。 ほとんどのSSL /TLS 証明書はRSAキーで署名されていました（現在もそうです）。
現在、ほとんどのCAはECDSAベースのサポートを実装していますが
証明書、この長期にわたる採用により、多くのレガシーシステムのみが導入されました
RSAをサポートします。 したがって、ベンダーが旧バージョンとの下位互換性を必要とする場合
クライアントソフトウェアでは、RSAで署名された証明書を使用する必要があります。 今日、
ただし、最新のクライアントのほとんどは、ECDSAのサポートを実装しています。
おそらく近い将来、この互換性の制約を取り除くでしょう。

標準成熟度

RSAはSSL /用に最初に標準化されましたTLS 1994年[06]、ECDSAが導入された間
の仕様で TLS 1.2年のv2008 [07]。 この年齢差は
のベストプラクティスを説明する標準の成熟度の格差
各アルゴリズム。 ただし、RSA標準は広範囲にわたって調査され、
監査されたため、ECDSAはそれほど注目されていません。 最近、これの擁護
主要なCAによるアルゴリズムと最新のSSL /での採用TLS クライアントは
より広範な研究が発表されたが、それでもまだ残っている
比較的新しいスキーム。 これにより、未発見の設計上の欠陥や
誤った実装が将来開示される。

キーサイズとセキュリティレベルの比率

セキュリティレベル [08]は、強度を表す暗号化のメトリックです。
暗号プリミティブまたは関数の。 一般に、「ビット」で測定されます。
攻撃者が侵害するために実行する必要がある操作の数を示します
セキュリティ。 このメトリックは、有効性を比較するための定量化方法を提供できます
さまざまな暗号システムの。 公開鍵のサイズも
ビットで測定されますが、それは完全に異なる概念であり、
キーの物理的なサイズ。

この点で、共通のRSA 2048ビット公開鍵は、次のセキュリティレベルを提供します。
112ビット。 ただし、ECDSAは、224ビットサイズの公開鍵だけで、
同じ112ビットのセキュリティレベル。 キーサイズのこの驚くべき違いはXNUMXつあります
重要な影響。 鍵のサイズが小さいほど、必要な帯域幅が少なくて済み、
SSL /TLS ストリーム、つまりECDSA証明書はモバイルに最適です
アプリケーション。 さらに、このような証明書は多くのデバイスに保存できます
より多くのメモリ制約を制限し、m /TLS スタックする
多くのリソースを割り当てずにIoTデバイスに実装されます。 公開済み
研究は、ECDSAが組み込みに実装する方がより効率的であることを示しています[09]
デバイス。

パフォーマンスと時間の複雑さ

アルゴリズムは、特定の目標を達成する方法を説明する抽象的なレシピです。
コンピュータサイエンスでは、それらのパフォーマンスは数を数えることによって測定されます
この所定の終了に到達するために必要な基本操作
状態。 このようなメトリックは 時間の複雑さ。 入力が異なるため
サイズは異なる数の操作を必要とし、時間の複雑さは通常
入力サイズの関数として表されます。

問題の両方のアルゴリズムは、ほぼ同じ時間のかかる実行します
除算や乗算などの数学演算。 したがって、入力サイズ
（この場合はキーのサイズです）が最も重要なままです
彼らのパフォーマンスに影響を与える要因。 XNUMXつのアルゴリズムを比較すると、
メッセージの署名と署名の検証を区別します。 ほとんどの場合
実際の実装では、RSAはECDSAよりもかなり高速であるように見えます
署名を検証しますが、署名中は遅くなります。

セキュリティレベルが高くなると、状況は複雑になります。 たとえば、ほとんどの
セキュリティレベルが112ビットの一般的な構成、RSAには2048ビットが必要
ECDSAには224ビットのキーが必要です。 次の一般的な128ビットのレベルでは、RSA
ECDSAは3072ビットのみですが、256ビットのキーが必要です。 これにより、RSA
パフォーマンスは劇的に低下しますが、ECDSAへの影響はわずかです。 なので
このスケーリング問題の結果ですが、RSAは、
セキュリティ要件の継続的な増加により、
ECDSAは将来のデファクトソリューションです。

ポスト量子耐性

ショアのアルゴリズム [10]は、RSA鍵を解読するためのよく知られたアルゴリズムです。
量子コンピューター。 の（パブリック）実用的な実装がないため
このようなマシン、以下は公開鍵の将来についての推測です
暗号化。 この記事の執筆時点では、Shorの最適な実装
アルゴリズムは、15ビットのキーRSA暗号化を無効にすることができます。 これは鳴りませんが
ますます多くの研究が量子コンピューティングに向けられているので、RSA
いつでも深刻なトラブルに巻き込まれる可能性があります。

ECDSAの支持者は、楕円形であるため、すぐに祝うべきではありません。
曲線暗号 も脆弱です [11] Shorの修正版へ
アルゴリズム。 したがって、両方の暗号が量子コンピューターによって破られる可能性がある場合、
唯一の客観的な測定基準は、そのような
攻撃。 公開調査によると、RSA 2048ビットキーには4098キュービットが必要です
（および5.2兆のTofolliゲート）は打ち負かされるが、ECDSA 256ビットキー
2330キュービット（および126億のトフォリゲート）のみが必要です。 したがって、RSAは
理論的な量子マシンを使用すると、壊れるのに費用がかかります。

まとめ

この比較は決して包括的なものではありませんが、
RSAはリーディングデジタル署名としての地位を正当に獲得しました
ほとんどの証明書アプリケーションのアルゴリズム。 ただし、テクノロジーは常に
より予測不可能な方法で進歩し、セキュリティ意識とニーズも
増加しています。 XNUMX年ちょっと前、組み込みデバイスのセキュリティは
フィクションと今日の安全な通信は、現実の世界ではなくてはならないものです
応用。 その結果、ECDSAが比較的若い場合でも、
SSL /での認証の標準と​​してRSAに取って代わるかどうかを推測します。TLS
実装

読者が選択するアルゴリズムをまだ決定できない場合は、
ECDSAとRSAの両方を（フォールバックメカニズムとして）サポートするためのソリューション
暗号化コミュニティは勝者に落ち着きます。 この記事のセクションで将来を確認してください
ハウツーガイド。

TL; DRテーブル

参考文献

• 【01] RSAアルゴリズム
• 【02] ECDSAアルゴリズム
• 【03] 公開鍵暗号
• 【04] デジタル署名アルゴリズム
• 【05] NPの複雑さ
• 【06] SSL v.0.0 RFC
• 【07] TLS v.1.2RFC
• 【08] セキュリティレベル
• 【09] 組み込みシステムのRSAとECC
• 【10] ショーのアルゴリズム
• 【11] ECDLの量子リソース見積もり