素数生成

| コメント(0) | トラックバック(0)

典型的な公開鍵暗号方式である、RSA暗号方式では、例えば200桁程度の大きい素数が必要になる。その2つの大きい素数をp,qとすると、pqという積を用いて公開鍵が生成され、(p-1)(q-1)という積を用いて、秘密鍵が生成される。

すなわち、RSA暗号方式の安全性が、大きい整数の素因数分解の困難さに依存している、というのはよく知られているところである。

それでは、私が公開鍵暗号方式を用いたシステムにユーザ登録するとする。すると、システムは、あるアルゴリズムに従い、2つの大きい素数p,qを生成し、そこからさらに、上記のように、公開鍵と秘密鍵を生成して、私に渡すことになる。

そこで素朴な疑問は、私専用の2つの大きい素数p,qを、システムはどうやって生成するのか、ということである。そこはおそらく企業秘密らしく、公開鍵暗号方式で、どうやって2つの大きい素数p,qを生成するのかきちんと書かれた文献を私は見たことがない。単に私が不勉強で知らないだけかもしれないが。

では、私が勝手に、公開鍵暗号方式用にコンピュータで大きい素数を生成する方法を考えてみる。すると一番ナイーブな方法はまず、とりあえず200桁程度の整数をランダムに生成して、それが素数かどうかを判定する方法である。ところが、素数定理によれば、ランダムに生成された200桁程度の整数が素数である確率は、600分の1程度である。さらに難しいのは、200桁程度の整数が素数かどうかを判定する方法の計算量である。

ものの本によれば、素数判定法には、ソロベイ・シュトラッセン法とか、ミラー・ラビン法などがある。ミラー・ラビン法によれば、与えられた判定すべき整数nに対して、それと素な任意の数aを選んで、あるアルゴリズムを適用すると、nは合成数/nは素数のどちらかの判定が得られる。このとき、「nは合成数」の方の結論はそのまま正しいと言えるが、「nは素数」の方の判定は、3/4の確率でしか正しくないという。すると、異なるaをm個か選んで、すべてが「nは素数」の判定であることをもって、1-(1/4)mの確率で、nが本当に素数である、ということになる。

この方法で、素数であるだろうとp,qを選んで、実はp,qのどちらか一方または両方が実は合成数だったら、RSA暗号方式は暗号化または複号化が破綻するのだろうか。そのあたりも不勉強で、さっぱり分からない。ただ、ディリクレのL関数に対する拡張リーマン予想が正しければ、aの選び方が限定できて、それによって、ミラー・ラビン法が多項式時間で、nの素数判定ができるのだそうである。

そんなややこしいことを仮定しなくても、多項式時間で素数判定できるアルゴリズムを、2002年8月に、インド工科大学のアグラワル他が考え出したそうである。しかし、計算機に乗せるのはあまり実用的でないようで、依然として実用上は、ミラー・ラビン法等が使われるそうである。

さて、戻って、オンデマンドで公開鍵暗号方式を生成するために、一々、その都度200桁程度の整数で乱数で生成し、ミラー・ラビン法等で素数判定する、という方法で試行錯誤で素数を2個得ているのだろうか。それはそれで、相当に計算が大変そうである。

するともしかして、次のような方法だろうかと、考えてみたのは、エラトステネスの篩を使う方法である。すなわち、相当に計算時間がかかってもよいので、バッチで、200桁程度の素数を100万個程度、エラトステネスの篩の方法で作成しておく。そうやって生成した100万個の素数を保持しておけば、オンデマンドでのキー作成の要求に対して、100万個の素数をランダムに重ならないように2個選んで返す。この方法なら、瞬時にキーが生成できるし、100万×100万で、1兆とおりの組合わせがあるので、とりあえず数に困ることはない。すると、この方法が使われているのか。と書いてみて、1億程度の数にエラトステネスの篩を適用する乗りで200桁の数にそのような篩を適用することを気軽に考えていたことに気付いた。少し考えたら分かるが、エラトステネスの篩の計算量は、O(n1/2)である。すると、200桁の数にエラトステネスの篩を適用することはほとんど無理であることが分かる。それで結局、ミラー・ラビン法等に戻る。

以上、その道のプロに笑われそうな素人の考えであった。

トラックバック(0)

トラックバックURL: http://commutative.world.coocan.jp/mt/mt-tb.cgi/1510

コメントする

このブログ記事について

このページは、あやたろうが2009年10月18日 08:56に書いたブログ記事です。

ひとつ前のブログ記事は「Winnyの判決要旨」です。

次のブログ記事は「思考停止命題」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。