RSA暗号と素数の秘密（公開鍵暗号）

Q: RSA暗号と素数の秘密（公開鍵暗号）とは何ですか？

RSA暗号は、2つの巨大素数の積 n = pq と、オイラーのトーシェント関数 \phi(n) = (p-1)(q-1) を基盤とする公開鍵暗号方式である。公開鍵指数 e に対し、ed \equiv 1 \pmod{\phi(n)} となる秘密鍵 d を計算する。 平文 m の暗号化: c \equiv m^e \pmod{n} 暗号文 c の復号化: m \equiv c^d \pmod{n}

Q: RSA暗号と素数の秘密（公開鍵暗号）は社会やプログラミングでどのように使われていますか？

公開鍵暗号によるメッセージ暗号化・復号化エンジン: 暗号化関数 `encrypt(m, e, n)` と復号化関数 `decrypt(c, d, n)` のTypeScript実装。繰り返し二乗法（モジュラー冪乗）により、巨大な指数計算も高速に処理する。

「掛け算は簡単だが、素因数分解は極めて困難」という非対称性を利用した現代暗号の金字塔

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: RSA暗号と素数の秘密（公開鍵暗号）の本質的な定義と直感的ビジュアルをシミュレーターで体験できる。
2: 公式や証明の背景にある数学的意味と、厳密な導出ステップを解説。
3: 実社会における工学応用（公開鍵暗号によるメッセージ暗号化・復号化エンジン）のTypeScript実装コードを収録。

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

RSA暗号と素数の秘密（公開鍵暗号）の基礎原理を体系化し、抽象的な計算を直感的に扱うために誕生した。

身につく武器・思考力

「掛け算は簡単だが、素因数分解は極めて困難」という非対称性を利用した現代暗号の金字塔。この考え方を身につけることで、複雑な課題を単純化して数理モデルとして解く力が養われる。

実社会・ITでの活躍現場

•公開鍵暗号によるメッセージ暗号化・復号化エンジン
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

小さな素数 p=3, q=11 から作られた公開鍵 (e, n) と秘密鍵 (d, n) がすでに計算されている。平文メッセージのスライダーを動かすと、暗号文 c = m^e mod n と、それを秘密鍵で復号した結果 m = c^d mod n がリアルタイムに再計算され、どんな数字でも元の平文へ完璧に復元される様子を確認できる。

Step 1: 2つの素数から鍵を生成

素数 p

素数 q

公開鍵 (e, n)

(3, 33)

誰にでも公開してOK

秘密鍵 (d, n)

(7, 33)

絶対に秘密！

Step 2: メッセージ（数字）の暗号化と復号化

平文メッセージ (m < 33): 5

元のメッセージ (平文)

数字データ

暗号文 c = m^3 mod 33

盗聴されても解読不能

復号文 m = c^7 mod 33

秘密鍵 d=7 で復元成功！

↑ 公開鍵 $(e, n)$ を使って $c = m^e \\bmod n$ を計算するのは一瞬ですが、暗号文 $c$ から秘密鍵 $d$ を割り出すには $n = 33$ を素因数分解して $p=3, q=11$ を突き止める必要があります。桁数が数百桁になると、世界最速のスパコンでも数千年かかります。

Layer 2 — 定義・受験・証明

定義

RSA暗号は、2つの巨大素数の積 $n = pq$ と、オイラーのトーシェント関数 $\phi(n) = (p-1)(q-1)$ を基盤とする公開鍵暗号方式である。公開鍵指数 $e$ に対し、 $ed \equiv 1 \pmod{\phi(n)}$ となる秘密鍵 $d$ を計算する。平文 $m$ の暗号化:

c \equiv m^e \pmod{n}

暗号文 $c$ の復号化:

m \equiv c^d \pmod{n}

公式・数理モデル

c = m^e \bmod n \iff m = c^d \bmod n

証明・導出

フェルマーの小定理・オイラーの定理の証明： $ed \equiv 1 \pmod{\phi(n)}$ より、ある整数 $k$ を用いて $ed = 1 + k\phi(n)$ と書ける。

復号化の計算を行うと、

c^d = (m^e)^d = m^{ed} = m^{1 + k\phi(n)} = m \cdot (m^{\phi(n)})^k \pmod{n}

オイラーの定理により、 $\gcd(m, n) = 1$ のとき $m^{\phi(n)} \equiv 1 \pmod{n}$ が成り立つため、

c^d \equiv m \cdot (1)^k = m \pmod{n}

となり、暗号文 $c$ を $d$ 乗して $n$ で割った余りを計算するだけで、必ず元の平文 $m$ が復元される。

押さえておきたいポイント

公開鍵 $(e, n)$ は誰にでも見せてよいが、秘密鍵 $d$ を持っている人しか暗号文を解読できない
解読するには $n$ を素因数分解して $p$ と $q$ を知る必要があるが、数百桁の素数の積の素因数分解にはスーパーコンピュータでも天文学的な時間がかかる
「掛け算は一瞬だが、因数分解は超難解」という計算複雑性のギャップ（一方向性関数）が暗号の安全性の源泉である
今日のインターネットのHTTPS通信、クレジットカード決済、電子署名の基盤として24時間稼働している

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

公開鍵暗号によるメッセージ暗号化・復号化エンジン

暗号化関数 `encrypt(m, e, n)` と復号化関数 `decrypt(c, d, n)` のTypeScript実装。繰り返し二乗法（モジュラー冪乗）により、巨大な指数計算も高速に処理する。

1// 繰り返し二乗法による高速モジュラー冪乗 (base^exp % mod)
2function modPow(base: number, exp: number, mod: number): number {
3  let result = 1;
4  base = base % mod;
5  while (exp > 0) {
6    if (exp % 2 === 1) result = (result * base) % mod;
7    base = (base * base) % mod;
8    exp = Math.floor(exp / 2);
9  }
10  return result;
11}
12
13// 公開鍵: (e = 3, n = 33) ※ p=3, q=11
14// 秘密鍵: (d = 7, n = 33) ※ φ(n)=20, 3*7 = 21 ≡ 1 (mod 20)
15const e = 3, d = 7, n = 33;
16
17const message = 4; // 暗号化したい秘密の数字
18const cipher = modPow(message, e, n); // c = 4^3 % 33 = 64 % 33 = 31
19const decrypted = modPow(cipher, d, n); // m = 31^7 % 33 = 4
20
21console.log(`平文: ${message} -> 暗号文: ${cipher} -> 復号: ${decrypted}`);