ECDH VS. DH benchmarking in JAVA

So basically my problem is the odd result i get when measuring the time it takes to generate a ECDH key in java vs. the time it takes to generate a DH key.

I compare the time it takes to generate:

• 192bit ECDH-key to a 512bit DH-key
• 224bit ECDH-key to a 1024 DH-key

Now I expected the ECDH key pair generation to beat regular DH keys due to difference in key size, however that is not the case when I do it. Perhaps I'm measuring this wrong or is there another explanation.

    public void generateKeyPair() {

try {

keyfactory = KeyFactory.getInstance("ECDH");

keyPairGenerator = KeyPairGenerator.getInstance("ECDH", "BC");

//NIST EC-Curve P-224"
org.bouncycastle.jce.spec.ECParameterSpec ecSpec = ECNamedCurveTable.getParameterSpec(EllipticCurveDiffieHellman.curveNames.get(new Integer(224)));

keyPairGenerator.initialize(ecSpec, new SecureRandom());

int num = 10;

/* Warm up */
for (int wRound = 0; wRound < 200; wRound++) {
keyPairGenerator.generateKeyPair();
}

/*
* Finding the right number of iterations such that we iterate for
* at least 2s
*/
for (;;) {

long begin = System.currentTimeMillis();

for (int i = 0; i < num; i++) {

keypair = keyPairGenerator.generateKeyPair();
}

long end = System.currentTimeMillis();

long time = end - begin;

if (time >= 2000) {
System.out.printf("Average keygen time: %.2f ms\n",
(double) time / num);
break;
}

num *= 2;
}

} catch (Exception e) {
e.printStackTrace();
}
}

-
Sorry but none of us know how to program, at least that is the assumption you should be going with when posting on Crypto SE. It is likely questions with large amounts of code are better suited on StackOverflow or Security SE, and it is the case here. That said, I suppose the time difference is due to the fact that generating an ECDH key isn't as easy as selecting a random prime, you need to perform some setup operations, likely more than in DH (or maybe your KeyPairGenerator is slow, but that's out of our control). – Thomas Feb 2 '13 at 9:15
Generating a keypair is simply a scalar multiplication for ECDH and a modular exponentiation for DH, both with fixed base point (allows some speedup if the implementation takes advantage of that). | @Thomas You don't need to select a random prime for either of them. Selecting prime is part of group generation, not of keypair generation. – CodesInChaos Feb 2 '13 at 9:17
Which curves are you using for ECDH? Fast ECC implementations need to be optimized for the specific curve you're working on. Perhaps the curves you're working on aren't well optimized in your ECC library. – CodesInChaos Feb 2 '13 at 9:20
@CodesInChaos Thanks for the correction, not very literate in ECC. Still, I think the question should be rewritten to ask for theoretical differences in performance (based on the algorithms themselves and not a black-box implementation) to be on topic. – Thomas Feb 2 '13 at 9:21
You should generate many keypairs (such as 1000 or 10k) in a loop. Else startup code, JIT cost etc. might dominate the actual generation cost. You also forgot to describe your performance results. How fast are your four measurements? – CodesInChaos Feb 2 '13 at 9:31

Generating an (EC)DH key pair entails "producing" the group parameters (the curve or the modulus+generator), then the private key $x$, (a random integer modulo the group order $q$), and then applying the private key to the generator (i.e. computing $xG$ on the curve, $g^x \mod p$ for plain DH). Producing new group parameters would be the most expensive operation, especially for elliptic curves; however, there is no security issue in reusing the same group parameters for several key pairs.

Most ECDH implementation focus on a handful of standard curves (a subset of the 15 FIPS curves) and never generate new ones. Generating new group parameters for DH is quite easier, but still expensive, which is why some implementations just reuse a few pre-generated parameters. Thus, the remaining operations for (EC)DH key pair generation are fast; we are in the milliseconds range.

Your code for measuring generation time fails to take into account the idiosyncrasies of Java. The first time an application accesses a class, it must load that class, which entails locating it in the Jar archives, reading it from disk, uncompressing it, decoding the class file format, and launching the initialization code for that class, which may do a lot of expensive things. Then, for each method, the first call to the method triggers the verification which is a flow analysis by which the JVM makes sure that the code complies to the Java typing rules. Finally, the first few invocations of the method will use interpretation; only methods which are invoked sufficiently many times will be translated to efficient native code (this is known as "JIT compilation").

All this translates to the following: to benchmark Java code, you must allow for some considerable "warm up". Also, you will want to run the code several times in a loop so as to get an average execution time because any single invocation can be substantially delayed in case, for instance, of a garbage collector run (the JVM aims at perceived smooth execution, but human beings do not perceive hiccups below about 20ms). So your benchmark code should look like this:

/* warm-up */
for (int i = 0; i < 200; i ++) {
generateKeyPair();
}

/* find the right number of loop iterations such that we loop for at
least two seconds */
int num = 10;
for (;;) {
long begin = System.currentTimeMillis();
for (int i = 0; i < num; i ++) {
generateKeyPair();
}
long end = System.currentTimeMillis();
long time = end - begin;
if (time >= 2000) {
System.out.printf("average keygen time: %.2f ms",
(double)time / num);
System.out.println();
break;
}
num *= 2;
}

-
Cheers Thomas!:) This was indeed enlightning. – Nyfiken Feb 3 '13 at 16:53
I find this really strange, ECDH (224bit) keygen takes approx: ~7ms while DH (1024bit) takes approx: ~3 ms. Now, i would expect that java's standard security lib uses some (as Thomas mentioned) predefined curves for respective keysizes. Even though finding any info regarding this seems impossible. – Nyfiken Feb 3 '13 at 18:24
What's strange is that my own EC code, written in pure Java, takes about 1 ms for such an operation, on the NIST P-224 curve. This might be a case of sloppy coding, which is surprising since Sun themselves wrote the EC code for OpenSSL, and they invented Java, so chances are that they know what they are doing. – Thomas Pornin Feb 3 '13 at 22:05
I might be doing something wrong, and if so im dont have the slightest clue to what it is. I find it unlikely that th Sun library is the problem. Just for the sake of it i poste the revised code again. – Nyfiken Feb 5 '13 at 15:54

I made sure I used the java (Sun) implementation in Java 7 and tried these different generators:

EC:

keyPairGenerator = KeyPairGenerator.getInstance("EC");
ECGenParameterSpec spec = new ECGenParameterSpec("secp224r1");
keyPairGenerator.initialize(spec, new SecureRandom());


DH:

keyPairGenerator = KeyPairGenerator.getInstance("DH");
keyPairGenerator.initialize(1024, new SecureRandom());


These give me results:

EC: 0.83ms (constantly the same value)
DH: 2.00ms (this fluctuates by max 0.1 ms for each run)

That makes EC more than twice as fast as Diffe-Hellman.

For fun I clocked RSA, which took $\approx$58 ms.

Using BC with the same parameters, I get 6-7 ms for EC, and around 3ms for DH.

This should prove that the issue lies with the bouncy castle implementation.

EDIT:

I should mention that I use JDK 7.0, since 6.0 and earlier don't ship with a built-in EC implementation.

-
BC uses affine coordinates (at least the implementation I looked at, perhaps it offers multiple), which are really slow for most curves. Optimized implementations should be 10-20 times as fast as BC. – CodesInChaos Jul 2 '13 at 19:01
FWIW, NIST rates ECC-224 as similar strength of DH-2048, and other authorities (excluding the oldest) at www.keylength.com range up to 3154, which presumably further increases the ECC advantage. – dave_thompson_085 Jul 10 '15 at 10:29
Java is a bad language for crypto, since it does not give access to machine-dependent features like SIMD. Better to call out to native code by JNI (but OpenJDK does not do this for some reason). – Demetri May 22 at 4:32