carry-less multiplication optimization for ECC over GF(2^m) in MIRACL

Question

Link to MIRACL crypto library by CertiVox

Following the instructions in fastgf2m.txt, I've been able to get everything to compile. However, after execution, the benchmark (bmark.exe) program halts when evaluating curves over GF(2^m) with error, "This is not a point on the curve!"

I am able to get everything to work without the optimization but I'm unsure where the problem exists. I haven't modified any curve parameters and followed instructions in the distribution. I'm compiling on 64-bit Windows 8.1, on an Intel i7-3520M.

If anyone has any advice on how to correct this, it would be greatly appreciated.

Thanks!!

Answer 1

The method outlined in fastgf2m.txt is for generating unrolled code associated with a fixed m value determined at compile time. The bmark program changes m at runtime, and so the unrolled code will often not be correct in this case. The documentation could be clearer on this point.

Also make sure your processor does support the PCLMULQDQ instruction - many older processors will not.

It might be better to test the method on the ecsgen2/ecssign2/ecsver2 programs to implement ECDSA over GF(2^283) for example.