では、実務上のRSA暗号について。— OAEPパディングからTLS 1.3まで

何故暗号化しなければならないのか、という話を先にしておきましょう。
BelleがAliceに手紙を送るとして、その配達員Clemくんが「善良」である確証は一切ありません。
＝送信元Belleから受信先Aliceにメッセージを送るとして、それに使用する通信経路や中継サーバーに潜む「Clem」は信用できるのか（このClemくんは Man In The Middle = MITM とか言ったりします）。

Belleが「これは文字数を数値にしたあと、ある特定の数値を加算してそのまま文字列に変換する暗号で、+3するよ」と解読法を添付した場合、Aliceは解読できます。ですが、Clemくんも解読できてしまいます。当然、添付されたメッセージは本メッセージごとClemが輸送するのですから。
＝ですから、Clemが分からない方法で、BelleとAliceだけが解読できる暗号が必要なのです。

「鍵を安全に届けるために暗号化したいのに、その暗号を解くための鍵を送る手段がない」という矛盾、これを鍵配送問題と言います。

Aliceだけが保持する「秘密鍵」と、BelleとClem（それに世界中の人々！）が見ることのできる「公開鍵」の話をしましょう。
この場合、公開鍵とは「南京錠」のイメージをした方が直感的かもしれません。

Aliceは、この公開鍵（「誰でも自由にロックしていい、まだ開いている錠」）を世界中にばらまきます。Clem、そしてもちろんBelleはこの公開鍵を手に入れることができますし、自由に閉めることができます。
BelleはAliceに秘密の手紙を送りたいとき、手紙を箱に入れ、Aliceの南京錠を「パチン」とロックして発送します。この瞬間、手紙はBelle本人にすら開けられなくなります。

途中で配達員のClemくんが箱を盗み見ようとしても、かかっているのは南京錠です。Clemくんも公開鍵（開いた南京錠）は持っていますが、鍵を開けるための「鍵」を持っていないため、箱を壊さない限り中身を読むことはできません。
無事に箱を受け取ったAliceは、自分のポケットから秘密鍵を取り出して南京錠を開け、中の手紙を読むことができます。公開鍵は、秘密鍵でのみ開けることが可能です。

先ほどまでの文章はあまりに簡略で、これだけで満足する人はおおよそいないと思いますし、巨大な素数同士の積の素因数分解が極端なまでに難しいことは基本的に知っていると思います。そういった初歩的な話は全て飛ばしましょう。

RSA暗号の安全性は、以下の2つの数学的基礎に基づいて保障されています。

1. 素因数分解問題の困難性
   2つの巨大な素数 $p, q$ （ただし $p \neq q$）の積 $n = pq$ を計算することは容易（人力であっても！）ですが、$n$ から素因数 $p, q$ を復元することは困難です。現代の計算機スペックであっても、$p, q$ 単体のビット長が512bit（$n$ が1024bit）を超えてくると、現実的な時間内での素因数分解は実質的に不可能です（もし何らかの要因でどっかの国がアメリカ国防総省をブチギレさせてその国が1024bitのnしか使ってない国だったらそのうち突破されるかもしれませんが！）。
   
2. オイラーの $\varphi$ 関数
   正の整数 $n$ に対して、$n$ 以下で $n$ と互いに素な正の整数の個数を表す関数を $\varphi(n)$ と定義します。$n = pq$ （$p, q$ は相異なる素数）であるとき、オイラー関数の乗法性より以下が成立します。 $$\varphi(n) = (p-1)(q-1)$$

巨大素数 $p, q$ が実際に用意できたと仮定し、鍵生成アルゴリズムをなぞってみましょう。

1. $1 < e < \varphi(n)$ かつ $\gcd(e, \varphi(n)) = 1$ の条件を満たす整数 $e$ を選定します。一般的には、計算効率化のために $e = 65537 = 2^{16} + 1$ （フェルマー素数 $F_4$）が使用されます。
2. 秘密鍵 $d$ の算出
   $e \cdot d \equiv 1 \pmod{{\varphi(n)}}$、即ちある整数 $k \in \mathbb{{Z}}$ が存在して、以下の線形ディオファントス方程式を満たす $d$ を求めます。 $$e \cdot d = k \cdot \varphi(n) + 1$$

今この場には、2つの鍵、 公開鍵 $(e, n)$ と 秘密鍵 $(d, n)$ 存在しています。
公開鍵はインターネット上で誰でも受け取れる形で配信されています。一方、秘密鍵はクライアントのみが保持し、絶対に誰も知ることができません。

メッセージ空間を有限環 $\mathbb{{Z}}_n = \{ 0, 1, 2, \dots, n-1 \}$ 内の要素（数）として表現します。

• 暗号化写像 $E$
  平文 $m \in \mathbb{{Z}}_n$ に対し、公開鍵 $(e, n)$ を用いた暗号化関数 $E: \mathbb{{Z}}_n \to \mathbb{{Z}}_n$ は以下の冪乗剰余演算として定義されます。 $$c = E(m) \equiv m^e \pmod n$$
• 復号写像 $D$
  暗号文 $c \in \mathbb{{Z}}_n$ に対し、秘密鍵 $(d, n)$ を用いた復号関数 $D: \mathbb{{Z}}_n \to \mathbb{{Z}}_n$ は以下の通りです。 $$m' = D(c) \equiv c^d \pmod n$$

何故、公開鍵による暗号化は秘密鍵を用いた復号でのみ解除できるのでしょうか？
復号処理によって元の平文が厳密に復元されること、すなわち $D(E(m)) \equiv m \pmod n$ となることを証明します。

基本的に、ネットで見かけるRSA暗号の解説はここまで（ええと、本当にこれ以降について書いてある記事ってあるのでしょうか...?）です。ですが、ここはあくまでも「記事」ではなく「Docs」。今まで話した内容をそのまま実装するのは暗号システムとしては完全な落第点です。決定性暗号である教科書的RSAには、数多くの攻撃手段が存在する為です。

同一の平文$m$に対する暗号文$c$は常に一定です。攻撃者が平文の候補（たとえば、Yes/Noの二パターン）を予め知っている場合、公開鍵(e,n)を用いてE("Yes")とE("No")を事前に計算し、傍受した暗号文$c$と照合するだけで、平文を完全に特定できます。

RSAの冪乗剰余演算は乗法準同型性を持ちます。2つの暗号文 $c_1 \equiv m_1^e \pmod n$ と $c_2 \equiv m_2^e \pmod n$ に対し、以下が成立します。

攻撃者は平文を知らなくても、暗号文 $c$ に任意の数 $r^e \bmod n$ を掛け合わせることで、復号後の平文を $m \cdot r \bmod n$ に変造できてしまいます。

Coppersmithの攻撃: 公開指数 $e$ が小さい値（例えば3）であり、かつ平文 $m$ の一部が判明している場合、格子基底縮小アルゴリズム（LLL）を用いて多項式の小根を計算し、平文の未知部分を多項式時間で特定できます。

Bleichenbacher攻撃（Million Message Attack）: PKCS #1 v1.5 パディングを適用したRSAにおいて、サーバーが復号時のパディングエラーの有無を応答（オラクル）として返す場合、攻撃者は適応的選択暗号文攻撃（CCA）を行うことで、数百万回の試行で秘密鍵を使わずに暗号文を解読できます。

教科書的RSAの構造的欠陥を根本から解決するために考案されたのが、RSA-OAEPです。
平文を直接累乗するのではなく、ハッシュ関数に基づく 2ラウンドの Feistel 類似構造 を用いて乱数化および拡散を行います。
これにより、以下の3つの重要な性質が同時に達成されます。

• 確率的暗号化（Probabilistic Encryption）: 暗号化ごとにランダムなシードを組み込むため、同一の平文から常に異なる暗号文が生成される（CPA耐性の獲得）。
• 全位相同値性・ plaintext-awareness: 暗号文を任意に改変（乗法性の利用など）した場合、復号処理のパディング検証フェーズで高確率（ほぼ $1 - 2^{'{-|k_1|}}$）で検出・棄却される（CCA2耐性 / 非展延性の獲得）。
• 部分平文の漏洩防止: 平文の一部分だけが判明している場合でも、格子攻撃（Coppersmith等）による全解読を防止する。

実際の中身は以下の通りなのですが、極端なまでに専門性が高く、実質的な読める睡眠薬です。未説明用語は基本的に全て後で解説しているので、Ctrl+Fを駆使しながら是非..

RSAのモジュラス $n$ のビット長を $k$ バイトとします。

• パラメータ設定:
  • $k\_0$: セキュリティパラメータ（シード $r$ のバイト長。例: 32バイト / 256bit）
  • $k\_1$: パディング検証用ゼロパラメータ（バイト長。例: 32バイト）
  • $M$: 暗号化対象のメッセージ（バイト長 $mLen \le k - k\_0 - k\_1 - 2$）
  • $G, H$: 暗号学的ハッシュ関数に基づくマスク生成関数（MGF: Mask Generation Function）
    • $G: \{0,1\}^{k\_0} \to \{0,1\}^{k - k\_0}$
    • $H: \{0,1\}^{k - k\_0} \to \{0,1\}^{k\_0}$

平文 $M$ からフォーマット済みデータ $EM$（Encoded Message）を生成するアルゴリズムは以下の通りです。

1. パディング列の構築:
   メッセージ $M$ の直後に 0x01 バイトを連結し、全体構造長が $k - k\_0$ バイトになるよう 0x00 を付与します。 $$DB = \text{Hash}(L) \parallel \text{PS} \parallel \text{0x01} \parallel M$$※ここで $\text{Hash}(L)$ はオプションのラベルハッシュ、$\text{PS}$ は 0x00 のパディング列。
2. シードの生成:
   $k\_0$ バイトの真性乱数（または暗号論的擬似乱数） $r \leftarrow \{0,1\}^{k\_0}$ を生成。
3. 第1ラウンド（データブロックのマスク）:
   乱数 $r$ から MGF を用いてマスクキー $maskedDB$ を算出します。 $$dbMask = G(r)$$ $$maskedDB = DB \oplus dbMask$$
4. 第2ラウンド（シードのマスク）:
   $maskedDB$ から MGF を用いてシード $r$ 自体をマスクします。 $$seedMask = H(maskedDB)$$ $$maskedSeed = r \oplus seedMask$$
5. エンコードメッセージの完成:$$EM = \text{0x00} \parallel maskedSeed \parallel maskedDB$$ この $EM$（長さ $k$ バイト）を整数表現に変換したものを $\hat{m}$ とします。

• 暗号化:$$c \equiv (\hat{m})^e \pmod n$$
• 復号と OAEP デコード:
  1. 秘密鍵 $d$ を用いて $\hat{m}' \equiv c^d \pmod n$ を計算。
  2. $\hat{m}' $ を $k$ バイトのバイト列 $EM'$ に変換。先頭バイトが 0x00 でない場合は即座に復号エラー（棄却）。
  3. $EM'$ を分割: $\text{0x00} \parallel maskedSeed \parallel maskedDB$
  4. 逆Feistel構造により復元: $$r = maskedSeed \oplus H(maskedDB)$$ $$DB = maskedDB \oplus G(r)$$
  5. $DB$ 内の構造検証:
     先頭の $\text{Hash}(L)$ が一致し、パディング内の 0x01 の位置が正しいかを検証。不整合がある場合は棄却。
  6. 0x01 以降のバイト列を真のメッセージ $M$ として抽出。

Bleichenbacher 攻撃（PKCS #1 v1.5 に対する攻撃）は、サーバーが「パディングフォーマットエラー」と「その他のエラー」で異なる応答時間やエラーコードを返す（エラーオラクル）ことを利用し、数百万回の選択暗号文を送信して秘密鍵を使わずに $m$ を段階的に絞り込む攻撃でした。

OAEP では以下の2重の対策によりこれを遮断します。

1. 定数時間処理:
   復号アルゴリズムにおいて、$EM'$ のフォーマットエラー、$\text{Hash}(L)$ の不一致、0x01 の欠損など、どの段階でエラーが発生した場合でも、処理時間や返却するエラーレスポンスを厳密に同一に保ちます。
2. 証明可能安全:
   ランダムオラクルモデルにおいて、有効な $c$ を生成するためには、攻撃者はハッシュ関数 $G$ と $H$ への問い合わせを通じて正しい $r$ と $M$ の関係を知っていなければなりません。ランダムに改変された $c'$ を復号しても、確率 $1 - 2^{'{-k\_1}}$ で $DB$ 内の検証条件（0x01 や固定ゼロの存在）を確定的に外すため、オラクルとして有益な情報を漏洩させません。

実運用環境における RSA の計算コスト $O((\log n)^3)$ を回避し、データ通信を $O(N)$ の共通鍵暗号へ委任するハイブリッド暗号において、旧来の RSA 鍵配送（TLS 1.2 RSA Key Exchange）と現代の Diffie-Hellman 鍵共有（TLS 1.3 ECDHE）には、数学的・安全性において根本的な構造差異が存在します。

TLS 1.2 までの RSA 鍵共有方式では、クライアントが生成した 48バイトの Premaster Secret ($PMS$) を RSA-PKCS#1 v1.5（または RSA-OAEP）で暗号化し、サーバーへ送信していました。

• 鍵導出:
  両者は $PMS$ と双方の Client/Server Random から擬似乱数関数（PRF）を用いてマスターシード $MS$ を導出し、対称鍵（AES-GCM 鍵および IV）を生成します。 $$MS = \text{PRF}(PMS, \text{"master secret"}, R_{\text{client}} \parallel R_{\text{server}} )$$
• 破綻理由（PFSの欠如と受動的盗聴）:
  攻撃者 Clem が通話データをすべて記録していた場合、将来的にサーバーの長期秘密鍵 $d$ が漏洩（破棄ハードディスクの回収、裁判所の差押、ハートブリード等の脆弱性）した時点で、記録された暗号文 $c$ から一括して $PMS$ が復号可能となります。 $$PMS = D_{\text{RSA-Priv}} (c)$$ これにより、過去数年分の全通信トラフィックの対称鍵 $MS$ が即座に計算され、すべて解読されます。

TLS 1.3 では、鍵暗号化機能としての RSA を完全に削除し、一時鍵対（Ephemeral Keypair）による ECDHE 鍵共有へ一本化されました。ここでの RSA は、認証（Authentication）のためのデジタル署名生成アルゴリズムとしてのみ利用されます。

1. クライアントとサーバーは、通信ごとに使い捨ての楕円曲線秘密鍵 $x, y \in \mathbb{{Z}}_q$ と公開鍵 $X = x \cdot G, Y = y \cdot G$ を生成（$G$ は基点）。
2. 平文で公開鍵 $X, Y$ を交換し、双方で共有パラメータ $S$ を計算。 $$S = x \cdot Y = x(y \cdot G) = y(x \cdot G) = y \cdot X$$
3. $S$ の $x$ 座標等から HKDF（HMACベース鍵導出関数）を用いてハンドシェイク用・アプリケーション用のセッション鍵を導出。

攻撃者 Clem による Man-In-The-Middle（MITM）攻撃（自身の ECDHE 公開鍵を送信して中間者攻撃を行う手法）を防ぐため、サーバーは自身の長期 RSA 秘密鍵 $d_{\text{RSA}} $ を用いてハンドシェイク全体のハッシュに対して署名を付与します。

1. サーバーはここまでのハンドシェイクログのハッシュ値 $H(\text{Handshake\_Messages})$ を計算。
2. 確率的署名方式 RSA-PSS（Probabilistic Signature Scheme: OAEP と同様にハッシュと塩を用いた安全性証明つきパディング）を用いて署名 $\sigma$ を生成。 $$\sigma = \text{Sign}_{d_{\text{RSA}}}(\text{RSA-PSS-Encode}(H(\text{Handshake\_Messages})))$$
3. クライアントは、認証局によって検証されたサーバーの RSA 公開鍵 $e_{\text{RSA}} $ を用い、署名 $\sigma$ を検証。 $$\sigma^e \equiv \text{EncodedHash} \pmod n$$

これにより、通信データの秘匿化・鍵共有（ECDHE） と 通信相手の身元証明（RSA署名） が完全に分離され、仮に長期 RSA 秘密鍵 $d_{\text{RSA}} $ が後に漏洩したとしても、ECDHE 側の使い捨て秘密鍵 $x, y$ はメモリ上から破棄されているため、過去の通信データを解読する術は数学的に存在しません。

まあ　私は数年前まで技術ドキュメントが一切読めなかったので、何故あなたが理解できていないのかおおよそ理解しているつもりです。