はじめに
RSA暗号の安全性の根拠として、「大きな数の素因数分解が難しいから」とよく言われます。今回は、「なぜそれで暗号化と復号が成り立つのか？」という数学的な仕組みを調べてみました。
この記事では、mod（剰余）の基本的な意味がわかる程度の前提知識で、RSA暗号の仕組みを順を追って説明します。
RSA暗号のざっくりしたイメージ
まず、細かい話の前にざっくりしたイメージを掴みましょう。
RSA暗号では、平文に公開鍵を使って計算すると暗号文になります。その暗号文に秘密鍵を使って計算すると、元の平文に戻ります。
暗号文 = 平文に公開鍵でゴニョゴニョ計算
平文 = 暗号文に秘密鍵でゴニョゴニョ計算
もう少し具体的にします。
平文を m（messageの略）とします。2つの素数 p, q を用意して、この2つに対して都合の良い e を選び、そこから d を計算で求めます。
公開鍵は「p × q の結果（これを n と呼ぶ）」と「e」のペアです。
暗号化は「m の e 乗を n で割った余り」です。この余りが暗号文 c（ciphertextの略）になります。
c = m^e mod n
復号は「c の d 乗を n で割った余り」です。すると元の平文 m が出てきます。
m = c^d mod n
なぜこれで元に戻るのか？ e と d はどうやって決めるのか？ これを理解するのがこの記事の目的です。
登場する値
RSA暗号で使う値を整理します。
| 記号 | 意味 | 公開/秘密 |
|---|---|---|
| p, q | 2つの素数 | 秘密 |
| n | p × q | 公開 |
| L | (p-1) × (q-1) | 秘密 |
| e | 公開指数（暗号化に使う） | 公開 |
| d | 秘密指数（復号に使う） | 秘密 |
| m | 平文（送りたいメッセージ） | - |
| c | 暗号文 | - |
暗号化と復号の計算
暗号化
平文 m を暗号文 c に変換します。
c = m^e mod n
つまり「m の e 乗を n で割った余り」が暗号文です。
復号
暗号文 c を平文 m に戻します。
m = c^d mod n
つまり「c の d 乗を n で割った余り」が元の平文です。
具体例
p = 3, q = 5, e = 3, d = 3 の場合
n = 3 × 5 = 15
【暗号化】
m = 2（平文）
c = 2^3 mod 15 = 8 mod 15 = 8
【復号】
c = 8（暗号文）
m = 8^3 mod 15 = 512 mod 15 = 2
元に戻った！
512 ÷ 15 = 34 余り 2 なので、確かに 512 mod 15 = 2 です。
なぜ元に戻るのか
ここからは「なぜ復号で元に戻るのか」を理解するために、必要な数学的概念を順番に説明します。
オイラーのトーシェント関数 φ(n)
オイラーのトーシェント関数 φ(n) は「1 から n までの整数のうち、n と互いに素なものの個数」を表します。
例えば n = 6 の場合：
1 → 6と互いに素 ○
2 → 6と公約数2を持つ ✗
3 → 6と公約数3を持つ ✗
4 → 6と公約数2を持つ ✗
5 → 6と互いに素 ○
6 → 6と公約数6を持つ ✗
φ(6) = 2（1と5の2個）
素数の場合
p が素数なら、1 から p-1 までの全ての数が p と互いに素です。
φ(p) = p - 1
例えば φ(7) = 6（1, 2, 3, 4, 5, 6 の6個）。
φ(n) の乗法性
オイラーのトーシェント関数には、次の性質があります。
a と b が互いに素なら、φ(a × b) = φ(a) × φ(b)
RSA では n = p × q で、p と q は異なる素数です。異なる素数は必ず互いに素なので：
φ(n) = φ(p × q) = φ(p) × φ(q) = (p - 1) × (q - 1)
この (p-1) × (q-1) を、本記事では L と呼びます。つまり L = φ(n) です。
オイラーの定理
オイラーの定理は次のように述べられます。
m と n が互いに素のとき、m の φ(n) 乗を n で割ると、余りは 1 になる
数式で書くと：
m^φ(n) ≡ 1 (mod n)
RSA では φ(n) = L なので：
m^L ≡ 1 (mod n)
具体例で確認してみましょう。p = 3, q = 5 のとき：
n = 15
L = φ(15) = 2 × 4 = 8
m = 2 の場合：
2^8 = 256
256 ÷ 15 = 17 余り 1
確かに 2^8 mod 15 = 1
RSAでこの条件は満たされる？
オイラーの定理は「m と n が互いに素」という条件付きです。RSA では n = p × q（p, q は素数）なので、m が p または q の倍数でない限り、m と n は互いに素になります。
実用上、平文 m は n より小さい数に変換して使うため、m が巨大な素数 p や q の倍数になる確率は極めて低く、この条件はほぼ確実に満たされます。
復号で元に戻るにはどうすればいい？
オイラーの定理から m^L ≡ 1 (mod n) がわかりました。これを使って、復号で元に戻る仕組みを考えてみましょう。
ステップ1：m^L = 1 を活用したい
m^L が 1 になるなら、m に m^L をかけても m のままです。
m × m^L = m × 1 = m
これを指数で書くと m^(1+L) = m です。
さらに、1 を何回かけても 1 なので、(m^L)^k = 1 です。つまり：
m × (m^L)^k = m × 1 = m
指数で書くと m^(1 + L×k) = m（k は任意の整数）です。
ステップ2：でも L は公開したくない
ここで問題があります。暗号化に使う指数を「1 + L×k」としてしまうと、L を公開することになります。
n と L の両方がわかると、p と q を簡単に求められてしまいます。なぜなら：
n = p × q
L = (p-1)(q-1) = pq - p - q + 1 = n - p - q + 1
この2つの式から p + q = n - L + 1 がわかり、p × q = n と合わせると p と q は二次方程式の解として求まります。
だから L は秘密にしなければなりません。
ステップ3：1 + L×k を e × d に分割する
L を公開せずに「1 + L×k」という形を作りたい。そこで、この値を e × d という2つの数の積に分割します。
e × d = 1 + L × k
e だけを公開し、d は秘密にします。L を知らない攻撃者は d を計算できません。
なぜ攻撃者は L を求められないのか？
攻撃者には n（= p × q）と e だけが公開されています。L = (p-1)(q-1) を計算するには p と q が必要ですが、n から p と q を求めるには 素因数分解 が必要です。
現代の暗号で使われる n は 2048 ビット以上（10進数で600桁以上）の巨大な数です。このサイズの数の素因数分解は、現在のコンピュータでは現実的な時間内に計算できません。これが RSA 暗号の安全性の根拠です。
ステップ4：d は拡張ユークリッドの互除法で求まる
「e × d = 1 + L × k」を変形すると：
e × d - L × k = 1
e × d + L × (-k) = 1
これは「e × □ + L × △ = 1」という形です。拡張ユークリッドの互除法で □（= d）と △（= -k）を求められます。
ステップ5：ベズーの等式が存在を保証する
ベズーの等式によれば：
「a × x + b × y = 1 が整数解を持つ」⇔「a と b は互いに素」
つまり e と L が互いに素なら、d は必ず存在します。だから e を選ぶときは「L と互いに素な数」を選ぶ必要があります。
ステップ6：これで復号できる
e と d が e × d = 1 + L × k を満たすとき、暗号文 c = m^e を d 乗すると：
c^d = (m^e)^d = m^(e×d) = m^(1 + L×k) = m × (m^L)^k = m × 1 = m
オイラーの定理で m^L = 1 になるので、元の平文 m が出てきます。
e と d の具体的な求め方
ステップ4と5で、d は拡張ユークリッドの互除法で求まり、ベズーの等式により存在が保証されることを説明しました。ここでは具体的な計算方法を見ていきます。
e の選び方
e は「L と互いに素な数」であれば自由に選べます。
実用上は 65537 がほぼ常に使われます。理由は：
- 素数なので、ほとんどの L と互いに素になる
- 二進数で
10000000000000001（1が2つだけ）なので計算が速い - 十分大きいので、小さい e に対する攻撃を防げる
d の計算：拡張ユークリッドの互除法
e を決めたら、「e × d + L × k = 1」を満たす d を拡張ユークリッドの互除法で求めます。
手順1：ユークリッドの互除法で互いに素か確認
まず普通のユークリッドの互除法で、e と L の最大公約数を求めます。「大きい数を小さい数で割って、余りが出たらその余りで割る」を繰り返します。
例として、e = 3 と L = 8 の場合：
8 = 3 × 2 + 2
3 = 2 × 1 + 1
2 = 1 × 2 + 0 ← 余りが0になったので終了
最大公約数は 1（互いに素）→ d が存在する
手順2：逆にたどって d を求める
上の計算過程を逆にたどって「3 × □ + 8 × △ = 1」となる □ を見つけます。
1 = 3 - 2 × 1
= 3 - (8 - 3 × 2) × 1
= 3 - 8 + 3 × 2
= 3 × 3 - 8 × 1
つまり 3 × 3 + 8 × (-1) = 1
よって d = 3 が求まりました。
確認
e × d = 3 × 3 = 9 = 1 + 8 × 1 なので、確かに「e × d = 1 + L × k」を満たしています。
まとめ
RSA暗号の数学的な仕組みを整理すると：
- オイラーの定理 により m^L ≡ 1 (mod n) が成り立つ（L = φ(n) = (p-1)(q-1)）
- e × d = 1 + L × k となるように e と d を選ぶ
- すると m^(e×d) = m × (m^L)^k ≡ m × 1 ≡ m となり、元に戻る
- d を求めるには 拡張ユークリッドの互除法 を使う
- ベズーの等式 により、e と L が互いに素なら d が存在することが保証される
- L を秘密にすることで、攻撃者は d を計算できない（素因数分解の困難性）
暗号化 → 復号で元に戻るのは「たまたま」ではなく、数学的に保証されているということがわかりました。
参考資料
- RFC 8017 - PKCS #1 - RSA暗号の標準仕様
- 芝浦工業大学 2020年度 代数学Iの授業資料
Discussion