RSA暗号｜公開鍵暗号と電子署名を支える

2025.10.04

RSA暗号

RSA暗号は、巨大な合成数の素因数分解が計算量的に困難であるという前提に依拠する代表的な公開鍵暗号である。鍵生成で素数

と

qを選び、積n＝pqとオイラー関数φ(n)＝(p−1)(q−1)から公開鍵と秘密鍵を構成する。暗号化・復号はモジュラ累乗により実行され、電子署名と鍵交換の両方に用いられる。実装ではパディング（OAEP）や定数時間化、乱数品質、サイドチャネル対策が安全性を左右する。現在も広く使われるが、適切な鍵長と最新のプロトコル運用が前提である。

Table Of Contents

数学的基盤と成立要件

RSAの核心はモジュラ算術とオイラーの定理である。p,qを互いに独立な大きな素数とし、n＝pq、φ(n)＝(p−1)(q−1)と定義する。公開鍵指数eと秘密鍵指数dはed≡1 (mod φ(n))を満たすように選ぶ。任意のメッセージM（0≤M＜n）に対し、C≡M^e mod nで暗号化し、M≡C^d mod nで復号できるのは、M^{ed}≡M (mod n)が成り立つからである。これはMがp,qのいずれにも割り切れないときフェルマーの小定理を介して示され、一般の場合も中国剰余定理で整合が取れる。dの導出には拡張ユークリッド互除法でeのφ(n)に関する逆元を求める。

鍵生成手順

  1. 十分離れたビット長の大きなランダム素数p,qを安全な乱数から生成する（素性検査はミラー–ラビンなどの確率的テストを多段で用いる）。
  2. n＝pq、φ(n)＝(p−1)(q−1)を計算する。
  3. eは一般に小さな奇数（例：65537）を選ぶが、既存鍵との相互運用や署名検証の速度も考慮する。
  4. 拡張ユークリッド互除法によりd≡e^{-1} (mod φ(n))を求める。dは秘匿する。
  5. 公開鍵：(n,e)、秘密鍵：(n,d)に加えてCRT用パラメータ（d_p,d_q,q^{-1} mod p）を保持すると高速化できる。

暗号化・復号と電子署名

暗号化はC≡M^e mod n、復号はM≡C^d mod nである。電子署名ではハッシュ値H(m)をパディング後にS≡H(m)^d mod nとして生成し、検証側はS^e mod nがパディング規格に適合しハッシュが一致するか確認する。生のメッセージやハッシュに直接べき乗するのは危険であり、暗号化にはOAEP、署名にはPSSといった耐選択暗号文攻撃（IND-CCA）・強健性を意識したパディングを必須とする。

パディングと規格（PKCS#1）

PKCS#1はRSAの実装規格であり、暗号化にはRSAES-OAEP、署名にはRSASSA-PSSを推奨する。従来のPKCS#1 v1.5パディングは運用次第でオラクル攻撃（Bleichenbacher攻撃）を受けるため、最新運用ではエラーのふるまい統一、定数時間化、サイドチャネル抑止を併用する。ASN.1/DERでハッシュ識別子を埋め込む署名形式の解釈も実装互換性上の要点である。

安全性評価と代表的攻撃

  • 数論的攻撃：nの素因数分解（GNFS）が最も強力で、鍵長が短いと破られる。p,qが近い、バイアスのある乱数、平滑数構造なども脅威となる。
  • 指数関連攻撃：小さすぎるd（Wiener攻撃）や、eの選択とメッセージ構造の不備が弱点になる。
  • 実装攻撃：タイミング、電力解析、フォールト注入。対策としてブラインディング、定数時間べき乗、CRT利用時の整合検査（Shamir対策）を行う。
  • プロトコル攻撃：復号エラーを通じたオラクル化、ハンドシェイク上のダウングレード、鍵再利用の不備など。

鍵長と性能の目安

現在の一般的運用では2048ビットが最低ラインとされ、長期秘匿や高価値資産には3072ビット以上を選ぶ。鍵長を伸ばすと暗号化・復号・署名の計算時間が増すため、RSAを鍵カプセル化や署名に限定し、実データは高速な共通鍵暗号（例：AES）で処理するハイブリッド方式が常道である。モジュラ累乗はモンゴメリ乗算や平方繰返し法で最適化し、CRTで復号・署名を約4倍高速化する。

実装の要点（安全運用）

  1. 高品質CSPRNGでp,qを生成し、素数の偏り・再利用を避ける。
  2. OAEP/PSSの規格準拠、エラー均一化、タイミング漏えい抑止、サイドチャネル耐性を確保する。
  3. 秘密鍵の格納にはHSMやTPMの利用を検討し、鍵導出・バックアップ・廃棄手順を文書化する。
  4. TLS、S/MIME、OpenPGPなど上位プロトコルでの相互運用試験を行い、アルゴリズム識別子やハッシュの選択（例：SHA-256以上）を統一する。

代表的利用場面

TLSにおけるサーバ証明書の署名検証、ソフトウェア配布におけるコード署名、電子メールのS/MIME署名・鍵配布、パッケージ管理系の署名検証、VPN・ゼロトラスト環境での装置認証などで広く使われる。近年は鍵交換自体は楕円曲線（ECDHE）に委ね、RSAは証明書署名と後方互換のために併用される構成が主流である。

量子計算との関係

大規模な量子計算機が実用化されればショアのアルゴリズムにより素因数分解が効率化し、RSAの前提が崩れる。現時点では耐量子暗号（格子ベース等）への移行計画と暗号アジリティ確保が望ましい。移行期には証明書・署名・鍵管理の棚卸しと、ハイブリッド化（古典＋耐量子）による段階的移行が現実的である。

数値例と運用指針

実務ではe＝65537の採用、PSS署名、OAEP暗号化、SHA-256以上のハッシュ、2048〜3072ビット鍵、定数時間実装、CRT復号＋結果再検証、鍵の定期ローテーションと失効管理、証明書失効情報（CRL/OCSP）の配信整備を最低限の標準とする。ログには鍵素材を決して残さず、署名結果のフォーマット検証を厳格に行うことで破壊的バグや攻撃連鎖を防ぐ。

コメント（β版）