1
$\begingroup$

I'm pretty familiar with using ssh-keygen to create groups that go in the /etc/ssh/moduli file for the Diffie-Hellman Group Exchange in openssh. Reading over the man page, it says "By default, each candidate will be subjected to 100 primality tests. This may be overridden using the -a option." I'm making an educated guess that the tests being performed are some non-deterministic test for primality (Miller–Rabin?), although the man page doesn't seem to say. Experimenting with that -a option shows that 4 is the lowest that ssh-keygen will accept as an argument for -a.

what I'm wondering what the chances are of getting a composite number (or a non-safe prime number, or some other problematic situation) with values like 4 or 100 for -a? Is this on the order of a 1 in 100 risk, or 1 in a million risk?

Thank you.

Improve this question
$\endgroup$
1
  • $\begingroup$ I don't know whether-or-not they use Miller-Rabin, but if so, then this paper $\hspace{1.84 in}$ gives upper bounds on that probability. $\;$ $\endgroup$
    – user991
    Commented Aug 2, 2015 at 2:04

1 Answer 1

Reset to default
2
$\begingroup$

In ssh-keygen.c of the OpenSSH source code, there is the following call:

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

...and a comment for the function prime_test says:

 * perform a Miller-Rabin primality test

Therefore, it does indeed use a Miller-Rabin test. One can show that for composite $n$, at least half of the possible random choices prove the compositeness of $n$ (in fact, there are even stronger bounds), hence the confidence in $n$'s primality after $k$ runs of that test is larger than $1-2^{-k}$. In the particular case $k=100$, the probability is (larger than) roughly $1-2^{-100}=0.999999999999999999999999999999$, which is a lot.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ For bit-length of at least 700, the paper I linked to gives a better bound $\hspace{2.12 in}$ than 1-(2^(-30)) even with just one test. $\;$ $\endgroup$
    – user991
    Commented Aug 2, 2015 at 16:25
  • $\begingroup$ If I'm reading the HAC(p. 148) right, 3 rounds suffice for $1-2^{-80}$ probability of primality at 1000 bit. 100 rounds would yield a very high probability for primality. $\endgroup$
    – SEJPM
    Commented Aug 2, 2015 at 16:25
  • $\begingroup$ One should distinguish between the two scenarios of (1) a random input of a given size, and (2) an arbitrary input given by a third party. The former is modeled by Damgård et al. and similar papers. If you have complete control over the random selection, this seems reasonable, and leads to extraordinarily small probabilities for the large sizes. The latter is modeled by the Monier bounds of $4^{-k}$, as there exist numbers that have nearly that many bases that fail. The former takes into account how rare those are, the latter assumes that the input will be worst case. $\endgroup$
    – DanaJ
    Commented Aug 3, 2015 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.