Efficient RNS Bases for Cryptography - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2005

Efficient RNS Bases for Cryptography

Jean-Claude Bajard
Nicolas Méloni
Thomas Plantard
  • Function : Author
  • PersonId : 860544

Abstract

Residue Number Systems (RNS) are useful for distributing large dynamic range computations over small modular rings, which allows the speed up of computations. This feature is well known, and already used in both DSP and cryptography. In this paper we deal with implementa- tion for huge numbers like those used for ciphering as with RSA or ECC on prime finite fields. Modular multiplication is the main operation of these protocols. We find very interesting modular multiplication algorithms in RNS where the conversion from an RNS basis to another represents the main part of the complexity. Hence, we propose in this paper an analysis of the criteria for selecting some bases giving efficient conversions. We conclude by giving methods for constructing an efficient basis in function of the size of different parameters like the basic operators, the key of the cryptosystem, etc. Residue Number Systems (RNS) are useful for distributing large dynamic range computations over small modular rings, which allows the speed up of computations. This feature is well known, and already used in both DSP and cryptography. In this paper we deal with implementation for huge numbers like those used for ciphering as with RSA or ECC on prime finite fields. Modular multiplication is the main operation of these protocols. We find very interesting modular multiplication algorithms in RNS where the conversion from an RNS basis to another represents the main part of the complexity. Hence, we propose in this paper an analysis of the criteria for selecting some bases giving efficient conversions. We conclude by giving methods for constructing an efficient basis in function of the size of different parameters like the basic operators, the key of the cryptosystem, etc.
Fichier principal
Vignette du fichier
D547.PDF (114.08 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00106470 , version 1 (16-10-2006)

Identifiers

  • HAL Id : lirmm-00106470 , version 1

Cite

Jean-Claude Bajard, Nicolas Méloni, Thomas Plantard. Efficient RNS Bases for Cryptography. 17th IMACS World Congress Scientific Computation, Applied Mathematics and Simulation, Jul 2005, Paris, France. ⟨lirmm-00106470⟩
188 View
2339 Download

Share

Gmail Mastodon Facebook X LinkedIn More