RSA暗号を完全に理解したので備忘録として残しておきます。

完全数と素数

RSA暗号の原点は、古代ギリシャまで遡ります。
古代ギリシャの人々は、数のあらゆる特性に関心を抱いていました。
完全数は彼らが見つけ出したものの1つです。
完全数とは約数の和が自分自身と等しくなる数のことであり、古代ギリシャの時代でも以下の4つが完全数であることが知られていました。

\begin{align}
6&=1 + 2 + 3 \\
28&=1 + 2 + 4 + 7 + 14 \\
496&=1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 \\
8128&=1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064
\end{align}

これらの完全数を素因数分解すると、以下のようになります。

\begin{align}
6&=2^1\cdot3 \\
28&=2^2\cdot7 \\
496&=2^4\cdot31 \\
8128&=2^6\cdot127
\end{align}

そして上式を眺めると、以下のパターンに気づきます。

\begin{align}
6&=2^1\cdot(2^2-1)& \\
28&=2^2\cdot(2^3-1)& \\
120&=2^3\cdot(2^4-1)& \text{Not a Perfect Number}\\
496&=2^4\cdot(2^5-1)& \\
2016&=2^5\cdot(2^6-1)& \text{Not a Perfect Number}\\
8128&=2^6\cdot(2^7-1)&
\end{align}

$n=2, 3, 5, 7$のとき$2^{n-1}\cdot2^n-1$は完全数ですが、注目すべきは$2^n-1$が素数であることです。
$2^n-1$が素数のとき、$n$は素数です。
これは背理法によって証明できます。

証明

$n$が素数ではないとすると、$n$は以下のような因数$u, v$を持たなければならない。

n=uv, u>1, v>1

ここで、

\begin{align}
x^2-y^2&=(x-y)(x+y) \\
x^3-y^3&=(x-y)(x^2+xy+y^2)
\end{align}

であるように、

\begin{align}
x(x^n+x^{n-1}y+...+xy^{n-1}+y^n)=x^{n+1}+x^ny+x^{n-1}y^2+...+xy^n \\
y(x^n+x^{n-1}y+...+xy^{n-1}+y^n)=x^ny+x^{n-1}y^2+...+xy^n+y^{n+1}
\end{align}

として、上式から下式を引くと

x^{n+1}-y^{n+1}=(x-y)(x^n+x^{n-1}y+...+xy^{n-1}+y^n)

が成り立つので、

\begin{align}
2^n-1&=2^{uv}-1 \\
&=(2^u)^v-1 \\
&=(2^u-1)((2^u)^{v-1}+(2^u)^{v-2}+...+(2^u)+1)
\end{align}

と変形できる。ここで、$u>1$であるので、

\begin{align}
1&<2^u-1 \\
1&<(2^u)^{v-1}+(2^u)^{v-2}+...+(2^u)+1 \\
\end{align}

となり、$2^n-1$は$1$よりも大きい2つの因数を持つ。
しかし、これは$2^n-1$が素数であるという仮定に矛盾するため、この仮定は正しくない。
したがって、$n$は素数でなければならない。

では、その逆はどうでしょうか。
つまり、「$n$が素数ならば$2^n-1$は素数」でしょうか。
答えはNOです。

2^{11}-1=2047=23×89

が反例として挙げられます。

フェルマーの小定理

数学者フェルマーは$2^n-1$という形式をもとに、その基底が$2$以外、すなわち任意の整数$a$に対して$a^n-1$であればどうか、ということを考えました。
そして、以下の定理を発見しています。

pが素数ならば、任意の0<a<pに対してa^{p-1}-1はpで割り切れる

フェルマーは発見した多くの定理に対して証明を残しませんでした。この定理の証明も同様です。

したがって、この定理は発見後もしばらく証明がありませんでしたが、その約100年後に数学者オイラーがようやく証明してみせました。
その間100年ですから、証明にはいくつかの知識が必要になります。

簡約

12時間の時計を午前8時から7時間進めると午後3時になります。

数式で表すと、$8+7=12\hspace{3pt}あまり\hspace{3pt}3$です。
$(8+7)\hspace{3pt}\text{mod}\hspace{3pt}12=3$とも書きます。
時計はいくら進めても$0～11$の値を取ります。
つまりどんな整数でも、$12$で割ると必ず$0～11$の値を取ります。
このように、整数$n$で割ってできあがる数の集合を「$n$を法とする」といいます。
整数$n$を法とするとき、掛け算も成り立ちます。
$(5×6)\hspace{3pt}\text{mod}\hspace{3pt}12=6$です。
数$x$と数$y$を掛けて$1$になるとき、それらは簡約され、$y$は$x$の逆数、$x$は$y$の逆数と言います。

さて、話を素数に戻して、素数の$7$を法としたときの掛け算表を見てみましょう。

たとえば、$(2×4)\hspace{3pt}\text{mod}\hspace{3pt}7=1$です。つまり$2$と$4$は互いに逆数です。
この表を眺めているといくつか法則が見えてきます。

各行、各列には必ず$1～6$がそれぞれ1つずつ存在する
各行、各列には必ず$1$が存在する
自分自身を掛けて$1$となるのは$1$と$6$のみ

この法則は、他の素数でも成立するでしょうか。

定理1

素数pよりも小さい2つの整数の積はpで割り切れない

これは次の数式に書き換えることができます。

pは素数である\land 0<a,b<p\implies ab=mp+r\hspace{3pt}(0<r<p)

証明

$ab$が$p$の倍数であると仮定する。
このとき、$ab=mp$となるような、最も小さい整数$b$を選択する。
$p$は素数であるため、$b$で割ったときの余り$r'$が生じて

p=m'b+r'\hspace{3pt}(0<r'<m')

と書ける。この方程式の両辺に$a$を掛けると

\begin{align}
ap&=m'ab+ar' \\
ap-m'ab&=ar' \\
ap-m'mp&=ar' \\
ar'&=(a-mm')p \hspace{5pt}(0<r'<m') \\
\end{align}

と変形できる。
$r'$は$p$を$b$で割ったときの余りなので、取り得る範囲は$0<r'<m'<b\leq p$であり、$ar'$は$ab$よりも小さい。
これは$ab=mp$となるような最も小さい整数$b$を選択したことに矛盾するため、この仮定は正しくない。
よって、$ab$は$p$で割り切れない。

定理2

$p$が素数であるとすれば、任意の$0<a<p$に対して、以下の式が成り立つ。

\displaylines{
a\cdot\{1,...,p-1\}=\{a,...,a(p-1)\}=\{q_1p+r_1,...,q_{p-1}p+r_{p-1}\} \\
このとき\hspace{5pt}0< r_i<p\hspace{3pt}\land\hspace{3pt}i\ne j \implies r_i\ne r_j \\
}

これはつまり、素数$p$を法とする掛け算の表において、各行、各列には必ず$1～6$までの数がそれぞれ1回ずつ出現する（一意である）、ということです。

証明

$r_i= r_j\hspace{5pt}(i < j)$と仮定する。つまり、2つの剰余が等しいとき、その要素の差は

\begin{align}
aj-ai=(q_jp+r_j)-(q_ip+r_i)&=q_jp-q_ip \\
&=(q_j-q_i)p \\
\end{align}

となり、整理すると

\begin{align}
aj-ai=(q_j-q_i)p \\
a(j-i)=(q_j-q_i)p
\end{align}

を得る。
得られた等式は$ab=mp$の形式であり、$p$よりも小さい2つの整数の積が$p$で割り切れることを意味する。
これは定理1と矛盾するため、この仮定は正しくない。したがって、剰余は一意でなければならない。

定理3

\begin{align}
&pが素数であるとすれば、任意の\hspace{5pt}0<a<p\hspace{5pt}に対して \\
&\hspace{80pt}ab=mp+1 \\
&となるような数\hspace{5pt}0 < b < p\hspace{5pt}が存在する
\end{align}

つまり、各行、各列には必ず1が存在するということです。
この証明は簡単です。

証明

定理2より、集合

a\cdot\{1,...,p-1\}

の剰余には必ず$1$が含まれる。
したがって、$a$を$1$に変換する（乗法の）逆数$b$が存在しなければならない。

定理4

\begin{align}
&任意の\hspace{5pt}0<a<p\hspace{5pt}に対して \\
&a^2=mp+1\implies a=1\hspace{5pt}\lor\hspace{5pt}a=p-1 \\
&が成り立つ
\end{align}

自分自身を掛けて簡約されるのは$1$と$p-1$のみです。

証明

$1$でも$p-1$でもない、自己簡約する$a$があると仮定する。
すなわち

a \ne 1 \hspace{5pt}\land\hspace{5pt} a \ne p-1 \implies 1<a<p-1

証明の条件を整理すると

\begin{align}
a^2-1&=mp \\
(a-1)(a+1)&=mp
\end{align}

ここで、$a$の取り得る範囲は$1<a<p-1$なので、$a-1<p,\hspace{5pt}a+1<p$であり、$p$よりも小さい$2$つの整数の積が$p$で割り切れるため、定理1と矛盾する。
よって、この仮定は正しくない。自己簡約要素は$1$と$p-1$のみである。

さて、これでフェルマーの小定理を証明するための準備はほとんど整いましたが、証明に便利な定理を1つ紹介しておきます。

ウィルソンの定理

$p$が素数のとき、以下のような整数$m$が存在する。

(p-1)!=mp+(p-1)

あるいは以下のように言い換えられる。

(p-1)!=(p-1)\hspace{5pt}\text{mod}\hspace{5pt}p

証明

定義より

(p-1)!=1\cdot2\cdot3...(p-1)

が成り立つ。
また、定理4より自己簡約要素は$1$と$p-1$のみであり、その他の要素については定理3より逆数が必ず存在し簡約できる。
すなわち、$1$と$p-1$以外の要素は$mp+1$にまとめることができて、

\begin{align}
(p-1)!&=1\cdot(mp+1)\cdot(p-1) \\
&=mp\cdot p-mp+p-1 \\
&=(mp-m)p+(p-1)
\end{align}

となる。
このとき$v=mp-m$は定理を満たす。

フェルマーの小定理の証明

式$\prod_{i=1}^{p-1}ai$について考える。項$a$を積の外に出すと、以下の式が得られる。

\begin{align}
\prod_{i=1}^{p-1}ai=a^{p-1}\prod_{i=1}^{p-1}i
\end{align}

ウィルソンの定理を右辺に適用すると、

\begin{align}
\prod_{i=1}^{p-1}ai&=a^{p-1}(mp+(p-1)) \\
&=a^{p-1}mp+a^{p-1}p-a^{p-1} \\
&=(a^{p-1}m+a^{p-1})p-a^{p-1}
\end{align}

一方、$\prod_{i=1}^{p-1}ai$は$\lbrace a,...,a(p-1)\rbrace$の集合であり、定理2から$\lbrace q_1p+r_1,...,q_{p-1}p+r_{p-1}\rbrace$と等しい。
すなわち

\begin{align}
\prod_{i=1}^{p-1}ai&=a^{p-1}\prod_{i=1}^{p-1}(q_ip+r_i) \\
\end{align}

と書ける。
ここで、右辺の積を展開すると多くの$p$倍の項と、すべての$r_i$の積が得られるので、それらをまとめると

\begin{align}
\prod_{i=1}^{p-1}ai&=up+\prod_{i=1}^{p-1}r_i \\
\end{align}

となる。ここで再び右辺の積にウィルソンの定理を適用し

\begin{align}
\prod_{i=1}^{p-1}ai&=up+vp+(p-1) \\
&=wp-1
\end{align}

が得られる。
したがって、次の等式が成り立つ。

\begin{align}
wp-1=(a^{p-1}m+a^{p-1})p-a^{p-1}
\end{align}

これを整理すると、

\begin{align}
a^{p-1}+wp-1&=(a^{p-1}m+a^{p-1})p \\
a^{p-1}-1&=(a^{p-1}m+a^{p-1})p-wp \\
a^{p-1}-1&=(a^{p-1}m+a^{p-1}-w)p \\
&=np
\end{align}

したがって、$a^{p-1}-1$は$p$で割り切れる。

オイラーの定理への拡張

さて、フェルマーが$2^n-1$を$a^{p-1}-1$へと一般化したように、オイラーもフェルマーの小定理を一般化できないか考えました。
フェルマーは$a^n-1$の形で、$n=p-1$のときそれは$p$で割り切れることを示しましたが、素数ではない場合、つまり、すべての整数が対象となる場合はどうでしょうか。

素数ではない、$10$を法とした掛け算表を考えてみます。

素数$7$との違いは、各行、各列に$1$が必ずしも存在せず、定理3が成り立ちません。
また、各行、各列に$1～9$がそれぞれ1回ずつ出現しないこともあり、定理2が成り立ちません。

そこでオイラーは定理2と定理3が成り立つ行と列のみ、すなわち、$1～9$までの整数がそれぞれ1回ずつ出現する行と列に注目しました。

$1～9$がそれぞれ1回ずつ出現する行と、$1～9$がそれぞれ1回ずつ出現する列を塗り、$1～9$がそれぞれ1回ずつ出現しない行、列を消すと、上図のように特定の数$1,3, 7, 9$が浮かび上がってきます。

オイラーはこれらの数が1と自身以外に約数を持たない素数のように、法$n$とその数が$1$より大きい公約数を持たない数、すなわち互いに素な数であることに気が付きます。

そこで、互いに素な数の集合の大きさを

\phi(n)=|\{0<i<n\hspace{3pt}\land\hspace{3pt}\text{coprime}(i,n)\}|

と定義しました。オイラーのトーシェント関数と呼びます。
$\phi(n)$は、$n$を法とする掛け算の表において、色が塗られたエントリを含んでいる行（または列）の数をあらわします。
たとえば、$\phi(10)=4,\hspace{5pt}\phi(7)=6$です。

当然、素数は自身よりも小さな数と約数を持たないため、素数のトーシェントは

\phi(p)=p-1

になります。
すなわち、フェルマーの小定理が$p-1$という特殊なケースに過ぎないことを示しています。

オイラーの定理

a, nが互いに素である \iff　a^{\phi(n)}-1はnで割り切れる

証明は、フェルマーの小定理を少し書き換えるだけで示せます。

証明

定理2において、$n$と互いに素な$a$だけを調べる。

\displaylines{
a\cdot\{1,...,\phi(n)\}=\{a,...,a\cdot\phi(n)\}=\{q_1p+r_1,...,q_{\phi(n)}p+r_{\phi(n)}\} \\
0< r_i<p\hspace{3pt}\land\hspace{3pt}i\ne j \implies r_i\ne r_j \\
}

証明は定理2とほとんど同じだが、

\begin{align}
a(j-i)=(q_j-q_i)n
\end{align}

の部分においては、$a$と$n$が互いに素であるから等式が成り立たず、仮定が正しくない、という議論になる。

定理2が成り立つので同じ議論により定理3も成り立つ。

定理4について、

\begin{align}
(a-1)(a+1)&=mn
\end{align}

のとき、この等式が成り立つのは$a-1=n$または$a+1=n$だが、$a$の取り得る範囲は定理3より$1<a<n-1$なので、$a-1<n, \hspace{3pt}a+1<n$であり、この等式が成り立つことはない。したがって仮定が正しくなく、定理4も成り立つ。

定理4が成り立つので、ウィルソンの定理も$n$と互いに素な要素の積において、同様の証明で成り立つ。
すなわち、

\begin{align}
\prod_{i=1}^{\phi(n)}x_i=mn+(n-1)
\end{align}

が成り立つ。たとえば、$\phi(10)$のとき$x_i=\lbrace 1, 3, 7, 9\rbrace$。

したがって、式

\begin{align}
\prod_{i=1}^{\phi(n)}ax_i=a^{\phi(n)}\prod_{i=1}^{\phi(n)}x_i
\end{align}

を考えると、フェルマーの小定理と全く同様の証明方法で導ける。

任意のトーシェントの求め方

まず、どんな整数も素因数分解に落とし込めるので、任意の整数に対して$p^u\cdot q^v...$と書けます。
そのため、まず素数$p$のべき乗のトーシェント$\phi(p^u)$を計算してみます。
まず、$p^u$と互いに素になり得る数は最大で$p^u-1$個あります。
なぜなら$p^u$より小さい正の整数は$1～p^u-1$だからです。

$p$と互いに素でないものは$p$自身も含めた$p$の倍数$\lbrace p, 2p, ..., p^u-p\rbrace$であり、これらを引く必要があります。
したがって、

\begin{align}
\phi(p^u)&=(p^u-1)-|\lbrace p, 2p, ..., p^u-p\rbrace| \\
&=(p^u-1)-|\lbrace 1, 2, ..., p^{u-1}-1\rbrace| \\
&=(p^u-1)-(p^{u-1}-1) \\
&=p^u-p^{u-1} \\
&=p^u\biggl( 1-\frac{1}{p} \biggr)
\end{align}

となります。

$\phi(p^u\cdot q^v)$の場合も同様に$p$の倍数の個数と$q$の倍数の個数の両方を引きますが、このままでは$p\cdot q$の倍数が二重に引かれてしまうので、最後にもう一度足す必要があります。
すなわち、

\begin{align}
\phi(p^uq^v)&= (p^uq^v-1)-\biggl(\frac{p^uq^v}{p}-1 \biggr)-\biggl(\frac{p^uq^v}{q}-1 \biggr)+\biggl(\frac{p^uq^v}{pq}-1 \biggr)\\
&=p^uq^v-\frac{p^uq^v}{p}-\frac{p^uq^v}{q}+\frac{p^uq^v}{pq}\\
&=p^uq^v\biggl(1-\frac{1}{p}-\frac{1}{q}-\frac{1}{pq}\biggr)\\
&=p^uq^v\Biggl[\biggl(1-\frac{1}{p}\biggr)-\frac{1}{q}\biggl(1-\frac{1}{p}\biggr)\Biggr]\\
&=p^uq^v\biggl(1-\frac{1}{p}\biggr)\biggl(1-\frac{1}{p}\biggr)\\
&=p^u\biggl(1-\frac{1}{p}\biggr)q^v\biggl(1-\frac{1}{p}\biggr)\\
&=\phi(p^u)\phi(q^v)
\end{align}

となります。
つまり、以下の方程式が成り立ちます。

\phi(p_1q_2)=\phi(p_1)\phi(q_2)

たとえば、$\phi(10)$は

\phi(10)=\phi(5)\phi(2)=(5-1)\cdot(2-1)=4

と計算できます。
3つ以上の積の一般化についてはここでは紹介しませんが、この方程式の関係がRSA暗号の数学的根拠になっています。
すなわち、$\phi(p_1q_2)$から$\phi(p_1)\phi(q_2)$を計算するのはとても簡単ですが、$p_1q_2$に素因数分解できるという答えを知っていなければ、$\phi(p_1q_2)$を求めるのはとても大変です。

RSA暗号

まず、2つの十分に大きな素数$p_1, p_2$を用意し、$\phi(p_1q_2)=\phi(p_1)\phi(q_2)$を計算します。
次に、$\phi(p_1q_2)$と互いに素でランダムな数を公開鍵$pub$として配布します。
最後に、$\phi(p_1q_2)$を法としたときの$pub$の（乗法の）逆数を秘密鍵$prv$として保存します。
つまり、$pub×prv=k\phi(p_1q_2)+1$です。

RSA暗号では、平文$m$を$pub$乗して暗号化し、その暗号文を$prv$乗すると$\phi(p_1q_2)$を法として余りが平文$m$になります。
すなわち、

(m^{pub})^{prv}=v\phi(p_1q_2)+m=m\hspace{5pt}\text{mod}\hspace{5pt}\phi(p_1q_2)

です。

最後にこれを証明してみましょう。

証明

pub×prv=k\phi(p_1q_2)+1

であるので、

\begin{align}
(m^{pub})^{prv}&=m^{pub×prv}\\
&=m^{k\phi(p_1q_2)+1}\\
&=mm^{k\phi(p_1q_2)}\\
&=m(m^{\phi(p_1q_2)})^k
\end{align}

ここで、オイラーの定理を用いると$a^{\phi(n)}-1$は$n$で割り切れる、すなわち

a^{\phi(n)}=vn+1

となるので、

\begin{align}
(m^{pub})^{prv}&=m(m^{\phi(p_1q_2)})^k\\
&=m(vn+1)^k\\
\end{align}

と変形できる。
$(vn+1)^k$は、展開すると多くの$n$倍の項と、$1^k=1$が得られるので、

\begin{align}
(m^{pub})^{prv}&=m(wn+1)\\
&=mwn+m\\
&=zn+m\\
&=m\hspace{5pt}\text{mod}\hspace{5pt}n\\
&=m\hspace{5pt}\text{mod}\hspace{5pt}\phi(p_1q_2)
\end{align}

となるので命題を満たす。

改めて強調しておきたいのは、$\phi(p_1q_2)$が簡単に逆算できないことです。
秘密鍵がバレないことはもちろん重要ですが、$p_1q_2$の素因数分解が総当たりで予測できてしまえば公開鍵の逆数である秘密鍵は容易に計算できます。
たとえば手元で$851$を素因数分解してみてください。
$851$という3桁の数字でさえ、愚直に計算するには結構な時間がかかります。
したがって、$n=p_1q_2$に十分大きな素数の積を取ると、簡単に$p_1q_2$は求められなくなります。

参考文献

その数式、プログラムできますか？ Alexander A. Stepanov, Daniel E. Rose