楕円曲線のPKCとキーサイズ

簡単な紹介
PKCのトラップドア機能
DLPへの攻撃がキーサイズに与える影響
もっと良い方法はないのか？

簡単な紹介

楕円曲線上の点群に基づく公開鍵暗号プロトコル(PKCプロトコル)は、近年多くのアプリケーションで利用されています。PGP、TLS、SSHのようないくつかの人気のある安全なチャネルや認証サービスは、今日では楕円曲線に基づいたアルゴリズムを使用しています。Blackberry (Research in Motion, 当時) は楕円曲線暗号 (ECC) の最初の大規模な採択者であり、2000年代にECCを主流にするのに貢献しました。最近では、暗号通貨 – ブロックチェーン技術に基づく通貨の一種で、普遍的にネットワーク内のユーザー間のトランザクションを認証するために楕円曲線デジタル署名アルゴリズム（ECDSA）を実装しています。

これらのアプリケーションの共通点は？すべてのアプリケーションは、楕円曲線ベースのPKCプロトコルによって提供される小さなキーサイズから大きな恩恵を受けています。例えば、暗号通貨のブロックチェーンに格納されているすべてのトランザクションは、トランザクションを認証するためにデジタル署名を必要とします – デジタル署名で使用される公開鍵は、トランザクションに沿って格納されています。

PKCのトラップドア機能

PKC プロトコルで使用されるキーサイズは、ブルートフォース攻撃に対するセキュリティに直接対応しています。

理想的には PKC プロトコルは、どのアルゴリズムも(正確には「攻撃」も)ブルートフォースよりも優れたものにならないように設計されています。このような偉業はAES のような対称暗号プロトコルでのみ達成されていますが、どの PKC プロトコルでも不可能です。

なぜか? PKCプロトコルのセキュリティ特性は、有限群上で定義されたトラップドア関数に基づいています。ロブスタートラップ、一方通行の鏡、実際のトラップドアに似ていますが、この考えは、関数は片道で計算するのは簡単ですが、逆に計算するのは非常に難しいということです。これは、暗号化は簡単ですが復号化のための秘密を解明するのは難しいということを意味します。

今日使用されているほとんどのPKCプロトコルは、2つの異なりが関連する難しい問題に基づいてトラップドア関数を実装しています。以下では、離散対数問題の2つのインスタンス、整数DLPと楕円曲線DLPに注目して、従来の楕円曲線ベースのPKCと比較します。素因数分解は整数DLPと強く関連していることに注意してください。

以下の表は、整数群DLPと楕円曲線DLPのいくつかの類似点と相違点をまとめたものです。有限群における合成演算は、暗号化を実行するために順番に適用される群の基本的な演算です。DLP のどちらの場合も、暗号化を計算する際に使用される値は、大きな最大値 p によって制限されていることに注意してください。DLPのいずれかのインスタンスに基づくPKCプロトコルの鍵のサイズは、この最大値pのサイズと直接相関します。

DLPへの攻撃がキーサイズに与える影響

任意の有限群設定で動作するDLPを解くための “PollardのRhoアルゴリズム “と呼ばれる完全に一般的なアルゴリズム(または攻撃)が存在します。平均して、PollardのRhoアルゴリズムは、ブルートフォース攻撃がDLPを解くために必要とする計算ステップの平方根を必要とするだけです。ポラードのRhoアルゴリズムは、同じ希望のセキュリティを達成するために、キーサイズを効果的に2倍の長さにすることを強制します。

「数体ふるい法アルゴリズム」、つまりGNFSアルゴリズムは、PKCプロトコルで使用されるトラップドア関数をより速く解くことができますが、一般的ではありません。GNFSアルゴリズムは、グループ要素が十分に定義されたサイズを持つ有限グループのDLP(および素因数分解) を解くためにのみ使用できます。例えば、整数グループでは要素5は3よりも大きく、10001は53よりも大きく、7は23よりも小さくなります。すべての伝統的な（非楕円曲線）PKCプロトコルは、このカテゴリに該当する有限グループを使用しています。GNFSアルゴリズムは、整数DLPまたはファクタリングを解くためにPollardのRhoアルゴリズムよりも指数関数的に少ない計算ステップを必要とし、鍵サイズを大きく膨らませます。

幸いなことに、楕円曲線上の点のサイズを比較する明確に定義された方法がないため、GNFS攻撃は適用されません。下の表は、楕円曲線ベースのプロトコルを使用した場合のキーサイズの固有の利点を示しています。