I am working on an Android project for school and I am supposed to do a DHKE (Diffie Hellman Key Exchange). Everything works well. The problem is that it takes a lot of time (really a lot) to generate DHParameters. Basically, in my code, this is the part that is the most time (and battery) consuming:

KeyPairGenerator kpgDH = KeyPairGenerator.getInstance("DH");
KeyPair kpDH = kpgDH.generateKeyPair();

As you can see, the key length is only 512 bits, so it's not long, and it still takes at least 30-40 seconds (best case scenario), but it can go up to 400 seconds. I've tested it on several phones: Samsung Galaxy s2 (quad core), Samsung Galaxy s4 (quad core), Samsung Galaxy note 10.1 (quad core).

Does anybody know an alternative to generate more quickly the $p$ and $g$ for the Diffie-Hellman in order to speed up the process?

  • $\begingroup$ If you are generating new primes, they need to be tested for primality, which is very time consuming. It is best to do that once and save the prime, the private key is the one that is important to be different every time $\endgroup$ – Richie Frame Feb 7 '14 at 20:15
  • 1
    $\begingroup$ Try using ECDHE, much faster as the key sizes don't have to be as big and the curves are pre-generated. As a side note, number of cores won't help since everything is done on one thread. $\endgroup$ – initramfs Feb 7 '14 at 21:53

The standard solution is to generate $g$ and $p$ once during application development, then hardcode $g$ and $p$ in your code. There are standard choices for $p$ and $g$, e.g., documented by NIST in their FIPS series. I suggest using one of those. There is no need to re-generate $g$ or $p$ each time. You can use the same $g$ and $p$ for everyone. See also Is it safer to generate your own Diffie-Hellman primes or to use those defined in RFC 3526? for more details in this vein.

And make sure you use larger parameters. For security, I recommend that the prime $p$ should be at least 2048 bits long, and $g$ should generate a subgroup of size at least $2^{128}$ (or generate the whole group).

ECDHE will provide even better performance than Diffie-Hellman, but you can try the above first. Hardcoding the parameters should already make a huge difference.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.