はじめに

RSA は公開鍵暗号の代表例です。
直感的には

公開鍵で暗号化できる
しかし復号は秘密鍵がないと難しい
その非対称性を整数論で作っている

という仕組みです。

ただし RSA の本質は「大きな素数を使うと安全」という一言ではありません。数学的には、

法 $n=pq$ の下での合同式
乗法群 $\mathbb{Z}_n^\times$
Euler の定理や Fermat の小定理
Chinese Remainder Theorem

がきれいにつながって、復号が正しく動くように作られています。

この記事では RSA を数式中心に整理します。特に

なぜ鍵生成がこの形になるのか
なぜ復号すると元に戻るのか
署名がなぜ検証できるのか
何が安全性の根拠で、何が限界か

を順に説明します。

1. 記法と基本事項

1.1 合同式

整数 $a,b,n$ に対して

a \equiv b \pmod{n}

とは、 $n$ が $a-b$ を割り切ることです。

例えば

17 \equiv 2 \pmod{5}

です。RSA では、整数を普通の実数として扱うのではなく、法 $n$ の世界で扱います。

1.2 剰余類環と乗法群

法 $n$ の剰余類全体を

\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}

と書きます。この中で、 $n$ と互いに素な元だけを集めると

\mathbb{Z}_n^\times = \{\,x \in \mathbb{Z}_n \mid \gcd(x,n)=1\,\}

となり、これは乗法について群になります。

RSA の核は、この $\mathbb{Z}_n^\times$ 上で

x \mapsto x^e \pmod{n}

という写像を考えることです。

1.3 Euler の $\varphi$ 関数

正整数 $n$ に対し、 $1,\dots,n$ のうち $n$ と互いに素な整数の個数を

\varphi(n)

と書きます。特に $p,q$ が異なる素数なら

\varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1)

です。

1.4 Euler の定理と Fermat の小定理

$\gcd(a,n)=1$ なら

a^{\varphi(n)} \equiv 1 \pmod{n}

が成り立ちます。これが Euler の定理です。

特に $p$ が素数で $p \nmid a$ なら

a^{p-1} \equiv 1 \pmod{p}

となります。これが Fermat の小定理です。

RSA の復号の正しさは、ほぼこの定理の応用です。

2. RSA の問題設定

RSA では、平文を整数

m \in \{0,1,\dots,n-1\}

として表し、暗号文も同じく法 $n$ の整数として扱います。

公開鍵を $(n,e)$ 、秘密鍵を $d$ とすると、

暗号化:

c \equiv m^e \pmod{n}

復号:

m' \equiv c^d \pmod{n}

です。

目標は

(m^e)^d \equiv m \pmod{n}

を常に成り立たせるように $e,d,n$ を作ることです。

3. 鍵生成

RSA の鍵生成は次の通りです。

3.1 素数を選ぶ

大きな異なる素数 $p,q$ を選び、

n = pq

とします。

この $n$ が公開鍵の一部になります。

3.2 $\varphi(n)$ または $\lambda(n)$ を計算する

素数の積なので

\varphi(n) = (p-1)(q-1)

です。

より鋭い量として Carmichael 関数

\lambda(n)=\mathrm{lcm}(p-1,q-1)

を使うことも多いです。
実装や証明では $\lambda(n)$ を使う方が本質的です。なぜなら、 $\mathbb{Z}_n^\times$ の任意の元 $x$ について

x^{\lambda(n)} \equiv 1 \pmod{n}

が成り立つからです。

3.3 公開指数 $e$ を選ぶ

次に

1 < e < \lambda(n), \qquad \gcd(e,\lambda(n))=1

を満たす整数 $e$ を選びます。

実務では

e=65537

がよく使われます。これは

2 進表現が扱いやすい
十分に大きく、かつ計算も速い

からです。

3.4 秘密指数 $d$ を求める

$e$ の $\lambda(n)$ に関する逆元を $d$ とします。つまり

ed \equiv 1 \pmod{\lambda(n)}

を満たす $d$ を求めます。

これは拡張 Euclid の互除法で計算できます。

別の書き方をすると、ある整数 $k$ が存在して

ed = 1 + k\lambda(n)

です。

これで

公開鍵: $(n,e)$
秘密鍵: $d$ （実際には $p,q$ も保持する）

が完成です。

4. なぜ復号で元に戻るのか

RSA の核心はここです。

暗号化したあと復号すると

m' \equiv (m^e)^d = m^{ed} \pmod{n}

です。したがって、

m^{ed} \equiv m \pmod{n}

を示せばよいことになります。

4.1 まずは $\gcd(m,n)=1$ の場合

$m \in \mathbb{Z}_n^\times$ 、つまり

\gcd(m,n)=1

とします。このとき

ed = 1 + k\lambda(n)

なので

m^{ed} = m^{1+k\lambda(n)} = m\left(m^{\lambda(n)}\right)^k.

Carmichael の性質から

m^{\lambda(n)} \equiv 1 \pmod{n}

ですから

m^{ed} \equiv m \cdot 1^k \equiv m \pmod{n}.

これで復号の正しさが示せました。

4.2 $m$ が $n$ と互いに素でない場合

実は RSA では、平文 $m$ が $p$ や $q$ の倍数であっても復号は正しく動きます。
この点は Euler の定理だけでは少し見えにくいので、Chinese Remainder Theorem を使って示します。

$n=pq$ なので、

m^{ed} \equiv m \pmod{n}

を示すには

m^{ed} \equiv m \pmod{p} \qquad \text{かつ} \qquad m^{ed} \equiv m \pmod{q}

を示せば十分です。

まず法 $p$ で考えます。 $ed \equiv 1 \pmod{p-1}$ なので、ある整数 $r$ があって

ed = 1 + r(p-1)

です。

場合 1: $p \mid m$

このとき

m \equiv 0 \pmod{p}

なので明らかに

m^{ed} \equiv 0 \equiv m \pmod{p}.

場合 2: $p \nmid m$

このとき Fermat の小定理より

m^{p-1} \equiv 1 \pmod{p}

だから

m^{ed} = m^{1+r(p-1)} = m\left(m^{p-1}\right)^r \equiv m \pmod{p}.

したがってどちらの場合でも

m^{ed} \equiv m \pmod{p}

です。同様に

m^{ed} \equiv m \pmod{q}

も成り立ちます。よって CRT より

m^{ed} \equiv m \pmod{n}

が従います。

これで すべての平文に対して復号が正しい ことが分かります。

5. 数値例

実際に小さな数で確かめます。もちろんこれは説明用で、実用には全く小さすぎます。

5.1 鍵生成

素数を

p=61,\qquad q=53

とすると

n=pq=3233

で、

\varphi(n)=(61-1)(53-1)=60 \cdot 52 = 3120

です。

公開指数として

e=17

を選ぶと、 $\gcd(17,3120)=1$ です。

次に

17d \equiv 1 \pmod{3120}

を解くと

d=2753

です。実際、

17 \cdot 2753 = 46801 = 1 + 15 \cdot 3120.

5.2 暗号化

平文を

m=65

とすると、暗号文は

c \equiv 65^{17} \pmod{3233} = 2790

です。

5.3 復号

復号すると

m' \equiv 2790^{2753} \pmod{3233} = 65

となり、元の平文に戻ります。

実際の計算では巨大な指数をそのまま計算するのではなく、繰り返し二乗法で

O(\log e), \quad O(\log d)

回程度の modular multiplication で計算します。

6. RSA 署名も同じ数式で動く

RSA では同じ構造で署名も作れます。

メッセージ $M$ のハッシュ値を $h=H(M)$ として、

s \equiv h^d \pmod{n}

を署名とします。

検証側は公開鍵 $(n,e)$ を使って

s^e \equiv h \pmod{n}

を確認します。

なぜこれでよいかというと

s^e \equiv (h^d)^e = h^{de} \equiv h \pmod{n}

だからです。

つまり

暗号化: 公開鍵で前に進む
署名: 秘密鍵で前に進み、公開鍵で検証する

という対称的な構造になっています。

ただし実務では 生のメッセージに直接 RSA をかけることはしません。必ずハッシュと署名用パディングを入れます。

7. CRT を使うと復号は速くなる

秘密鍵側は $p,q$ を知っているので、復号を mod $n$ で一発計算する代わりに、mod $p$ と mod $q$ に分けて計算できます。

まず

d_p = d \bmod (p-1), \qquad d_q = d \bmod (q-1)

を計算し、

m_p \equiv c^{d_p} \pmod{p}, \qquad m_q \equiv c^{d_q} \pmod{q}

を求めます。

その後、CRT で $m$ を復元します。
$q^{-1} \bmod p$ を使って

h \equiv q^{-1}(m_p - m_q) \pmod{p}

とおけば

m = m_q + hq

が mod $n$ の解です。

この方法が速い理由は、 $n$ ビットの指数演算を 1 回する代わりに、ほぼ半分のビット長の法で 2 回計算すればよいからです。実装では CRT 復号が標準です。

8. なぜ安全だと考えられるのか

RSA の公開鍵は $(n,e)$ です。攻撃者が知っているのは

n=pq

という積だけで、 $p,q$ 自体は知りません。

$d$ を求めるには

ed \equiv 1 \pmod{\lambda(n)}

を解く必要があるので、実質的には $\lambda(n)$ 、したがって $p,q$ を知る必要があります。

つまり RSA の安全性は大きく言えば

$n$ を素因数分解すること
あるいは $x \mapsto x^e \pmod{n}$ の逆像を求めること

が困難であることに依存しています。

ここで区別すべきなのは次の 2 つです。

8.1 整数因数分解問題

公開された

n = pq

から $p,q$ を求める問題です。大きな $n$ に対しては非常に難しいと考えられています。

8.2 RSA 問題

$n,e,c$ が与えられたとき

m^e \equiv c \pmod{n}

を満たす $m$ を求める問題です。

RSA の安全性はこの RSA 問題の困難性に依存します。
整数因数分解ができれば RSA は破れますが、逆に RSA を破れることが整数因数分解と常に同値かどうかは、一般には未解決です。

したがって、厳密には

「RSA の安全性 = 因数分解の難しさ」

と完全同一視するのではなく、

「因数分解の困難性が RSA 安全性の主要な根拠である」

と理解する方が正確です。

9. 教科書 RSA はそのままでは危ない

数学的に正しいことと、暗号として安全なことは別です。
教科書的な RSA

c \equiv m^e \pmod{n}

をそのまま使うと、次の問題があります。

9.1 決定論的である

同じ平文 $m$ を暗号化すると、常に同じ暗号文 $c$ が出ます。
これは IND-CPA 安全ではありません。

9.2 構造が露出する

RSA には乗法性があり、

(m_1^e)(m_2^e) \equiv (m_1m_2)^e \pmod{n}

です。したがって、生の RSA は malleable です。

9.3 署名も生では危険

もし署名を

s \equiv m^d \pmod{n}

と生で作ると、攻撃者が代数的性質を利用して偽造できる余地が生まれます。

このため実務では

RSA-OAEP: 暗号化用
RSA-PSS: 署名用

が使われます。
RSA 自体は trapdoor permutation ですが、安全な暗号方式にするには 乱数化とエンコーディング が必要です。

10. 実務上の設計ポイント

RSA を使うときは、数学だけでなく方式全体で考える必要があります。

10.1 平文全体を RSA で暗号化しない

RSA は大きなデータを直接暗号化するのに向いていません。
通常はランダムな共通鍵 $K$ を生成して

$K$ を RSA-OAEP で暗号化する
本文は AES-GCM などの共通鍵暗号で暗号化する

という hybrid encryption を使います。

10.2 鍵長

現代では少なくとも 2048-bit、用途によっては 3072-bit 以上が使われます。
小さすぎる鍵は因数分解の進歩に耐えられません。

10.3 素数生成の品質

$p,q$ は十分にランダムで独立に生成される必要があります。
乱数が弱いと、数学が正しくても鍵が破られます。

10.4 量子計算

Shor のアルゴリズムが大規模量子計算機上で実用化されれば、RSA は本質的に破られます。
そのため長期保護が必要な用途では post-quantum cryptography も併せて考える必要があります。

11. まとめ

RSA の構造を一言でまとめると、

\text{公開指数 } e \text{ と秘密指数 } d \text{ を} \quad ed \equiv 1 \pmod{\lambda(n)}

となるように選ぶことで、

m \mapsto m^e \pmod{n}

の逆写像を秘密鍵だけが計算できるようにしている、ということです。

数学的な要点は次の通りです。

法 $n=pq$ の構造を使う
$\mathbb{Z}_n^\times$ 上では $x^{\lambda(n)} \equiv 1 \pmod{n}$ が成り立つ
そのため $ed \equiv 1 \pmod{\lambda(n)}$ なら $m^{ed} \equiv m \pmod{n}$
平文が $n$ と互いに素でない場合も CRT で正しさを示せる
署名も同じ指数法則で検証できる

そして暗号として安全に使うには、

因数分解が難しいサイズの鍵を使う
生の RSA ではなく OAEP / PSS を使う
乱数生成、実装、サイドチャネル対策まで含めて設計する

必要があります。

RSA は古典的な方式ですが、整数論、群論、計算量の考え方がきれいに結びついた非常に美しい暗号でもあります。数式で追うと、「なぜ動くのか」がかなり透明に見えてきます。