楕円曲線暗号

2013年、ニューヨーク・タイムズ紙は、デュアル楕円曲線決定論的乱数ビット生成（Dual_EC_DRBG）がNSAの影響によりNISTの国家標準に採用されたと報じた。NSAはアルゴリズムと推奨楕円曲線に意図的な弱点を組み込んでいた。^{[ 9 ]} RSA Securityは2013年9月に、Dual_EC_DRBGに基づくソフトウェアの使用を中止するよう顧客に勧告する勧告を出した。^{[ 10 ] [ 11 ]} Dual_EC_DRBGが「NSAの秘密作戦」として暴露されたことを受け、暗号専門家はNISTが推奨する楕円曲線のセキュリティについても懸念を表明し、^{[ 12 ]}非楕円曲線群に基づく暗号化への回帰を示唆した。

さらに、2015年8月、NSAはECCに対する量子コンピューティング攻撃への懸念から、Suite Bを新しい暗号スイートに置き換える計画を発表した。 ^{[ 13 ] [ 14 ]} NSAはその後、国家安全保障システム向けの量子耐性アルゴリズムへの移行に関するCNSA 2.0ガイダンスを公開した。^{[ 7 ]}

RSAの特許は2000年に失効しましたが、少なくとも1つのECC方式（ECMQV）を含むECC技術の特定の側面をカバーする有効な特許が存在する可能性があります。しかし、RSA Laboratories ^{[ 15 ]}とDaniel J. Bernstein ^{[ 16 ]}は、米国政府の楕円曲線デジタル署名標準（ECDSA; NIST FIPS 186-3）および特定の実用的なECCベースの鍵交換方式（ECDHを含む）は、これらの特許を侵害することなく実装できると主張しています。

公開鍵暗号は、特定の数学的問題の難解性に基づいています。RSAの1983年の特許のような初期の公開鍵システムは、互いに大きく離れた2つ以上の大きな素因数から構成される大きな整数を因数分解することが困難であるという仮定に基づいてセキュリティを構築していました。楕円曲線プロトコルの場合、中心的な難解性の仮定は、楕円曲線離散対数問題（ECDLP）です。公開基点が与えられた場合、${\displaystyle P}$そしてもう一つのポイント${\displaystyle Q=kP}$回復は不可能であるはずだ${\displaystyle k}$ECDHのような鍵合意プロトコルは、計算の難しさなどの関連するディフィー・ヘルマン仮定に依存している。${\displaystyle abP}$から${\displaystyle P}$、${\displaystyle aP}$、 そして${\displaystyle bP}$楕円曲線暗号の安全性は、点乗算を効率的に計算できる能力と、適切に選択された曲線と鍵サイズであれば、それを逆算することが事実上不可能であることに依存します。問題の難易度は、曲線方程式を満たす座標ペアの総数だけでなく、曲線群のサイズと構造によって決まります。

楕円曲線暗号がRSAなどの代替手段に比べて約束する主な利点は、鍵のサイズが小さく、ストレージと送信の要件が削減されることです。^{[ 1 ]}例えば、256ビットの楕円曲線公開鍵は、3072ビットのRSA公開鍵と同等のセキュリティを提供するはずです。

いくつかの離散対数ベースのプロトコルが楕円曲線に適用され、群を置き換えている。${\displaystyle (\mathbb {Z} _{p})^{\times }}$楕円曲線群を持つ場合：

• 楕円曲線ディフィー・ヘルマン（ECDH）鍵合意方式は、ディフィー・ヘルマン方式に基づいており、
• X25519とX448は、IRTFによってモンゴメリー形式の曲線で使用するために指定されたディフィー・ヘルマン関数である^{[ 17 ]。}
• 楕円曲線統合暗号化方式（ECIES）は、楕円曲線拡張暗号化方式、または単に楕円曲線暗号化方式とも呼ばれ、
• 楕円曲線デジタル署名アルゴリズム（ECDSA）は、デジタル署名アルゴリズムに基づいています。
• エドワーズ曲線デジタル署名アルゴリズム（EdDSA）はシュノール署名に基づいており、ねじれたエドワーズ曲線を使用します。^{[ 18 ]}
• ECMQVキー合意スキームはMQVキー合意スキームに基づいています。
• ECQV暗黙的証明書スキーム。

ECCを使用するには、すべての関係者が楕円曲線を定義するすべての要素、つまりスキームのドメインパラメータに合意する必要があります。基礎となる有限体は通常、素体であり、$\displaystyle \mathbb {F} _{p}}$、またはバイナリフィールド、表記される$\displaystyle \mathbb {F} _{2^{m}}}$バイナリの場合、${\displaystyle m}$そして既約還元多項式${\displaystyle f}$フィールド表現を指定します。${\displaystyle f}$は補助曲線ではありません。楕円曲線は、定義方程式の係数によって定義されます。最後に、巡回部分群は、その生成元（基点とも呼ばれる）Gによって定義されます。暗号化アプリケーションでは、Gの位数、つまり、となる最小の正の数nが、${\displaystyle nG={\mathcal {O}}}$（曲線の無限遠点、および単位元）は、通常素数である。nはの部分群のサイズであるため${\displaystyle E(\mathbb {F} _{q})}$ラグランジュの定理から、その数は${\displaystyle h={\frac {1}{n}}|E(\mathbb {F} _{q})|}$は整数です。暗号化アプリケーションでは、この数値hはコファクターと呼ばれ、通常は小さく、理想的には 1 です。コファクターが 1 より大きい曲線を使用するプロトコルは、コファクターを適切に処理する必要があります。まとめると、素数の場合、ドメインパラメータは次のようになります。${\displaystyle (p,a,b,G,n,h)}$バイナリの場合、それらは${\displaystyle (m,f,a,b,G,n,h)}$。

ドメインパラメータが、その使用に関して信頼できる当事者によって生成されたという保証がない限り、ドメインパラメータは使用前に検証されなければならない。

ドメインパラメータの生成は、曲線上の点の数を計算する必要があり、時間と手間がかかるため、通常は各参加者が個別に行うことはありません。そのため、いくつかの標準化団体が、一般的な体サイズに対応した楕円曲線のドメインパラメータを公開しています。このようなドメインパラメータは一般に「標準曲線」または「名前付き曲線」と呼ばれ、名前付き曲線は、名前または標準文書で定義されている一意のオブジェクト識別子によって参照できます。

• NIST、SP 800-186: 離散対数ベース暗号化に関する推奨事項: 楕円曲線ドメインパラメータ^{[ 6 ]}
• SECG、SEC 2：推奨される楕円曲線領域パラメータ

• ECC Brainpool ( RFC 5639 )、ECC Brainpool 標準曲線と曲線生成は、Wayback Machineに 2018-04-17 にアーカイブされています^{[ 19 ] [ 20 ]} 

SECG テストベクトルも利用可能です。^{[ 21 ]} NIST は多くの SECG 曲線を承認しているため、NIST と SECG が公開している仕様にはかなりの重複があります。EC ドメインパラメータは、値または名前で指定できます。

前述の注意にもかかわらず、独自のドメインパラメータを構築することにした場合は、基礎となるフィールドを選択し、以下のいずれかの方法を使用して、適切な（つまり、素数に近い）数の点を持つ曲線を見つけるための以下の戦略のいずれかを使用する必要があります。

• ランダムな曲線を選択し、一般的な点計数アルゴリズム（例えば、SchoofのアルゴリズムまたはSchoof–Elkies–Atkinアルゴリズム）を使用します。
• 点の数を簡単に計算できるファミリーからランダムな曲線を選択する（例：コブリッツ曲線）、または
• 点の数を選択し、複素乗算法を用いてこの数の点を持つ曲線を生成します。^{[ 22 ]}

いくつかの種類の曲線は弱く、避けるべきである。

• カーブを越えて$\displaystyle \mathbb {F} _{2^{m}}}$非素数mはワイル降下攻撃に対して脆弱である。^{[ 23 ] [ 24 ]}
• nが割り切れるような曲線${\displaystyle p^{B}-1}$（ここでpは体の標数です。素体の場合はq 、または${\displaystyle 2}$十分小さいBに対して、二元体の場合）は、小次数拡張体で通常の離散対数問題(DLP)を適用するMenezes–Okamoto–Vanstone (MOV) 攻撃^{[ 25 ] [ 26 ]}に対して脆弱である。$\displaystyle \mathbb {F} _{p}}$ECDLP を解くには、境界Bは、フィールドの離散対数が$\displaystyle \mathbb {F} _{p^{B}}}$楕円曲線上の離散対数を計算するのと少なくとも同程度に難しい${\displaystyle E(\mathbb {F} _{q})}$[ ^{27 ]​}
• 曲線が${\displaystyle |E(\mathbb {F} _{q})|=q}$曲線上の点を加法群にマッピングする攻撃に対して脆弱である。$\displaystyle \mathbb {F} _{q}}$[ ^{28 ] [ 29 ] [ 30 ]​}

ECDLPを解くことができる既知の最速アルゴリズム（ベビーステップジャイアントステップ、ポラードのρなど）はすべて、${\displaystyle O({\sqrt {n}})}$ステップから、基となるフィールドのサイズはセキュリティパラメータの約2倍である必要があることがわかります。たとえば、128ビットのセキュリティの場合、曲線は$\displaystyle \mathbb {F} _{q}}$、 どこ$q ≈ 2256$^{これは、 3072ビット}の公開鍵と 256 ビットの秘密鍵を必要とする有限体暗号 (DSA など) や、秘密鍵が 3072 ビットの n 値を必要とする整数因数分解暗号 (RSA など⁾とは対照的です。ただし、特に処理能力が限られている場合は、効率的な暗号化に対応するために公開鍵を小さくすることができます。

過去の公開 ECDLP チャレンジ記録には、素体ケースの 112 ビット鍵と二進体ケースの 109 ビット鍵が含まれています。素体ケースについては、200 台以上のPlayStation 3ゲームコンソールのクラスタを使用して 2009 年 7 月に破られ、このクラスタを連続して実行すれば 3.5 か月で完了できた可能性があります。^{[ 32 ]}二進体ケースは、2600 台のコンピュータを使用して 2004 年 4 月に 17 か月かけて破られました。^{[ 33 ]}二進体 ECC2K-130 チャレンジは、CPU、GPU、FPGA を使用した分散コンピューティングによってもターゲットにされています。^{[ 34 ]}

加算規則を詳しく調べると、2 つの点を加算するには、$\displaystyle \mathbb {F} _{q}}$しかし、反転操作でもある。反転（与えられた場合）${\displaystyle x\in \mathbb {F} _{q}}$探す$\displaystyle y\in \mathbb {F} _{q}}$そのため${\displaystyle xy=1}$）は乗算よりも1～2桁遅い^{[ 35 ]}。しかし、曲線上の点は、 2点を加算するために逆演算を必要としない異なる座標系で表現することができる。そのようなシステムがいくつか提案されている。射影座標系では、各点は3つの座標で表現される。${\displaystyle (X,Y,Z)}$以下の関係式を使用します。${\displaystyle x={\frac {X}{Z}}}$、${\displaystyle y={\frac {Y}{Z}}}$ヤコビアンシステムでは、点も3つの座標で表されます。${\displaystyle (X,Y,Z)}$しかし、異なる関係が用いられる。${\displaystyle x={\frac {X}{Z^{2}}}}$、${\displaystyle y={\frac {Y}{Z^{3}}}}$;ロペス・ダハブ系では、関係は次のようになる。${\displaystyle x={\frac {X}{Z}}}$、${\displaystyle y={\frac {Y}{Z^{2}}}}$修正ヤコビアンシステムでは、同じ関係式が使用されるが、4つの座標が格納され、計算に使用される。${\displaystyle (X,Y,Z,aZ^{4})}$チュドノフスキー・ヤコビアン系では5つの座標が使用される。${\displaystyle (X,Y,Z,Z^{2},Z^{3})}$。命名規則が異なる場合があることに注意してください。たとえば、IEEE P1363 -2000 規格では、一般的にヤコビ座標と呼ばれるものを指すのに「射影座標」を使用しています。混合座標を使用すると、さらに高速化できます。^{[ 36 ]}

pを法とする還元(加算と乗算に必要な) は、素数p が擬似メルセンヌ素数(ソリナス素数)である場合、はるかに高速に実行できます。${\displaystyle p\approx 2^{d}}$; 例えば、${\displaystyle p=2^{521}-1}$（P-521）または${\displaystyle p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1.}$バレット還元と比較すると、1桁の速度向上が見込める。^{[ 37 ]}ここでの速度向上は理論的なものではなく実用的なものであり、2のべき乗に近い数の剰余演算は、ビット演算でバイナリ数を操作するコンピュータによって効率的に実行できるという事実から生じる。

曲線が${\displaystyle \mathbb {F} _{p}}$擬似メルセンヌP-256およびP-384は、NISTによってSP 800-186で推奨されています。NIST曲線はa  =  −3も使用しており、ヤコビアン座標での加算を改善しています。BernsteinとLangeは、 NIST曲線の設計上の選択のいくつかを批判し、SafeCurvesプロジェクトで曲線選択の代替基準を挙げています。^{[ 38 ]}

その他広く使われている曲線も、効率的な還元を可能にする特別な形式の素数を使用しています。${\displaystyle p=2^{255}-19}$Curve25519 および${\displaystyle 2^{448}-2^{224}-1}$Curve448の場合。^{[ 38 ]}

他のほとんどの離散対数問題(DLP) システム (二乗と乗算に同じ手順を使用できる) とは異なり、EC 加算は、使用する座標系に応じて、倍数化 ( P = Q ) と一般加算 ( P ≠ Q ) で大きく異なります。したがって、たとえば固定パターン ウィンドウ (別名コム) メソッド^{[ 39 ]}を使用して、サイドチャネル攻撃(タイミング攻撃や単純/差分電力解析攻撃など)に対抗することが重要です(計算時間は増加しません)。あるいは、エドワーズ曲線を使用することもできます。これは、倍数化と加算を同じ操作で実行できる楕円曲線の特殊なファミリーです。^{[ 40 ]} ECC システムに関するもう 1 つの懸念は、特にスマート カード上で実行する場合のフォールト攻撃の危険性です。^{[ 41 ]}

暗号専門家は、国家安全保障局が少なくとも1つの楕円曲線ベースの擬似乱数発生器に盗聴バックドアを挿入したのではないかと懸念を表明している。 ^{[ 42 ]}元NSA契約職員のエドワード・スノーデンがリークした内部メモによると、NSAはDual EC DRBG標準にバックドアを仕込んだとされている。^{[ 43 ]}バックドアの可能性に関する分析では、アルゴリズムの秘密鍵を所有する攻撃者は、わずか32バイトのPRNG出力から暗号鍵を取得できると結論付けている。^{[ 44 ]}

SafeCurvesプロジェクトは、バックドアの可能性を最小限に抑えるために、安全に実装しやすく、完全に公開検証可能な方法で設計された曲線をカタログ化しています。^{[ 45 ]}

ショアのアルゴリズムは、十分な大きさの耐障害性量子コンピュータ上で離散対数を計算することで、楕円曲線暗号を破るために使用できます。 256 ビットのモジュラス (128 ビットのセキュリティ レベル) を持つ曲線を破るための公開されている量子リソースの見積もりには、2330 個の論理量子ビットと 1260 億個のトフォリ ゲートが含まれています。^{[ 46 ]}バイナリ楕円曲線の場合、128 ビットのセキュリティを破るには 906 個の論理量子ビットが必要です。^{[ 47 ]}これらの見積もりは、現在の量子コンピュータが展開されている ECC システムを破ることができることを意味するものではありませんが、移行計画を立てる理由となります。

2024 年 8 月、NIST はポスト量子暗号に関する最初の 3 つの連邦情報処理標準(FIPS 203 (ML-KEM)、FIPS 204 (ML-DSA)、FIPS 205 (SLH-DSA)) を承認しました。^{[ 48 ]} NIST はこれらの標準を鍵確立とデジタル署名の主要なポスト量子標準と説明しています。^{[ 49 ]} NSA の CNSA 2.0 ガイダンスも同様に国家安全保障システム向けの量子耐性アルゴリズムを特定し、移行中は CNSA 1.0 への準拠が引き続き必要であると述べています。^{[ 7 ]}

超特異同種ディフィー・ヘルマン鍵交換は、同種を用いた楕円曲線ベースの鍵交換のポスト量子形式として提案された。^{[ 50 ]}しかし、新たな古典的攻撃により、このプロトコルの安全性が損なわれた。^{[ 51 ]}

2015年8月、NSAは「そう遠くない将来」に量子攻撃に耐性のある新しい暗号スイートに移行する計画を発表した。「残念ながら、楕円曲線暗号の使用の増加は、量子コンピューティングの研究の継続的な進歩と衝突しており、暗号戦略の再評価が必要となっている。」^{[ 13 ]}

ECCの実装では、秘密のスカラーを攻撃者が指定した点と乗算する際に、その点が意図した曲線上および正しい部分群にあることを検証しない場合、無効曲線攻撃に対して脆弱になる可能性がある。このような攻撃では、無効な点または小位数の点に対する繰り返し演算によって、秘密スカラーに関する情報が漏洩する可能性がある。2019年には、AMD Secure Encrypted Virtualizationに対する無効曲線攻撃によってPlatform Diffie–Hellman (PDH)の秘密鍵が復元されたことが報告されている。^{[ 52 ]}