RSA - key generation time
1,827 views
Skip to first unread message
mgr_inz_Rafal
May 10, 2010, 6:06:50 AM5/10/10
to Crypto++ Users
Hello everyone.
I need to introduce some basic RSA encryption in my application. I
used Crypto++ a lot for AES stuff and it worked great, so it's not a
surprise that I managed to use RSA smoothly.
Yet, I am wondering about the time needed to generate the RSA keys. I
use the following code (it is a - more or less - copy from the
examples) with the intention to generate the 4096-bit key:
CryptoPP::AutoSeededRandomPool rng;
CryptoPP::InvertibleRSAFunction parameters;
parameters.GenerateRandomWithKeySize(rng, 4096);
CryptoPP::RSA::PrivateKey privateKey(parameters);
CryptoPP::RSA::PublicKey publicKey(parameters);
privateKey.Save(CryptoPP::StringSink(privateKey_string));
std::string publicKey_string;
publicKey.Save(CryptoPP::StringSink(publicKey_string));
The method takes from 3 to about 7 seconds to execute and the keys are
ready. I am not an crypto-expert but isn't it a little bit to quick to
create the 4096-bit long key pair?
Could someone shed some light on the issue or point me to the
materials about key generation algorithms used by Crypto++?
Thank you very much.
--
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-user...@googlegroups.com.
More information about Crypto++ and this group is available at http://www.cryptopp.com.
I need to introduce some basic RSA encryption in my application. I
used Crypto++ a lot for AES stuff and it worked great, so it's not a
surprise that I managed to use RSA smoothly.
Yet, I am wondering about the time needed to generate the RSA keys. I
use the following code (it is a - more or less - copy from the
examples) with the intention to generate the 4096-bit key:
CryptoPP::AutoSeededRandomPool rng;
CryptoPP::InvertibleRSAFunction parameters;
parameters.GenerateRandomWithKeySize(rng, 4096);
CryptoPP::RSA::PrivateKey privateKey(parameters);
CryptoPP::RSA::PublicKey publicKey(parameters);
privateKey.Save(CryptoPP::StringSink(privateKey_string));
std::string publicKey_string;
publicKey.Save(CryptoPP::StringSink(publicKey_string));
The method takes from 3 to about 7 seconds to execute and the keys are
ready. I am not an crypto-expert but isn't it a little bit to quick to
create the 4096-bit long key pair?
Could someone shed some light on the issue or point me to the
materials about key generation algorithms used by Crypto++?
Thank you very much.
--
You received this message because you are subscribed to the "Crypto++ Users" Google Group.
To unsubscribe, send an email to cryptopp-user...@googlegroups.com.
More information about Crypto++ and this group is available at http://www.cryptopp.com.
Zooko O'Whielacronx
May 10, 2010, 9:13:57 AM5/10/10
to mgr_inz_Rafal, Crypto++ Users
On Mon, May 10, 2010 at 4:06 AM, mgr_inz_Rafal <rchab...@gmail.com> wrote:
> The method takes from 3 to about 7 seconds to execute and the keys are
> ready. I am not an crypto-expert but isn't it a little bit to quick to
> create the 4096-bit long key pair?
As far as I know, that is to be expected.
> The method takes from 3 to about 7 seconds to execute and the keys are
> ready. I am not an crypto-expert but isn't it a little bit to quick to
> create the 4096-bit long key pair?
I intend to solve the problem that I am having with this by switching
from RSA to elliptic curve DSA.
Regards,
Zooko
Mark Cohen
May 16, 2010, 8:41:45 PM5/16/10
to Crypto++ Users
On May 10, 5:06 am, mgr_inz_Rafal <rchabow...@gmail.com> wrote:
> Hello everyone.
> The method takes from 3 to about 7 seconds to execute and the keys are
> ready. I am not an crypto-expert but isn't it a little bit to quick to
> create the 4096-bit long key pair?
Quick compared to what?
RSA key generation, as you've noted, takes a variable amount of time.
This is because in order to generate a 4096-bit key, you have to find
2 2048-bit pseudorandom prime numbers. This involves generating a
2048-bit pseudorandom number, setting it to odd (because all even
numbers are not prime), then testing for primality. If it's not
prime, then you usually increment by 2 (the next odd number) and test
again for primality. You repeat this process until you find a prime
number. Then you have to repeat the above process for the second 2048-
bit prime. Then you have to do a few more calculations and validity
tests.
There are a few potential slow steps in this process:
1) Getting pseudorandom numbers. By default, the AutoSeeded* classes
in Crypto++ use the nonblocking pseudorandom number generators (/dev/
urandom on Unix, CryptGenRandom on Windows) from the host OS to seed
Crypto++'s PRNG. This will always acquire pseudorandom bytes
instantly, but with arguably less entropy. On Unix, you can tell the
PRNG constructor to use the blocking PRNG function (/dev/random)
instead, which will stall until it has enough entropy to satisfy the
calling function. You can also use an entropy-gathering daemon, tell
GnuPG (or OpenSSL) to use it and key generation is sped up
dramatically because the PRNG seeding function doesn't have to wait on
a blocking PRNG.
2) Primality tests. The speed of primality tests varies depending on
how sure you wanna be that the number you're testing is indeed prime
or is not a special prime that could be subject to attack. OpenSSL
and .NET include functionality to automatically block known weak keys
(believe it or not some people are stupid enough to use test vector
keys in production environments).
3) Key validity tests.
I've found that Crypto++ and OpenSSL generate RSA keys with
approximately the same speed, though Crypto++ is a bit faster in
general. I don't know enough of the source code in either to say what
the difference is. But I always use the blocking RNG seed and always
do the full validity tests.
Now if you're comparing the RSA key generation time to something like
OpenPGP key generation, remember that OpenPGP basically requires 2 RSA
keys for a single OpenPGP key. This is because if you sign data with
the same key you use to encrypt data, you're opening yourself up to a
HUGE security hole. This is why GnuPG will bark at you if you try to
create an OpenPGP keypair without a separate signing subkey. PGP
Desktop won't even let you try to use such a key. So OpenPGP key
generation takes at least twice as long (usually longer since the
blocking PRNG seeding function never contains enough entropy to seed 4
2048-bit numbers).
The reason elliptic curve keys are generated so quickly is that an
elliptic curve private key is simply a pseudorandom number. It's
shorter than RSA numbers and doesn't have to be prime, so you skip
over 2 of the above slow steps. Too bad the EC arena is a big patent
lawsuit-bomb. Sony was sued by Certicom immediately after releasing
Blu-ray, which included EC encryption. It doesn't matter if you claim
that your implementation is not covered by patents; the threat of a
lawsuit, even a bogus lawsuit, is enough to prevent widespread
adoption. But I'm getting a little off-topic here.
2 bottom lines:
1) The security of your RSA key depends on the entropy of your
pseudorandom number generator, not the speed of key generation. This
is why TrueCrypt tells you to spend a few minutes moving your mouse
around and pressing keys before is encrypts a volume. A 16384-bit RSA
key is worthless if your PRNG was seeded with predictable data.
PRNG's have had game-breaking security holes in every operating system
known to man, though they're getting better (unless you're using
Windows prior to XP SP3). On Windows, you have to trust that
Microsoft is doing it right since they won't open-source their PRNG
(though they make cute little promises that it does the job right,
doesn't leak/store PRNG state, and will let you peek at their code
behind closed doors if you pay them large sums of money).
2) Don't use the same key for separate signing and encryption,
especially in an automated process that will encrypt or sign anything
sent to it. I've seen this so many times it's almost laughable. But
the reality is that you practically need a PhD in number theory in
order to get this stuff right.
> Hello everyone.
> The method takes from 3 to about 7 seconds to execute and the keys are
> ready. I am not an crypto-expert but isn't it a little bit to quick to
> create the 4096-bit long key pair?
RSA key generation, as you've noted, takes a variable amount of time.
This is because in order to generate a 4096-bit key, you have to find
2 2048-bit pseudorandom prime numbers. This involves generating a
2048-bit pseudorandom number, setting it to odd (because all even
numbers are not prime), then testing for primality. If it's not
prime, then you usually increment by 2 (the next odd number) and test
again for primality. You repeat this process until you find a prime
number. Then you have to repeat the above process for the second 2048-
bit prime. Then you have to do a few more calculations and validity
tests.
There are a few potential slow steps in this process:
1) Getting pseudorandom numbers. By default, the AutoSeeded* classes
in Crypto++ use the nonblocking pseudorandom number generators (/dev/
urandom on Unix, CryptGenRandom on Windows) from the host OS to seed
Crypto++'s PRNG. This will always acquire pseudorandom bytes
instantly, but with arguably less entropy. On Unix, you can tell the
PRNG constructor to use the blocking PRNG function (/dev/random)
instead, which will stall until it has enough entropy to satisfy the
calling function. You can also use an entropy-gathering daemon, tell
GnuPG (or OpenSSL) to use it and key generation is sped up
dramatically because the PRNG seeding function doesn't have to wait on
a blocking PRNG.
2) Primality tests. The speed of primality tests varies depending on
how sure you wanna be that the number you're testing is indeed prime
or is not a special prime that could be subject to attack. OpenSSL
and .NET include functionality to automatically block known weak keys
(believe it or not some people are stupid enough to use test vector
keys in production environments).
3) Key validity tests.
I've found that Crypto++ and OpenSSL generate RSA keys with
approximately the same speed, though Crypto++ is a bit faster in
general. I don't know enough of the source code in either to say what
the difference is. But I always use the blocking RNG seed and always
do the full validity tests.
Now if you're comparing the RSA key generation time to something like
OpenPGP key generation, remember that OpenPGP basically requires 2 RSA
keys for a single OpenPGP key. This is because if you sign data with
the same key you use to encrypt data, you're opening yourself up to a
HUGE security hole. This is why GnuPG will bark at you if you try to
create an OpenPGP keypair without a separate signing subkey. PGP
Desktop won't even let you try to use such a key. So OpenPGP key
generation takes at least twice as long (usually longer since the
blocking PRNG seeding function never contains enough entropy to seed 4
2048-bit numbers).
The reason elliptic curve keys are generated so quickly is that an
elliptic curve private key is simply a pseudorandom number. It's
shorter than RSA numbers and doesn't have to be prime, so you skip
over 2 of the above slow steps. Too bad the EC arena is a big patent
lawsuit-bomb. Sony was sued by Certicom immediately after releasing
Blu-ray, which included EC encryption. It doesn't matter if you claim
that your implementation is not covered by patents; the threat of a
lawsuit, even a bogus lawsuit, is enough to prevent widespread
adoption. But I'm getting a little off-topic here.
2 bottom lines:
1) The security of your RSA key depends on the entropy of your
pseudorandom number generator, not the speed of key generation. This
is why TrueCrypt tells you to spend a few minutes moving your mouse
around and pressing keys before is encrypts a volume. A 16384-bit RSA
key is worthless if your PRNG was seeded with predictable data.
PRNG's have had game-breaking security holes in every operating system
known to man, though they're getting better (unless you're using
Windows prior to XP SP3). On Windows, you have to trust that
Microsoft is doing it right since they won't open-source their PRNG
(though they make cute little promises that it does the job right,
doesn't leak/store PRNG state, and will let you peek at their code
behind closed doors if you pay them large sums of money).
2) Don't use the same key for separate signing and encryption,
especially in an automated process that will encrypt or sign anything
sent to it. I've seen this so many times it's almost laughable. But
the reality is that you practically need a PhD in number theory in
order to get this stuff right.
Mark Cohen
May 16, 2010, 8:55:33 PM5/16/10
to Crypto++ Users
On May 10, 8:13 am, "Zooko O'Whielacronx" <zoo...@gmail.com> wrote:
is happening too quickly.
> On Mon, May 10, 2010 at 4:06 AM, mgr_inz_Rafal <rchabow...@gmail.com> wrote:
> > The method takes from 3 to about 7 seconds to execute and the keys are
> > ready. I am not an crypto-expert but isn't it a little bit to quick to
> > create the 4096-bit long key pair?
>
> As far as I know, that is to be expected.
>
> I intend to solve the problem that I am having with this by switching
> from RSA to elliptic curve DSA.
>
> Regards,
>
> Zooko
> --
I think you misunderstood the question. He thinks RSA key generation
> > The method takes from 3 to about 7 seconds to execute and the keys are
> > ready. I am not an crypto-expert but isn't it a little bit to quick to
> > create the 4096-bit long key pair?
>
> As far as I know, that is to be expected.
>
> I intend to solve the problem that I am having with this by switching
> from RSA to elliptic curve DSA.
>
> Regards,
>
> Zooko
> --
is happening too quickly.
mgr_inz_Rafal
May 19, 2010, 2:11:46 PM5/19/10
to Crypto++ Users
Hello.
Thank you very much for an elaborate explanation... I therefore assume
that the RSA keys generated by Crypto++ in ~5 sec. would be of fair
quality to use in my solution.
However, is there a way to force Crypto++ to introduce some entropy in
key generation?
I use the library on Windows, which - as you explained - uses a
secret, closed-source approach. Maybe I can convince Crypto++ to
include some - I would say - hardware related randomness (disk space,
mouse position, etc.)?
Thank you very much for an elaborate explanation... I therefore assume
that the RSA keys generated by Crypto++ in ~5 sec. would be of fair
quality to use in my solution.
However, is there a way to force Crypto++ to introduce some entropy in
key generation?
I use the library on Windows, which - as you explained - uses a
secret, closed-source approach. Maybe I can convince Crypto++ to
include some - I would say - hardware related randomness (disk space,
mouse position, etc.)?
Wojciech S. Czarnecki
May 21, 2010, 3:21:45 PM5/21/10
to cryptop...@googlegroups.com
Dnia Wed, May 19, 2010 at 11:11:46AM -0700, mgr_inz_Rafal napisał(a):
> I use the library on Windows, which - as you explained - uses a
> secret, closed-source approach. Maybe I can convince Crypto++ to
> include some - I would say - hardware related randomness (disk space,
> mouse position, etc.)?
http://eprint.iacr.org/2007/419
> I use the library on Windows, which - as you explained - uses a
> secret, closed-source approach. Maybe I can convince Crypto++ to
> include some - I would say - hardware related randomness (disk space,
> mouse position, etc.)?
It mentions Win2000 but is confirmed upto Win XP Sp3.
Newer Microsoft OS PRNG implementation oficially has improwed since.
If your code is open sorced you may take a look at truecrypt windows
code for real example (though messy) code. If you will write your own,
remember that idea of 'random' os level events was born in truly multiuser
environment. Desktop PC/one user are far form being random.
Reading old but still sound RFC1750 may too help you.
--
Wojciech S. Czarnecki
<< ^oo^ >> OHIR-RIPE
Reply all
Reply to author
Forward
0 new messages