Subject: [Cfrg] Recommended Miller-Rabin iterations?

From: Simon Josefsson <[email-masked]>
Date: Fri, 15 Oct 2010 11:24:04 +0200

Are there any established recommendations on the number of MR iterations
that crypto software should perform when generating primes?  My context
is DH parameters for TLS DHE, but pointers to recommendations that apply
to RSA prime generation would be appreciated too.  RFC 5246 and RFC 3447
are rather silent on this topic, or I missed it.

/Simon

---

From: "Santosh Chokhani" <[email-masked]>
Date: Fri, 15 Oct 2010 06:35:52 -0400

FIPS 186-3 and ANSI standards define the way to generate or test
probabilistic primes.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Simon Josefsson
Sent: Friday, October 15, 2010 5:24 AM
To: [email-masked]
Subject: [Cfrg] Recommended Miller-Rabin iterations?

/Simon
_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 18 Oct 2010 09:38:16 -0700

Hmmmm, you're thinking about generating DH modulii on the fly?  I'm not
sure if that's the best idea.

With DH using a modulus p, the security of the system depends rather
critically on the factorization of p-1 (and whether p-1 happens to have
any large prime factors).  Now, if you pick a random prime p, well, it's
probable that p-1 will happen to have at least one large factor, but I
don't know if I'd be comfortable on a system that is probably secure.

   (In addition to p-1 having a large prime factor q, the group
generated by g needs to have a subblock of order q.  That turns out to
be extremely probable (probability (q-1)/q if g was selected randomly),
and so I wouldn't worry about that).

Now, it's certainly possible to efficiently generate a modulus p with
p-1 having a large prime factor (say, Lim-Lee primes), but unless you're
going to go through that effort, I'd recommend you use a fixed
known-good prime of the appropriate size (the groups that IKE uses are
quite good for this purpose).