**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.

**Category / Keywords: **public-key cryptography / elliptic curve, curve9767

**Date: **received 3 Jan 2020

**Contact author: **thomas pornin at nccgroup com

**Available format(s): **PDF | BibTeX Citation

**Version: **20200106:083308 (All versions of this report)

**Short URL: **ia.cr/2020/009

[ Cryptology ePrint archive ]