本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
RSA暗号の数学的なしくみ
- 鍵生成
-
- 相違なる大きな素数$p,q$を適当に選ぶ
- $n=pq$を計算する
- $p-1$と$q-1$の最小公倍数を$m$とおく
- $m$と互いに素となる$e$を適当に選ぶ
- $m$を法として$ed\equiv 1$となる$d$のうち小さいものを選ぶ
このうち，$(n,e)$を暗号化鍵とし，$d$を復号鍵とする。
$m$は$\varphi(n)$としてもよいのですが，計算効率性から最小公倍数$m$を選ぶ方が実践的です。
- 暗号化
-
平文$x$に対し，
\begin{align}
y\equiv x^{e}\pmod{n}\label{暗号化}
\end{align}となる$y$を求める。ただし，$0\leq y<n$とする。
簡単のため$x<n$の場合を考えます。$x\geq n$の場合は平文を分割します。
- 復号
-
平文$y$に対し，
\begin{align}
z\equiv y^{d}\pmod{n}\label{復号}
\end{align}となる$z$を求める。ただし，$0\leq z<n$とする。このとき，$x=z$となる。
RSA暗号は初等整数論の入門を学ぶために最適な題材です。発明者はMIT（マサチューセッツ工科大学）の学者であるRivest・Shamir・Adlemanの三名で，頭文字からRSA暗号と呼ばれています。
はじめに
暗号化鍵と復号鍵については「このように定めれば暗号化と復号が上手くいく」と天下り的に与えられるものと理解するのがよいでしょう。したがって，本稿では
- 暗号鍵$(n,e)$が存在すること
- 復号鍵$d$が存在すること
- 平文$x$を式($\ref{暗号化}$)により暗号化された$y$が，復号の手順(\ref{復号})により正しく復号されること
を証明します。
証明
暗号鍵$(n,e)$が存在すること
適当な素数$p,q$を選ぶことにより，$n{=}pq$は計算することができます。ユークリッドの互除法などにより$p{-}1$と$q{-}1$の最大公約数を求めることができれば，整数の積の最大公約数と最小公倍数による表現より$p{-}1$と$q{-}1$の最小公倍数$m$も求めることができるため，$m$も求めることができます。このとき，$m$の因数は既知であるため$m$と互いに素となる$e$も適当に選ぶことができます。
補足
$m$は$n$を素因数分解しないと得られませんが，一般に巨大な数の素因数分解は非常に困難であることが知られています。したがって，RSA暗号の安全性はこの$m$が第三者にとって計算不可能であることにより担保されているといえます。
私がRSA暗号の仕組みを理解する際に引っかかったポイントとして，なぜオイラー関数$\varphi(n)$を持ち出す必要があるのかという点が挙げられます。端的にこの疑問に答えると「復号時にフェルマーの小定理を適用するために$p{-}1$の倍数かつ$q{-}1$の倍数であればよいという要件であるため，別にオイラー関数$\varphi(n)$を持ち出す必然性はない」となります。オイラー関数の性質より，$p{-}1$と$q{-}1$の積がオイラー関数$\varphi(n)$と等しくなるからオイラー関数$\varphi(n)$がたまたま登場しているだけで，$p{-}1$と$q{-}1$の最小公倍数$m$でも要件を満たします。
$m$を$\varphi(n)$とする場合に$\varphi(n)$が計算できることはオイラー関数の計算方法により保証されます。
復号鍵$d$が存在すること
$m$と$e$が互いに素であることから，
ed &\equiv 1\pmod{m}\label{edの定義}
\end{align}
を満たす$d$は，一次合同式の解の公式を用いることにより具体的に与えられます。
手順(\ref{復号})により正しく復号されること
手順(\ref{復号})に従えば，
z\equiv y^{d} \equiv x^{ed}\pmod{n}
\end{align}
となります。そこで，
x^{ed}\equiv x\pmod{n}\label{復号証明の目標}
\end{align}
を示すことができれば，
z &\equiv x\pmod{n}
\end{align}
が示されます。さらに，$n{=}pq$であることから，$p$を法として$x^{ed}{\equiv}x$であること，および$q$を法として$x^{ed}{\equiv}x$であることを示すことができれば式($\ref{復号証明の目標}$)が示されることに注意します。式($\ref{edの定義}$)を利用すれば，$x^{ed}$は自然数$k,l$を用いて
x^{ed}
&= x^{km+1}
= x^{kl(p-1)+1}
= (x^{p-1})^{kl}\cdot x
\equiv 1\cdot x
\equiv x\pmod{p}
\end{align}
と表されます。ただし，$m$は$p{-}1$の倍数であることとフェルマーの小定理を利用しました。同様に，
x^{ed}
&\equiv x\pmod{q}
\end{align}
が得られます。したがって，$pq$を法として$x^{ed}{\equiv}x$となり，式($\ref{復号証明の目標}$)が示されました。
具体例
平文$x{=}37$を暗号化および復号しなさい。
相違なる素数として$p{=}3,q{=}13$を選びます。このとき，$n{=}3\cdot 13{=}39$，および
m &= \gcd(3-1,13-1) = 12
\end{align}
となります。$m$と互いに素となる$e$として$5$を選び，，
5d \equiv 1\pmod{12}\label{dを得るための合同式の例}
\end{align}
を満たす$d$を求めます。いま，オイラー関数の性質より
\varphi(12)
&= 12\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)
= 12\cdot\frac{1}{2}\cdot\frac{2}{3}
= 4
\end{align}
となることに注意すると，一次合同式の解の公式より，
d &= 5^{\varphi(12)-1}\cdot 1
= 5^{3} = 5^{2}\cdot 5 \equiv 1\cdot 5 \equiv 5\pmod{12}
\end{align}
が得られます。
今回の場合は$12$を法として$24d\equiv 0$となること，および式($\ref{dを得るための合同式の例}$)より$25d\equiv 5$となることを利用した方が早いでしょう。
そこで，小さい$d$として$5$を選びます。以上をまとめると，
- 暗号化鍵：$(n,e)=(39,5)$
- 復号鍵：$d=5$
となります。式($\ref{暗号化}$)に従えば，暗号文$y$は
y &= x^{e} = 37^{5} \equiv (-2)^{5} \equiv -32 \equiv 7\pmod{39}
\end{align}
となります。この暗号文を式($\ref{復号}$)に従って復号すると，
z &= y^{d} = 7^{5} = (7^{2})^{2}\cdot 7 \equiv 10^{2}\cdot 7 \equiv 10\cdot 70 \equiv 10\cdot (-8) \equiv -2 \equiv 37\pmod{39}
\end{align}
となり，平文$37$が得られました。
コメント