Skip to content
検索結果に戻る

楕円曲線暗号

提唱者
Neal Koblitz
年
1985
種類
asymmetric encryption and key agreement
系統
Public-key cryptography

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

楕円曲線暗号(ECC)は、有限体上の楕円曲線のもつ代数構造に基づいた公開鍵暗号方式である。1985年にニール・コブリッツとビクター・ミラーによって独立に提案されたECCは、RSAと同等の安全性をはるかに小さい鍵サイズで提供する。現代の暗号技術では、その効率性からECCがますます重視されており、256ビットのECC鍵は2048ビットのRSA鍵に匹敵するセキュリティを提供するため、リソースが制約された環境や高性能システムに最適である。

手法の背後にある直感

ECCは、楕円曲線離散対数問題に基づいている。これは、曲線の方程式と2つの点を与えられた場合、曲線の幾何学的性質を用いてそれらの和を容易に計算できるが、この操作を逆算して、ある点を別の点に到達させるために何回加算する必要があるかを見つけることは極めて困難であるという性質である。この非対称性が安全な鍵生成と交換を可能にする。RSAが素因数分解問題に依存しているのに対し、ECCの困難さは楕円曲線群の構造に由来する。

歴史学

ECCは、1985年から1987年にかけてニール・コブリッツとビクター・ミラーによって独立に発明された。当初、特許懸念とRSAの確立された優位性により、採用は遅かった。しかし、2000年代以降、特に米国国家安全保障局(NSA)が機密情報に楕円曲線の使用を推奨した後、ECCは優れた代替手段として注目を集めた。TLS 1.3、Signal、ブロックチェーンシステムなどの現代のプロトコルは、Curve25519やP-256などのECC曲線にほぼ標準化されている。

使うべき場面

ECCは、モバイルデバイス、IoTシステム、組み込みシステムなど、リソースが限られた環境で強力なセキュリティを必要とするアプリケーションに最適である。現代のインターネットプロトコル(TLS 1.3はECDHEを使用)、ブロックチェーンシステム(BitcoinおよびEthereumはECDSAを使用)、およびメッセージングアプリ(SignalはCurve25519を使用)で標準化されている。ECCは、優れたパフォーマンスと同等のセキュリティにより、新しいシステムではRSAよりも優先されるべきである。

限界と注意点

  • RSAよりも数学的基盤が複雑であり、実装と分析がより困難になる
  • 楕円曲線パラメータの慎重な選択が必要であり、弱い曲線(埋め込み次数が低いものなど)は攻撃に対して脆弱である
  • セキュリティは使用される特定の曲線に大きく依存しており、標準化された曲線が好ましいが、その選択にはいくらかの論争が伴う

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 同等のセキュリティレベルに対してRSAよりもはるかに小さい鍵サイズであり、ストレージと伝送のオーバーヘッドを削減する
  • 同じセキュリティ強度に対してRSAよりも高速な鍵生成、暗号化、復号
  • 携帯電話、IoTデバイス、スマートカードなどのリソース制約型デバイスに適している
  • 現代の暗号ライブラリやプロトコル全体で標準化およびサポートが拡大している

応用

  • TLS/SSL暗号化(HTTPSおよび現代のWebセキュリティ用、ECDHE鍵交換を使用)
  • ブロックチェーンおよび暗号通貨システム(Bitcoinはsecp256k1でECDSAを使用、Ethereumはsecp256k1でアカウントおよびトランザクション署名を使用)
  • メッセージングおよび安全な通信(SignalプロトコルはCurve25519およびX25519を使用)
  • スマートカード、ハードウェアセキュリティモジュール、および政府発行の認証情報における認証およびデジタル署名
  • 計算リソースが限られているIoTおよび組み込みシステムのセキュリティ
  • ポスト量子暗号研究、量子耐性アルゴリズムのための双曲線曲線に関する研究

使い方

使い方

1

楕円曲線の方程式(通常は有限体上の y^2 = x^3 + ax + b)、曲線上の生成元点 G、および位数 n(曲線上の点の数)を選択する。秘密鍵 d はランダムな整数であり、公開鍵 Q = d × G は点の乗算によって計算される。

2

楕円曲線上の点は、幾何学的な加算演算の下で群を形成する。2つの異なる点を加算するには、それらを通る直線を引き、それが曲線と交差する点を見つけ、その結果をx軸に関して反射させる。点の二重化には代わりに接線を使用する。

3

公開鍵 Q に対してメッセージを暗号化するには、ランダムな k を生成し、2つの値、すなわち点 (x, y) = k × G と、メッセージと k × Q のハッシュを組み合わせた暗号化メッセージを計算する。

4

受信者は秘密鍵 d を使用して d × (k × G) = k × (d × G) = k × Q を計算し、共有秘密を復元してメッセージを復号する。

よくある落とし穴

  • 点の乗算をサイドチャネル攻撃から保護せずに実装すると、タイミングや電力消費の分析を通じて秘密鍵が漏洩する可能性がある
  • セキュリティを皆無のレベルに低下させる数学的な弱点を持つ可能性のある、弱いまたは非標準の楕円曲線を使用すること
  • ECDSA署名における一時鍵 k に暗号学的に安全な乱数生成器を使用しないと、署名が偽造可能になる

よくある質問

なぜ256ビットECC鍵は2048ビットRSA鍵と同等のセキュリティを持つのか?

楕円曲線上の離散対数問題は、整数分解問題よりも困難である。量子コンピュータを使用するShorのアルゴリズムを用いても、ECDLPの解決には指数時間が必要であるが、整数分解は量子コンピュータ上では多項式時間になる。

最も一般的に使用されている楕円曲線は?

NIST標準化曲線はP-256、P-384、P-521である。実装攻撃に対する堅牢性から、BernsteinのCurve25519が現代のシステムで好まれている。Bitcoinはsecp256k1を使用し、Ethereumもアカウントおよびトランザクション署名にsecp256k1を使用している。

ECCは量子コンピュータに対して脆弱か?

はい、Shorのアルゴリズムは量子コンピュータ上で楕円曲線離散対数問題を解くことができるため、ECCとRSAの両方が脆弱になる。ポスト量子暗号研究では、格子ベース、符号ベース、多変数ベースの代替手段が開発されている。

ECDHとECDSAの違いは何ですか?

ECDH(楕円曲線ディフィー・ヘルマン)は、安全でないチャネル上で共有秘密を確立するための鍵合意プロトコルである。ECDSA(楕円曲線デジタル署名アルゴリズム)は、デジタル署名の作成と検証に使用される。

ECDHとECDSAに同じ鍵を使用できますか?

技術的には可能だが推奨されない。暗号化と署名操作に別々の鍵を使用することは、鍵分離の原則に従い、微妙な脆弱性のリスクを低減する。

関連する手法

参考文献

  1. Miller, V. S. (1985). Use of Elliptic Curves in Cryptography. In Proceedings of the Advances in Cryptology - CRYPTO 1985, LNCS 218, pp. 417-426.

    DOI 文献を開く
    コピーしました。
  2. Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177), 203-209.

    DOI 文献を開く
    コピーしました。