RSA暗号の一般的な素数生成方法

質問

一般的なRSA暗号について質問です。
RSAでは鍵の生成に、大きな素数 p, q および (p-1)*(q-1)と互いに素となる素数eを使用します。
ただ、p, qの一般的に使用される桁数は1024bit（300桁超）であるため、素数の生成に非常に大きな時間がかかってしまいます。

e は3か65537を使用することで生成のための計算を省くことができますが…

RSAで暗号鍵を生成する際に300桁もの素数を毎回計算して生成するのは時間がかかりすぎるため現実的ではないと思いますが、実際にはどのようにして300桁の素数を生成しているのでしょうか。
もしくは、計算済みの素数リストや固定の値を使用しているのでしょうか。
（後者はあり得ないとは思いますが…）

宜しくお願いします。

回答No.1

hanabutako · ベストアンサー

詳しくはリンクしたページを見ていただきたいのですが、2種類の方法があります。
ひとつはランダムに値をとって、確率的に素数であることを判定する方法で、もう一つはすでにある素数からそれよりも大きな別の素数を作り出す方法です。どちらの場合も乱数によって値を選ぶところがあり、暗号に使うための乱数生成器で乱数を作り出せばRSAなどに十分使える素数が作れると思います。

ちなみに、前者でなぜできるかというと、素数定理によって、十分大きな桁数の場合、ランダムに値を取ると素数になる可能性が高いことが知られています。素数でないことを判定するアルゴリズムは既にいくつかあるので、それを何度も適用することで素数である可能性が十分高い数を見つけ、それを使えます。

計算済みの素数リストや固定の値というのはDiffie-Hellman key exchangeなど素数が公開情報であっても構わない場合には使えそうですが、素数を秘密情報としないといけない場合にはまず使えないと思います。計算済みの場合だとそれが他の人に何らかの方法で知られたら安全ではなくなりますが、それを誰かが計算して与えるとしたら、渡した人は秘密にすべき素数を知っていることになると思います。また、いくつかリストがあってそこから選ぶ場合でも、長いリストを渡すことは現実的ではないと思うので、やはり鍵が取りうるパターンが限定されていて、安全とはいえないでしょう。

http://www.ipa.go.jp/security/fy14/crypto/prime_num/invest.pdf