RSAは1977年、MITのRon Rivest、Adi Shamir、Leonard Adlemanの3人によって考案された公開鍵暗号方式です。頭文字を並べた命名が示すとおり、整数論の素因数分解問題の困難性を安全性の根拠としています。発表当時、対称鍵しか存在しなかった暗号の世界に「鍵を公開しても安全」という発想を持ち込み、後のSSL/TLS、PGP、電子署名、SSHなど現代の鍵交換と認証の枠組みすべての原型となりました。本記事ではRSAの仕組み、誕生の経緯、現在の立ち位置を解説します。
この記事の目次
- 素因数分解の困難性に依拠する仕組み
- MITの3人と公開鍵暗号の誕生
- TLSハンドシェイクと電子署名
- 楕円曲線暗号（ECC）への置き換え
- まとめ
素因数分解の困難性に依拠する仕組み
RSAの鍵生成では、まず大きな素数pとqを2つ選び、その積n=pqを計算します。オイラーのトーシェント関数φ(n)=(p-1)(q-1)を求め、φ(n)と互いに素な公開指数eを選択し、e×d ≡ 1 (mod φ(n)) を満たす秘密指数dを拡張ユークリッド互除法で算出します。公開鍵は(n, e)、秘密鍵は(n, d)で、暗号化はc = m^e mod n、復号はm = c^d mod nというべき乗剰余演算で行います。eには16進数で0x10001=65537がよく使われます。
安全性の根拠は、nを与えられても元の素数pとqを復元するのが計算量的に困難であるという素因数分解問題です。n=pqが分かってもφ(n)を求められず、dを逆算できないため、秘密鍵を持つ人だけが復号できます。現在は鍵長2048ビット以上が推奨され、政府機関や長期保管用途では3072〜4096ビットも使われます。なお、署名生成ではメッセージのハッシュ値をdでべき乗してsを得て、検証側はeでべき乗してハッシュと比較する形になります。
MITの3人と公開鍵暗号の誕生
公開鍵暗号という発想自体は、1976年にWhitfield DiffieとMartin HellmanがNew Directions in Cryptographyで提案したのが嚆矢でした。ただし両者の論文は鍵交換の枠組みを示しただけで、実用的な暗号化手法は与えていません。MITの若手研究者だったRivest、Shamir、Adlemanはこの論文に刺激を受け、1976年末から春にかけて議論を重ね、1977年4月にRSA方式を発見しました。Rivestは過越祭の夜に酒を飲みながら横になり、頭の中でアイデアを練ったという逸話が残っています。
論文は1978年2月にCommunications of the ACMで公表され、Martin Gardnerが同年8月号のScientific Americanのコラム「Mathematical Games」で紹介したことで一躍有名になりました。1983年にMITが米国特許4,405,829を取得し、1996年にはRSA Data Security社（後のRSA Security）として商業展開。2000年9月20日に特許が満了し、それ以降は誰でも自由に実装できるようになりました。3人は2002年にチューリング賞を受賞しています。
TLSハンドシェイクと電子署名
RSAの最大の活躍場面はTLSのハンドシェイクでした。TLS 1.2まではクライアントがプレマスターシークレットをサーバーの公開鍵で暗号化して送信し、それを共通鍵暗号の種に使う方式が広く使われていました。電子証明書の世界でも、X.509証明書の署名アルゴリズムとしてsha256WithRSAEncryptionが長らく標準で、ブラウザにプリインストールされたルートCA証明書の多くもRSA鍵で発行されています。
SSH接続のキーペア認証、GnuPGによるメール署名・暗号化、Windowsの実行ファイルへのAuthenticodeコード署名など、「公開鍵で本人性を保証する」あらゆる場面でRSAが使われてきました。TLS 1.3では前方秘匿性の観点から鍵交換は楕円曲線Diffie-Hellman（ECDHE）に置き換わりましたが、サーバー証明書の署名検証は今もRSAが多数派です。つまり鍵交換からは後退しても、認証の柱としては依然として現役なのです。
楕円曲線暗号（ECC）への置き換え
現代の暗号現場では、RSAは徐々に楕円曲線暗号（ECC）に置き換えられつつあります。ECCは楕円曲線上の離散対数問題を安全性の根拠とし、同等の安全強度をRSAの約1/10の鍵長で実現できます。256ビットの楕円曲線鍵はRSA 3072ビットに匹敵する強度を持ち、計算量・帯域・電力すべての面でRSAより軽量です。iOS、Android、Let's EncryptのECDSA証明書、SSHのed25519鍵など、新規導入はECC優位の流れが続いています。
それでもRSAが完全に消えない理由は、互換性と実装の枯れ具合にあります。古いブラウザや古いSSHクライアント、組織内のCAインフラ、レガシーシステムとの相互運用ではRSAが必須の場面が依然として多く、FIPS 140認定済みハードウェアの多くもRSAをサポートしています。一方、Shorのアルゴリズムを実装した量子計算機が実用化されれば、RSAもECCも破られるため、NISTは2024年にCRYSTALS-Kyberなどの耐量子計算機暗号を標準化しました。RSAの50年近い覇権は、最後の局面に差し掛かっています。
まとめ
RSAは公開鍵暗号という概念を実用的なアルゴリズムへ落とし込んだ最初の方式であり、現代のインターネットの認証基盤を半世紀近く支えてきました。楕円曲線暗号や耐量子計算機暗号への移行が進む今も、TLS証明書の署名検証など要所で現役を続けています。
※本記事はIT用語辞典の手書きドラフトです。公開前に最新情報・出典を確認のうえ加筆修正してください。
コメント