Diffie-Hellman 私鑰大小
我目前正在編寫自己的 Diffie-Hellma n 實現（這不是為了實際使用。這完全是為了讓我自己更好地了解 DH。）
對於素數和生成器，我使用的是RFC 3526，更具體地說是 4096 位素數。
我的問題是，Diffie-Hellman 是否有特定的標準秘密整數生成？由於秘密整數的安全性（通常是兩個，但 DH 確實支持多於 1-1 的通信）對於密鑰交換的安全性非常重要。
DHKE
在用 DHKE 表示的指數Diffie-Hellman中，一個取一組 $ G $ 帶發電機 $ g $ 以其順序 $ n $ .
Alice 和 Bob 在密鑰交換期間生成隨機數 $ 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 $ 被稱為索菲熱爾曼素數。
這是針對Pohlig-Hellman 算法的一種對策，該算法受益於 $ p-1 $ . 如果使用安全素數，則因子為 $ 2 $ 和 $ q $ . 擁有一個大的因素是針對 Pohlig-Hellman 的對策。
還有Schnorr組 $ p = r,q + 1 $ . 這可以被認為是安全素數的推廣。安全素數是最佳的。
通常，發電機 $ g $ 選擇生成訂單 $ q $ 使勒讓德符號 $ g^a $ 不洩漏低位 $ a $ .
素數生成
天真的方法產生一個素數 $ q $ 然後檢查素數 $ 2 , q +1 $ （梅內塞斯：算法 4.86）。在虛擬碼中；
do p = randomPrime(k-bit integer) while ((p − 1)/2 is composite)有更快的方法
- David Naccache 的雙速安全素數生成，2003 年
正如標題所暗示的那樣，通過測試兩者，這將速度提高了大約兩倍 $ 2q + 1 $ 和 $ (q − 1)/2 $ 為素數。
這個想法是使用隨機素數 $ p $ 作為安全素數或 Sophie Germain 素數；
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 $ 人們使用相同的安全（不可預測）隨機數生成器來生成他們的隨機密鑰。為了簡化這一點，我們可以假設有一個人生成隨機數。在這種情況下，這完全是生日悖論，在密碼學中，我們將其視為生日攻擊，以找到與 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 表。
由於模數是由標準預先確定的，因此可以說一些具有超能力的組織為模數建立了一些 DLog 表。
這也不是危險。假設他們可以建立一個表格 $ 2^{64} $ 那麼你隨機命中的機率是$$ \frac{\ell , 2^{64}}{2^{2048}} $$和 $ \ell $ 嘗試。將您的組可能的密鑰生成號放入 $ \ell $ . 因此，2048 位是一個非常大的數字。