Efficient Fixed Base Exponentiation and Scalar Multiplication based on a Multiplicative Splitting Exponent Recoding

Jean-Marc Robert 1 Christophe Negre 1 Thomas Plantard 2
1 DALI - Digits, Architectures et Logiciels Informatiques
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, UPVD - Université de Perpignan Via Domitia
Abstract : Digital Signature Algorithm (DSA) (resp. ECDSA) involves modular exponentiation (resp. scalar multiplication) of a public and known base by a random one-time exponent. In order to speed-up this operation, well-known methods take advantage of the memorization of base powers (resp. base multiples). Best approaches are the Fixed-base Radix-R method and the Fixed-base Comb method. In this paper we present a new approach for storage/online computation trade-off, by using a multiplicative splitting of the digits of the exponent radix-R representation. We adapt classical algorithms for modular exponentiation and scalar multiplication in order to take advantage of the proposed exponent recoding. An analysis of the complexity for practical size shows that our proposed approach involves a lower storage for a given level of online computation. This is confirmed by implementation results showing significant memory saving, up to 3 times for the largest NIST standardized key sizes, compared to the state of the art approaches.
Type de document :
Article dans une revue
Journal of Cryptographic Engineering, Springer, In press, 〈10.1007/s13389-018-0196-7〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01926767
Contributeur : Christophe Negre <>
Soumis le : lundi 19 novembre 2018 - 14:27:21
Dernière modification le : mercredi 21 novembre 2018 - 01:16:25

Fichier

fixed-base-expo-and-scalar-mul...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Marc Robert, Christophe Negre, Thomas Plantard. Efficient Fixed Base Exponentiation and Scalar Multiplication based on a Multiplicative Splitting Exponent Recoding. Journal of Cryptographic Engineering, Springer, In press, 〈10.1007/s13389-018-0196-7〉. 〈lirmm-01926767〉

Partager

Métriques

Consultations de la notice

15

Téléchargements de fichiers

13