暗号強度とは？TLSの仕組みとDH・ECC・RSA・格子暗号の計算量比較
「256bitだから安全」は半分だけ正しい説明です。暗号強度は鍵長だけでなく、その裏にある数学的問題を解くアルゴリズムの進歩によって変わります。
TLSはどう暗号を組み合わせているか
HTTPS通信を支えるTLS(Transport Layer Security)は、単一の暗号アルゴリズムではなく、複数の暗号技術を 役割ごとに組み合わせた「暗号スイート」で構成されています。TLS 1.3のハンドシェイクを例にすると、 おおむね次のような役割分担になっています。
| 鍵交換 | ECDHE(楕円曲線Diffie-Hellman、一時鍵)。通信のたびに新しい鍵ペアを生成し、Forward Secrecy(前方秘匿性)を確保 |
|---|---|
| 署名・認証 | RSAまたはECDSA。サーバー証明書によって「本当にそのドメインの持ち主か」を保証 |
| 共通鍵暗号 | AES-GCMやChaCha20-Poly1305。実際の通信データはこちらの高速な共通鍵暗号で暗号化 |
| ハッシュ関数 | SHA-256等。鍵導出(HKDF)やメッセージ認証に使用 |
つまりTLSは「公開鍵暗号で鍵を安全に共有し、共有した鍵で高速な共通鍵暗号を使う」という ハイブリッド構成を取っています。OpenSSLのようなライブラリは、この暗号スイートの組み合わせを 実装し、サーバーとクライアントの双方が対応しているアルゴリズムをネゴシエーションします。
OpenSSLで使われる暗号の種類
鍵交換・署名に使われる公開鍵暗号は、大きく分けて3つの数学的問題のいずれかに安全性の根拠を 置いています。
| DH(Diffie-Hellman) | 有限体上の離散対数問題(DLP)。g^x mod pからxを求める困難さに依拠 |
|---|---|
| ECC(楕円曲線暗号) | 楕円曲線上の離散対数問題(ECDLP)。同じ安全性強度をDHより大幅に短い鍵長で実現できる |
| RSA | 大きな合成数の素因数分解問題。n = p × qからp, qを求める困難さに依拠 |
| 格子暗号(耐量子) | 格子上の最短ベクトル問題(SVP)・Learning With Errors(LWE)。量子コンピュータでも効率的に解く方法が(現時点で)知られていない問題として、NISTの耐量子暗号標準(ML-KEM/Kyber、ML-DSA/Dilithium)に採用 |
既知アルゴリズムと計算量の関係
「鍵長が長いほど安全」というのは、同じアルゴリズムファミリーの中でのみ成り立つ話です。実際には、 それぞれの問題を解く「最良の既知アルゴリズム」の計算量こそが、実質的な安全性強度を 決めています。
| RSA(素因数分解) | 一般数体篩法(GNFS)が最良の古典アルゴリズム。計算量は準指数関数的exp((64/9)^(1/3) · (ln n)^(1/3) · (ln ln n)^(2/3))のオーダーで、鍵長の増加とともに緩やかに攻略が難しくなる |
|---|---|
| DH/ECC(離散対数) | 有限体上はGNFS系の指数計算法、楕円曲線上はPollardのρ法が最良の古典アルゴリズム。ρ法は完全指数関数的(2^(n/2)のオーダー)であるため、ECCはRSAよりずっと短い鍵長で同等の安全性強度を得られる |
| 格子(SVP/LWE) | LLL法・BKZ法が実用上の最良アルゴリズム。パラメータ次第で困難度が指数関数的に増大するよう設計されている |
たとえばRSA-3072とECC(楕円曲線)の256bit鍵は、おおむね同程度の安全性強度(128bit security)とされています。 これはRSA側の攻撃アルゴリズム(GNFS)が準指数関数的なのに対し、ECC側の攻撃アルゴリズム(Pollardのρ法)が 完全指数関数的であるという、攻撃側アルゴリズムの計算量クラスの違いに起因します。
暗号強度の見積もりは、あくまで「現時点で知られている最良のアルゴリズムに対して」計算されたものです。 もし将来、素因数分解や離散対数問題に対して現在より高速な古典アルゴリズムが発見されれば、鍵長を 増やす対応だけでは追いつかない可能性があります。実際、格子暗号がNISTの標準に選ばれた最大の理由も 「量子コンピュータでSVP/LWEを効率的に解くアルゴリズムが、現時点で知られていない」という消極的な 理由にすぎず、将来その状況が変わらない保証はどこにもありません。暗号の安全性は「鍵長」という 静的な数字ではなく、「その問題を解くアルゴリズム研究がどこまで進んでいるか」という動的な競争の 上に成り立っています。
まとめ
- TLSは鍵交換(ECDHE等)・署名(RSA/ECDSA)・共通鍵暗号(AES等)を組み合わせたハイブリッド構成
- DH・ECC・RSAはそれぞれ離散対数問題・楕円曲線離散対数問題・素因数分解問題に安全性の根拠を置く
- ECCがRSAより短い鍵長で同等の安全性を得られるのは、攻撃アルゴリズムの計算量クラスの違いによる
- 暗号強度は固定値ではなく、攻撃アルゴリズム研究の進歩によって将来変わりうる相対的な評価である