Help us understand the problem. What is going on with this article?

RSA暗号の仕組み

More than 1 year has passed since last update.

 公開鍵暗号

皆さんは公開鍵暗号というのを知っていますか? おそらく皆さんが想像するようなものはシーザー暗号やエニグマのようなものを想像すると思います。これらの暗号には鍵というものが存在し、その鍵が知られると暗号が解かれてしまいます。この鍵のうちの一部を知られてもいい情報として扱う暗号を公開鍵暗号と言います。今回はそのうちの一つ、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)

のようにします。

stmtk
Complex System/Alife/fractal lang: C++/ Haskell/clojure/ ruby/ python/ nim /vim
https://stmtk.github.io
yyphp
PHPerが毎週集まり、ざっくばらんに情報交換する雑談コミュニティ
https://yyphp.connpass.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away