Fwd: Tor security advisory: DH handshake flaw

[astiglic at okiok.com]

Some info on primality testing.

Miller-Rabin probabilistic primality tests work really well when you are
searching for a prime and picking candidates from a uniform random
distribution, also works well if you pick an initial candidate from a
uniform random distribution and then increment on that initial candidate,
until you find a probable prime. See the references

Damgard, Landrock and Pomerance (1993), Average case error estimates for
the strong probable prime test, Mathematics of Computation 61 (203).

Brandt, Damgard (1993) On generation of probable primes by incremental
search.  CRYPTO 92.

Summaries of the results can be found in the Handbook of applied
Cryptography.

On a side note about Miller-Rabin, there is something allot of people get
wrong.  The basic results we know is that one iteration of the
Miller-Rabin test will err in declaring a composite integer to be prime
with probability less than 1/4, while t iterations will err with
probability (1/4)^t.
You can find a proof for this is textbooks such as that of Koblitz.
If X stands for "n is composite", and Y_t stands for RepeatRabin(n, t)
returned "prime", where RepeatRabin is the algorithm that executes t
iterations of Miller-Rabin's test and outputs "composite as soon as an
iteration fails, "prime" if all iterations passed.
Now, given the basic theorem mentioned above, all we can say is that
Prob[Y_t | X ] <= (1/4)^t, in English “if n is composite, then
RepeatRabin(n,t) will return “prime” with probability less than or equal
to (1/4)^t”.  Much more interesting is to figure out Prob[X | Y_t], that
is “if RepeatRabin(n,t) returns “prime”, what is the probability that X is
actually composite and we got screwed?”.  It just happens to be that
Prob[X | Y_t] <= (1/4)^t when n is chosen from a uniform random
distribution, because in such cases prob[Y_1 | X] is actually much smaller
than ¼.
See
Beauchemin, Brassard, Crépeau, Goutier, Pomerance. The generation of
random numbers that are probably prime”, Journal of Cryptology, 1, 53-64.

Ok, back to the main topic.
So Miller-Rabin is good for testing random candidates, but it is easy to
maliciously construct an n that passes several rounds of Miller-Rabin.  
The Miller-Rabin probabilistic primality test actually comes from a true
primality test, called Miller test, which is polynomial (but not efficient
in practice) and works assuming the Extended Riemann Hypothesis.

On proposed algorithm is to use two iterations of the Miller-Rabin test
followed by a single iteration of the Lucas probable prime test.  The
advantage of this test is that there is yet no known composite integer
that passes even a single Miller-Rabin test to the base 2 followed by a
single Lucas probable prime test.  There is also an open challenge
regarding this (something like 640$ coming directly from the pockets of
Pomerance and al.).  See
Pomerance (1984) Are There Counter-Examples to the Baillie-PSW Primality
Test?

This is the algorithm mentioned by Hal.  No, there is no proof that you
can’t find a counter-example, but Pomerance hasn’t found one yet, and
that’s good enough for me for the time being!

If you want primality certificates, and not just a randomized test that
has some probability of given you a wrong answer, look at Elliptic curve
primality test and Maurer’s algorithm.  These are both described in the
ISO 18032 “prime number generation” standard and ANSI X9.80 (this just
goes to show that these are not purely academic creations, but stuff you
can use in practice).

Elliptic Curves for Primality Proving (ECPP) is used like Miller-Rabin in
order to generate a prime:  chose random candidates until one passes the
test; but in addition it produces a certificate that allows you to verify
primality using a different algorithm (much less complicated than the one
used to generate a prime, so this allows you to validate the correctness
of the implementation of the prime generating algorithm as well).
See
Atkin, Morain (1993).  Elliptic curves and primality proving.  Mathematics
of Computations.


Maurer’s method doesn’t pick and test random candidates, rather it
constructs, in a special way, an integer that is guaranteed to be prime.
Don’t be concerned about secrecy of prime generated with Maurer’s method,
the method generates primes that are almost uniformly distributed over the
set of all numbers (this is different from another algorithm called
Shawe-Taylor, which is similar in functioning but only reaches 10% of all
primes of a specified set).
Maurer’s method is much easier to code than ECPP. See
Maurer (1995) Fast generation of prime numbers and secure public-key
cryptographic parameters.  Journal of Cryptology, 8(3), 123-155
Maurer.  Fast generation of secure RSA-moduli with almost maximal
diversity.  EUROCRYPT'89.



So, in conclusion, there is allot of good stuff to choose from!

--Anton


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com