4

I just generated Diffie-Hellman parameters and it seemed way too fast. The whole thing was over in under a second:

$ openssl dhparam -out /etc/ssl/certs/dhparam.pem 2048
This is going to take a long time
..............................................+.++*++*
$

I'm running on a relatively new ECS t2.medium instance (2 VCPU, 4GB RAM).

So I ran it again and this time it printed 5918 characters and took about 30 seconds.

What happened the first time?

1
  • I'd say you just got lucky the first time. It's the thing about randomness. Commented May 10, 2016 at 6:00

1 Answer 1

6

When creating Diffie Hellman parameters it takes the most time to create the modulo p, which is a big prime number. To create this, a semi-random number is taken and checked for primality. If you are lucky and you pick a prime number soon, the algorithm finishes quickly.

Specifically:

  • BN_generate_prime_ex calls probable_prime_dh_safe that takes a random number and checks whether it is divisable by the first 2048 primes. If it is, it takes another random number, etc. If it finds a likely prime, it prints a dot.
  • It calls BN_is_prime_fasttest_ex, which does the Miller–Rabin primality test. It prints a '+' if the tested value is prime.
  • It tests both p and (p-1)/2 this way, and prints a * if both are prime. It tests it a couple of times to be really sure. For 2048 bits, it checks it twice. That is why you see ++*++* on the end of the output.

It repeats these steps until it finds a number that is very likely to be prime. How many loops are necessary depends on chance.

Openssl docs

2
  • 1
    Is there any chance that there could be a flaw in EC2 or Xen that causes a well known prime to be found quickly? Commented May 10, 2016 at 17:34
  • 1
    Also, such a big cloud operator as Amazon could have patched the openssl library to outsource the dhparam generation to a mutualized resource (totally random guess here)
    – mveroone
    Commented Sep 2, 2016 at 13:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .