Welcome to the resource topic for 2020/009
Title:
Efficient Elliptic Curve Operations On Microcontrollers With Finite Field Extensions
Authors: 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.
ePrint: https://eprint.iacr.org/2020/009
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .