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

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
elliptic curvecurve9767
Contact author(s)
thomas pornin @ nccgroup com
History
Short URL
https://ia.cr/2020/009

CC BY

BibTeX

@misc{cryptoeprint:2020/009,
author = {Thomas Pornin},
title = {Efficient Elliptic Curve Operations On Microcontrollers With Finite Field Extensions},
howpublished = {Cryptology ePrint Archive, Paper 2020/009},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/009}},
url = {https://eprint.iacr.org/2020/009}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.