cryptography - How long does it take to generate large prime numbers? -

using c implementation of bigint without assembly, sse etc. running on 2ghz dual core pentium laptop; average time 1 should expect prime number created in?

is normal primes greater 512 bits take 30 seconds?

what 2048, 4096 bits etc.?

from security stackexchange question 56214

i generated custom diffie hellmann parameters long (in below case 4096 bit) primes.
generation took 2 hours cannot >generated on fly........

is typical ? - 2 hours generate 4096 bit key ...

no, 4 hours not typical.

generation of large random primes depends on following:

1. the speed , entropy within random number generator
2. the used algorithm test candidates primality
3. the implementation
4. and luck

the random number generator used important. long term keys may require random bit generator contains large amount of entropy. can achieved accessing e.g. /dev/random on linux operating systems, instance. there 1 unfortunate problem: /dev/random may block until sufficient entropy gathered. depending on system can fast or very slow.

now, second algorithm. when generating new dh parameters method generate called safe prime used. generating safe primes much harder generating number probable prime. however, prime used dh parameters not key pair itself. generating safe prime not needed; can used set of pre-calculated or named parameters.

the implementation can make bit of difference well. although won't change order of complexity, may still influence result if implementation thousand times slower fast implementation. these kind of differences not unheard of within cryptography; slow, interpreted language may slower hardware accelerated version, or version directly running using vector instructions of cpu or indeed gpu.

furthermore, way see if number prime test number. there no deterministic method of generating primes. problem although there many, many primes available, can still take long time find one. luck factor comes in: first number test prime, can run through oodles of numbers before finding one. in end runtime of procedure indeterministic.

---

for c program, generating safe prime of 4096 bits in on 2 hours seems bit much. however, if runs old cpu, without sse, not mean fundamentally wrong. however, taking 30 seconds 512 bit prime very long. openssl command line takes between 0.015 (lucky) , 1.5 (unlucky) seconds on laptop (but that's core i7).

---

notes:

• rsa requires 2 primes half key size, , these not safe primes. generating dh key pair (with new parameters) take much longer generating rsa key pair of same size.
• if possible try use predefined dh parameters. unfortunately openssl command line doesn't seem support named dh parameters; supported dsa key pairs.
• if want speed, try elliptic curve dh predefined parameters. generating key fast generating 256 random bits (for p-256 curve, instance). , until quantum crypto comes off age, keys stronger dh keys on top of it.