RSA の数理（モジュラ冪乗・オイラー関数・CRT 高速化）

RSA は「冪乗して mod を取るだけ」

公開鍵暗号 の代表格である RSA は、突き詰めると 整数を整数乗して、ある数 n で割った余りを取る という一行の演算（モジュラ冪乗）でできています。暗号化も復号も署名も、すべて同じ形です。

暗号化:  c = m^e mod n     （公開鍵 (e, n) で）
復号:    m = c^d mod n     （秘密鍵 (d, n) で）

ここで n（法）と e（公開指数）は公開、d（秘密指数）だけが秘密です。c = m^e mod n から m を逆算するのが難しい一方、d を知る本人は c^d mod n で一発で戻せる。なぜ戻るのか、なぜ逆算が難しいのかを、ここから数論で詰めていきます。

鍵生成：n・e・d をどう決めるか

鍵生成は次の手順です。各ステップに理由があります。

1. 大きな素数 p, q を独立にランダム生成し、n = p * q を作る。
2. オイラー関数 φ(n) = (p-1)(q-1)、またはカーマイケル関数 λ(n) = lcm(p-1, q-1) を計算する。
3. gcd(e, λ(n)) = 1 となる公開指数 e を選ぶ（実務では e = 65537 固定が定番）。
4. e の逆元として、e * d ≡ 1 (mod λ(n)) を満たす秘密指数 d を拡張ユークリッド互除法で求める。
5. 公開鍵は (e, n)、秘密鍵は d（実装上は p, q も保持）。

φ(n) は「1 から n までで n と互いに素な整数の個数」です。n = pq では φ(n) = (p-1)(q-1) になります。d は e の mod λ(n) における逆数 にあたり、この e*d ≡ 1 という関係こそが復号成立の核心です。

なぜ復号で元に戻るのか：オイラーの定理から導出

RSA の正しさは、ただ一つの主張に集約されます。

任意の m（0 ≤ m < n）について  m^(e*d) ≡ m (mod n)

これが成り立てば、c^d = (m^e)^d = m^(ed) ≡ m となり、復号で平文が戻ります。導出の道具は オイラーの定理 です。

オイラーの定理:  gcd(a, n) = 1 ならば  a^φ(n) ≡ 1 (mod n)

鍵生成で e*d ≡ 1 (mod λ(n)) を課したので、ある整数 k を使って e*d = 1 + k*λ(n) と書けます。m と n が互いに素なら、カーマイケルの定理（m^λ(n) ≡ 1 (mod n)。mod p と mod q でそれぞれフェルマーの小定理を使い CRT で束ねると、λ(n) = lcm(p-1, q-1) を指数にした合同式が成立する）から、

m^(ed) = m^(1 + k·λ(n))
       = m · (m^λ(n))^k
       ≡ m · 1^k
       = m   (mod n)

となり、元に戻ります。問題は m が p または q の倍数で gcd(m,n) ≠ 1 の場合ですが、ここで n = pq の合成数構造が効きます。mod p と mod q のそれぞれで m^(ed) ≡ m が成り立つことを示し（一方が m ≡ 0 の自明ケースでも成立する）、中国剰余定理（CRT） で mod n に合成すれば、すべての m について成立が言えます。つまり RSA の正しさそのものが CRT に支えられています。

CRT による復号高速化

CRT は正しさの証明だけでなく、復号の高速化にも直接使えます。c^d mod n は d が n と同程度に巨大なため重い演算ですが、p と q を知る本人だけは、計算を mod p と mod q の二つに分割できます。

事前計算（秘密鍵に同梱）:
  dp = d mod (p-1)
  dq = d mod (q-1)
  qInv = q^(-1) mod p

復号（Garner のアルゴリズム）:
  m1 = c^dp mod p
  m2 = c^dq mod q
  h  = (qInv * (m1 - m2)) mod p
  m  = m2 + h * q

ポイントは二つあります。第一に、指数が d から dp, dq（それぞれ約半分のビット長）に縮む。第二に、法が n から p, q（約半分のビット長）に縮む。モジュラ冪乗の計算量はビット長の3乗に比例するため、半分のサイズの計算を2回行うほうが、フルサイズを1回行うより圧倒的に速く、理論上およそ4倍 の高速化になります。OpenSSL をはじめ実装はこの CRT 復号を標準採用しており、PKCS#1 の秘密鍵には dp, dq, qInv が最初から格納されています。

安全性の根拠：素因数分解の困難性

RSA の安全性は「n から d を求められないこと」に依存し、それは実質 n = pq の素因数分解が難しいこと に等しくなっています。p, q がわかれば λ(n) が計算でき、λ(n) がわかれば e の逆元として d が即座に求まるからです。逆に n を因数分解する効率的な古典アルゴリズムは知られていません（一般数体ふるい法でも準指数時間）。

注意すべきは、鍵長を倍にしても強度は倍にならない点です。同じ強度なら RSA は楕円曲線暗号（ECC）より鍵がはるかに長く（128ビット強度で RSA-3072 対 ECC-256）、これが新規システムで ECC が好まれる理由です。さらに将来的には、Shor のアルゴリズム を実装した大規模量子コンピュータが素因数分解を多項式時間で解くため、RSA は原理的に破られます。耐量子（PQC）への移行が議論されるのはこのためです。

教科書 RSA はなぜ危険か：パディングの必然性

ここまでの c = m^e mod n をそのまま使う「教科書 RSA」は、実は そのまま使うと危険 です。理由は決定性とべき乗の代数的性質にあります。

• 決定的である：同じ平文は必ず同じ暗号文になる。攻撃者は候補平文を片端から暗号化して照合でき、選択肢が少ない平文（Yes/No、暗証番号など）は即座に特定される。
• 低指数攻撃：e=3 で m が小さく m^3 < n だと、mod が効かず単なる立方根で平文が戻る。同じ平文を3人の異なる n に送ると、CRT（Håstad 攻撃）で復元される。
• 準同型性：(m1^e)(m2^e) ≡ (m1·m2)^e (mod n)。暗号文を掛け合わせると平文を掛けた暗号文が作れてしまい、選択暗号文攻撃や署名の偽造に悪用される。

これらを潰すのが パディング です。暗号化には OAEP（Optimal Asymmetric Encryption Padding）を使い、平文に乱数（シード）とハッシュを混ぜてから冪乗します。これにより同じ平文でも毎回異なる暗号文になり（確率的暗号化）、上記の構造的攻撃が成立しなくなります。署名には PSS（Probabilistic Signature Scheme）を使います。素のハッシュへの署名は準同型性で偽造の余地が残るため、乱数入りのエンコードで安全性を担保するわけです。

まとめ

RSA の正しさは m^(ed) ≡ m (mod n) の一点に集約され、これは鍵生成で ed ≡ 1 (mod λ(n)) を課し、オイラーの定理と CRT を使って導けます。復号は秘密指数 d が重いため、p, q を知る本人だけが CRT で mod p／mod q に分割して約4倍高速化します。安全性は素因数分解の困難性に依存し、安全な鍵長は現状 2048 ビット以上（長期は 3072 以上）が目安です。そして教科書 RSA は決定性・準同型性ゆえに危険で、暗号化は OAEP、署名は PSS のパディングが必須です。

土台となる公開鍵と署名の考え方は 暗号の基礎、鍵と持ち主の結びつきを保証する仕組みは 公開鍵基盤（PKI）と証明書、一方向関数との対比は ハッシュ化と暗号化の違い と合わせて押さえると、RSA が実システムのどこに効いているかが見えてきます。