Diffie-Hellman秘密鍵のサイズ
私は現在、Diffie-Hellmanの独自の実装を書いています（これは実際の使用ではありません。これは、自分で行うことによってDHをよりよく理解するために厳密に使用されます。）
プライムとジェネレーターには、RFC 3526、より具体的には4096ビットのプライムを使用しています。
私の質問は、Diffie-Hellmanの特定の標準的な秘密整数生成はありますか？秘密整数（通常は2つですが、DHは1対1以上の通信をサポートします）のセキュリティは、鍵交換のセキュリティにとって非常に重要です。
回答
DHKE
DHKEで表される指数関数的なDiffie-Hellmanでは、グループを取ります$G$ 発電機付き $g$ その順序で $n$。
アリスとボブは、鍵交換中に乱数を生成します $a$ そして $b$ 範囲内 $a,b\in (1,n)$ 送信します $g^a$ そして $g^b$ そして最後に、彼らは次のように鍵を確立します $g^{ab}$ 次に、KDFを使用して、対称鍵とIV / nonceを導出します。
DHKEの楕円曲線バージョンもあり、ECDHで表され、従来の指数バージョンよりも使用されています。
プライム
DHKEでは、安全な素数として素数を選択します。 $p = 2 \cdot q + 1$ と $q$素数でもあります。ザ・$q$ソフィージェルマン素数と呼ばれます。
これは、ポーリヒヘルマンアルゴリズムに対する対抗策であり、$p-1$。安全な素数が使用されている場合、要因は$2$ そして $q$。大きな要因を持つことは、ポーリヒヘルマンに対する対抗策です。
ありシュ・グループと$p = r\,q + 1$。これは、セージ素数の一般化と見なすことができます。セージ素数が最適です。
プライム生成
素朴なアプローチは素数を生成します $q$ 次に、の素数性を確認します $2 \, q +1$（Menezes：アルゴリズム4.86）。擬似コードで;
do
p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)
より速い方法があります
2003年のDavidNaccacheによる倍速セーフプライム生成
タイトルが示すように、これは両方をテストすることでこれを約2倍高速化します $2q + 1$ そして $(q − 1)/2$ 素数性のために。
アイデアはランダム素数を使用しています $p$ 安全な素数またはソフィージェルマン素数として;
do p = randomPrime(k-bit integer) while ((p − 1)/2 and 2p + 1 are composite)Michael J. Wienerによる複合ふるいによる安全なプライム生成、2003年。
彼らは小さな素数をふるいにかけることを提案しました $2^{16}$。これは提供します$15x$ 素朴なアルゴリズムよりも高速化します。
アイデアはこの観察から始まります。どちらも$q$ そして $q=2p+1$ に合同である必要があります $2$ モジュロ $3$。したがって、次のような候補を排除することができます。$0$ モジュロ $3$ そして $1$ モジュロ $3$。
これは任意の奇数の素数に一般化できます $r$。排除する$q$に一致するの $(r-1)/2$ モジュロ $r$ この場合から $p$ 分割可能です $r$。
セットを取る $S$ すべての奇数素数 $<B$。次に$\prod_{r\in S}(r-2)/r$ 候補者の数はふるいを生き残るでしょう。
場合 $B=2^{16}$ 生産できると推定されています $\approx \times 15$ スピードアップ。
衝突
次に、同じ乱数が存在する場合に到着する確率を調べます。 $k$同じDHKE係数を使用している人。私たちは、$k$同じ安全な（予測不可能な）乱数ジェネレーターを使用してランダムキーを生成する人々。これを単純化するために、乱数を生成する人が1人いると仮定できます。この場合、これは完全に誕生日のパラドックスであり、暗号化では、これが50％との衝突を見つけるための誕生日攻撃であることがわかります。これは、ハッシュ関数の衝突を調べる一般的な方法です。
しましょう $H$ 乱数ジェネレーターの範囲であり、 $p$ 必要な確率を表し、 $n(p; H)$ 選択しなければならない値の最小数である;
$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$
古典的なハッシュ衝突の場合、 $p=1/2$ そしてこのアプローチ
$$n(0.5;H) \approx 1.1774 \sqrt H$$ そして私達は通常として表す $\mathcal{O}(\sqrt{H})$
それでは、実際の数値をいくつか見てみましょう。
2048ビットプライム
と仮定する $n$ 2048ビットの数値です。覚えておいてください $n$ 発電機の注文でした $g$。次に
$$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$
50％の確率で $$n(0.5;2^{2048})\approx 2^{1204}$$
結果として、あなたは生成する必要があります $2^{1204}$50％でもう一度ヒットする乱数。現実的ではありません。
4096ビットプライム
$$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$
50％の確率で $$n(0.5;2^{4096})\approx 2^{2048}$$
結果として、あなたは生成する必要があります $2^{2048}$50％でもう一度ヒットする乱数。現実的ではありません。離散対数テーブルを事前に計算します。
モジュラスは標準によって事前に決定されているため、スーパーパワーを持つ一部の組織はモジュラスのDLogテーブルを作成したと主張できます。
これも危険ではありません。彼らが最大でテーブルを構築できると仮定しましょう$2^{64}$ ランダムヒットの確率は $$\frac{\ell \, 2^{64}}{2^{2048}}$$ と $\ell$試してみてください。グループの可能なキー生成番号を$\ell$。したがって、2048ビットは処理するのに非常に大きな数です。