RSA暗号を理解する

RSA暗号は、桁の大きな合成数の素因数分解が難しいことを根拠とした暗号化方式です。

開発したロナルド・リベスト(Ronald Rivest)、アディ・シャミア(Adi Shamir)、レオナルド・エーデルマン(Leonard Adleman)３人の頭文字を取って、RSA暗号です。

RSA暗号の数学的根拠

数学的根拠として、フェルマーの小定理とオイラーの定理に基づいています。

正直説明が難しいので、興味がなければ読み飛ばして構いません。

フェルマーの小定理

pを素数とし、aをpの倍数でない整数（aとpは互いに素）とするときに、
$$a^{p-1} \equiv 1 \pmod{p}$$
が成り立つ。

出典：フェルマーの小定理
（2021年5月20日 (木) 8:31　JSTの版）『ウィキペディア日本語版』

$p=5$として確認すると、確かに成立しています。

• $1^{4} = 1 \equiv 1 \pmod{5}$
• $2^{4} = 16 \equiv 1 \pmod{5}$
• $3^{4} = 81 \equiv 1 \pmod{5}$
• $4^{4} = 256 \equiv 1 \pmod{5}$
• $6^{4} = 1296 \equiv 1 \pmod{5}$
• $7^{4} = 2401 \equiv 1 \pmod{5}$

オイラーの定理

$n$が正の整数で$a$を$n$と互いに素な正の整数としたとき、
$$a^{\phi(n)} \equiv 1 \pmod{n}$$
が成り立つ。ここで$\phi(n)$はオイラー関数である。

出典：オイラーの定理(数論)
（2021年5月20日 (木) 8:31　JSTの版）『ウィキペディア日本語版』

オイラー関数

オイラー関数とは、正の整数nに対して、nと互いに素である1以上n以下の自然数の個数$\phi(n)$を与える数論的関数$\phi$である。

出典：オイラーのφ関数
（2021年5月20日 (木) 8:31　JSTの版）『ウィキペディア日本語版』

また、オイラー関数は以下の性質を持っています。

• $n$が素数の場合、$\phi(n)=n-1$
• $m,m$が互いに素な自然数の場合、$\phi(nm)=\phi(n)\phi(m)$

オイラーの定理を$a=7$として確認すると、確かに成立しています。

• $7^{\phi(2)} = 7^1 = 7 \equiv 1 \pmod{2}$
• $7^{\phi(3)} = 7^2 = 49 \equiv 1 \pmod{3}$
• $7^{\phi(4)} = 7^2 = 49 \equiv 1 \pmod{4}$
• $7^{\phi(5)} = 7^4 = 2401 \equiv 1 \pmod{5}$
• $7^{\phi(6)} = 7^2 = 49 \equiv 1 \pmod{6}$

RSA暗号の仕組み

暗号化

平文$M$(Message)と$E$(Encrypt)から、以下の式を用いて暗号文$C$(Cipher)を計算します。

$$C \equiv M^{E} \pmod{N}$$

このときのパラメータ$E$と$N$の組合せ($E, N$)が暗号化に使う鍵（公開鍵）となります。

複号化

暗号化と同様に、暗号文$C$と$D$(Decrypt)から平文$M$を計算します。

$$M \equiv C^{D} \pmod{N}$$

このときのパラメータ$D$と$N$の組合せ($D, N$)が複号化に使う鍵（秘密鍵）となります。

なぜ公開鍵から秘密鍵がばれないのか

秘密鍵の秘匿性を確保するためには、公開鍵から秘密鍵が計算できないことが必須です。

暗号として成立するために目指すべきは、以下の式が成り立つこと、つまり暗号化、複合化を経て元の平文に戻ってくることが必要です。
$$M^{E \cdot D} \equiv M \pmod{N}$$

ここで、オイラーの定理の式を変形します。（$v$は任意の整数）

$$\begin{gather}a^{\phi(N)} \equiv 1 \pmod{N}\\[10px]a^{\phi(N)v+1} \equiv a \pmod{N}\end{gather}$$

つまり、以下を満たす$E,D,N$の組合せが必要です。

$$E \cdot D = \phi(N)v+1$$

この1次不等方程式が自然数解を持つためには、$E,D$と$\phi(N)$は互いに素な整数である必要があります。

公開鍵から秘密鍵を計算不可とするために

$E$と$N$は公開されているので、$\phi(N)$が計算できると、秘密鍵$D$が簡単に計算できてしまいます。
また$N$が素数だと、オイラー関数の以下の性質より簡単に計算されてしまいます。
$$\phi(N) = N-1$$

そこで、桁数の大きい素数同士の素因数分解が難しいという性質を利用して、$N=pq$（$p,q$は素数）なる自然数$N$を導入します。

オイラー関数の性質より以下の式が成り立ちますが、素因数である$p,q$の値を知らなければ$\phi(N)$の計算は難しいです。

$$\phi(N)=\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$$

したがって、任意の$a$について以下の式を満たす$p,q$の素数の組を採用することで、暗号の安全性が担保されます。

$$a^{\phi(N)v+1} \equiv a \pmod{N}$$