概要
RSA暗号は現在普及している公開鍵暗号の基礎となる暗号技術である。説明しているサイトは色々あるが、他人が書いたものなので読みにくかった。私にとって分かりやすいように書く。Wikipediaの同項目を参考にした。
証明中で用いたオイラーのφ関数とフェルマーの小定理については後半で解説した。
暗号化と復号
0以上n未満の整数の集合を
とおく。
異なる２つの素数 
をとり、
を定義する。
と互いに素であるような
（公開鍵）を任意に設定する。
このとき、秘密鍵
は
\begin{align} d \equiv e^{-1} \pmod n \end{align}
、すなわちのモジュラ逆数となるように作成される。のみから導くのは困難だが、が既知であれば、ユークリッドの互除法によって導出できる。
平文
について、暗号文
は、
\begin{align} b = \{ z \in \mathbb{Z}_n | z \equiv a^e \pmod n \} \end{align}
と算出できる。これを復号したものを
とすると、
\begin{align} a' = \{ z \in \mathbb{Z}_n | z \equiv b^d \pmod n \} \end{align}
とかけ、
である。
原理の証明
と
（オイラーのφ関数）は互いに素だから、任意の正の整数
について、
\begin{align} de -x\phi(n)= 1\end{align}
となるような正の整数
が存在する。
定義より
\begin{align} a' \equiv a^{de} \pmod n = a^{x\phi(n)+1} = (a^\phi(n))^x \cdot a \tag{1} \end{align}
である。したがって、
\begin{align} a' \equiv (a^\phi(n))^x \cdot a \pmod p \tag{2} \\\ a' \equiv (a^\phi(n))^x \cdot a \pmod q \tag{3} \end{align}
が成立する。
は
未満であることから、以下の( i )( ii )( iii )によって、すべての場合を扱える。以下では式(1),(2),(3)を用いる。
( i ) が
のそれぞれと互いに素であるとき
フェルマーの小定理より
\begin{align} a^{\phi(n)} \equiv 1 \pmod p \tag{3} \\\ a^\phi(n) \equiv 1 \pmod q \tag{4} \end{align}
が成立する。式(3),(4)より
\begin{align} a^{\phi(n)} \equiv 1 \pmod n \end{align}
であるから、
\begin{align} a' = (a^{\phi(n)})^x \cdot a \equiv a \pmod n \end{align}
が成立する。
( ii ) が
の倍数であるとき
\begin{align} a \equiv 0 \pmod p \end{align}
であるから、
\begin{align} a' = a^\phi(n) \cdot a \equiv a \pmod p \tag{5} \end{align}
である。
は
と互いに素だから、フェルマーの小定理より、
\begin{align} a^{q-1} \equiv 1 \pmod q \end{align}
が成立する。よって、
\begin{align} a^\phi(n) = a^{(p-1)(q-1)} \equiv 1 \pmod q \end{align}
であることから、
\begin{align} a' = (a^\phi(n))^x \cdot a \equiv a \pmod q \tag{6} \end{align}
となる。式(5),(6)より、
\begin{align} a' \equiv a \pmod n \end{align}
が成立する。
( iii ) がの倍数であるとき
( ii )と同様にして
\begin{align} (a^\phi(n))^x \cdot a \equiv a \pmod n \end{align}
が示される。
( i )( ii )( iii )より、すべての場合について
\begin{align} a' \equiv a \pmod n \end{align}
が成立する。
であるから、
である。
正の整数に対して、と互いに素である
以上以下の整数の個数
のことをこう呼ぶ。
したがって、が素数ならば
である。
異なる２つの素数 について 
を定義したとき、
\begin{align} \phi(n) = (p-1)(q-1) \end{align}
が成り立つ。
任意の素数 と、の倍数でない任意の整数 について、
\begin{align} a^p \equiv a \pmod p \end{align}
が成立する。
証明
任意の素数 と任意の正の整数 
をおく。二項定理より、
\begin{align} (m+1)^p=m^p+{}_p\mathrm{C}_1 m^{p-1} + {}_p\mathrm{C}_2 m^{p-2} + \cdots + {}_p\mathrm{C}_{p-1} m + 1 \tag{★} \end{align}
が成り立つ。
が素数であるため、未満の正の整数
について
がの倍数となることから、
\begin{align} (m+1)^p \equiv m^p+1 \pmod p \end{align}
が成立する。
( i ) 式(★)に 
を代入すると、
\begin{align} 2^p \equiv 2 \pmod p \end{align}
となり、
において命題は成り立つ。
( ii ) 命題が 
において成立すると仮定する。
このとき、式(★)から、
\begin{align} (k+1)^p \equiv k^p+1 \pmod p \end{align}
であり、仮定より、
\begin{align} k^p \equiv k \pmod p \end{align}
であることを踏まえると、
\begin{align} (k+1)^p \equiv k+1 \pmod p \end{align}
となり、
においても命題が成立する。
( i )と( ii )より、題意は示された。
まとめ
楽しかった。せっかく原理を学んだので、RSAで平文を暗号化するツールを作りたい。
