RSA 暗号 (1977)（アールエスエー）
Ron Rivest / Adi Shamir / Leonard Adleman 1977年発明の公開鍵暗号。素因数分解問題に基づく非対称暗号、TLS / SSH / コード署名で広範採用・量子コンピュータ対策で後継PQC へ移行中。
概要
RSA はRon Rivest / Adi Shamir / Leonard Adleman (3人の頭文字R-S-A) がMIT で1977年に発明、1983年特許化・2000年特許失効した最初の本格的公開鍵暗号。素因数分解問題 (1024bit 以上の大整数N = p×q の因数分解困難性) に基づく非対称暗号、公開鍵 (n, e) で暗号化 / 検証 / 秘密鍵 (n, d) で復号 / 署名。1977年Communications of the ACM に Martin Gardner 連載で初公開、現代インターネットセキュリティの基盤。
RSA 主要マイルストーン
| 年月 | 出来事 |
|---|---|
| 1976 | Diffie-Hellman 公開鍵暗号構想 |
| 1977 | RSA 発明 (Rivest/Shamir/Adleman) |
| 1977-04 | Martin Gardner 連載「A new kind of cipher」(Scientific American) |
| 1978-02 | 論文「A Method for Obtaining Digital Signatures and Public-Key Cryptosystems」 |
| 1982 | RSA Data Security (Rivest 創業) |
| 1983 | 米国特許 4405829 |
| 2000-09 | 特許失効 (RSA Security Inc.) |
| 2001-11 | NIST AES 標準化 (DES 後継・対称暗号) |
| 2018-08 | TLS 1.3 (RFC 8446・RSA 鍵交換 廃止) |
RSA 鍵長と推奨
| 鍵長 | セキュリティ | 推奨 |
|---|---|---|
| 512bit | 破られ済 (1999) | 廃止 |
| 1024bit | 危険 (~2030年破られる予測) | 廃止 |
| 2048bit | 現在最低 | 移行中 |
| 3072bit | 推奨 | 標準 |
| 4096bit | 高セキュリティ | 推奨 |
| 8192bit | 超高セキュリティ | 機密用 |
| 15360bit | 量子耐性 (Shor 対応?) | 研究 |
NIST 推奨: 2024年現在 2048bit 移行・2030年以降3072bit 必須。
RSA の数学的基礎
-
鍵生成:
- 2つの大素数 p, q (1024+bit) 選択
- n = p × q (2048+bit)
- φ(n) = (p-1)(q-1) (Euler 関数)
- e (公開鍵指数・通常65537) 選択
- d ≡ e⁻¹ (mod φ(n)) (秘密鍵指数)
-
暗号化: 暗号文 = 平文^e mod n
-
復号: 平文 = 暗号文^d mod n
セキュリティは「n の素因数分解 (p, q 復元) が困難」に依存、最大の脅威は量子コンピュータShor アルゴリズム。
RSA の用途
| 用途 | 内容 |
|---|---|
| 鍵交換 | TLS 1.0-1.2 (廃止 in 1.3) |
| 電子署名 | 全コード署名 / 文書署名 |
| SSH | ~2025年標準・Ed25519 へ移行中 |
| GPG / PGP | メール暗号化・電子署名 |
| SSL/TLS 証明書 | Let's Encrypt 等 |
| 認証 | RSA SecurID (旧) |
| ID カード | マイナンバーカード / Smart Card |
量子コンピュータ脅威 (Shor アルゴリズム)
Peter Shor (MIT・1994年) が考案した量子コンピュータアルゴリズムでRSA n を多項式時間 (古典指数時間) で素因数分解可能:
- 4000 qubit + 安定動作で 2048bit RSA を数時間で破れる
- 現在Google Sycamore / IBM Eagle は数百qubit
- 2030-2040年に大規模量子コンピュータ実用化見込み
- NIST 2024年Post-Quantum Cryptography (PQC) 標準化 (ML-KEM / ML-DSA / SLH-DSA)
TLS 1.3 で RSA 鍵交換廃止
TLS 1.2 (2008-2018) はRSA Key Exchange が主流だったが、Forward Secrecy 不在 / 静的鍵 / Shor 脅威でTLS 1.3 (2018) では完全廃止:
- 鍵交換: ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) のみ
- 署名: RSA-PSS / Ed25519 / ECDSA (P-256/P-384)
- RSA は署名のみ継続
関連用語との違い
- vs AES: 公開鍵 / 対称
- vs ECC: RSA 古典 / ECC 楕円曲線 (短鍵 + 高速)
- vs PQC: 古典数学 / 量子耐性 (Lattice / Hash等)
FAQ
Q1: RSA 2048 はいつまで安全? A: NIST「2030年まで」とされるが、量子コンピュータ実用化次第。早ければ2035年・遅くても2050年代に破られる予測。
Q2: SSH で RSA 使うべき? A: 新規はEd25519 推奨・既存RSA は 4096bit + 定期回転。SSH 2.0以降ed25519 デフォルトで RSA は互換性のみ。
Q3: 特許失効? A: 2000年9月に米国特許失効・以後完全フリー。それ以前はRSA Data Security ライセンス必要 (PGP 初期で問題化)。