Multi-thread

[Karl Magdsick]

Make that about 5 times as large as allowed for US federal agencies by FIPS
183-3.

On Tue, Oct 13, 2009 at 2:50 PM, Karl Magdsick <kmagnum at gmail.com> wrote:

> 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/e210393f/attachment-0001.htm>