RSA の鍵生成部分、より具体的には、p 素数と q 素数の選択を理解しようとしています。モジュラス n のターゲット ビット長が与えられた場合、p と q をどの範囲で生成する必要がありますか?
モジュラス n は、p と q の積です。ここで、p と q は両方とも素数です。p と q は互いに比較的近く、sqrt(n) 付近のどこかにあるはずだと読みました。たとえば、ターゲットのビット長が 32 ビット (非常に小さいと思います) の場合、p と q は最大 16 ビットのランダムな素数である必要がありますか?
明確にしていただきありがとうございます
ロブ
32ビットモジュラスの場合、質問は少しアカデミックです。製品を選択する主な目的はp、q製品を因数分解しにくくすることですが、よりも小さい数の素因数分解を見つけるの2^32は非常に簡単なので、サイズについて心配する必要はほとんどありません。pこのq場合。pとqが明確な素数である限り、数学は問題なく機能することに注意してください。
1024ビットのモジュラスなど、より現実的なものについては、はい、2つの512ビットの素数をランダムに選択するのが非常に安全ですp。qつまり、範囲内のすべての素数のセットから均一に選択pします。「強素数」の概念があります。これは、特定の可能性のある既知の攻撃を回避するように設計された素数です---たとえば、ポラードを使用した簡単な因数分解を防ぐために、大きな因子を持つように選択する必要がある推奨事項が表示されます。 p-1'アルゴリズム。ただし、これらの推奨事項は、大きな係数および最先端の因数分解アルゴリズム（GNFS、ECM ）には実際には適用されません。q[2^511, 2^512]pqp-1q-1）。理論的には簡単な因数分解を行うことができる他の可能性のあるケースがありますが、実際にはランダムな選択から現れる可能性は非常に低く、心配する価値はありませんp。q
要約：ビット長が等しい2つのランダムな素数を選択するだけで、完了です。
いくつかの追加のコメントと考慮すべき事項：
もちろん、2つの512ビット素数を選択すると、 1023ビットまたは1024ビットのモジュラスになります。それはおそらく心配する価値はありませんが、正確に1024ビットのモジュラスを取得することに本当に関心がある場合は、範囲を制限してさらに言うか、1023ビットのモジュラスを破棄して再試行することができます。pq[1.5 * 2^511, 2^512]
意図的に選択pしqて、それらが互いに近くなるようにしないでください。pとqが本当に互いに近い場合（たとえば、10^10離れていない場合など）、それらの積はフェルマーの素因法pqによって簡単に因数分解されます。しかし、ランダムな素数を選択していて、その範囲内にある場合、これは現実的な確率では起こりません。pq[2^511, 2^512]
素数をランダムに選択する場合、魅力的な戦略は、範囲内のランダムな（奇数の）整数を選択し[2^511, 2^512]、最初の素数が見つかるまでそれをインクリメントすることです。しかし、それはすべての素数の間で均一な選択を与えるわけではないことに注意してください。大きなギャップの後に発生する素数は、他の素数よりも発生する可能性が高くなります。より良い戦略は、ランダムな奇数を選び続け、最初の素数を維持することです（または、実際には素数であると確信できる非常に多くのランダムに選択された塩基に対する強力な確率的素数）。
素数を生成するために、非常に優れた乱数の暗号化ソースが手元にあることを確認してください。