リーマン予想とＲＳＡ暗号の安全性

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

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

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

この感覚を実感するために、数値例で考えてみます。例えば鍵長 1024 ビットのＲＳＡ暗号を使用する場合、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 は１秒間に
    4 * 10^9
回の割り算が処理できることになり、512ビットの素数全てで割り算するには
    1.88 * 10^151 / (4*10^9) = 4.71 * 10^141 (秒)
                             = 8.97 * 10^135 (年)
がかかります。これは 1 台の PC でしか考えていませんが、
仮に 10^80 台のＰＣが使用可能（宇宙に存在する原子の個数）としても
    8.97 * 10^135 / (10^80) = 8.97 * 10^55 (年)
を必要とし、地球の年齢 4.6 * 10^9 年よりはるかに大きな値となります。

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

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

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

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

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

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

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

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

【関連ブログ記事】

• 2009年11月19日(木) NHKスペシャル: 『魔性の難問～リーマン予想・天才たちの闘い～』の再放送
• 2009年11月17日(火) NHKスペシャル『魔力の難問～リーマン予想・天才たちの闘い～』 を見ました
• 2009年11月10日(火) NHKスペシャル: 『素数の魔力に囚われた人々』