Fast Multiplication in Binary Fields on ARMv8 Processors

Efficient algorithms performing binary field operations are often required in cryptography such as for digital signatures on binary elliptic curves. The most important operation that affects the performance of such algorithms is the multiplication since most microprocessors do not support instruction sets to carry out polynomial multiplications. This paper describes a new multi-layer algorithm for the multiplication of two polynomials in binary field. This algorithm combines the Karatsuba algorithm, the 128-bit and the 192-bit multipliers on 32-bit (AArch32) and 64-bit (AArch64) ARMv8 processors. The paper illustrates the performance improvement of using multi-layer algorithm in ECDSA, ECDH, ECMQV cryptographic primitives on the curves NIST_B283, NIT_B409 and NIST_B571. Our evaluation results showed that the proposed algorithm is 4, 5 and 5 times faster than the corresponding previous techniques in GF(2
²⁸³
), GF(2
⁴⁰⁹
) and GF(2
⁵⁷¹
) while being executed on the same hardware as Samsung Galaxy Tab S2 (AArch32) or IMX8M Kit (AArch64).