2017年4月
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30            
無料ブログはココログ

« FC 2010: Accepted Papers | トップページ | 祝20万ヒット »

リーマン予想とRSA暗号の安全性

NHKスペシャル『魔性の難問~リーマン予想・天才たちの闘い~』に関連し、何人かの知人からリーマン予想とRSA暗号の安全性について質問を受けました。せっかくの機会なので、リーマン予想とRSA暗号の安全性について少しまとめておきたいと思います。

理由は以下に書いていきますが、結論としては
    「リーマン予想が証明されても、RSA暗号の安全性には影響がない」
ということになると思います。

まず、リーマン予想が証明されても、個々の素数が簡単に求められるようにはなりません。例え、(どうやってかは知りませんが)個々の素数が簡単に求められるようになったとしても、RSA暗号の秘密鍵として使用されている特定の素数を見つけ出すのはメモリ的にも時間的にも不可能です。

この感覚を実感するために、数値例で考えてみます。例えば鍵長 1024 ビットのRSA暗号を使用する場合、512 ビットの素数を2個使用します。「素数定理」(これはリーマン予想とは無関係に証明される定理です)によると、1 から X までに含まれる素数の個数は、およそ pi(X) = X/log_e(X) 個に近似できます(特に、X が大きければ大きいほどこの近似は良くなります)。この「素数定理」によると、512 ビットの素数の個数は
    pi(2^512-1) - pi(2^511-1) = 1.88 * 10^151 (個)
であることがわかります。512 ビットの素数の全てを書き出した場合、必要なメモリ量は
    1.88*10^151 * 512 = 9.65 * 10^153 (bit)
                      = 1.10 * 10^141 (TetaByte)
となり、とてもではないですが、保存不可能なデータ量です。

また、(どうやってかは知りませんが) 512 ビットの全ての素数を書き出せたとしましょう。1 個の素数による割り算が 1 クロックで実行できると仮定すると(素数による割り算は実際には何十クロックも必要になります)、周波数 4 GHz の PC は1秒間に
    4 * 10^9
回の割り算が処理できることになり、512ビットの素数全てで割り算するには
    1.88 * 10^151 / (4*10^9) = 4.71 * 10^141 (秒)
                             = 8.97 * 10^135 (年)
がかかります。これは 1 台の PC でしか考えていませんが、
仮に 10^80 台のPCが使用可能(宇宙に存在する原子の個数)としても
    8.97 * 10^135 / (10^80) = 8.97 * 10^55 (年)
を必要とし、地球の年齢 4.6 * 10^9 年よりはるかに大きな値となります。

このように、候補となる素数をチェックしていくアプローチでは、残念ながらRSA暗号を解読することはできません。

となると、リーマン予想が証明された場合に、RSA暗号の他の解読方法がありえるか、という話になるわけですが、現状ではこちらも期待薄でしょう。そもそもリーマン予想とは「ゼータ関数のゼロ点は一直線上にならぶ」というもので、命題の内容は既にわかっており、リーマン予想が正しいと仮定したときのRSA暗号の解読方法は考えることができるのです。しかし現実的に解読方法は知られていませんので、リーマン予想が証明されても、状況はあまり変わらないと考えられます。

えっと、こみいってきているのですが、私が本稿で書きたいのは

リーマン予想が証明されても、RSA暗号が解読できるようになるとは思えない

ということです。RSA暗号が絶対に解読できないとは思いませんが、リーマン予想の証明と結びつけるのは、現時点では証拠がなさすぎる、ということです。もちろん、リーマン予想が証明される際に新しい理論が進展し、その新しい理論によってリーマン予想もRSA暗号も解かれる、ことがあり得ると思います(それってどんな理論なんでしょうねぇ。ワクワク)。そうだとしても、現時点でRSA暗号が解読される道筋は知られていないと思います。

最後に補足情報を。MarrigeTheorem さんに教えていただいたのですが、数学セミナー2009年11月号に首都大の内山さんが『リーマン予想と暗号』という記事を書かれています。曰く

リーマン予想が解決されればRSA暗号が効率的に解読される,などといった話は筆者は聞いたことはなく

ということですので、私の雑文の内容はともかく、結論に納得してもらえるのではないかと思います ^^;

【関連ブログ記事】

« FC 2010: Accepted Papers | トップページ | 祝20万ヒット »

RSA暗号」カテゴリの記事

コメント

「(番組で)リーマン予想が証明されると、RSA暗号が解読できるようになる、と述べられている」とありますが、そのようなことが番組で述べられていましたでしょうか?
「素数の謎がすべて明らかになり巨大な素数のリストが広く知られるようになれば、現代社会の通信の安全性(RSA暗号のことでしょう)は大きく揺らぐのです」と述べられているのみで、リーマン予想の系として RSA の解読法があるという説明はどこにもなかったのではないかと思います。「素数の謎がすべて明らかになる」というすさまじい仮定をしているから番組の主張は正しいのではないでしょうか。
(見落としがあったらすみません。)

Nyoho さま、ご指摘ありがとうございました。確かに私の筆が(指が)すべってしまい、知人から受けたコメントと、番組の内容がごっちゃになっておりました。番組は本記事の発端でしかないため、文章全体に手をいれさせていただきました。

「物理と数学のかきしっぽ」

っていう本でリーマン予想

を解きました

全ての素数の謎を明らかにしたかもしれない

と思います

The Answer of the Axiom Equivalent to Riemann Hypothesis

っていう名前の

論文として

フローの論文誌に載せました

中身が大きく変わったものとなっています

見てみてくださると嬉しい

論文を修正しました

こんどこそ正解!!と思いながら

19回目の変更後のものです

http://taibuturi.fuma-kotaro.com/

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/177150/46815665

この記事へのトラックバック一覧です: リーマン予想とRSA暗号の安全性:

» リーマン予想と暗号化・・・なんて話はしません: 鍵がテーマ [学問・芸術が大好き]
リーマン予想の本を読んだことは,2回ほど,2編に分けてブログに書きました.これとこれです. [続きを読む]

« FC 2010: Accepted Papers | トップページ | 祝20万ヒット »

リンク