ED25519 implementation speed issues

[trianglman]

In my work porting the python implementation of the ed25519 curve math into PHP, and especially in writing the unit tests for it, I have found that the one bottleneck of the code is the scalarmult function. I think this is mostly due to the depth of recursion that is required.

[roverwolf]

The main culprit seems to be the expmod function (which gets called indirectly from the scalarmult function).

[ghost]

Just for reference, someone has made a php-extension for this. So it might be wise to detect this and use it instead. It would mean making your API compatible with the extension of course. https://github.com/floodyberry/ed25519-donna Specifically this part: https://github.com/floodyberry/ed25519-donna/tree/master/fuzz which is the extension part.

There is also another extension based on the above: https://github.com/Novators/php-ext-sqrl

[ghost]

Also once you have this solved, I would separate it out as a separate library and composer project so others can use it.

[ghost]

I used the Xdebug profiler feature with phpStorm and it seems specifically the time is taken up by the bcpowmod() function, 98% of the script execution is taken by this function!!

[trianglman]

Yeah, that's what I found too. Unfortunately, I don't know of any way to get around using it or to call it less frequently.

[trianglman]

As for the other extensions, there are several that have been posted to the SQRL news group. I made the the signature validation object a thin wrapper over the PHP implementation with an interface in order to allow anyone using the library to use a more efficient validator if they have one available. With everything set IP to use dependency injection, its just a couple lines of configuration whichever way a user wants to go.

[sneurlax]

As mentioned in this StackOverflow answer, GMP (vs. BCMath) dramatically decreased run time for me:

GMP generated in 0.031516075134277s
Array
(
    [spendKey] => 5909a346d4e39d49681eda0be83f443d192f8d7edb8e2fc951beff0670530b00
    [viewKey] => 1823fd2ad6ce3aeb0296d916e952e4041ee4d31a3d1434edde6d999d35399f00
    [publicKey] => b75a3dd252c7194062e14741a66951b7688518dfd996407e0a3da71727bb8e6b
)
BCMath generated in 18.893861055374s
Array
(
    [spendKey] => 5909a346d4e39d49681eda0be83f443d192f8d7edb8e2fc951beff0670530b00
    [viewKey] => 1823fd2ad6ce3aeb0296d916e952e4041ee4d31a3d1434edde6d999d35399f00
    [publicKey] => b75a3dd252c7194062e14741a66951b7688518dfd996407e0a3da71727bb8e6b
)