Mailing List Archive

Did you add an extra zero in there, or are you really generating 30,000-bit
RSA keys? If you really need 30,000-bit RSA in 2009, either you know
something about breaking RSA that the public doesn't, or you have a lot of
other things to worry about besides just cryptography.
I'm not sure what questions lead to "30,000-bit keys" being the answer, but
you should probably take a step back and see if you're asking the right
high-level questions before going into the details of how to generate
30,000-bit keys faster.
Do you really need keys that amazingly large? If so, you probably also want
to do something like use RSA to encrypt a key encrypted using an elliptic
curve method, read up on cryptosystems that appear difficult to crack with
quantum computers, and definitely hire a professional cryptographer to
review your design and implementation. As far as I know, not even
governments use 30,000-bit RSA. (I've heard the NSA now uses 511-bit
elliptic curve crypto.)

Problems big enough to require keys that big also probably require at a
minimum a vault and armed guards, probably thermite and anti-tamper sensors,
and perhaps an armored tank or two, For the cost of cracking 30,000-bit RSA
using current publicly known algorithms, an attacker could hire a small
private army. Personally, I'd just prefer not to deal in secrets whose
value may justify the costs of hiring someone to kidnap me and coerce my
keys out of me, but that's just a personal preference.

As to your original question, I believe the APIs are thread-safe, but not
internally multi-threaded. If you're only generating one key, the latency
for generating one key isn't terrible and happens rarely. Making the
library internally multi-threaded would reduce its efficiency (locking,
scheduling, and context switch overhead) in generating many keys at once in
a server situation or in applications that use a lot of keys.

Since prime number generation is a stochastic guess-and-check operation, as
an ugly hack, you may be able to get a slight speed-up by having each core
generate one key, and using whichever key gets generated first. I imagine
your entropy source may very well be your bottle neck, though. Generating
two 15,000-bit cryptographically pseudorandom prime numbers is going to burn
through a lot of cryptographically secure pseudorandom bits.

Now, there's a hornets' nest in my back yard that I've been meaning to get
rid of and my tank is on the fritz... do any of you have a maintenance
manual for a WWII Sherman?

On Wed, Oct 7, 2009 at 5:47 AM, Antoine Dumont
<antoine.dumont86@gmail.com>wrote:

> Hy,
> First of all, thanks a lot to the developers of this library and
> particularly to Werner Koch for his job.
> My purpose is about the generation of asymetric keys. When I generate a
> couple of key of DSA or RSA algorithm thanks to the function gcry_pk_genkey
> it can be very long and I understand that generate primary numbers of 15000
> bits is not very simple. But i asked me why the library use only one core. I
> can compile and run my program in machine whose have many core and I suppose
> it's possible.
> After reading the reference manual, I saw that multi-thread is supported, I
> suppose it's meaning that we can use the library into a multi-thread
> program, but is the library itself multi-thread ?
> Thanks a lot for your answers !
> Best regards,
> Lao
>
> _______________________________________________
> Gcrypt-devel mailing list
> Gcrypt-devel@gnupg.org
> http://lists.gnupg.org/mailman/listinfo/gcrypt-devel
>
>

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. 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 . 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.
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.
I must understand that you prefer to make the generation of key without
multi-thread but I just would like to know why.
An other question, again about the key generation , when I try to
generate a 7680bit DSA key or an DSA key whose length is higher than
6000bits, I have a stranger error :
"Ohhh jeeee : ... this is a bug (pubkey.c:2266:_gcry_pk_genkey)"
and after the program exit.
Are you familiar with this sort of bug ?
Thank again for your job,
Best regards

Le 08/10/2009 15:24, Karl Magdsick a écrit :
> Did you add an extra zero in there, or are you really generating
> 30,000-bit RSA keys? If you really need 30,000-bit RSA in 2009,
> either you know something about breaking RSA that the public doesn't,
> or you have a lot of other things to worry about besides just
> cryptography.
>
> I'm not sure what questions lead to "30,000-bit keys" being the
> answer, but you should probably take a step back and see if you're
> asking the right high-level questions before going into the details of
> how to generate 30,000-bit keys faster.
>
> Do you really need keys that amazingly large? If so, you probably
> also want to do something like use RSA to encrypt a key encrypted
> using an elliptic curve method, read up on cryptosystems that appear
> difficult to crack with quantum computers, and definitely hire a
> professional cryptographer to review your design and implementation.
> As far as I know, not even governments use 30,000-bit RSA. (I've
> heard the NSA now uses 511-bit elliptic curve crypto.)
>
> Problems big enough to require keys that big also probably require at
> a minimum a vault and armed guards, probably thermite and anti-tamper
> sensors, and perhaps an armored tank or two, For the cost of cracking
> 30,000-bit RSA using current publicly known algorithms, an attacker
> could hire a small private army. Personally, I'd just prefer not to
> deal in secrets whose value may justify the costs of hiring someone to
> kidnap me and coerce my keys out of me, but that's just a personal
> preference.
>
> As to your original question, I believe the APIs are thread-safe, but
> not internally multi-threaded. If you're only generating one key, the
> latency for generating one key isn't terrible and happens rarely.
> Making the library internally multi-threaded would reduce its
> efficiency (locking, scheduling, and context switch overhead) in
> generating many keys at once in a server situation or in applications
> that use a lot of keys.
>
> Since prime number generation is a stochastic guess-and-check
> operation, as an ugly hack, you may be able to get a slight speed-up
> by having each core generate one key, and using whichever key gets
> generated first. I imagine your entropy source may very well be your
> bottle neck, though. Generating two 15,000-bit cryptographically
> pseudorandom prime numbers is going to burn through a lot of
> cryptographically secure pseudorandom bits.
>
> Now, there's a hornets' nest in my back yard that I've been meaning to
> get rid of and my tank is on the fritz... do any of you have a
> maintenance manual for a WWII Sherman?
>
> On Wed, Oct 7, 2009 at 5:47 AM, Antoine Dumont
> <antoine.dumont86@gmail.com <mailto:antoine.dumont86@gmail.com>> wrote:
>
> Hy,
> First of all, thanks a lot to the developers of this library and
> particularly to Werner Koch for his job.
> My purpose is about the generation of asymetric keys. When I
> generate a couple of key of DSA or RSA algorithm thanks to the
> function gcry_pk_genkey it can be very long and I understand that
> generate primary numbers of 15000 bits is not very simple. But i
> asked me why the library use only one core. I can compile and run
> my program in machine whose have many core and I suppose it's
> possible.
> After reading the reference manual, I saw that multi-thread is
> supported, I suppose it's meaning that we can use the library into
> a multi-thread program, but is the library itself multi-thread ?
> Thanks a lot for your answers !
> Best regards,
> Lao
>
> _______________________________________________
> Gcrypt-devel mailing list
> Gcrypt-devel@gnupg.org <mailto:Gcrypt-devel@gnupg.org>
> http://lists.gnupg.org/mailman/listinfo/gcrypt-devel
>
>

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@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

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@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@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
>

On Wed, Oct 07, 2009 at 11:47:29AM +0200, Antoine Dumont wrote:
> Hy,
> First of all, thanks a lot to the developers of this library and
> particularly to Werner Koch for his job.
> My purpose is about the generation of asymetric keys. When I generate a
> couple of key of DSA or RSA algorithm thanks to the function
> gcry_pk_genkey it can be very long and I understand that generate
> primary numbers of 15000 bits is not very simple. But i asked me why the
> library use only one core. I can compile and run my program in machine
> whose have many core and I suppose it's possible.
> After reading the reference manual, I saw that multi-thread is
> supported, I suppose it's meaning that we can use the library into a
> multi-thread program, but is the library itself multi-thread ?
> Thanks a lot for your answers !
> Best regards,
> Lao

You do understand that mere fact of having "multiple threads" makes no
difference. You'd need tasks to give to each thread. Just like having
multiple cores in your CPU, you need *distinct* tasks to divide to
these threads.

Generating a keypair is not something that can be divided into
distributable subtasks readily, thus making it very difficult to benefit
from multithreading.

Aki Tuomi

That is a very good and complete answer !
Thanks ! I will read documentation more :)
Sorry to ask some questions again but about the problem of a good random
generation have you find something else than /dev/random (or
/dev/urandom for less quality) ?
Have a nice day !


Le 13/10/2009 21:05, Karl Magdsick a écrit :
> 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@gmail.com
> <mailto:kmagnum@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@gmail.com <mailto:antoine.dumont86@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
>
>

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

_______________________________________________
Gcrypt-devel mailing list
Gcrypt-devel@gnupg.org
http://lists.gnupg.org/mailman/listinfo/gcrypt-devel