【超丁寧に】RSAに利用されている数式を数学ド素人に向けて分かりやすく解説します！

本記事は教養記事シリーズその２９です。その他の教養記事はコチラの目次をご覧ください。

RSAとは

RSAとは公開鍵暗号化方式を実現するための手法の１つです。RSAという名前は，開発メンバーであるリベスト氏，シャミア氏，エーデルマン氏の頭文字に由来しています。公開鍵暗号化方式に関しては，コチラの記事で丁寧に解説しています。RSA以外にも，暗号化方式ではいろいろな手法（アルゴリズム）が用いられてきました。

RSAの流れ

RSAの詳しい解説に入る前に，全体の流れを説明しておこうと思います。RSAでは「大きな数の素因数分解がとても難しい」という性質を利用して暗号化を行います。コチラの記事で例えているように，レシピ通りにカレーを作ることは簡単でも，出されたカレーから具材の種類と量を完璧に言い当てることは難しいです。それと同じで，大きな数を素因数分解するのは非常に難しいのです。

そして，素因数分解することで得られる情報は数学の定理に応用されます。「オイラーの定理」と呼ばれる有名な定理を利用することで，RSA暗号化のしくみは成り立っています。

利用する数学の定理

さて，ここから数式を利用していきます。身構える必要はありません！一緒に少しずつ着実に理解していけば大丈夫です。RSAでは，主に「オイラーの定理（→フェルマーの小定理）」「ユークリッドの互除法」「一次不定方程式の整数解の存在定理」が用いられます。順番に確認していきましょう。

これらの定理を利用して，RSAのしくみを探っていきたいと思います。

数学的な説明

ここからは，文字を利用して数学的な解説をしていこうと思います。数学が苦手な方も，１行ずつ追いつくようにすれば必ず理解できると思いますので，一緒に頑張っていきましょう。

まずは，文字を決めます。

このとき，平文と暗号文は以下のように表されます。

\begin{eqnarray}
B \equiv A^{l_b}\ ({\rm mod}\ m)\\
A \equiv B^{l_a}\ ({\rm mod}\ m)
\end{eqnarray}

その通りです。少し，今の状況を整理します。

というような具合です。そこで，以下では「知らない」となっている要素に関して，数学の定理を利用しながら求めていきたいと思います。まずは，式(5)に式(6)を代入します。そうすると，このようになります。

\begin{eqnarray}
B \equiv B^{l_{a}l_{b}}\ ({\rm mod}\ m)
\end{eqnarray}

今後，この式(7)が成立することを証明すれば，暗号化と復号が上手くいっている証明になります。そこで，式変形を進めていきたいと思います。両辺を$B$で割ると

\begin{eqnarray}
B^{l_{a}l_{b} – 1}\equiv1\ ({\rm mod}\ m)
\end{eqnarray}

その通りです。オイラーの定理と少し並べてみてみましょう。

オイラーの定理の要件は，$a$，$m$が正で互いに素であることでしたから，$B$が正，かつ$B$と$m$が互いに素であるという条件下で「$\varphi(m)=l_{a}l_{b} – 1$」となる$l_a$と$l_b$を作ることができるということを示せば，式(7)が成立していることを示すことができます。

さて，「$\varphi(m)=l_{a}l_{b} – 1$」を式変形してみましょう。

\begin{eqnarray}
l_{a}l_{b} – \varphi(m) = 1
\end{eqnarray}

その通りです。しかし，$\varphi(m)$に係数がかかっていないので定理を適用することができません。そこで，式(10)をいじってから式を変形していくことにします。$w (≠0)$を利用して，式(10)の両辺を$\frac{1}{w}$乗してみます。

\begin{eqnarray}
B^{\frac{l_{a}l_{b} – 1}{w}}\equiv1\ ({\rm mod}\ m)
\end{eqnarray}

この状態で，先ほどと同じような操作をすると，以下の等式が得られます。分かりやすいように，$-w$を$v$とおくことにします

\begin{eqnarray}
l_{a}l_{b} – \varphi(m)w = 1
\end{eqnarray}

\begin{eqnarray}
l_{a}l_{b} + \varphi(m)v = 1
\end{eqnarray}

見事，式(4)の形と一致しました。ここで，１つ問題があります。式(4)と見比べる時に，$l_a$と$l_b$のどちらを$u$とみなすかという問題です。これは，$l_a$と$l_b$の意味をよく考えれば分かります。公開するのは$l_b$の方です。ですので，式(14)の要件を満たす形で$l_b$を決めてから，式(14)に当てはめて$l_a$を求めて復号のための秘密鍵$s$とすればよいのです。

式(14)の要件というのは「$l_b$と$\varphi(m)$が互いに素」という条件でしたから，そのように$l_b$を定めればよいということになります。ちなみに，$l_a$に関しては「$l_a>0$」という要件が残っています。これに関して証明を加えておきます。つまり，式(14)を満たす$l_a(>0)$が存在することを示します。

式(14)を満たす整数$l_a$と$v$は定理より見つかりますから，適当に見つけたとします。それらを$l_{a_0}$，$v_0$と置きます。このとき，以下が成り立ちます。

\begin{eqnarray}
l_{b}l_{a_0} + \varphi(m)v_0 = 1
\end{eqnarray}

式(15)を整数nを利用して少しいじると

心配いりません。$\varphi(m)$は$m=pq$より小さい正の整数のうち，$m=pq$と互いに素な数の個数を表しているのでした。$p$と$q$は素数ですので，$m$より小さな$m-1$個の正数から，$p$の倍数と$q$の倍数の数を引けばよいです。

$m$よりも小さな$p$の倍数は，$p,2p,\ldots,(q-1)p$の$q-1$個です。同様に，$m$よりも小さな$q$の倍数は，$q,2q,\ldots,(p-1)p$の$p-1$個です。以上から，$\varphi(m)$を計算することができます。

\begin{align}
\varphi(m) &= (pq-1)-(q-1)-(p-1) \\
&= pq-p-q+1 \\
&= (p-1)(q-1)
\end{align}

ちなみに，RSA暗号の説明の中には，$p-1$と$q-1$の最小公倍数を用意するものもあります。これは，$\varphi(m)$と互いに素な整数$l_b$を探すという$\varphi(m)$本来の役割に着目したものです。$l_b$を探す場面に限定すれば，$p-1$と$q-1$の最小公倍数$L$を考えれば十分だからです。

\begin{eqnarray}
L = \rm{lcm}[p-1, q-1]
\end{eqnarray}

ただし，$\rm{lcm}[\alpha, \beta]$は$\alpha$と$\beta$の最小公倍数を表します。このとき，整数$k$を用いて$\varphi(m)$は以下のように表されます。

\begin{align}
\varphi(m) &= kL
\end{align}

式(14)に代入すると，以下が得られます。

\begin{align}
l_{a}l_{b} + kLv &= 1 \\
l_a l_b + Lv &= 1
\end{align}

ただし，$kv$を改めて$v$と置き直しました。以上の議論から，RSAの定式化において$\varphi(m)$の代わりに$L$を考えても破綻しないことが分かりました。逆に言えば，わざわざ最小公倍数を持ち込まなくてもRSAの定式化は可能ですが，一般に$p-1$と$q-1$の積を取ると桁数が大きくなってしまうため，計算を簡単にするという観点から$\varphi(m)$ではなく$L$が好んで利用されるようです。

いい指摘です。$l_a$の存在は示せましたが，それを実際に計算で求めることは可能なのかという疑問ですね。これについては，「係数が互いに素である一次不定方程式はユークリッド互除法を利用して解を求めることができる」という定理があります。そちらを利用すれば，ユークリッドの互除法を計算方法として利用して$l_a$を求めることができることが分かりました。

具体的には，式(14)「$l_{a}l_{b} + Lv = 1$」を満たす$l_a$を求めればよいのですが，$v$は途中で途中で勝手に定めた定数ですので，modを利用してvを無くします。すなわち，

\begin{eqnarray}
l_{a}l_{b} \equiv 1\ \rm{mod}\ L
\end{eqnarray}

を満たす形で$l_a$を決定すればよいことになります。これにて，RSA暗号化方式の証明が完了しました。

RSAの流れ再確認

実際に，簡単な素数を用いて公開鍵を暗号鍵を生成してみましょう。まず，自分で定めるのは$p$と$q$でした。ここでは，簡単に$p=17, q=19$としましょう。続いて，公開鍵の要素である$m$を求めます。$p$と$q$の積ですので，$323$と求められます。

続いて，$p-1$と$q-1$の最小公倍数である$L$を求めましょう。$L=\rm{lcm}[16, 18]=144$となります。

次に求めるのは，$l_b$です。$l_b$は$L$と互いに素であればOKですから，その中で一番小さな値を設定しましょう。つまり，$l_b=5$です。$l_b$が求まりましたので，$l_a$も求めることができます。$l_{a}l_{b} \equiv 1\ (\rm{mod}\ L)$を満たすように$l_a$を設定しましょう。

$l_b$と$L$を代入すれば，$l_{a}\cdot 5 \equiv 1\ (\rm{mod}\ 144)$となります。これを満たす$l_a$は，最も簡単な候補としては$144/5 + 1 \fallingdotseq 29$ となります。実際に，$l_a = 29$を$l_{a}\cdot 5 \equiv 1\ (\rm{mod}\ 144)$に代入してみると，$29 \cdot 5 = 145 \equiv 1\ (\rm{mod}\ 144)$となり，確かに成立していることが分かります。以上で，公開鍵と秘密鍵の生成は完了しました。

実際に確認してみる

以上の設定を用いて，平文$A=10$を暗号化し，復号してみましょう。暗号化の式から，

\begin{eqnarray}
B=10^{5}\;({\mathrm mod}\;323)=193
\end{eqnarray}

となります。また，復号化の式に従って計算を行うと，

\begin{eqnarray}
193^{29}\;({\mathrm mod}\;323)=10
\end{eqnarray}

となり，元の平文$10$が復号されることが確認できました．

ひとこと

非常にややこしい分野でした。多くの人が，「RSAは桁数の大きい素因数分解が大変であること」を利用していることは知っているかと思います。しかし，ここまで踏み込んで理解している人はごく少数だと思われます。個人的に美しいのが，暗号化にまでも「オイラーの定理」が応用されていることです。「数学が役に立つ例」として非常に分かりやすいのは今回のRSAではないでしょうか。