公開鍵暗号
皆さんは公開鍵暗号というのを知っていますか？ おそらく皆さんが想像するようなものはシーザー暗号やエニグマのようなものを想像すると思います。これらの暗号には鍵というものが存在し、その鍵が知られると暗号が解かれてしまいます。この鍵のうちの一部を知られてもいい情報として扱う暗号を公開鍵暗号と言います。今回はそのうちの一つ、RSA暗号に関して書こうと思います
オイラーの定理 （整数論）
フェルマーの小定理を一般化したものですね。証明方法はさほど変わりません。
自然数 $ a, n $ に対して $ a $ と $ n $ が互いに素であるとき、次の式が成り立つ
\begin{equation}
a ^ {\phi(n)} \equiv 1 ( \mod n )
\end{equation}
ただし、$ \phi ( n ) $ はオイラーの $ \phi $関数
（引用：http://mathmatik.jp/2016/02/12/euler_theorem1/)
この定理がかなり重要になって来ます。このオイラーの $ \phi $関数は $ n $を素因数分解しないと求められない仕組みになっています。どのような数になるかというと$ n $の素因数を $ p_1, p_2, ...... p_m $とするとき、
\phi ( n ) = n ( 1 - \frac{1}{p_1})(1 - \frac{1}{p_2}).......(1 - \frac{1}{p_n})
となります。証明を読めばわかりますが、これはちょうど$ n $以下の $ n $と違いに素な数の個数です
RSA暗号とは
適当に素数 $ p, q $を決めます。すると公開鍵のうちの一つ、 $ n = pq $が定まります。このとき、$ \phi ( n ) = pq(1 - \frac{1}{p}) (1 - \frac{1}{q}) = (p - 1) (q - 1) $となるので、平文（暗号化する前の数）を$ a $とすると
a ^ { \phi ( n ) + 1 } \equiv a ^ { \phi ( n ) } \times a \equiv 1 \times a \equiv a ( \mod n)
なので、
ed = \phi( n ) + 1
となるような二つの自然数 $ e, d $を選びます。そして$ d $を秘密鍵、$ e $を公開鍵にします
暗号化の方法は $ a $を平文、 $ b $を暗号文とすると
a ^ e \equiv b (\mod n)
復号は
b ^ d \equiv a (\mod n)
のようにします。