離散對數密鑰未均勻分佈是否存在安全問題？
通常，基於離散對數的算法指定將私鑰選擇為 1 和組階之間的標量（表示為 $ q $ 這裡）。例如，IEEE P1363 和 FIPS 186-3 都為 DL 私鑰指定了這個範圍。如果沒有從該範圍內統一選擇密鑰，是否有問題？
一種可能性是選擇一個隨機整數 $ k=\log_2(q) $ 位並減少它 $ q $ . 在這種情況下，私鑰更有可能在該範圍內 $ [1,2^k-q] $ 比其他的。發生這種情況的另一種情況是，如果實現修復了最高位，例如重複生成 $ k $ - 位整數，直到小於 1 $ q $ 生成）。所以攻擊者知道密鑰不在範圍內 $ [1…2^{k-1}] $ .
當使用像這樣的密鑰生成技術時，攻擊者可以獲得多少優勢？顯然，總密鑰空間減少了，但除此之外，安全性是否有所降低？例如，一個 160 位的 DSA 密鑰 $ q $ 和 $ x $ 固定為 159 位比 159 位的 DSA 密鑰更容易破解 $ q $ 和 $ x $ 完全隨機？
離散對數問題可以使用特定或通用算法來解決。一種特定的算法是一種試圖利用使用離散對數的特定組的結構弱點的算法；例如，當我們談論以大素數取冪時的指數微積分。通用算法僅使用群定律，因此適用於“任何”群。對於正常的橢圓曲線（不包括那些允許有效配對的曲線），沒有特定的算法是已知的。
對於一個團體 $ N $ 元素，在統一選擇私鑰的情況下，最好的通用算法與成本一起工作 $ O(\sqrt{N}) $ ; 因此，對於 160 位組，您具有安全性 $ 2^{80} $ . 如果私鑰選擇不統一，則可以調整通用算法以考慮到這一點：最終，這相當於減少 $ N $ . 在您的範例中，“等效” $ N $ 不小於 $ q/2 $ ，因此您將安全性降低不超過 $ \sqrt{2} $ 因素：不值得擔心。
然而，在 (EC)DSA 簽名生成中，一個新值（稱為 $ k $ 在 FIPS 186-3 中）必須以模數生成 $ q $ 每個簽名；它有時被稱為“臨時私鑰”。與私鑰相反 $ x $ ， 價值 $ k $ 必須統一生成。例如，如果 $ k $ 通過選擇長度比長度小一的隨機位序列來選擇 $ q $ ， 或者如果 $ k $ 通過採用相同長度的隨機位序列來選擇 $ q $ 並減少它模 $ q $ , 然後是私鑰 $ x $ 可以通過觀察許多簽名和總成本來重建 $ 2^{63} $ ，雖然仍然很大，但遠低於預期 $ 2^{80} $ . 這是 Bleichenbacher 在 2001 年發現的；我不確定它是否在任何地方正式發布（Vaudenay 將其稱為“私人通信”）。這裡的問題不在於離散對數本身，而在於如何 $ k $ 和 $ x $ 用於計算 $ s $ （（EC）DSA 簽名的後半部分）。
目前的 FIPS 186 (FIPS 186-3) 通過生成至少長64 位的位序列來解決該問題。 $ q $ ，然後將其取模 $ q $ （這使得偏差足夠小以至於不重要）。在 X9.62-2005（ECDSA 標準）中，它們只生成長度為 $ k $ 如果這產生的值不在 $ 1 $ 和 $ q-1 $ .
無論哪種方式，對於正確安全的 (EC)DSA 簽名生成，您必須有一種方法來生成合理無偏的 $ k $ 價值觀；因此，您可以使用相同的生成器來生成私鑰 $ x $ .