目次

暗号学入門 5. 公開鍵暗号編
公開鍵暗号の考え方
RSA
概要
鍵生成
暗号化・復号
RSA の安全性
素数の選び方が甘いと破れる
OAEP パディング
楕円曲線暗号 (ECC)
ECDSA (楕円曲線デジタル署名アルゴリズム)
EdDSA / Ed25519
デジタル署名
目的
一般的な署名の流れ
主な署名アルゴリズム
ハッシュ関数
暗号学的ハッシュ関数の性質
主なハッシュ関数
「破られている」とは？
証明書と PKI
問題: 公開鍵の信頼性
X.509 証明書
証明書チェーン
トラストストアはひとつではない
「OS に入れたのに繋がらない」
証明書の失効
参考文献
#crypto

暗号学入門 5. 公開鍵暗号編

前回では，共通鍵暗号でデータを暗号化する仕組みを解説しました．
本稿では，公開鍵暗号とデジタル署名を扱います．HTTPS の証明書検証や，ssh-keygen で作った鍵の署名検証も，ここで扱う内容に繋がります．

シリーズ目次
  1. 抽象代数学の基礎
  2. 楕円曲線
  3. DH 鍵共有，ECDH 鍵共有
  4. 共通鍵暗号 (AES など)
  5. 公開鍵暗号 (RSA, ECC など) (本稿)
  6. TLS
  7. (余談) SSH

公開鍵暗号の考え方

共通鍵暗号では，送信者と受信者が同じ鍵を共有する必要がありました．
公開鍵暗号では，各ユーザが鍵ペアを持ちます．

  • 公開鍵 (Public Key): 誰にでも公開してよい鍵
  • 秘密鍵 (Private Key): 所有者だけが保持する鍵

暗号化には受信者の公開鍵を使い，復号には受信者の秘密鍵を使います．
公開鍵から秘密鍵を求めることが計算困難であるため，公開鍵を公開しても安全です．

RSA

概要

RSA は，1977 年に Ron Rivest, Adi Shamir, Leonard Adleman が発表した公開鍵暗号の方式で，素因数分解の問題 の困難性に基づいています．
(Shamir 先生は暗号分野のいろんなとこで名前を見ます．)

鍵生成

  1. 大きな素数 p,qp, q をランダムに選ぶ (それぞれ 1024 ビット以上)
  2. n=p×qn = p \times q を計算 (RSA モジュロス)
  3. オイラーのトーシェント関数 φ(n)=(p−1)(q−1)\varphi(n) = (p-1)(q-1) を計算
  4. φ(n)\varphi(n) と互いに素な整数 ee を選ぶ (一般的に e=65537=216+1e = 65537 = 2^{16} + 1)
  5. e×d≡1(modφ(n))e \times d \equiv 1 \pmod{\varphi(n)} を満たす dd を計算（第1章の拡張ユークリッドの互除法）
  • 公開鍵: (n,e)(n, e)
  • 秘密鍵: (n,d)(n, d)

暗号化・復号

  • 暗号化: c=me mod nc = m^e \bmod n(mm: 平文，cc: 暗号文)
  • 復号: m=cd mod nm = c^d \bmod n

フェルマーの小定理 (より正確にはオイラーの定理) により，(me)d≡m(modn)(m^e)^d \equiv m \pmod{n} が成り立ちます．

RSA の暗号化と復号（公開鍵で暗号化・秘密鍵で復号）

具体例（小さな数で試す）
  • 素数 p=61, q=53p = 61,\ q = 53 → n=pq=3233n = pq = 3233，φ(n)=(p−1)(q−1)=3120\varphi(n) = (p-1)(q-1) = 3120
  • e=17e = 17（φ(n)\varphi(n) と互いに素）→ d=e−1 mod φ(n)=2753d = e^{-1} \bmod \varphi(n) = 2753
  • 平文 m=65m = 65 を暗号化: c=6517 mod 3233=2790c = 65^{17} \bmod 3233 = 2790
  • 復号: m=27902753 mod 3233=65m = 2790^{2753} \bmod 3233 = 65

17×2753=46801≡1(mod3120)17 \times 2753 = 46801 \equiv 1 \pmod{3120} なので，暗号化と復号がちょうど打ち消し合って元に戻ります．実際の RSA はこれを 2048 ビット以上の巨大な素数で行います．

RSA の安全性

RSA の安全性は，n=p×qn = p \times q の素因数分解が困難 であることに基づきます．

nn が与えられたとき pp と qq を求められれば，φ(n)\varphi(n) を計算でき，dd を算出できてしまいます．
しかし，nn が十分大きければ (2048 ビット以上)，現在の計算機では素因数分解は実行不可能です．

RSA 鍵長安全性レベル推奨状況
1024 ビット~80 ビット❌ 非推奨 (2010年以降)
2048 ビット~112 ビット✅ 最低限推奨
3072 ビット~128 ビット✅ 推奨

(参考: NIST SP 800-57)

素数の選び方が甘いと破れる

RSA は「nn を素因数分解できない」ことが前提ですが，素数 p,qp, q の選び方が悪いと分解できてしまいます．鍵長が足りていても脆弱になる，という点が重要です．

  • 乱数が弱い: 乱数生成器の質が低いと p,qp, q が予測可能になります．Debian OpenSSL の PRNG バグ (2008) では生成されうる鍵が極端に限られ，大量の脆弱な鍵が実際に出回りました．
  • 素数の使い回し: 別々の鍵がたまたま素数を共有すると，2 つの公開鍵から gcd⁡(n1,n2)\gcd(n_1, n_2) を計算するだけで共通の素数が求まり，両方の秘密鍵が割れます．2012 年の大規模調査 (“Ron was wrong, Whit is right”) では，公開されていた多数の RSA 鍵がこの方法で破られました．公開鍵を集めて GCD を取るだけでよく，攻撃コストが低いのが怖い点です．
  • pp と qq が近すぎる: 差が小さいと フェルマー法 で簡単に分解されます．Infineon 製チップの偏った素数生成 (ROCA, 2017) のように，生成方法に癖があると分解が現実的になります．

実務では，鍵は信頼できるライブラリ (OpenSSL, libsodium など) の安全な乱数で生成し，自前実装や弱い RNG，鍵の使い回しを避けます．脆弱性対応の観点では，「鍵長は足りているか」だけでなく「その鍵がどう生成されたか」まで見る必要がある，ということです．

OAEP パディング

素の RSA (教科書的 RSA) にはいくつかの脆弱性があります．たとえば，同じ平文を同じ公開鍵で暗号化すると同じ暗号文が得られるため，辞書攻撃が可能です．

RSA-OAEP (Optimal Asymmetric Encryption Padding, RFC 8017) は，ランダムなパディングを追加することでこの問題を解決します．

実用上，RSA を暗号化に使う場合は 必ず OAEP を使用 します．
なお，Web PKI や TLS 1.3 で RSA が登場する場面は，主に証明書や署名であり，RSA そのものでアプリケーションデータを暗号化するわけではありません．

楕円曲線暗号 (ECC)

第2章 で解説した楕円曲線を使った暗号方式群です．RSA と比較して短い鍵で同等の安全性を提供します．

ECDSA (楕円曲線デジタル署名アルゴリズム)

NIST FIPS 186-5 で標準化された署名アルゴリズムです．

鍵ペア:

  • 秘密鍵: 整数 dd (ランダムに選択)
  • 公開鍵: 点 Q=dGQ = dG（GG は 第2章 で扱った基点，dGdG はスカラー倍）

署名生成 (秘密鍵 dd でメッセージ mm に署名) の手順です．

  1. ランダムな整数 kk を選ぶ
  2. 点 (x1,y1)=kG(x_1, y_1) = kG を計算
  3. r=x1 mod nr = x_1 \bmod n を計算 (nn は GG の位数)
  4. s=k−1(H(m)+rd) mod ns = k^{-1}(H(m) + rd) \bmod n を計算 (HH はハッシュ関数)
  5. 署名は (r,s)(r, s)

この kk は毎回一意で秘密でなければならず，再利用や偏りは秘密鍵漏洩に直結します．
そのため実装では，RFC 6979 に従ってメッセージと秘密鍵から決定的に kk を生成することも多いです．

署名検証 (公開鍵 QQ で署名 (r,s)(r, s) を検証) の手順です．

  1. u1=H(m)×s−1 mod nu_1 = H(m) \times s^{-1} \bmod n，u2=r×s−1 mod nu_2 = r \times s^{-1} \bmod n を計算
  2. 点 (x1,y1)=u1G+u2Q(x_1, y_1) = u_1 G + u_2 Q を計算
  3. x1 mod n=rx_1 \bmod n = r なら署名は有効

EdDSA / Ed25519

RFC 8032 で標準化されたデジタル署名アルゴリズムです．

Curve25519 と同じ体上のツイスト・エドワーズ曲線 Edwards25519 を使用します．

ECDSA との主な違いは次の通りです．

  • 決定的: 署名時にランダム値を使わない (ランダム値の生成ミスによる秘密鍵漏洩を防ぐ)
  • 高速: 定数時間実装が容易
  • シンプル: 実装ミスが起きにくい設計

SSH では ssh-ed25519 として広く使われており，新規の鍵生成には Ed25519 が推奨 されています．

デジタル署名

目的

デジタル署名は，以下の 3 つの性質を提供します．

  1. 認証 (Authentication): 署名者の身元を確認
  2. 完全性 (Integrity): データが改ざんされていないことを確認
  3. 非否認性 (運用込み): 適切な本人確認と鍵管理が前提なら，後から「署名していない」と言い逃れしにくくする

一般的な署名の流れ

  1. 署名者: メッセージのハッシュを計算し，秘密鍵で署名
  2. 検証者: メッセージのハッシュを計算し，署名者の公開鍵で署名を検証

署名: Sign(秘密鍵, Hash(メッセージ)) → 署名値
検証: Verify(公開鍵, Hash(メッセージ), 署名値) → 有効/無効

図にすると，次のような流れです．

flowchart LR
  M["メッセージ"] --> H1["Hash"]
  H1 --> S["秘密鍵で署名"]
  S --> SIG["署名値"]
  M --> H2["Hash"]
  H2 --> V["公開鍵で検証"]
  SIG --> V
  V --> R["有効 / 無効"]

主な署名アルゴリズム

アルゴリズム基盤鍵長推奨状況
RSA-PSS素因数分解2048+ bit✅ 推奨
ECDSA (P-256)ECDLP256 bit✅ 推奨
Ed25519ECDLP256 bit✅ 推奨

ハッシュ関数

デジタル署名にはハッシュ関数が不可欠です．

暗号学的ハッシュ関数の性質

任意長の入力から固定長の出力 (ハッシュ値 / ダイジェスト) を生成する関数で，以下の性質を満たす必要があります．

  1. 原像耐性: ハッシュ値 hh から，H(m)=hH(m) = h となる mm を求めることが困難
  2. 第二原像耐性: m1m_1 が与えられたとき，H(m1)=H(m2)H(m_1) = H(m_2) となる m2m_2 を求めることが困難
  3. 衝突耐性: H(m1)=H(m2)H(m_1) = H(m_2) となる異なる m1,m2m_1, m_2 の組を見つけることが困難

主なハッシュ関数

アルゴリズム出力長推奨状況
MD5128 bit❌ 破られている
SHA-1160 bit❌ 衝突が発見されている (2017年，Google)
SHA-256 (SHA-2)256 bit✅ 推奨
SHA-384 (SHA-2)384 bit✅ 推奨
SHA3-256 / 384 / 512256 / 384 / 512 bit✅ 推奨

TLS 1.3 では SHA-256 以上のハッシュ関数が使用されます．

「破られている」とは？

表の「破られている」は，多くの場合 衝突耐性が破られた ことを指します．上の 3 つの性質のどれが破れたかで，意味も実害も変わります．

  • MD5: 衝突を現実的な計算で作れます．実害の例として，マルウェア Flame (2012) が MD5 衝突を悪用して Microsoft のコード署名証明書を偽造し，正規の Windows Update になりすまして感染を広げました．
  • SHA-1: 2017 年の SHAttered で衝突が実証され，2020 年の “SHA-1 is a Shambles” では任意の接頭辞を選べる衝突 (chosen-prefix collision) まで現実的なコストになりました．証明書や Git のように「ハッシュが同じなら同じもの」とみなす用途で危険です．

注意したいのは，「破られている＝ハッシュから元の入力を逆算できる」ではないことです．原像耐性 (ハッシュ値から入力を求める) は MD5 や SHA-1 でも簡単には破れていません．破られているのは主に「同じハッシュ値を持つ別のデータを作れる」という衝突耐性で，署名・証明書のように「正しいものと偽物を取り違えさせたい」攻撃で致命的になります．

ハッシュの衝突とは（異なる入力が同じダイジェストになる）

逆に言えば，パスワードの保存のように原像耐性が要る用途と，署名のように衝突耐性が要る用途では，「破られた」の重みが違います．脆弱性対応では，そのハッシュが 何のために使われているか まで見て判断する必要があります．

☕ コラム: SHA-1 の衝突 — SHAttered

2017 年，Google と CWI Amsterdam のチームが SHA-1 の衝突を実際に生成することに成功しました (SHAttered，Google の発表)．

異なる内容の 2 つの PDF ファイルが同じ SHA-1 ハッシュ値を持つことを実証し，SHA-1 の安全性が実用上も損なわれていることを示しました．

この成果には約 6,500 年分の CPU 計算と約 110 年分の GPU 計算が必要でしたが，クラウドコンピューティングの時代には決して非現実的なコストではありません．

これをきっかけに，Git のハッシュアルゴリズムも SHA-1 から SHA-256 への移行が進められています．

証明書と PKI

問題: 公開鍵の信頼性

公開鍵暗号やデジタル署名で残る問題は，「この公開鍵が本当にその人のものか」をどう確認するかです．

第3章で触れた中間者攻撃と同じ問題です．攻撃者が偽の公開鍵を配布すれば，暗号通信を傍受できます．

X.509 証明書

この問題を解決するのが X.509 証明書 (RFC 5280) です．

証明書は，信頼された 認証局 (CA: Certificate Authority) が「この公開鍵はこのエンティティのものである」とデジタル署名で保証するものです．

証明書に含まれる主な情報は次の通りです．

  • Subject: 証明書の所有者 (ドメイン名，組織名など)
  • 公開鍵: Subject の公開鍵
  • Issuer: 証明書を発行した CA
  • 有効期間: 開始日と終了日
  • CA のデジタル署名: 上記情報に対する CA の署名
  • シリアル番号: 証明書の一意な識別子

証明書チェーン

CA の証明書自体も，別の CA (上位 CA) が署名しています．これが連鎖し，最上位の ルート CA に至ります．

graph TD
  Store["OS / ブラウザのトラストストア"] --> Root["ルート CA 証明書<br/>自己署名"]
  Root --> Inter["中間 CA 証明書"]
  Inter --> Server["サーバ証明書"]

ブラウザや OS は，信頼するルート CA の証明書を トラストストア として保持しています．
サーバ証明書の検証は，このチェーンを辿ってルート CA に到達できるかを確認します．

トラストストアはひとつではない

ここまで「OS やブラウザがルート CA を持っている」と書きましたが，実際にどのトラストストアを見るかは言語・ランタイムごとに違います．

大きく 3 通りに分かれます．

参照先例
OS のストアGo, .NET, OpenSSL を使うもの (curl など)
ランタイム同梱Java (cacerts), Node.js (Mozilla CA のスナップショットを同梱)
ライブラリ同梱Python の requests (certifi パッケージ)

Node.js はリリース時点の Mozilla CA ストアのスナップショットを同梱しており，既定では OS のストアを見ません (Node.js ドキュメント)．
requests は「certifi パッケージの証明書を使う」と明記されています (requests ドキュメント)．
一方 Go は OS のストアを読み，SSL_CERT_FILE / SSL_CERT_DIR で上書きできます (crypto/x509)．

ブラウザも一枚岩ではありません．Firefox は OS ではなく独自の NSS ストアを見ますし，Chrome も Chrome Root Store という独自ストアへ移行しています．

「OS に入れたのに繋がらない」

典型的なハマり方が，企業プロキシによる SSL インスペクションです．プロキシのルート CA を OS のストアに入れた のに，こうなります．

  • curl は通る (OS を見ている)
  • Go のアプリも通る (OS を見ている)
  • node は通らない (同梱の CA しか見ていない)
  • requests を使う Python も通らない (certifi を見ている)
  • Java も通らない (cacerts を見ている)

同じ Python でも，標準ライブラリの ssl は OpenSSL の既定パス (つまり OS) を見るため，urllib は通るのに requests だけ落ちる，ということも起こります．「ブラウザでは開けるのにアプリからは繋がらない」も同じ構図です．

対処は，そのランタイムが見ているストアに入れる ことです．

対象追加・切り替えの方法
OS (Debian / Ubuntu)/usr/local/share/ca-certificates/ に置いて update-ca-certificates
OpenSSL / GoSSL_CERT_FILE, SSL_CERT_DIR
Node.jsNODE_EXTRA_CA_CERTS=/path/ca.pem．--use-openssl-ca / --use-system-ca でも可
Python (requests)REQUESTS_CA_BUNDLE (なければ CURL_CA_BUNDLE)
Javakeytool で cacerts に import

コンテナでよく見る x509: certificate signed by unknown authority も，多くは ca-certificates パッケージが入っていない だけです (scratch や最小イメージ)．

証明書エラーを見たら，まず「このプロセスは誰を信頼していて，その信頼はどこに書かれているのか」を特定します．それだけで切り分けの大半は済みます．

証明書の失効

証明書が危殆化 (秘密鍵の漏洩など) した場合に備えて，失効の仕組みがあります．

  • CRL (Certificate Revocation List): CA が失効した証明書のリストを公開
  • OCSP (Online Certificate Status Protocol): リアルタイムに証明書の有効性を問い合わせ

TLS では，OCSP Stapling (サーバが OCSP レスポンスを TLS ハンドシェイクに含める方式) が広く使われます．

認証情報を発行するときには，PKI に限らず，Revoke 可能であることが非常に大切です．

参考文献