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 &lt; 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 &lt; num; i++) {

                keypair = keyPairGenerator.generateKeyPair();
            }

            long end = System.currentTimeMillis();

            long time = end - begin;

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

            num *= 2;
        }

    } catch (Exception e) {
        e.printStackTrace();
    }
}
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 &lt; 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 &lt; num; i ++) {
        generateKeyPair();
    }
    long end = System.currentTimeMillis();
    long time = end - begin;
    if (time &gt;= 2000) {
        System.out.printf("average keygen time: %.2f ms",
            (double)time / num);
        System.out.println();
        break;
    }
    num *= 2;
}