Multi-thread

[Karl Magdsick]

You still appear to me to be generating DSA keys approximately 10 times as
large as the largest size allowed for US government entities by FIPS 183-3.
 ("Federal government agencies shall generate digital signatures using one
or more of these choices." FIPS 183-3, section 4.2, listing possible values
of the DSA parameter L as 1024, 2048, and 3072.)  I doubt any NIST
recommendations published after FIPS 183-3 (and before today's date)
contradict FIPS 183-3.

On Tue, Oct 13, 2009 at 9:15 AM, Antoine Dumont
<antoine.dumont86 at gmail.com>wrote:

>  Hello,
> Thanks for this ironic answer Karl but you don't really answer the
> question.
> I think there was a little misunderstood, make sure that I don't want to
> generate a 30,000 bit RSA key , I'm not stupid.
> I spoke about a 15,000 DSA key , or a 7,000 bit DSA key  (for "N"
> parameter) I think it wasn't really unbelievable. It's just 2^15000 smaller
> than you think I propose.
>

You spoke of 15,000-bit primes for DSA or RSA.  RSA keys using 15,000-bit
primes use 30,000-bit moduli, assuming 2-factor RSA.  I believe 3-factor RSA
is encumbered with intellectual property issues.


> Moreover, NIST recommendations indicate that a such level of protection is
> equivalent of a level of 256 bits of securiy, it's not unbelievable. If I
> want to create an high authority which sign other keys for few years (3-5
> years), high value is required .
>

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.

Where are you getting these NIST recommendations for (L, N) ?  I don't see
anything in FIPS 183-3 that would suggest FIPS 183-3 compliant values for L
are anything but 1,024, 2,048, and 3,072.

On a side note, when one speaks of the number of bits of security for a
signature or hash algorithm, one takes into account the birthday attack, so
SHA-256 has at most 128-bit strength.  This convention helps in matching the
size of hash functions, signature algorithm parameters, and symmetric
encryption keys.


> The manual of libgcrypt says that 15360bit key or 7680bit (or any multiple
> of 8 between 512 and 15680 if  Q parameter is specified) for DSA algorithm
> is possible, and when I try to generate a such key it was very long and I
> use only one core, I think it's regrettable.
>

The libgcrypt manual may say that those sizes are possible (I haven't
checked), and if so, it would seem to be correct.  I don't think the manual
guarantees that these huge sizes will be speedy or even practical.


> You confirm me that primary test is a stochastic test, which is classic, so
> why don't make guess-and-check operations in different thread : the first
> who find the key stop the others ? It's just my question.
>

Because this is the simplest way I can think of that may give you a speed
increase without modifying libgcrypt.  It may or may not provide a speed
increase.  It's certainly less efficient, providing a speed-up that's very
much less than linear.


> I must understand that you prefer to make the generation of key without
> multi-thread but I just would like to know why.
>

Amdahl's law plus synchronization, coordination, and communication overhead.


Cheers,
-Karl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/attachments/20091013/58948f4b/attachment.htm>