Multi-thread

[Ian Goldberg]

On Tue, Oct 13, 2009 at 02:50:11PM -0400, Karl Magdsick wrote:
> FIPS 183-3 (approved and published June, 2009), section 4.2 (page 15) lists
> values for N of 160, 224, and 256.  N is the number of bits in the prime q.
>  The  largest L listed is 3,072, resulting in a 3,072-bit prime p.  This
> standard points to SP 800-57 for further guidance on domain parameter size.
>  SP 800-57, section 4.2.4.1 (page 37) mentions the same parameter sizes.
>  FIPS 183-3, sections A.1.1 and A.1.2 don't mention use of any parameters
> that would be anywhere near 15,000 bits.

You're both right. N=256 is the value for 128-bit security, due to the
sqrt(q) attacks such as Pollard's kangaroo method.  That corresponds to
3072-bit p.

But the original question was about 256-bit security, which indeed would
require a 512-bit q and a p on the order of 10,000-15,000 bits.

Note, however, that there's no good reason to want 256-bit security
here.  You can't be worried about large-scale quantum computing, since
that would break DSA completely.  If this is a signature key, the
security only has to last for the validity time of the signature.  (As
opposed to an encryption key, whose security has to last for the length
of time the data must remain secret.)  No one believes 128-bit security
is inadequate in the 3-5 year timeframe.  (Many people believe 80-bit
security is even adequate for that timeframe, but that's perhaps too
close to the edge for some.)

Also remember that you can technically reuse the public p and q values
for a DSA key; the security is in the secrecy of the x value.  So once
you generate your 15000-bit prime p such that p-1 has a 512-bit prime
factor q, you can just use that pair with different 512-bit values of x
to create different keys.

Note, however, that doing so is in violation of the FIPS, and indeed
using p and q that large is itself in violation of the FIPS (as was
pointed out by Karl).

   - Ian