2009年12月04日

RSA暗号とは@〜素数判定の処理〜

【郵便会社:顧客12万人分の情報紛失 近畿支社】
http://mainichi.jp/select/jiken/news/20091204k0000m040082000c.html

支社は「個人情報は暗号化されており、外部漏えいの可能性は低い」としている。
って事で、よくこういう釈明で使われる「可能性は低い」ってどういうことでしょうかね?(笑)

という事で、大抵この手の「暗号化」ってのは「RSA暗号」が使われているのだけど、今日はこの「RSA暗号」の話をします。
「RSA暗号」は現在、世の中で最も広く使われている暗号方式なんだ。ただ、厳密に言うと「RSA暗号」は、暗号を解く事は可能なのだけど、それが数十年とか数百年かかるために、本来俺達がイメージする「原理的に解けない暗号」とは少し異なるかもしれない。後日にこの「RSA暗号」の原理を説明しようと思うのだけど、これも非常に数学の知識が必要な話なので、とりあえず「RSA暗号を解くのに何故そんなに時間がかかるのか?」というポイントを今日は説明します。


とりあえず、例としてこんな問題を考えてみよう。
「12345678909876543210123456789098765432101」は素数か否か?
「そんなもん、スパコン使えばすぐに解けるんじゃない?」と思う方も多いでしょう。ところが、実はスパコンでさえ、この手の素数判定には相応の時間がかかるわけですよ。何故かと言うと、全ての素数を表す一般式が発見されていないので、素数かどうか判定しようとすると、「2で割り切れるか」「3で割り切れるか」「5で割り切れるか」……というように、与えられた数に対して、小さい素数から順々に割り切れるかどうかを、しらみつぶしで探すしかないわけですよ。そして、割り切れる素数が無ければ、その数は素数と認められるわけですが、上記の問題ではどれだけの素数があるかを考えるだけでも嫌になるような数ですねぇ……。

とりあえず、もう少し小さい数で考えて見ましょう。「91」が素数かどうかを考えてみます。

91pn_1st.jpg
まずは、↑のように91までの数で、2の倍数を消していきます。この結果、91は赤く塗りつぶされるわけではないので、2の倍数で無い事がわかります。

91pn_2nd.jpg
次に、↑のように2の次で消されていない数字は3なので、3の倍数を消していきます。この結果、91は3の倍数で無い事がわかります。

91pn_3rd.jpg
次に、↑のように3の次で消されていない数字は5なので、5の倍数を消していきます。この結果、91は5の倍数で無い事がわかります。

91pn_4th.jpg
次に、↑のように5の次で消されていない数字は7なので、7の倍数を消していきます。この結果、91は7の倍数で無い事がわかります。

91pn_5th.jpg
次に、↑のように7の次で消されていない数字は11なので、11の倍数を消していきます。この結果、91は11の倍数で無い事がわかります。(というか、すでに11の倍数で残っているのは11しかないので、非常に無生産な作業っぽいですが)

91pn_6th.jpg
次に、↑のように11の次で消されていない数字は13なので、13の倍数を消していきます。この結果、91が塗りつぶされる(13の倍数)事がわかるので、「91は素数ではない」事が判明しました。


という感じで、今は91という小さい数字で、しかも素数で無い事が判明する例なので大した作業量でもありません。ところが、大きな数字で素数だった場合は、この作業を全てのマスが塗りつぶされるまで延々と続けていくことになります。小さい数字の場合、コンピュータを使えば短時間でこの作業は終わるのですが、非常に大きい数になると計算量が指数的に増えるので、現実的な時間で解くことが難しくなるという事です。

RSA暗号は、素数判定における上記の性質(非常に大きな数字に対する素数判定(素因数分解)に時間が非常にかかる性質)を利用した暗号方式であるので、「現実的な時間では暗号を解けない」という事になります。


実際のRSA暗号の原理ですが、「公開鍵」と「秘密鍵」という二つの数字が暗号を解くために必要な数字になります。また、「フェルマーの最終定理」で有名なフェルマーが、このRSA暗号に深く関係してるのですが、RSA暗号の仕組みと背景にある数学原理は、次の回以降で説明することにしましょう。



今日のエントリーで、「なるほど」「ふむふむ」「面白い」などと思ってくれた方で、一票を頂ける方は是非ともお願いします。↓
人気ブログランキングへ
posted by きらっち at 00:00| Comment(7) | TrackBack(0) | 科学
この記事へのコメント
RSA暗号を解くという意味を明確にしたほうが良いのでは。
二つの鍵を特定することでしょうか。これは、できそうもないですね。
それとも、そうではなくて、暗号文から何らかの意味のある文章を導くことでしょうか。この場合、得られた結果が正しいことをどうやって判定するのでしょうか。

素数判定法はいろいろありますよね。(勿論、万能ではないが)
飽く迄、一般の人向けとして、それには触れなかったのでしょうか。
Posted by オドマンテス at 2009年12月05日 02:01
>オドマンテスさん
ご無沙汰です。数学関係以外の人向けということで、おおざっぱ過ぎる書き方で申し訳ない。
次回以降に「素因数分解をして秘密鍵を導出するのは、非常に時間がかかる」という事につなげようと思って、素数判定について説明したわけなんです。
書き方が悪くて申し訳ありませんでした。(謝)
Posted by きらっち at 2009年12月09日 21:24

はじめまして、経済は社会科学分野(と呼べるのかは措くとして)における自分の最大の弱点と認識している者です。
ふむふむナルホドと理解に努めつつ、いつも記事を読ませて頂いております。

一点だけ、非常に下らない指摘で恐縮ですが、91は13で割り切れる前に7で割り切れます!
素因数分解による素数の特定がえらく時間を喰う、というご趣旨については何ら疑義はございません。

本当に下らなくてすいません。
Posted by aki at 2009年12月23日 01:31
>akiさん
経済に関しては自分の専門ではなく、あくまで私も勉強中の身なのですが、何かの参考になったのなら幸いです。
91に関しては、確かに7で割り切れますね。これは単純な私のミスでした。97なら素数かな?後日に修正しますよ。
どうも指摘の方、ありがとうございます。
Posted by きらっち at 2009年12月23日 11:48
素数を表す一般式というものがあるそうです。
次式です。

p(n)=1+Σ[m=1〜2^n][[n/Σ[j=1〜m]F(j)]^(1/n)]
ただし F(j)=[{cos(π((j-1)!+1)/j)}^2]
Σの変数の範囲を示す[ ]以外の[ ]はガウス記号です。

ここで、ガウス記号とは、Aを実数とするとき
n<=A<n+1を満たす自然数nのことです。

(情報提供:らすかるさん)
Posted by CEGIPO at 2010年07月19日 16:38
補足

a^bはaのb乗の意味。
納k=c〜d](f(k))は
kがcからdまでの全ての自然数値をとるように
f(k)の和をとる、という意味です。
Posted by CEGIPO at 2010年07月19日 16:41
参考リンクとして掲載させて頂きました!

http://kanasys.com/tech/118
Posted by フィロ at 2013年12月22日 23:29
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/33996827

この記事へのトラックバック