RSAアルゴリズムの計算方法を具体例でわかりやすく解説

RSAは公開鍵暗号方式（public-key encryption）を実現する暗号システムの一つで、インターネットなど安全性が保証されていないネットワークを経由して機密情報をやり取りする際に、広く利用されています。

RSAアルゴリズムは、最も代表的な非対称鍵暗号アルゴリズムです。その安全性の基盤となっているのは、「大きな素数を見つけて掛け合わせるのは簡単だが、その積を素因数分解することは極めて困難である」という数学的な性質です。RSAでは、秘密鍵と公開鍵という2つの鍵を使用します。

RSAアルゴリズムの計算手順（具体例）

ここでは、具体的な数値を使ってRSAの処理の流れを確認します。読みやすさのため、実際の値を手順と併せて示していきます。

ステップ1：2つの素数PとQを選ぶ

まず、素数を2つ選びます。ここでは説明を簡潔にするため小さな素数を用い、P = 7、Q = 17 とします（実際の運用では数百桁の巨大な素数が使用されます）。

ステップ2：N = P × Q を計算する

N = 7 × 17 = 119

このNは、暗号化と復号の両方で使われる法（モジュラス）となります。

ステップ3：公開鍵（暗号化鍵）Eを選ぶ

Eは、(P − 1) × (Q − 1) と互いに素（共通の約数を持たない）になるように選びます。

• (7 − 1) × (17 − 1) = 6 × 16 = 96 を求めます。

• 96の素因数は 2 と 3 です（96 = 2 × 2 × 2 × 2 × 2 × 3）。

• したがって、Eとしては2や3を約数に含まない数を選ぶ必要があります。たとえば 4（2を約数に持つ）、15（3を約数に持つ）、6（2と3の両方を持つ）は不適切です。

• ここでは E = 5 を採用します（2と3を約数に持たない他の数でも構いません）。

ステップ4：秘密鍵（復号鍵）Dを求める

Dは、次の式が成り立つように選びます。

(D × E) mod ((P − 1) × (Q − 1)) = 1

• E、P、Qの値を式に代入すると、(D × 5) mod (6 × 16) = 1、すなわち (D × 5) mod 96 = 1 となります。

• 計算の結果、D = 77 を選ぶと (77 × 5) mod 96 = 385 mod 96 = 1 となり、条件を満たします。

ステップ5：暗号化

平文（PT）から暗号文（CT）は、次の式で求めます。

CT = PT^E mod N

たとえば、平文 10 を暗号化する場合は以下のようになります。

CT = 10⁵ mod 119 = 100000 mod 119 = 40

ステップ6：暗号文の送信

計算された暗号文 40 を受信者に送信します。

ステップ7：復号

受信者は、受け取った暗号文（CT）から平文（PT）を次の式で復元します。

PT = CT^D mod N

この例では、PT = 40⁷⁷ mod 119 = 10 となり、ステップ5で暗号化した元の平文 10 が正しく復元されます。

まとめ

RSAアルゴリズムは、「素因数分解の困難さ」を安全性の根拠とする公開鍵暗号方式です。実際の運用では非常に巨大な素数が使われるため、暗号文から元の平文を不正に復元することは事実上不可能とされています。この仕組みによって、事前に鍵を秘密裏に共有することなく、安全な通信が実現されています。