- ベストアンサー
※ ChatGPTを利用し、要約された質問です（原文：RSA暗号の一般的な素数生成方法）
RSA暗号の一般的な素数生成方法
このQ&Aのポイント
- RSA暗号における素数生成方法について紹介します。
- RSAでは鍵の生成に、大きな素数 p, q および (p-1)*(q-1)と互いに素となる素数eを使用します。
- 生成には時間がかかるため、一般的にはどのようにして300桁の素数を生成するか疑問に思う方も多いです。
- perifla
- お礼率7% (2/27)
- その他([技術者向] コンピューター)
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
詳しくはリンクしたページを見ていただきたいのですが、2種類の方法があります。 ひとつはランダムに値をとって、確率的に素数であることを判定する方法で、もう一つはすでにある素数からそれよりも大きな別の素数を作り出す方法です。どちらの場合も乱数によって値を選ぶところがあり、暗号に使うための乱数生成器で乱数を作り出せばRSAなどに十分使える素数が作れると思います。 ちなみに、前者でなぜできるかというと、素数定理によって、十分大きな桁数の場合、ランダムに値を取ると素数になる可能性が高いことが知られています。素数でないことを判定するアルゴリズムは既にいくつかあるので、それを何度も適用することで素数である可能性が十分高い数を見つけ、それを使えます。 計算済みの素数リストや固定の値というのはDiffie-Hellman key exchangeなど素数が公開情報であっても構わない場合には使えそうですが、素数を秘密情報としないといけない場合にはまず使えないと思います。計算済みの場合だとそれが他の人に何らかの方法で知られたら安全ではなくなりますが、それを誰かが計算して与えるとしたら、渡した人は秘密にすべき素数を知っていることになると思います。また、いくつかリストがあってそこから選ぶ場合でも、長いリストを渡すことは現実的ではないと思うので、やはり鍵が取りうるパターンが限定されていて、安全とはいえないでしょう。 http://www.ipa.go.jp/security/fy14/crypto/prime_num/invest.pdf
