1. 鍵ペアの生成#
RSAでは、まず大きな素数pとqを選びます。
オイラーのトーシェント関数を計算します。
$$ \varphi(n) = (p-1)(q-1) $$次に、次の条件を満たす公開指数eを選びます。
秘密指数dは、eの法φ(n)における乗法逆元です。
鍵ペアは次のようになります。
公開鍵 : (e, n)
秘密鍵 : (d, n)2. 教科書的な暗号化と復号#
平文を整数M（0 ≤ M < n）とすると、公開鍵で暗号化します。
秘密鍵で復号します。
$$ M = C^d \bmod n $$ただし、この式をそのまま実装して文字列や大きなファイルを暗号化してはいけません。RSA-OAEPなどのパディングと、メッセージ長の制限を含む標準方式が必要です。
3. なぜ復号できるのか#
de ≡ 1 (mod φ(n))なので、ある整数kを使って次のように書けます。
互いに素なMについてオイラーの定理
を使うと、次が得られます。
$$ C^d = (M^e)^d = M^{ed} = M^{1+k\varphi(n)} \equiv M \pmod n $$実際のRSAの正確な証明では、Mがpやqと互いに素でない場合も含めて中国剰余定理を使って扱います。ここでは構造を理解するため、互いに素な場合の式に限定しています。
4. RSAの安全性の考え方#
RSAの安全性は、公開されているn = p × qから、元の素数pとqを求めることが難しいという仮定に関係します。十分に大きな鍵を使えば、素因数分解は計算上困難です。
ただし、鍵長だけで安全性が決まるわけではありません。乱数生成、パディング、秘密鍵の保護、実装のサイドチャネル、将来の量子計算への耐性なども重要です。
5. RSAとハッシュによるデジタル署名#
RSA署名では、メッセージ全体ではなくハッシュ値へ署名します。
- メッセージ
Mからハッシュ値H(M)を計算する。 - 送信者の秘密鍵で、署名パディングを含むハッシュ表現へ署名する。
- 受信者は送信者の公開鍵で署名を検証する。
- 受信したメッセージから再計算したハッシュ値と、署名から得られた値を比較する。
概念的には、次のように書けます。
$$ S = \operatorname{Sign}_{d}(H(M)) $$$$ \operatorname{Verify}_{e}(S, M) = \text{true} $$実用上は、単純なS = H(M)^d mod nではなく、RSA-PSSを使います。SHA-256やSHA-3などの安全なハッシュ関数は、改ざん検出と耐衝突性を提供しますが、ハッシュだけでは送信元を認証できません。秘密鍵による署名と公開鍵の真正性確認が必要です。
6. RSAが使われる場面#
- ハイブリッド暗号：RSA-OAEPで共通鍵を保護し、データ本体はAES-GCMなどで暗号化する。
- デジタル署名：RSA-PSSでメッセージやファイルの完全性と送信元を検証する。
- 証明書と認証：公開鍵証明書を使って、公開鍵と主体の対応を検証する。
大きなデータをRSAで直接暗号化するのは遅く、暗号文のサイズにも制限があります。そのため、公開鍵暗号は通常、短い鍵やハッシュ値の保護に使います。
まとめ#
- RSAは公開鍵
(e,n)と秘密鍵(d,n)を使う。 - 教科書的には
C = M^e mod n、M = C^d mod nである。 - 実際の暗号化ではRSA-OAEP、署名ではRSA-PSSを利用する。
- 大きなファイルは共通鍵暗号で処理し、RSAは共通鍵の保護に使う。
- ハッシュは完全性確認に役立つが、送信元の認証にはデジタル署名と公開鍵の信頼が必要である。