RSA暗号のしくみ
はじめに
Bloggerでの投稿練習にRSA暗号の仕組みを紹介してみたいと思います。
仕組み自体は簡単なのでググったら沢山でてきますが、実際は多くの攻撃があり素人が簡単に実装をできるものではありません。それに読み物としての記事が多くて素数の生成 はどうやるのか～など具体的に書いてなくて困ると思います。
その辺もどんな感じのアイデアを使ってるのか面白く書いてみたいと思いますので是非読んでみてください(^^)/
仕組み
まず、大きな素数（最近は2048bit）\(p, q\)を作り、\(N = pq\)とします。次に、\(\varphi(N)\)と互いに素な数\(e\)を作ります。\(ed \equiv 1 \pmod{\varphi(N)}\)となるように\(d\)を決めて\((e, N)\)を公開鍵、\((d, N)\)を秘密鍵とします。ここで\(\varphi\)はオイラーの\(\varphi\)関数で\(\varphi(N) = (p - 1)(q - 1)\)となります。
modの意味
\(a \bmod{b}\)は\(a\)を\(b\)で割った余りという意味です。\(a \equiv b \pmod{N}\)は\(a\)を\(N\)で割った余りと\(b\)を\(N\)で割った余りが等しいという意味で、これは\(a - b = kN\)となる\(k\)があることと同じ意味です。
\(ed \equiv 1 \pmod{\varphi(N)}\)なら\(ed - k\varphi(N) = 1\)となるので、ユークリッド互除法で\(e\)から\(d\)を求めることができます。
オイラーの\(\varphi\)関数
\(\varphi(N) = \mbox{1からNまでで互いに素な数の個数}\)のことです。例えば\(\varphi(8) = 4\)、\(\varphi(13) = 12\)となります。
\(p, q\)を素数とすると、\(\varphi(pq) = (p - 1)(q - 1)\)となります。
また、\(a^{\varphi(n)} \equiv 1 \pmod{n}\)が証明できます。
さて、\(M\)をメッセージとすると暗号文\(C\)は以下のように計算されます。
\[C = M^e \bmod N\]
また、元に戻す復号は以下のようになります。
\[M = C^d \bmod N\]
どうしてこれで復号できるかは以下の計算で簡単に分かります。
\begin{equation*}
\begin{split}
C^d \equiv (M^e)^d &\equiv M^{ed} \\
&\equiv M^{1 + k\varphi(N)} \mbox{\(\quad [ed = 1+k\varphi(N)\)となる\(k\)があるから]} \\
&\equiv M(M^{\varphi(N)})^k \\
&\equiv M \pmod{N} \mbox{$\quad [M^{\varphi(N)} \equiv 1$だから]}
\end{split}
\end{equation*}
暗号のアイデアはたったこれだけです！（破られないように使うにはOAEPのようなパディングが必要です）
しかし、巨大な素数\(p, q\)はどうやって作るのか？などまだ疑問があると思います。2048bitとなると天文学的数字なんかよりもはるかに大きな数です(笑)
素数生成
素数生成は処理の中でも時間がかかり厄介な部分です。実際にどうやっているか簡単な紹介だけしたいと思います。
素数の生成にはミラーラビン法という確率的な判定方法を使います。これは１回素数だと判定すると素数でない確率は\(1/4\)以下です。50回もやれば\(1/2^{100}\)以下なので素数と思っていいわけです。2048bitの乱数を生成して素数かどうか判定して素数であればそれを使います。また何回くらい乱数を生成すればいいかというのは素数定理を使えば分かります。2048bitの数が素数である確率は\(1/log(2^{2048}) \approx 1/1420\)くらいと評価できます。
素数定理
\(\pi(x)\)を\(x\)未満の素数の個数とすると、 \[\lim_{x \to \infty}\frac{\pi(x)}{\frac{x}{log(x)}} = 1\] というのが素数定理です。攻撃
素数生成時の乱数
数字が大きいほど素数は少なくなりますから、乱数もきちんと考えなければ生成される素数が限られてしまいます。それによって素数が予測されてしまわないようにしなければなりません。c言語などに最初からついてるrand関数なんかは使えません。
Wienerの連分数攻撃
\(d<\frac{1}{3}N^{1/4}\)になってしまうとWiener's attackで\(d\)が分かってしまうので注意が必要です。
他にもパディングに対する攻撃などここに書ききれないくらい沢山の攻撃があるので実際に使う場合は暗号のプロの方に任せた方がいいでしょう。
まとめ
RSA暗号は簡単な数学しか使わないので原理はすぐに理解できてしまいますが、暗号に詳しくないと自作したものを使うのは危険であることが分かると思います。
はじめての投稿で色々な書き方を覚えることができていい練習になりました。
htmlなど慣れていないので、おかしな部分などあれば教えていただきたいですm(_ _)m
コメント
コメントを投稿