暗号化された安全な素数にRabin-Millerを何回使用する必要がありますか?

cryptography primes
暗号化された安全な素数にRabin-Millerを何回使用する必要がありますか?

pと(p-1)/ 2が両方とも素数であるような、Diffie-Hellman型キーpに対して2048ビットの安全な素数を生成しています。

pと(p-1)/ 2の両方でRabin-Millerの反復を何回使用しても、暗号的に強力なキーに自信があるのですか? 私が行った研究では、1024ビットの通常の素数に対して6〜64回の繰り返しをすべて聞いたので、この時点では少し混乱しています。 そして、それが確立されたら、通常のプライムではなく安全なプライムを生成している場合、数値は変わりますか?

計算時間は非常に重要なので、これは実際的な質問です。基本的に、保証されたセキュリティを維持しながら、できるだけ少ないテスト数を見つける方法を知りたいと思っています。

  16  10


ベストアンサー

Miller-Rabinが言うように、ランダムな値を選択することで素数_p_を選択すると仮定しましょう。 Miller-Rabinテストでは、最大で_n_ラウンドを使用します。 (いわゆる「セーフプライム」の場合、2つのネストされたテストを実行することを除いて、物事は変更されません。)

ランダムな1024ビット整数が素数である確率は約1/900です。 今、あなたは愚かなことをしたくないので、_odd_値のみを生成します(1024ビット整数でも非プライムが保証されます)、そしてより一般的には、値が「明らかに」でない場合にのみMiller-Rabinテストを実行します「非素数、つまり 小さな素数で割ることができます。 したがって、素数(平均)に到達する前にMiller-Rabinで約300個の値を試すことになります。 値が非素数の場合、Miller-Rabinは各ラウンドで確率3/4でそれを検出するため、単一の非素数の値に対して平均して実行するMiller-Rabinラウンドの数は1+(1/4 )(1/16) …​ = 4/3. 300の値の場合、これは、_n_の選択内容に関係なく、約400ラウンドのミラーラビンを意味します。

したがって、たとえば、_n_を40に選択すると、_n_が意味するコストは、計算コスト全体の10%未満になります。 ランダム素数選択プロセスは、選択した_n_の値の影響を受けない非素数のテストによって支配されます。 ここでは、1024ビット整数について説明しました。大きな数の場合、サイズが大きくなると素数がまばらになるため、_n_の選択はさらに重要ではありません(2048ビット整数の場合、上記の「10%」は「5%」になります)。

したがって、_n = 40_を選択し、それに満足することができます(または、少なくとも_n_を削減しても、あまり買われないことを知ってください)。 一方、40より大きい_n_を使用しても意味がありません。これは、単純な誤算のリスクよりも低い確率になるからです。 コンピューターはハードウェアであり、ランダムな障害が発生する可能性があります。 たとえば、宇宙線(高速で宇宙を駆け抜ける高エネルギー粒子)がたまたま適切なトランジスタに適切なタイミングで衝突するため、素数テスト関数は非素数値に対して「true」を返す可能性があります。 0( “false”)〜1( “true”)の戻り値。 これはめったにありませんが、確率_2 ^ -80 ^ _に劣らない可能性があります。 詳細については、https://stackoverflow.com/questions/4159333/rsa-and-prime-generator-algorithms/4160517#4160517 [this stackoverflow answer]をご覧ください。 一番下の行は、整数が素数であることを確認する方法に関係なく、避けられない確率論的要素があり、Miller-Rabinの40ラウンドは既にあなたに期待できる最高のものを与えているということです。

要約すると、40ラウンドを使用します。

26


Damgard-Landrock-Pomeranceによる論文http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf[強力なプライムテストの平均ケースエラー推定値]では、ランダムに k `-bit奇数 n`で、連続して t`の独立したRabin-Millerテストを適用すると、 n`が合成である確率には、より強い境界があります。

実際、 3 ⇐ t ⇐ k / 9`および k> = 21`の場合、

image:https://i.stack.imgur.com/7rNJ7.gif [ここに画像の説明を入力]

k = 1024`ビットプライムの場合、 t = 6`の繰り返しにより、エラー率は 10 ^(-40)​​未満になります。

9


Rabin-Millerを繰り返すたびに、数値が1/4であるという確率が低下します。

そのため、64回の反復の後、2 ^ 128に1つの確率しかありません。

これらを公開鍵アルゴリズムに使用していると仮定します(例: RSA)、およびあなたが(たとえば)128ビットキーを使用して対称アルゴリズムとそれを組み合わせていると仮定すると、敵はその確率であなたのキーを「推測」できます。

一番下の行は、アルゴリズムに選択している他のサイズの球場内にその確率を入れるための反復回数を選択することです。

[更新、詳細化]

答えは、数値を使用するアルゴリズムと、それらのアルゴリズムに対する最も知られている攻撃に完全に依存します。

たとえば、http://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_key_lengths [Wikipedia]によると:

_
2003年現在、RSA Securityは、1024ビットRSAキーの強度は80ビット対称キー、2048ビットRSAキーは112ビット対称キー、3072ビットRSAキーは128ビット対称キーと同等であると主張しています。
_

したがって、これらの素数を使用して(たとえば)1024ビットRSAキーを生成することを計画している場合、Rabin-Millerを40回以上実行する理由はありません。 Why? なぜなら、あなたが失敗するまでに、攻撃者はいずれにせよあなたの鍵の1つをクラックする可能性があるからです。

もちろん、時間が許せば、それ以上の繰り返しを実行する理由はありません。 そうすることはあまり_ポイント_ではありません。

一方、2048ビットのRSAキーを生成する場合は、Rabin-Millerの56回(またはそれ以上)の反復がより適切です。

暗号化は通常、素数生成、RSA、SHA-2、AESなどのプリミティブの構成として構築されます。 これらのプリミティブの1つを他のプリミティブよりも2 ^ 900倍強くしたい場合は可能ですが、それは丸太小屋に10フィートのスチール製の金庫の扉を置くようなものです。

あなたの質問に対する決まった答えはありません。 それは、暗号化システムに入る他の部分の強度に依存します。

とは言っても、2 ^ -128はばかげているほど小さな確率なので、たぶん64回の反復を使用します:-)。

4


libgcryptのソースから: `/ *私たちは64のRabin-Millerラウンドを使用します。 ルーカステストの実装はないため、いくつかのRabin-Millerを実行してから1つのルーカステストを実行するX9.31の推奨方法では実行できません。 * / `cipher / primegen.c行番号1295

2


それは重要ですか? なぜ1000回繰り返し実行しないのですか? 素数を検索する場合、Rabin-Millerテストの最初の失敗時に適用を停止します。そのため、素数を見つけるのにかかる時間は、反復回数の上限はどうでもかまいません。 完全に確実にするために、これらの1000回の反復後に決定論的な素数性チェックアルゴリズムを実行することもできます。

つまり、n回の反復後に数が素数になる確率は4 ^ -nです。

-1


タイトルとURLをコピーしました