RSA暗号計算シミュレーター

RSA暗号とは？世界を守る大きな素数の魔法

RSA暗号は、1977年にロナルド・リベスト、アディ・シャミア、レオナルド・エードルマンの3人によって考案された、世界で最も広く使われている公開鍵暗号アルゴリズムです。Webサイトの閲覧（HTTPS）、メールの署名、ソフトウェアのアップデートなど、私たちが意識せずに行っている通信の安全性の多くが、このRSA暗号によって守られています。

その最大の特徴は、「誰でも見ることができる鍵（公開鍵）」で暗号化し、「本人しか持っていない鍵（秘密鍵）」で復号するという「非対称性」にあります。

RSAアルゴリズムの5つのステップ

RSAの仕組みは、整数論という数学の分野に基づいています。以下の手順で鍵が作成されます：

1. 2つの大きな素数 $p$ と $q$ を選ぶ： 実際の実装では、数千桁の非常に大きな素数が使われます。
2. モジュラス $n$ の計算： $n = p \times q$ を求めます。この $n$ の長さ（ビット数）が鍵の長さとなります。
3. オイラーのφ関数 $\phi(n)$ の計算： $\phi(n) = (p-1)(q-1)$ を求めます。これは $n$ と互いに素な整数の個数です。
4. 公開鍵 $e$ の決定： $1 < e < \phi(n)$ かつ $\gcd(e, \phi(n))=1$ となる整数 $e$ を選びます。
5. 秘密鍵 $d$ の計算： $e \times d \equiv 1 \pmod{\phi(n)}$ となる整数 $d$ を「拡張ユークリッド互除法」を用いて求めます。

なぜ安全なのか？素因数分解の壁

RSA暗号の安全性は、「巨大な数を素因数分解するのは、コンピュータにとっても非常に時間がかかる」という事実に基づいています。

$n = p \times q$ を計算するのは一瞬ですが、逆に巨大な $n$ だけを見て、元の $p$ と $q$ を当てるのは、現在のスーパーコンピュータを何年も稼働させても不可能なほど困難です。$p$ と $q$ がわからない限り、秘密鍵 $d$ を導き出すことはできません。

暗号化と復号の数式

実際のデータの変換は、以下の剰余演算（Mod演算）で行われます：

• 暗号化： $C = M^e \pmod{n}$ （平文 $M$ を $e$ 乗して $n$ で割った余り）
• 復号： $M = C^d \pmod{n}$ （暗号文 $C$ を $d$ 乗して $n$ で割った余り）

フェルマーの小定理やオイラーの定理といった数学の魔法により、この計算を行うと不思議と元のメッセージ $M$ が完璧に戻ってくるのです。

現代におけるRSAの役割と限界

RSAは強力ですが、計算負荷が高いため、現代では「共通鍵暗号（AESなど）」の鍵を受け渡すためにだけ使われ、実際のデータ通信はAESで行うというハイブリッド方式が一般的です。また、将来的に「量子コンピュータ」が実用化されると、$n$ を高速に素因数分解できる可能性が指摘されており、より強固な暗号方式（耐量子暗号）の研究も進んでいます。

まとめ

RSA暗号は、数学という究極の真理を武器にデジタルの壁を築いた、人類の知恵の結晶と言えます。当シミュレーターを通じて、普段何気なく使っている「鍵」の背景にある、壮大な数学の世界を体験してみてください。