Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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");
kpgDH.initialize(512);
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?

share|improve this question
    
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 –  Richie Frame Feb 7 at 20:15
1  
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. –  CPU Terminator Feb 7 at 21:53

1 Answer 1

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.

share|improve this answer
    
I'm pretty sure 128 should be replaced with 2^128. $\;$ –  Ricky Demer Feb 7 at 22:39
    
Right on, @RickyDemer -- thank you! Fixed. –  D.W. Feb 8 at 0:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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