高校生のためのRSA暗号入門

RSA暗号とは

RSA暗号は、1977年にRivest、Shamir、Adlemanの3人によって開発された公開鍵暗号の代表的な暗号方式です。インターネットでのクレジットカード決済やメールの暗号化など、私たちの身の回りで広く使われています。

従来の暗号では、暗号化と復号化に同じ鍵を使う「共通鍵暗号」が主流でしたが、RSA暗号では暗号化用の鍵（公開鍵）と復号化用の鍵（秘密鍵）が異なるのが特徴です。

RSA暗号に必要な数学の基礎知識

1. 素数

素数とは、1と自分自身以外に約数を持たない2以上の自然数です。

例：2, 3, 5, 7, 11, 13, 17, 19, 23, …

2. 互いに素

2つの整数の最大公約数が1であるとき、この2つの数は「互いに素」と言います。

例：6と35は互いに素（最大公約数が1）

3. オイラーのφ（ファイ）関数

n以下の正の整数のうち、nと互いに素な数の個数を表します。

pが素数のとき：$\phi(p) = p – 1$

p, qが異なる素数のとき：$\phi(pq) = (p-1)(q-1)$

4. 合同式

整数aとbをnで割った余りが等しいとき、$a \equiv b \pmod{n}$と書きます。

例：$17 \equiv 5 \pmod{12}$（17も5も12で割った余りは5）

5. 拡張ユークリッド互除法

ax + by = gcd(a, b)を満たす整数x, yを求める方法です。RSA暗号では秘密鍵を計算するのに使用します。

RSA暗号の仕組み

鍵の生成手順

1. 2つの素数p, qを選ぶ

   大きな素数ほど安全ですが、例では小さな素数を使用します。

2. n = p × qを計算

   nは「RSAモジュラス」と呼ばれます。

3. φ(n) = (p-1)(q-1)を計算

   これは「オイラーのトーシェント関数」の値です。

4. 公開指数eを選ぶ

   1 < e < φ(n)で、gcd(e, φ(n)) = 1となるeを選びます。

   よく使われる値：e = 3, 17, 65537

5. 秘密指数dを計算

   $ed \equiv 1 \pmod{\phi(n)}$を満たすdを求めます。

   つまり、$ed = k\phi(n) + 1$（kは整数）となるdです。

公開鍵：(n, e)
秘密鍵：(n, d)

暗号化と復号化

暗号化：平文mを暗号文cに変換
$c \equiv m^e \pmod{n}$

復号化：暗号文cを平文mに復元
$m \equiv c^d \pmod{n}$

具体例で理解しよう

例題1：小さな数でのRSA暗号

ステップ1：素数の選択
p = 7, q = 11を選びます。

ステップ2：nの計算
n = p × q = 7 × 11 = 77

ステップ3：φ(n)の計算
φ(n) = (p-1)(q-1) = (7-1)(11-1) = 6 × 10 = 60

ステップ4：公開指数eの選択
φ(n) = 60と互いに素な数を選びます。
60 = 2² × 3 × 5なので、2, 3, 5と互いに素な数を選ぶ必要があります。
e = 7を選びます（gcd(7, 60) = 1）。

ステップ5：秘密指数dの計算
$7d \equiv 1 \pmod{60}$を満たすdを求めます。
7d = 60k + 1の形で表せるdを探すと：
k = 1のとき：7d = 61, d = 61/7（整数でない）
k = 6のとき：7d = 361, d = 361/7 ≈ 51.57（整数でない）
k = 7のとき：7d = 421, d = 421/7 ≈ 60.14（整数でない）
実際に計算すると：d = 43が解になります。
確認：7 × 43 = 301 = 60 × 5 + 1 ✓

結果：
公開鍵：(77, 7)
秘密鍵：(77, 43)

暗号化・復号化の実行

平文：m = 5を暗号化してみましょう。

暗号化：
$c \equiv 5^7 \pmod{77}$
$5^7 = 78125$
78125 ÷ 77 = 1014…47
よって、c = 47

復号化：
$m \equiv 47^{43} \pmod{77}$

大きな数の計算には「繰り返し二乗法」を使います：

43 = 32 + 8 + 2 + 1 = 2⁵ + 2³ + 2¹ + 2⁰

よって、$47^{43} = 47^{32} × 47^8 × 47^2 × 47^1$

計算を省略しますが、結果はm = 5となり、正しく復号化されます。

練習問題

練習問題1

p = 5, q = 13として以下を求めてください。

1. n = ?
2. φ(n) = ?
3. e = 7とするとき、秘密鍵d = ?
4. 平文m = 3を暗号化した暗号文c = ?

練習問題2

練習問題1で求めた鍵を使って、暗号文c = 37を復号化してください。

RSA暗号の安全性

素因数分解問題

RSA暗号の安全性は「大きな合成数の素因数分解の困難さ」に基づいています。

• 公開鍵(n, e)から、nをp×qに素因数分解できれば秘密鍵dが求められる
• 現在のコンピュータでは、数百桁の数の素因数分解は現実的な時間では不可能
• 実用的なRSA暗号では2048bit（約600桁）以上の鍵長が推奨される

量子コンピュータの脅威

将来、十分に大規模な量子コンピュータが実用化されると、「ショアのアルゴリズム」により効率的な素因数分解が可能になり、RSA暗号は破られる可能性があります。そのため、量子耐性暗号の研究が進められています。

まとめ

RSA暗号は数学の美しい応用例の一つです。素数論、合同式、オイラー関数といった数学的概念が組み合わされて、安全な暗号システムを構築しています。

重要なポイント：

• 公開鍵と秘密鍵が異なる「公開鍵暗号」
• 安全性は素因数分解問題の困難さに依存
• 実用的には十分大きな鍵長が必要
• 現代のインターネット社会を支える基盤技術

この記事で学んだ基礎知識をもとに、より高度な暗号理論や情報セキュリティの世界を探求してみてください。