共通鍵暗号の最大の弱点は 「事前に鍵を共有する必要がある」 こと。インターネットで初めて出会うサーバとどう秘密鍵を共有するのか?この問いに答えたのが 公開鍵暗号(非対称暗号)。1976 年の Diffie-Hellman、1977 年の RSA という大発明から始まった暗号革命です。本講では RSA の数学的根拠(素因数分解の困難さ)、Diffie-Hellman の鍵交換(離散対数の困難さ)、現代主流の 楕円曲線、TLS や WireGuard で使われる ハイブリッド暗号 の発想、そして 2030 年代に向けて急速に進む 耐量子暗号(PQC) まで踏み込みます。
本講を終えると、以下を達成できるようになります。
初めて訪れる Web サイトと安全に通信するには、まず 共通鍵を共有 する必要があります。しかし、その共有自体が安全である保証はどこに?盗聴されているかもしれない回線で「秘密鍵」を送れば、すぐに盗まれます。これが公開鍵以前の世界の根本問題でした。
図の見方:左の世界では「鍵 K をどうやって秘密に渡すか」自体が問題。右の世界では、ボブが あらかじめ公開鍵を世界中に配っている。アリスは初対面でも、その公開鍵で暗号化するだけ。復号できるのは秘密鍵を持つボブ本人だけ。
つながる知識: 公開鍵の発想自体は マーケル(Ralph Merkle) が学生時代から温めていたもの(マーケルパズル)。Diffie・Hellman の論文と独立に、似た着想が複数の研究者から出てきていた。1977 年に MIT の Rivest・Shamir・Adleman が RSA として実装可能な具体的アルゴリズムを発表したことで、理論から技術への転換が起きた。
確認: 公開鍵暗号が解決しようとした「鍵配送問題」とは、共通鍵暗号のどのような困難を指すか?
正解:B。100 人なら 4950 通り、10000 人なら 5000 万通りの鍵ペアが必要で、しかもそれぞれ「事前に物理的に会う」「信頼できる別経路」で渡す必要があった。インターネット時代には現実的でない。公開鍵暗号は 「公開鍵を世界に晒したまま、誰とでも通信できる」 という構造でこれを根本的に解決した。
# 1) 素数選び(本物は数百桁、ここでは小学生サイズ)
p = 11, q = 13
n = p * q = 143
φ(n) = (p-1)(q-1) = 10 * 12 = 120
# 2) 公開指数 e を選ぶ(φ(n) と互いに素)
e = 7
# 3) 秘密指数 d を計算(7 * d ≡ 1 mod 120)
d = 103 (確認: 7 * 103 = 721 = 6 * 120 + 1)
# 公開鍵 = (e=7, n=143)
# 秘密鍵 = (d=103, n=143)
# 4) アリスが m = 9 をボブに送りたい
c = m^e mod n = 9^7 mod 143 = 48
# 5) ボブが復号
m = c^d mod n = 48^103 mod 143 = 9 ← 元に戻った!本物の RSA では n は 2048〜4096 bit(617〜1233 桁)。素因数分解の困難さに守られて、d を計算で導けない仕組みです。
これは オイラーの定理 の帰結:任意の整数 m < n、gcd(m, n) = 1 について mφ(n) ≡ 1 (mod n) が成り立つ。e と d は e × d ≡ 1 mod φ(n) を満たすように選んだので、med = m1 + k·φ(n) ≡ m × (mφ(n))k ≡ m × 1k ≡ m (mod n)。つまり「e 乗してから d 乗すれば元に戻る」。
素因数分解問題:n = p × q から p, q を求めること。古典コンピュータでは 準指数時間(GNFS)が最良。2048 bit n の分解は現代の計算機でも実用的に不可能。
n を p × q に分解できれば、φ(n) と d がすぐ計算できて秘密鍵が露出。世界中の RSA 暗号通信が一瞬で復号可能になる。これが 2030 年代に量子計算機が登場すると現実化 する(後述 §07)。
素の RSA(textbook RSA)は 同じ平文 m を 2 回送ると同じ暗号文 c になる(決定論的)、m が小さいと c = me が n より小さくなる、選択暗号文攻撃に弱い など、複数の脆弱性があります。実用では必ず OAEP パディング(RFC 8017) を施した RSA-OAEP を使います。OpenSSL のデフォルトもこちら。
確認: RSA の安全性の根拠として、最も適切なものはどれか。
正解:C。RSA は「素因数分解が困難」という未解決の計算量論的仮定の上に成立している(数学的に「絶対不可能」が証明されたわけではない)。現代の最強アルゴリズム GNFS でも 2048 bit の合成数を分解するには宇宙年齢級の時間がかかる。なお、量子計算機が登場すると Shor アルゴリズムで多項式時間に潰されるため、この前提が破綻する ─ これが PQC が急がれる本質的理由。アルゴリズムや公開鍵自体は秘密ではない(Kerckhoffs の原則)。
DH の本質を直感的に表す有名なアナロジー:
# 公開パラメータ
p = 23, g = 5 # (本物は p が 2048〜4096 bit)
# アリス側
a = 6 (秘密)
A = g^a mod p = 5^6 mod 23 = 8 (公開)
# ボブ側
b = 15 (秘密)
B = g^b mod p = 5^15 mod 23 = 19 (公開)
# 共有鍵を計算
アリス:K = B^a mod p = 19^6 mod 23 = 2
ボブ :K = A^b mod p = 8^15 mod 23 = 2
# 同じ K = 2 が得られる!(本物では K は 256+ bit のランダム値)盗聴者は p, g, A を知っているので、理論的には A = ga mod p を満たす a を求めれば良い。しかしこれが 離散対数問題 で、p が大きいと古典計算機では解けない。RSA の素因数分解問題と同じく、量子計算機(Shor アルゴリズム)では 多項式時間で解ける ─ ここが現代暗号の脆弱性の本丸。
つながる知識: 現代では 「同じセッション鍵を使い回さない」(Forward Secrecy)のため、セッションごとに DH を実行する Ephemeral DH(DHE / ECDHE) が標準。TLS 1.3 では ECDHE のみ 許容され、過去のセッション鍵を再利用する古いやり方は完全に廃止されました。
Q. 攻撃者が DH 鍵交換をすべて盗聴して g、p、A = g^a mod p、B = g^b mod p をすべて手に入れたとする。なぜそれでも共有秘密 K = g^(ab) mod p が攻撃者に求められないのか?
攻撃者が必要なのは K = g^(ab) mod p。手元には A = g^a と B = g^b がある。素直に計算するには a(または b)を A から逆算する必要があり、これが 離散対数問題:「g^a ≡ A (mod p) なる a を求めよ」。
p が 2048 bit クラスなら、現代の最強アルゴリズム(General Number Field Sieve の離散対数版)でも実用的時間では解けない。g^a と g^b から g^(ab) を計算する(Computational Diffie-Hellman 問題)も同等の難しさと信じられている。
別の手は MITM(中間者攻撃)で 偽の B を送り込む こと。これは数学的攻撃ではなく 認証の欠如 を突くもので、TLS では証明書による認証で塞がれている。「DH 単独」は MITM に弱いので、必ず認証(署名 / 証明書)と組み合わせて運用される。
| 強度(共通鍵相当) | RSA / DH 鍵長 | EC 鍵長 | 用途 |
|---|---|---|---|
| 80 bit | 1024 bit | 160 bit | レガシー(廃止推奨) |
| 112 bit | 2048 bit | 224 bit | 2030 年まで |
| 128 bit | 3072 bit | 256 bit(P-256, Curve25519) | 現代の標準 |
| 192 bit | 7680 bit | 384 bit | 高セキュリティ |
| 256 bit | 15360 bit | 512 bit | 政府機密・長期保存 |
RSA-3072 の暗号化は CPU・メモリ・通信量すべてに重い。スマホで TLS 接続するたびに 3072 bit の鍵を交換すると電池が減る。ECC-256 なら同じ強度で 計算量・通信量とも 1/10 程度。これが Web の TLS が ECDHE 中心に移った理由です。
2005 年に Daniel J. Bernstein(djb)が設計した Curve25519 は、安全性・速度・実装の単純さを兼ね備えた楕円曲線。SSH、WireGuard、TLS、Signal プロトコル など、新しい標準のほとんどがこれを採用。サイドチャネル攻撃に対する強さも特長で、NIST 曲線が抱えていたとされる懸念(NSA バックドア説) を回避する選択肢としても支持されています。
つながる知識: WireGuard は鍵交換に Curve25519、共通鍵に ChaCha20-Poly1305、ハッシュに BLAKE2s という、すべて djb 系のモダンプリミティブを採用しています。「現代暗号の最小限ツールキット」とも言える組み合わせ。
確認: 楕円曲線暗号(ECC)が RSA と同じ強度を「短い鍵」で達成できる理由として、最も適切なものはどれか。
正解:B。RSA / 古典 DH の前提となる「素因数分解」「整数離散対数」は GNFS で sub-exponential time で解ける。一方、楕円曲線群上の離散対数(ECDLP)は Pollard's rho 程度しか知られておらず、ほぼ完全な指数時間。だから 256 bit の楕円曲線で約 128 bit 強度 ≒ RSA-3072 と同等が達成できる。これがモバイル・IoT・WireGuard で ECC が好まれる理由。C は誤り(Shor は楕円曲線版もある)。
図の見方:TLS 1.3 では最初の 1 往復で ECDHE による鍵交換 + サーバ証明書による認証 が完了し、すぐに共通鍵での暗号化通信が始まる。公開鍵暗号は鍵交換と署名のみ、本文の暗号化は共通鍵が担う。これがハイブリッド暗号の現代の姿。詳細は 標準 TLS を参照。
Q. 「公開鍵暗号は遅い」と聞くと「全部共通鍵にすればいいのでは?」と思いがち。なぜ実際のプロトコル(TLS / SSH / WireGuard 等)はわざわざハイブリッド構成を取るのか?
共通鍵だけだと「鍵をどう渡すか」で詰む。 受信側が暗号文を復号するには共通鍵が必要だが、その共通鍵を平文で渡せば盗聴される。暗号化して渡すには別の鍵が必要 ─ 鶏と卵の問題。
公開鍵だけだと遅すぎる。 RSA-2048 の暗号化処理は数 ms 級、AES-GCM は数 GB/秒。1 GB のデータを RSA で全部暗号化するのは数時間〜数日かかり実用に耐えない。
解決策がハイブリッド。 「公開鍵で 共通鍵の値そのもの を安全に交換し、その後の本文は共通鍵で高速暗号化」。これにより「鍵配送問題」と「速度」を同時解決。TLS 1.3 ではさらに ECDHE を使って Forward Secrecy も同時に得る ─ 「最良の組み合わせ」が現代の標準形。
# 秘密鍵を生成(2048 bit)
openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:2048 \
-out rsa_priv.pem
# 公開鍵を抽出
openssl rsa -in rsa_priv.pem -pubout -out rsa_pub.pem
# 中身を確認
openssl pkey -in rsa_priv.pem -text -noout | head -20# 平文を作成
echo "hello from alice" > plain.txt
# ボブの公開鍵で暗号化(OAEP パディング)
openssl pkeyutl -encrypt -pubin -inkey rsa_pub.pem \
-pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 \
-in plain.txt -out cipher.bin
# ボブの秘密鍵で復号
openssl pkeyutl -decrypt -inkey rsa_priv.pem \
-pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 \
-in cipher.bin -out decrypted.txt
cat decrypted.txt
# → hello from alice注意:RSA-2048 で暗号化できるのは 最大 ~190 バイト。長いデータはハイブリッド方式(セッション鍵を RSA、本文を AES)で扱う。
# P-256 曲線の秘密鍵を生成
openssl genpkey -algorithm EC -pkeyopt ec_paramgen_curve:P-256 \
-out ec_priv.pem
# Curve25519 を使うなら(モダン)
openssl genpkey -algorithm Ed25519 -out ed_priv.pem
# 公開鍵を抽出
openssl pkey -in ec_priv.pem -pubout -out ec_pub.pem
# 鍵長を確認
openssl pkey -in ec_priv.pem -text -noout | grep -i bit
# → ASN1 OID: prime256v1 (= NIST P-256, 256 bit)# アリス・ボブの鍵ペアをそれぞれ作る
openssl genpkey -algorithm X25519 -out alice_priv.pem
openssl pkey -in alice_priv.pem -pubout -out alice_pub.pem
openssl genpkey -algorithm X25519 -out bob_priv.pem
openssl pkey -in bob_priv.pem -pubout -out bob_pub.pem
# アリス側で共有鍵を導出(自分の秘密 + ボブの公開)
openssl pkeyutl -derive -inkey alice_priv.pem \
-peerkey bob_pub.pem -out alice_shared.bin
# ボブ側で共有鍵を導出(自分の秘密 + アリスの公開)
openssl pkeyutl -derive -inkey bob_priv.pem \
-peerkey alice_pub.pem -out bob_shared.bin
# 同じ鍵が得られたか確認
diff alice_shared.bin bob_shared.bin && echo "同じ!"
xxd alice_shared.bin # → 32 バイトの共有鍵これで両者は 同じ 32 バイトの秘密値 を、公開チャネルだけで共有できました。以降は AES-GCM 等で暗号化通信できます ─ これがハイブリッド暗号の入口。
# pip install cryptography
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
alice = X25519PrivateKey.generate()
bob = X25519PrivateKey.generate()
# 公開鍵交換(普段はネットワーク越しに行う)
alice_pub = alice.public_key()
bob_pub = bob.public_key()
# 共有鍵を導出
alice_shared = alice.exchange(bob_pub)
bob_shared = bob.exchange(alice_pub)
print(alice_shared == bob_shared) # → True
print(alice_shared.hex()) # → 32 バイトの共有秘密量子計算機が完成するまで待つ必要はありません。攻撃者は 今のうちに暗号通信を全部記録 しておき、将来の量子計算機で復号することができます。長期機密(政府文書・医療記録・知財) は 今すぐ PQC に移行 する必要があるため、Cloudflare、Google、Apple、AWS などが既に ハイブリッド ECDH + Kyber 方式の TLS を実用化しています(2024 年現在)。
| 時期 | 主な動き |
|---|---|
| 2016 | NIST が PQC 公募開始 |
| 2022 | 第1回受賞者発表(Kyber, Dilithium, Falcon, SPHINCS+) |
| 2024 8月 | FIPS 203/204/205 として標準化完了 |
| 2024〜 | Cloudflare・Google・Apple が TLS で X25519+Kyber768 ハイブリッドを実装 |
| 2025〜 | OpenSSH 9.9 が PQC をデフォルト有効化 |
| 2030 年代 | 量子計算機が現実の脅威に → 全面移行が必須 |
つながる知識: PQC は「単に新しい暗号を選ぶ」だけでは済みません。鍵サイズが大きい(Kyber768 の公開鍵 ~1184 バイト、署名 ~2400 バイト)、計算量が増える、過去の機器が対応できない など、運用面の影響が大きい。今後 10 年は「ハイブリッド方式(ECDHE + Kyber 等を併用)」で 古典暗号と PQC を併用 しながら徐々に移行する見込みです。
確認: Shor アルゴリズムが量子計算機で動いた場合、影響を受けない暗号はどれか。
正解:D。Shor アルゴリズムは「素因数分解」「離散対数」を多項式時間で解く。RSA・DH・ECDH・ECDSA・Ed25519 はすべてこの 2 種類の困難性に立脚しているので 全滅。一方、AES のような共通鍵暗号は数論的構造ではなく純粋なビット操作で構成されるため、Shor は適用できない。共通鍵には Grover アルゴリズムが影響するが 鍵長を倍にすれば防げる。だから「PQC が必要なのは公開鍵側だけ」「共通鍵は AES-256 で生き残る」というのが量子時代の戦略。
| 用語 | 1行説明 |
|---|---|
| 公開鍵暗号 / 非対称暗号 | 2 つの鍵を使う。事前共有なしで秘密通信が可能 |
| RSA | 1977 年。素因数分解の困難さに依拠 |
| Diffie-Hellman 鍵交換 | 1976 年。離散対数問題に依拠 |
| ECDH / ECDHE | 楕円曲線版 DH。Ephemeral 化したもの |
| ECDSA / Ed25519 | 楕円曲線版の署名アルゴリズム |
| Curve25519 | djb 設計の楕円曲線。WireGuard・SSH・TLS で標準 |
| 離散対数問題 | g^a mod p から a を求める。古典では困難 |
| 素因数分解問題 | n=pq から p, q を求める。古典では困難 |
| OAEP パディング | RSA を安全に使うためのパディング(RFC 8017) |
| ハイブリッド暗号 | 公開鍵で鍵交換、共通鍵で本文の組み合わせ |
| Forward Secrecy(前方秘匿性) | セッション鍵を後から復元不可能にする性質 |
| Shor アルゴリズム | 量子計算機で素因数分解・離散対数を多項式時間で解く |
| PQC(耐量子暗号) | 量子計算機にも耐える新世代暗号(Kyber/Dilithium 等) |
| Kyber(ML-KEM) | NIST 標準化された格子暗号。鍵交換用 PQC |
| Dilithium(ML-DSA) | NIST 標準化された格子暗号。署名用 PQC |