ssh-keygen DH 素性測試

我非常熟悉使用 ssh-keygen 為 openssh 中的 Diffie-Hellman Group Exchange 創建 /etc/ssh/moduli 文件中的組。閱讀手冊頁，它說“預設情況下，每個候選人都將接受 100 次素性測試。這可以使用 -a 選項覆蓋。” 我做出有根據的猜測，正在執行的測試是一些非確定性的素性測試（Miller-Rabin？），儘管手冊頁似乎沒有說。對 -a 選項的試驗表明 4 是 ssh-keygen 將接受作為 -a 參數的最低值。

我想知道獲得-a 值為4 或100 的合數（或非安全素數，或其他有問題的情況）的機會有多大？這是 100 分之一的風險，還是百萬分之一的風險？

謝謝你。

在ssh-keygen.cOpenSSH 原始碼中，有以下呼叫：

       if (prime_test(in, out, rounds == 0 ? 100 : rounds,
           generator_wanted, checkpoint,
           start_lineno, lines_to_process) != 0)

…對該函式的評論prime_test說：

* perform a Miller-Rabin primality test

因此，它確實使用了 Miller-Rabin 檢驗。可以證明，對於復合 $ n $ ，至少有一半可能的隨機選擇證明了 $ n $ （事實上，還有更強的界限），因此有信心 $ n $ 之後的素數 $ k $ 該測試的執行大於 $ 1-2^{-k} $ . 在特定情況下 $ k=100 $ ，機率大致（大於） $ 1-2^{-100}=0.999999999999999999999999999999 $ ，這是很多。

引用自：https://crypto.stackexchange.com/questions/27279