素数を生成する
暗号鍵と整数論のための素数を生成します。篩(ふるい)、素数判定、safe prime の生成を学びましょう。
- 1
素数生成の手法:エラトステネスのふるい(N までのすべての素数。小さい素数に効率的)、ランダム探索(ランダムな奇数を生成して素数判定を繰り返す。暗号用)、Miller-Rabin(確率的素数判定。高速かつ正確)。暗号用途では、ランダム探索+Miller-Rabin で 1024〜4096 ビットの素数を生成します。
- 2 素数ジェネレーター →
素数を生成します。暗号用の素数にはビットサイズ(1024、2048 など)を、小さい素数には範囲を指定します。ツールはランダム探索と Miller-Rabin 判定を使います。生成された素数はおそらく素数です(誤り確率 < 2^-100)。
- 3 素数判定ツール →
生成された数が素数か検証します。チェッカは複数ラウンドの Miller-Rabin を使います。ラウンドを増やすほど信頼度が上がります。暗号用途では 40〜64 ラウンドで偽陽性確率が無視できるレベルになります。絶対的な確実性には AKS テスト(決定的だが遅い)を使ってください。
よくある質問
- 安全な素数とは何ですか?
- (p-1)/2 も素数であるような素数 p のことです。安全な素数は Diffie-Hellman で特定の攻撃(Pohlig-Hellman)を防ぐために使われます。生成は遅くなります。p を生成し、(p-1)/2 が素数か確認し、繰り返します。ほとんどの用途では通常の素数で十分です。DH グループ生成には安全な素数を使ってください。
- 暗号用の素数はどのくらいランダムでなければなりませんか?
- 非常にランダムである必要があります。素数生成が予測可能なら(逐次生成、低エントロピーのシードなど)、攻撃者が素数を推測して鍵を破れます。ランダム探索には CSPRNG を使ってください。特殊な構造を持つ素数(滑らかな p-1)は専門化された攻撃に対して脆弱なので避けてください。RFC 5234 が DSA 素数の要件を規定しています。