私は、Diffie-Hellman タイプのキー p に対して 2048 ビットの安全な素数を生成しています。この場合、p と (p-1)/2 は両方とも素数になります。
p と (p-1)/2 の両方で Rabin-Miller の反復回数をどれだけ少なくすれば、暗号的に強力なキーを確信できるでしょうか? 私が行った調査では、1024 ビットの通常の素数に対して 6 回から 64 回までさまざまな反復回数を聞いたことがあるため、この時点で少し混乱しています。そして、それが確立されると、通常の素数ではなく安全な素数を生成する場合、その数は変わりますか?
計算時間は貴重なので、これは実用的な質問です。基本的に、ほぼ保証されたセキュリティを維持しながら、実行できるテストの数をできるだけ少なくする方法を知りたいのです。
ベストアンサー1
素数を選択すると仮定しましょうpランダムな値を選択して、ミラー・ラビンが言うところの「素数に見える」値にたどり着くまで続ける。んミラー・ラビン テストでは最大 ラウンドです。(いわゆる「安全な素数」の場合、2 つのネストされたテストを実行すること以外は何も変わりません。)
ランダムな1024ビット整数が素数である確率は約1/900です。さて、あなたは愚かなことをしたくないので、奇数値（1024 ビットの偶数整数は非素数であることが保証されます）と、より一般的には、値が「明らかに」非素数でない、つまり小さな素数で割り切れない場合にのみ、ミラー ラビン テストを実行します。したがって、素数に当たるまでにミラー ラビンで約 300 個の値を試すことになります（平均）。値が非素数の場合、ミラー ラビンは各ラウンドで 3/4 の確率でそれを検出するため、1 つの非素数に対して平均して実行するミラー ラビン ラウンドの数は 1+(1/4)+(1/16)+... = 4/3 です。300 個の値の場合、これは、ミラー ラビンのラウンドを何にするかに関係なく、約 400 ラウンドになることを意味します。ん。
選択した場合ん例えば40であれば、んは、計算コスト全体の10%未満です。ランダム素数選択プロセスは、素数でないもののテストによって支配されており、これは、ん選択してください。ここでは1024ビットの整数について話しました。より大きな数値の場合は、ん素数はサイズが大きくなるにつれてまばらになるため、さらに重要ではなくなります (2048 ビットの整数の場合、上記の「10%」は「5%」になります)。
したがって、選択できるのは40人そして、それに満足してください（または少なくとも、んとにかく、それでは大した買い物はできません。一方、ん40 より大きい値は意味がありません。なぜなら、単純な計算ミスのリスクよりも低い確率になるからです。コンピュータはハードウェアであり、ランダムに故障することがあります。たとえば、素数テスト関数は、素数でない値に対して「真」を返すことがあります。これは、宇宙線 (高速で宇宙を駆け抜ける高エネルギー粒子) がたまたま適切なタイミングで適切なトランジスタに当たり、戻り値が 0 (「偽」) から 1 (「真」) に反転するためです。これは非常に起こりにくいことですが、確率よりも起こりやすいです。2 -80。 見るこのスタックオーバーフローの回答詳細は、こちらを参照してください。要するに、整数が素数であることをどのように確認しても、避けられない確率的要素が残り、ミラー・ラビン法を 40 ラウンド実行すれば、期待できる最高の結果が得られるということです。
合計すると、40 ラウンドを使用します。