Paper 2020/009

Efficient Elliptic Curve Operations On Microcontrollers With Finite Field Extensions

Thomas Pornin

Abstract

In order to obtain an efficient elliptic curve with 128-bit security and a prime order, we explore the use of finite fields $GF(p^n)$, with $p$ a small modulus (less than $2^{16}$) and $n$ a prime. Such finite fields allow for an efficient inversion algorithm due to Itoh and Tsujii, which we can leverage to make computations on an ordinary curve (short Weierstraß equation) in affine coordinates. We describe a very efficient variant of Montgomery reduction for computations modulo $p$, and choose $p = 9767$ and $n = 19$ to better map the abilities of small microcontrollers of the ARM Cortex-M0+ class. Inversion cost is only six times the cost of multiplication. Our fully constant-time implementation of curve point multiplication runs in about 4.5 million cycles (only 1.29 times slower than the best reported Curve25519 implementations); it also allows for efficient key pair generation (about 1.9 million cycles) and Schnorr signature verification (about 5.6 million cycles). Moreover, we describe variants of the Itoh-Tsujii algorithms that allow fast computations of square roots and cube roots (in less than twenty times the cost of a multiplication), leading to efficient point compression and constant-time hash-to-curve operations with Icart's map.