PLEASE NOTE: The code I link to below has not yet been reviewed by anyone with professional cryptography experience. I expect that it contains bugs, and it is definitely not production-ready. I am still learning about the JCA; there are parts of the code I have not finished, and there are parts that I will most likely go back and redo. That said, the tests on example data are passing, so I think it is functional enough for testing.
I have been working on exactly this problem (I want to have a fast Ed25519 Java implementation for use in I2P). In our measurements, the original code was taking about 4 s s+v (one sign operation + one verify operation), which is much too slow for a router. I was able to speed up this implementation by a factor of twenty:
- The implementation is a direct port of the slow Python implementation, which had its own expmod method. Using
BigInteger.modPow() instead sped the code up by a factor of ten to 457 ms s+v.
- I2P has a
NativeBigInteger which provides access to libgmp's native modPow() implementation. Using NativeBigInteger.modPow() increased the speed to 289 ms s+v.
Neither of these changes have the constant-time property of the reference implementation of Ed25519 (I think - I am new to this), but then neither did the original.
After these changes, I decided to port DJB's ref10 C implementation from SUPERCOP to Java, to try and gain additional speed increases. (I also rewrote the entire thing to leverage the Java Cryptography Architecture.) The primary change here was in using extended coordinates for the twisted Edwards curve, which decreases the number of required operations.
The code in my branch takes about 20-22 ms s+v, which is about 190x faster than the original. There is no noticeable increase in speed when using NativeBigInteger; my hypothesis is that the use of extended coordinates has greatly decreased the number of modPow() calls, and the code is primarily limited by the speed of scalar multiplication.
I want to make the code even faster (to around 1-2 ms s+v). But I am not sure if there is much more that can be done to speed the code up without moving to a radix-2^51 representation of FieldElements and using tables precomputed from the base (as is done in ref10). I will test using libgmp for multiply() calls, and see if that helps. Another avenue would be to find a better algorithm for scalar multiplication.
(On a side note, I am also unsure if it is possible to use BigIntegers for constant-time operations on secrets. Then again, the only reason I stayed with BigIntegers was because I2P already packages native code in NativeBigInteger, and I would rather have a pure-Java implementation that could leverage libgmp than have to compile more native code for different platforms. If NativeBigInteger provides no speedup, then there is nothing stopping a move to something that does allow for constant-time operations on secrets.)
UPDATE (2014-04-28): I have now ported across the scalarmult and doublescalarmult methods from ref10 (including pre-computation), and it now takes ~2.1ms to run the signing code, and ~3ms to run the verifying code (on my laptop's 64-bit Core i7-U 1.9GHz; this falls directly between the sign and verify speeds for ECDSA_SHA384_P384 and ECDSA_SHA512_P521). But the results aren't correct yet, and I suspect the cause is hidden somewhere in my conversion from C's unsigned and signed bytes into Java's signed bytes and ints. I'm still working to understand the optimizations in ref10, and in particular which optimizations are necessary (like how ref10 uses bit arithmetic to execute cmov - I don't know Java or C intimately enough to know whether this is a) necessary over a switch() statement, and b) potentially where Java's lack of unsigned bytes could be causing bugs).
UPDATE (2014-05-05): The ported code was in fact correct, it was just being passed inputs that weren't correct. Additionally, I discovered two things:
- My timing code was still including the creation of a PrivateKey from a seed. The actual signing time was half what I thought (both key extraction and signing are limited by the time to run
scalarMultiply()).
- The constant-time
FieldElement.cmov() implementation (using XOR and AND) was taking 285ns to run, and scalarMultiply() calls it 1728 times. A huge speed increase is seen by changing GroupElement.cmov() to instead use return (b == 0) ? this : other.
Current timings:
1.0934 each sign, 3.0052 each verify, 4.0986 s+v (with constant-time cmov)0.6006 each sign, 2.9454 each verify, 3.546 s+v (with simple cmov)
For us, this is excellent signing speed. Int comparison on 32-bit architecture is constant-time, so the only unknown here is whether boolean ? val : val is constant-time or not. Then again, much of the rest of the code is not constant-time yet...
