Efficient Modular Exponentiation Based on Multiple Multiplications by a Common Operand

Christophe Negre 1 Thomas Plantard 2 Jean-Marc Robert 1
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 : The main operation in RSA encryption/decryption is the modular exponentiation, which involves a long sequence of modular squarings and multiplications. In this paper, we propose to improve modular multiplications AB, AC which have a common operand. To reach this goal we modify the Montgomery modular multiplication in order to share common computations in AB and AC. We extend this idea to reduce the cost of multiple modular multiplications AB1,. .. , AB by the same operand A. We then take advantage of these improvements in the Montgomery-ladder and SPA resistant m-ary exponentiation algorithms. The complexity analysis shows that for an RSA modulus of size 2048 bits, the proposed improvements reduce the number of word operations (ADD and MUL) by 14% for the Montgomery-ladder and by 5%-8% for the m-ary exponentiations. Our implementations show a speed-up by 8%-14% for the Montgomery-ladder and by 1%-8% for the m-ary exponentiations for modulus of size 1024, 2048 and 4048 bits.
Type de document :
Communication dans un congrès
ARITH: Computer Arithmetic, Jun 2015, Lyon, France. IEEE 22nd Symposium on Computer Arithmetic, pp.144-151, 2015, <http://arith22.gforge.inria.fr>. <10.1109/ARITH.2015.24>
Liste complète des métadonnées


https://hal-lirmm.ccsd.cnrs.fr/lirmm-01142327
Contributeur : Jean-Marc Robert <>
Soumis le : mercredi 15 avril 2015 - 00:54:03
Dernière modification le : vendredi 9 juin 2017 - 10:42:08
Document(s) archivé(s) le : mardi 18 avril 2017 - 19:39:12

Fichier

exponentiation-with-optimized-...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Christophe Negre, Thomas Plantard, Jean-Marc Robert. Efficient Modular Exponentiation Based on Multiple Multiplications by a Common Operand. ARITH: Computer Arithmetic, Jun 2015, Lyon, France. IEEE 22nd Symposium on Computer Arithmetic, pp.144-151, 2015, <http://arith22.gforge.inria.fr>. <10.1109/ARITH.2015.24>. <lirmm-01142327>

Partager

Métriques

Consultations de
la notice

119

Téléchargements du document

159