公開鍵暗号（RSA）を体験しよう

RSA暗号の仕組みを、実際に計算しながら学びましょう。

合同式（mod）の基礎

RSA暗号では「合同式」という考え方を使います。手計算で解くためのポイントを押さえましょう。

合同式とは？

a ≡ b (mod N) は「aをNで割った余りとbをNで割った余りが等しい」という意味です。

例: 17 ≡ 3 (mod 7) → 17÷7=2余り3、3÷7=0余り3

例: 25 ≡ 4 (mod 7) → 25÷7=3余り4、4÷7=0余り4

手計算で使える性質

性質1: 掛け算の途中で余りを取ってよい

(a × b) mod N = ((a mod N) × (b mod N)) mod N

例: 8 × 9 mod 7 を計算

→ 直接計算: 72 mod 7 = 2

→ 途中で余り: (8 mod 7) × (9 mod 7) mod 7 = 1 × 2 mod 7 = 2 ✓

性質2: べき乗を分割できる

a^m+n mod N = (a^m × aⁿ) mod N

例: 3⁵ mod 7 を計算

→ 3⁵ = 3² × 3² × 3¹

→ 3² = 9 ≡ 2 (mod 7)

→ 3⁴ = (3²)² ≡ 2² = 4 (mod 7)

→ 3⁵ = 3⁴ × 3 ≡ 4 × 3 = 12 ≡ 5 (mod 7)

性質3: 余りの周期性

aⁿ mod N の値は、nが増えると周期的にループすることがある

例: 2ⁿ mod 7 の値

2¹=2, 2²=4, 2³=8≡1, 2⁴=16≡2, 2⁵=32≡4, 2⁶=64≡1, ...

→ 周期3で 2→4→1→2→4→1→... とループ！

手計算のコツ

1. 数が大きくなったらすぐ余りを取る - 計算を楽にするため
2. べき乗は2乗ずつ計算 - 3⁸は3→9→81→...より、3²=9, 9²=81, 81²=... と計算
3. 周期を見つける - 同じ数が出てきたらループしている

📚 コラム: eとdは「逆元」の関係

逆元とは？

通常の数では、ある数aに対して a × a^-1 = 1 となる数a^-1を「逆数」と呼びます。

例: 5の逆数は 1/5（= 0.2）で、5 × 0.2 = 1

合同式の世界でも同様に、a × b ≡ 1 (mod N) となるbを「aの逆元」と呼びます。

例: mod 7 における 3 の逆元

3 × ? ≡ 1 (mod 7) となる数を探す

3 × 1 = 3, 3 × 2 = 6, 3 × 3 = 9 ≡ 2, 3 × 4 = 12 ≡ 5, 3 × 5 = 15 ≡ 1 ✓

よって、mod 7 における 3 の逆元は 5

RSAにおけるeとd

RSA暗号では、次の関係が成り立つようにdを決めます:

e × d ≡ 1 (mod φ(N))

つまり、dはφ(N)を法とするeの逆元です。

なぜこれで復号できるの？

e × d ≡ 1 (mod φ) より、e × d = k × φ + 1 と書けます（kは整数）。

暗号文 C = M^e mod N を復号すると:

C^d = (M^e)^d = M^e×d = M^kφ+1 = M^kφ × M

フェルマーの小定理より M^φ ≡ 1 (mod N) なので、

M^kφ × M ≡ 1^k × M = M (mod N)

このように、逆元の性質により暗号化と復号が「打ち消し合う」のです。

逆元が存在する条件

aとNが互いに素（最大公約数が1）のとき、aの逆元が存在します。

RSAでeとφ(N)が互いに素である必要があるのは、eの逆元dを求めるためです。

【受信者側の作業】鍵を作る

① 素数pとqを選んでNを作る

2つの素数を選びます。これが秘密鍵のもとになります。

💡 手計算では小さい素数（例: 5, 7, 11, 13）を選ぶと楽です

250までの素数一覧

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241

p =

q =

N = p × q = ?← これが公開鍵の一部

② φ(N)を求める

1以上N以下の整数のうち、Nと互いに素な数の個数を求めます。

φ(N) = (p-1) × (q-1)

💡 p=5, q=7 なら φ(35) = 4×6 = 24

φ(N) = ?← これは非公開

③ φと互いに素な数eを選ぶ

φの約数でない素数を選ぶとよいです。小さい値の方が計算が楽です。

💡 e=3, 5, 7 などの小さい素数がおすすめ（ただしφの約数はNG）

e =

← これも公開鍵の一部

④ 秘密鍵dを求める

d × e ≡ 1 (mod φ) となるdを見つけます。

💡 言い換えると「d × e を φ で割った余りが 1」となるdを探す
→ m × φ ÷ e のあまりが e - 1 になるmを見つけ、d = (φ × m + 1) ÷ e で計算

m	m × φ mod e	計算式

m = ?

d = (φ(N) × m + 1) ÷ e

d = ?← これが秘密鍵

鍵のまとめ

公開鍵（みんなに教えてOK）

N = ?

e = ?

秘密鍵（絶対に秘密！）

d = ?

【送信者側の作業】メッセージを暗号化する

① 送信する情報を数字Mに変換

送信する数字はN未満である必要があります。

M =

② 暗号文Cを計算

C = M^e mod N

暗号文 C = ?

【受信者側の作業】暗号文を復号する

受信した暗号文Cから平文Mを復元

M = C^d mod N

復号結果 M = ?

【盗聴者の視点】

盗聴者は公開鍵（N, e）と暗号文Cだけを知っています。

復号するにはNを素因数分解してpとqを得る必要がありますが...

なぜRSAは安全なのか？

実際のRSAでは、1024ビット（約300桁）や2048ビット（約600桁）のNが使われます。

1秒間に10億回（1GHz）計算できるコンピュータで素因数分解を試みると...

• 1024ビットの場合：約 10¹³³ 年 かかる
• 宇宙の年齢は約137億年（1.37×10¹⁰年）
• つまり、宇宙の年齢の約 10¹²³ 倍 の時間が必要！