Paper 2018/985

Efficient Arithmetic In (Pseudo-)Mersenne Prime Order Fields

Kaushik Nath and Palash Sarkar

Abstract

Elliptic curve cryptography requires efficient arithmetic over the underlying field. In particular, fast implementation of multiplication and squaring over the finite field is required for efficient projective coordinate based scalar multiplication as well as for inversion using Fermat’s little theorem. In the present work we consider the problem of obtaining efficient algorithms for field multiplication and squaring. From a theoretical point of view, we present a number of algorithms for multiplication/squaring and reduction which are appropriate for different settings. Our algorithms collect together and generalise ideas which are scattered across various papers and codes. At the same time, we also introduce new ideas to improve upon existing works. A key theoretical feature of our work, which is not present in previous works, is that we provide formal statements and detailed proofs of correctness of the different reduction algorithms that we describe. On the implementation aspect, a total of fourteen primes are considered, covering all previously proposed cryptographically relevant (pseudo-)Mersenne prime order fields at various security levels. For each of these fields, we provide 64-bit assembly implementations of the relevant multiplication and squaring algorithms targeted towards two different modern Intel architectures. We were able to find previous 64-bit implementations for six of the fourteen primes considered in this work. On the Haswell and Skylake processors of Intel, for all the six primes where previous implementations are available, our implementations outperform such previous implementations.

Note: Minor corrections.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
field multiplicationfield squaringreductioninversionconstant-time computationFermat’s little theoremelliptic curve cryptographyscalar multiplication
Contact author(s)
kaushikn_r @ isical ac in
palash @ isical ac in
History
2020-01-07: last of 3 revisions
2018-10-18: received
See all versions
Short URL
https://ia.cr/2018/985
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/985,
      author = {Kaushik Nath and Palash Sarkar},
      title = {Efficient Arithmetic In (Pseudo-)Mersenne Prime Order Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2018/985},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/985}},
      url = {https://eprint.iacr.org/2018/985}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.