International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Combining leak--resistant arithmetic for elliptic curves defined over $\F_p$ and RNS representation

Authors:
J.C. Bajard
S. Duquesne
M. Ercegovac
Download:
URL: http://eprint.iacr.org/2010/311
Search ePrint
Search Google
Abstract: In this paper we combine the residue number system (RNS) representation and the leak-resistant arithmetic on elliptic curves. These two techniques are relevant for implementation of elliptic curve cryptography on embedded devices.\\ % since they have leak-resistance properties. It is well known that the RNS multiplication is very efficient whereas the reduction step is costly. Hence, we optimize formulae for basic operations arising in leak-resistant arithmetic on elliptic curves (unified addition, Montgomery ladder) in order to minimize the number of modular reductions. We also improve the complexity of the RNS modular reduction step. As a result, we show how to obtain a competitive secured implementation.\\ Finally, %we recall the main advantages of the RNS representation, %especially in hardware and for embedded devices, and we show that, contrary to other approaches, ours takes optimally the advantage of a dedicated parallel architecture.
BibTeX
@misc{eprint-2010-23212,
  title={Combining leak--resistant arithmetic for elliptic curves defined over $\F_p$ and RNS representation},
  booktitle={IACR Eprint archive},
  keywords={implementation / ellicptic curves, leak resistance, RNS, arithmetic},
  url={http://eprint.iacr.org/2010/311},
  note={ sylvain.duquesne@univ-rennes1.fr 14754 received 25 May 2010},
  author={J.C. Bajard and S. Duquesne and M. Ercegovac},
  year=2010
}