2023
Article dans une revue
-
- titre
- PMNS for Cryptography : A Guided Tour
- auteur
- Nicolas Méloni, François Palma, Pascal Véron
- article
- Advances in Mathematics of Communications, In press, ⟨10.3934/amc.2023033⟩
- resume
- The Polynomial Modular Number System (PMNS) offers an alternative to the conventional binary multi-precision representation system for large integers. Its effectiveness has been demonstrated for various cryptosystems using prime field arithmetic [2, 4, 6], with prime sizes ranging from 256 to 736 bits. However, as the size of p increases, the relative performance of PMNS compared to standard arithmetic diminishes. Furthermore, the generation process of a PMNS has a worst-case complexity of O(2 n), where n denotes the number of symbols used to represent an integer modulo p in this representation system. In this paper, we present several alternatives and improvements to the construction and implementation processes of PMNS, which are tailored to the size of p.
- typdoc
- Article dans une revue
- DOI
- DOI : 10.3934/amc.2023033
- Accès au texte intégral et bibtex
-
Chapitre d'ouvrage
-
- titre
- New Versions of Miller-loop Secured against Side-Channel Attacks
- auteur
- Nadia El Mrabet, Loubna Ghammam, Nicolas Méloni, Emmanuel Fouotsa
- article
- Arithmetic of Finite Fields, 13638, Springer International Publishing, pp.269-287, 2023, Lecture Notes in Computer Science, ⟨10.1007/978-3-031-22944-2_17⟩
- resume
- In this paper, we propose two new versions of Miller algorithm in order to secure pairing computations against existing side-channel attacks (SCA). We have chosen to use the co-Z arithmetic on elliptic curves from which we derive two methods for pairing computations: one based on Euclidean addition chains and one based on Zeckendorf representation. We show that our propositions are resistant to existing side-channel attacks against pairing-based cryptography. We consider differential power analysis and fault attacks. The complexities of our solutions are compared with state-of-the-art one. We demonstrate that our new proposed versions are more efficient by 17%.
- typdoc
- Chapitre d'ouvrage
- DOI
- DOI : 10.1007/978-3-031-22944-2_17
- Accès au texte intégral et bibtex
-
2022
Article dans une revue
-
- titre
- An Alternative Approach to Polynomial Modular Number System Internal Reduction
- auteur
- Nicolas Méloni
- article
- IEEE Transactions on Emerging Topics in Computing, 2022, ⟨10.1109/TETC.2022.3190368⟩
- resume
- The Polynomial Modular Number System (PMNS) is an alternative to the binary multi-precision representation that allows to transport the arithmetic of a finite field to a polynomial ring. The most important operation in that system is the internal reduction that follows any arithmetic operation. All recent works on the subject use the same algorithm derived from Montgomery's modular multiplications to perform this internal reduction. This paper designs and analyzes two new algorithms to perform the internal reduction, both based on Babai's Closest Vector algorithms. It allows to significantly reduce the number of additions needed to perform this operation. A comprehensive experimental analysis shows that one of those algorithms is also faster in practice. For that matter, a C code generation tool has been developed in order to produce implementations for any prime number field.
- typdoc
- Article dans une revue
- DOI
- DOI : 10.1109/TETC.2022.3190368
- Accès au texte intégral et bibtex
-
2021
Communication dans un congrès
-
- titre
- Compact variable-base ECC scalar multiplication using Euclidean addition chains
- auteur
- Fabien Herbaut, Nicolas Méloni, Pascal Véron
- article
- 18th International Conference on Security and Cryptography (SECRYPT 2021), Jul 2021, Online Event, Italy. pp.531-539, ⟨10.5220/0010551705310539⟩
- resume
- The random generation of Euclidean addition chains fits well with a GLV context (Dosso et al., 2018) and provides a method with decent performance despite the growth of the base field required to get the same level of security. The aim of this paper is to reduce the size of the base field required. Combined with an algorithmic improvement, we obtain a reduction of 21% of the memory usage. Hence, our method appears to be one of the most compact scalar multiplication procedure and is particularly suitable for lightweight applications.
- typdoc
- Communication dans un congrès
- DOI
- DOI : 10.5220/0010551705310539
- Accès au texte intégral et bibtex
-
2018
Article dans une revue
-
- titre
- Euclidean addition chains scalar multiplication on curves with efficient endomorphism
- auteur
- Fangan-Yssouf Dosso, Fabien Herbaut, Nicolas Méloni, Pascal Véron
- article
- Journal of Cryptographic Engineering, In press, ⟨10.1007/s13389-018-0190-0⟩
- resume
- Random Euclidean addition chain generation has proven to be an efficient low memory and SPA secure alternative to standard ECC scalar multiplication methods in the context of fixed base point [21]. In this work, we show how to generalize this method to random point scalar multiplication on elliptic curves with an efficiently computable endomorphism. In order to do so we generalize results from [21] on the relation of random Euclidean chains generation and elliptic curve point distribution obtained from those chains. We propose a software implementation of our method on various platforms to illustrate the impact of our approach. For that matter, we provide a comprehensive study of the practical computational cost of the modular multiplication when using Java and C standard libraries developed for the arithmetic over large integers.
- typdoc
- Article dans une revue
- DOI
- DOI : 10.1007/s13389-018-0190-0
- Accès au texte intégral et bibtex
-
2017
Communication dans un congrès
- titre
- Utilisation de chaines d'additions euclidiennes pour la multiplication scalaire sur des courbes elliptiques munies d'endomorphismes efficaces.
- auteur
- Fangan-Yssouf Dosso, Fabien Herbaut, Nicolas Méloni, Pascal Véron
- article
- Journées Codage et Cryptographie 2017, Apr 2017, La Bresse, France
- typdoc
- Communication dans un congrès
- Accès au bibtex
-
2016
Communication dans un congrès
-
- titre
- Random Digit Representation of Integers
- auteur
- Nicolas Méloni, M. Anwar Hasan
- article
- ARITH 23, Jul 2016, San Francisco, United States
- resume
- —Modular exponentiation, or scalar multiplication , is core to today's main stream public key cryptographic systems. In this article we generalize the classical fractional wNAF method for modular exponentiation-the classical method uses a digit set of the form {1, 3,. .. , m} which is extended here to any set of odd integers of the form {1, d2,. .. , dn}. We propose a general modular exponentiation algorithm based on a generalization of the frac-wNAF recoding and a new precomputation scheme. We also give general formula for the average density of non-zero therms in these representations, prove that there are infinitely many optimal sets for a given number of digits and show that the asymptotic behavior, when those digits are randomly chosen, is very close to the optimal case.
- typdoc
- Communication dans un congrès
- Accès au texte intégral et bibtex
-
2015
Article dans une revue
-
- titre
- Efficient Double Bases for Scalar Multiplication
- auteur
- Nicolas Méloni, M. A. Hasan
- article
- IEEE Transactions on Computers, 2015, 64 (8), pp.2204-2212. ⟨10.1109/TC.2014.2360539⟩
- resume
- In this paper we present efficient algorithms to take advantage of the double-base number system in the context of elliptic curve scalar multiplication. We propose a generalized version of Yao's exponentiation algorithm allowing the use of general double-base expansions instead of the popular double base chains. We introduce a class of constrained double base expansions and prove that the average density of non-zero terms in such expansions is $O\left(\frac{\log k}{\log \log k}\right)$ for any large integer $k$. We also propose an efficient algorithm for computing constrained expansions and finally provide a comprehensive comparison to double-base chain expansions, including a large variety of curve shapes and various key sizes.
- typdoc
- Article dans une revue
- DOI
- DOI : 10.1109/TC.2014.2360539
- Accès au texte intégral et bibtex
-
Communication dans un congrès
-
- titre
- Full Hardware Implementation of Short Addition Chains Recoding for ECC Scalar Multiplication
- auteur
- Julien Proy, Nicolas Veyrat-Charvillon, Arnaud Tisserand, Nicolas Méloni
- article
- Compas: Conférence d’informatique en Parallélisme, Architecture et Système, Jun 2015, Lille, France
- resume
- Ensuring uniform computation profiles is an efficient protection against some side channel attacks (SCA) in embedded systems. Typical elliptic curve cryptography (ECC) scalar multiplication methods use two point operations (addition and doubling) scheduled according to secret scalar digits. Euclidean addition chains (EAC) offer a natural SCA protection since only one point operation is used. Computing short EACs is considered as a very costly operation and no hardware implementation has been reported yet. We designed an hardware recoding unit for short EACs which works concurrently to scalar multiplication. It has been integrated in an in-house ECC processor on various FPGAs. The implementation results show similar computation times compared to non-protected solutions, and faster ones compared to typical protected solutions (e. g. 18 % speed-up over 192 b Montgomery ladder).
- typdoc
- Communication dans un congrès
- Accès au texte intégral et bibtex
-
2012
Article dans une revue
- titre
- Block Recombination Approach for Subquadratic Space Complexity Binary Field Multiplication based on Toeplitz Matrix-Vector Product
- auteur
- Anwar Hasan, Nicolas Méloni, Ashkan Hosseinzadeh Namin, Christophe Negre
- article
- IEEE Transactions on Computers, 2012, 61 (2), pp.151-163. ⟨10.1109/TC.2010.276⟩
- resume
- In this paper, we present a new method for parallel binary finite field multiplication which results in subquadratic space complexity. The method is based on decomposing the building blocks of the Fan-Hasan subquadratic Toeplitz matrix-vector multiplier. We reduce the space complexity of their architecture by recombining the building blocks. In comparison to other similar schemes available in the literature, our proposal presents a better space complexity while having the same time complexity. We also show that block recombination can be used for efficient implementation of the GHASH function of Galois Counter Mode (GCM).
- typdoc
- Article dans une revue
- DOI
- DOI : 10.1109/TC.2010.276
- Accès au bibtex
-
2011
Article dans une revue
- titre
- High performance GHASH and impacts of a class of unconventional bases
- auteur
- Nicolas Méloni, Christophe Negre, Anwar Hasan
- article
- Journal of Cryptographic Engineering, 2011, 1 (3), pp.201-218. ⟨10.1007/s13389-011-0013-z⟩
- resume
- This work presents a new method to compute the GHASH function involved in the Galois/Counter Mode of operation for block ciphers. If $X= X_1\dots X_n$ is a bit string made of $n$ blocks of 128 bits each, then the GHASH function essentially computes $X_1H^n + X_2H^{n-1} + \cdots+ X_nH$, where $H$ is the hash key and an element of the binary field $\Fd_{2^{128}}$. This operation is usually computed by using $n$ successive multiply-and-add operations over $\Fd_{2^{128}}$. Our proposed method replaces all but a fixed number of those multiplications by additions on the field. This is achieved by using the characteristic polynomial of $H$. We present both how to use this polynomial to speed up the GHASH function and how to efficiently compute it for each session that uses a new $H$. We also show that the proposed technique can be parallelized to compute GHASH even faster. In order to try to completely eliminate the need for a field multiplication, we investigate a different set of bases for the field element representation and report their architectural and possible security impacts.
- typdoc
- Article dans une revue
- DOI
- DOI : 10.1007/s13389-011-0013-z
- Accès au bibtex
-
2010
Communication dans un congrès
-
- titre
- Random Euclidean Addition Chain Generation and Its Application to Point Multiplication
- auteur
- Fabien Herbaut, Pierre-Yvan Liardet, Nicolas Méloni, Yannick Teglia, Pascal Véron
- article
- INDOCRYPT 2010, Dec 2010, Hyderabad, India. pp.238-261, ⟨10.1007/978-3-642-17401-8_18⟩
- resume
- Efficiency and security are the two main objectives of every elliptic curve scalar multiplication implementations. Many schemes have been proposed in order to speed up or secure its computation, usually thanks to efficient scalar representation [30,10,24], faster point operation formulae [8,25,13] or new curve shapes [2]. As an alternative to those general methods, authors have suggested to use scalar belonging to some subset with good computational properties [15,14,36,41,42], leading to faster but usually cryptographically weaker systems. In this paper, we use a similar approach. We propose to modify the key generation pro- cess using a small Euclidean addition chain c instead of a scalar k. This allows us to use a previous scheme, secure against side channel attacks, but whose efficiency relies on the computation of small chains computing the scalar. We propose two different ways to generate short Euclidean addition chains and give a first theoretical analysis of the size and dis- tribution of the obtained keys. We also propose a new scheme in the context of fixed base point scalar multiplication.
- typdoc
- Communication dans un congrès
- DOI
- DOI : 10.1007/978-3-642-17401-8_18
- Accès au texte intégral et bibtex
-
-
- titre
- High Performance GHASH Function for Long Messages
- auteur
- Nicolas Méloni, Christophe Negre, M. Anwar Hasan
- article
- ACNS: Applied Cryptography and Network Security, 2010, Beijing, China. pp.154-167, ⟨10.1007/978-3-642-13708-2_10⟩
- resume
- This work presents a new method to compute the GHASH function involved in the Galois/Counter Mode of operation for block ciphers. If $X= X_1\dots X_n$ is a bit string made of $n$ blocks of 128 bits each, then the GHASH function effectively computes $X_1H^n + X_2H^{n-1} + \dots X_nH$, where $H$ is an element of the binary field $\Fd_{2^{128}}$. This operation is usually computed by using $n$ successive multiply-add operations over $\Fd_{2^{128}}$. In this work, we propose a method to replace all but a fixed number of those multiplications by additions on the field. This is achieved by using the characteristic polynomial of $H$. We present both how to use this polynomial to speed up the GHASH function and how to efficiently compute it for each session that uses a new $H$.
- typdoc
- Communication dans un congrès
- DOI
- DOI : 10.1007/978-3-642-13708-2_10
- Accès au texte intégral et bibtex
-
2009
Communication dans un congrès
- titre
- Chaînes d'addition euclidienne et logarithme discret
- auteur
- Fabien Herbaut, Nicolas Méloni, Pascal Véron
- article
- Journées C2, Oct 2009, Fréjus, France
- typdoc
- Communication dans un congrès
- Accès au bibtex
-
-
- titre
- Elliptic Curve Point Scalar Multiplication Combining Yao's Algorithm and Double Bases
- auteur
- Nicolas Méloni, M. A. Hasan
- article
- Cryptographic Hardware and Embedded Systems - CHES 2009- 11th international workshop, Sep 2009, Lausanne, Switzerland. pp.304--316, ⟨10.1007/978-3-642-04138-9_22⟩
- resume
- In this paper we propose to take one step back in the use of double base number systems for elliptic curve point scalar multiplication. Using a modified version of Yao's algorithm, we go back from the popular double base chain representation to a more general double base system. Instead of representing an integer $k$ as $\sum^n_{i=1}2^{b_i}3^{t_i}$ where $(b_i)$ and $(t_i)$ are two decreasing sequences, we only set a maximum value for both of them. Then, we analyze the efficiency of our new method using different bases and optimal parameters. In particular, we propose for the first time a binary/Zeckendorf representation for integers, providing interesting results. Finally, we provide a comprehensive comparison to state-of-the-art methods, including a large variety of curve shapes and latest point addition formulae speed-ups.
- typdoc
- Communication dans un congrès
- DOI
- DOI : 10.1007/978-3-642-04138-9_22
- Accès au texte intégral et bibtex
-
2007
Article dans une revue
-
- titre
- Comparison of Simple Power Analysis Attack Resistant Algorithms for an Elliptic Curve Cryptosystem
- auteur
- Andrew Byrne, Nicolas Méloni, Arnaud Tisserand, Emanuel Popovici, William P. Marnane
- article
- Journal of Computers (JCP), 2007, 2 (10), pp.52-62. ⟨10.4304/jcp.2.10.52-62⟩
- resume
- There has been a lot of interest in recent years in the problems faced by cryptosystems due to side channel attacks such as Simple Power Analysis (SPA) attacks. Algorithms for elliptic curve point scalar multiplication such as the double and add method are prone to these attacks. The protected double and add algorithm provides a simple solution to this problem but is costly in terms of performance. Another class of algorithm for point scalar multiplication that makes use of special addition chains can be used to protect against SPA attacks. A reconfigurable architecture for a cryptographic processor is presented and a number of algorithms for point multiplication are implemented and compared. These algorithms have a degree of parallelism within their operations where a number of multiplications can be executed in parallel. Sophisticated scheduling techniques can exploit this parallelism in order to optimize the performance of the calculation. Post place and route results for the processor are given.
- typdoc
- Article dans une revue
- DOI
- DOI : 10.4304/jcp.2.10.52-62
- Accès au texte intégral et bibtex
-
-
- titre
- SPA Resistant Elliptic Curve Cryptosystem Using Addition Chains
- auteur
- Andrew Byrne, Francis Crowe, William P. Marnane, Nicolas Méloni, Arnaud Tisserand, Emanuel Popovici
- article
- International Journal of High Performance Systems Architecture (IJHPSA), 2007, 1 (2), pp.133-142. ⟨10.1504/IJHPSA.2007.015399⟩
- resume
- There has been a lot of interest in recent years in the problems faced by cryptosystems due to side channel attacks. Algorithms for elliptic curve point scalar multiplication such as the double-and-add method are prone to such attacks. By making use of special addition chains, it is possible to implement a Simple Power Analysis (SPA) resistant cryptosystem. In this paper, a reconfigurable architecture for a cryptographic processor is presented. A SPA resistant algorithm for point multiplication is implemented and is shown to be faster than the double-and-add method. Post place and route results for the processor are given.
- typdoc
- Article dans une revue
- DOI
- DOI : 10.1504/IJHPSA.2007.015399
- Accès au texte intégral et bibtex
-
Communication dans un congrès
-
- titre
- New Point Addition Formulae for ECC Applications
- auteur
- Nicolas Méloni
- article
- WAIFI: Workshop on the Arithmetic of Finite Fields, Jun 2007, Madrid, Spain. pp.189-201, ⟨10.1007/978-3-540-73074-3_15⟩
- resume
- In this paper we propose a new approach to point scalar multiplication on elliptic curves defined over fields of characteristic greater than 3. It is based on new point addition formulae that suit very well to exponentiation algorithms based on Euclidean addition chains. However finding small chains remains a very difficult problem, so we also develop a specific exponentiation algorithm, based on Zeckendorf representation (i.e. representing the scalar $k$ using Fibonacci numbers instead of powers of 2), which takes advantage of our formulae.
- typdoc
- Communication dans un congrès
- DOI
- DOI : 10.1007/978-3-540-73074-3_15
- Accès au texte intégral et bibtex
-
-
- titre
- SPA Resistant Elliptic Curve Cryptosystem using Addition Chains
- auteur
- Andrew Byrne, Nicolas Méloni, Francis Crowe, William P. Marnane, Arnaud Tisserand, Emanuel Popovici
- article
- ITNG'07: 4th International Conference on Information Technology, Apr 2007, Las Vegas, Nevada, U.S.A., pp.995-1000, ⟨10.1109/ITNG.2007.185⟩
- resume
- There has been a lot of interest in recent years in the problems faced by cryptosystems due to side channel attacks. Algorithms for elliptic curve point scalar multiplication such as the double and add method are prone to such attacks. By making use of special addition chains, it is possible to implement a Simple Power Analysis (SPA) resistant cryptosystem. In this paper a reconfigurable architecture for a cryptographic processor is presented. A SPA resistant algorithm for point multiplication is implemented and is shown to be faster than the double-and-add method. Post place and route results for the processor are given.
- typdoc
- Communication dans un congrès
- DOI
- DOI : 10.1109/ITNG.2007.185
- Accès au texte intégral et bibtex
-
Thèse
-
- titre
- Arithmetic for Cryptography based on Elliptic Curves
- auteur
- Nicolas Méloni
- article
- Cryptographie et sécurité [cs.CR]. Université de Montpellier 2, 2007. Français. ⟨NNT : ⟩
- resume
- Dans cette thèse, nous nous intéressons au problème de l'implantation de la multiplication de point par un scalaire sur les courbes elliptiques définies sur des corps premiers. Nous abordons ce problème aussi bien au niveau des algorithmes de multiplication de points, que de l'arithmétique de la courbe ou du corps sous-jacent. L'originalité des travaux présentés ici est qu'ils ne traitent pas de chaque aspects séparément. En effet nous avons toujours cherché à développer l'arithmétique à un niveau donné en gardant à l'esprit son lien avec les niveaux inférieurs ou supérieurs. La présente thèse compose de trois parties. La première partie est consacré à l'état de l'art concernant l'arithmétique des courbes elliptiques. Le chapitre 1 est un tour d'horizon des principales propriétés des courbes elliptiques et des différentes formules d'addition de points selon le système de coordonnées choisi. Dans le chapitre 2, nous présentons les principales méthodes de multiplication de points par un scalaire, aussi bien pour les courbes définies sur des corps premiers que pour les courbes définies sur des corps binaires. La deuxième partie a pour objet l'étude de nouvelles formules d'addition de points sur les courbes et les nouveaux algorithmes de multiplication de points que l'on peut en déduire. Le chapitre 3 détaille les nouvelles formules d'addition de points, ainsi que l'algorithme dit de "Fibonacci" et addition. Dans le chapitre 4 nous présentons un type de chaînes d'additions, les chaînes d'additions différentielles, naturellement adaptées aux formules introduites dans le chapitre précédent, puis, nous proposons une construction de chaînes particulières, afin d'en déduire un algorithme de multiplication de point le plus efficace possible. La troisième partie traite de la représentation RNS et de son adaptation à l'arithmétique des courbes elliptiques. Dans le chapitre 5 nous faisons un rappel des propriétés principale de la représentation RNS. Nous proposons, dans le chapitre 6, des bases RNS particulières permettant d'améliorer l'efficacité des calculs. Ensuite, dans le chapitre 7, nous proposons un algorithme d'inversion modulaire en RNS. Enfin, le chapitre 8 est consacré à l'étude de la complexité des sommes de produits modulaires en fonction du système de représentation choisi, puis à l'aménagement des formules d'additions de points sur les courbes afin de tirer avantages des spécificité du RNS.
- typdoc
- Thèse
- Accès au texte intégral et bibtex
-
2006
Communication dans un congrès
-
- titre
- Residue systems efficiency for modular products summation: Application to Elliptic Curves Cryptography
- auteur
- Jean-Claude Bajard, Sylvain Duquesne, Milos Ercegovac, Nicolas Méloni
- article
- Proceedings of SPIE : Advanced Signal Processing Algorithms, Architectures, and Implementations XVI, Aug 2006, pp.0
- resume
- Residue systems of representation, like Residue Number Systems (RNS) for primary field($GF (p)$) or Trinomial Residue Arithmetic for binary field ($GF (2^k )$), are characterized by efficient multiplication and costly modular reduction. On the other hand, conventional representations allow in some cases very efficient reductions but require costly multiplications. The main purpose of this paper is to analyze the complexity of those two different approaches in the summations of products. As a matter of fact, the complexities of the reduction in residue systems and of the multiplication in classical representations are similar. One of the main features of this reduction is that it doesn't depend on the field. Moreover, the cost of multiplication in residue systems is equivalent to the cost of reduction in classical representations for special well-chosen fields. Taking those properties into account, we remark that an expression like $A * B + C * D$, which requires two products, one addition and one reduction, evaluates faster in a residue system than in a classical one. So we propose to study types of expressions to offer a guide for choosing a most appropriate representation. One of the best domain of application is the Elliptic Curves Cryptography where addition and doubling points formulas are composed of products summation. The different kinds of coordinates like affine, projective, and Jacobean, offer a good choice of expressions for our study.
- typdoc
- Communication dans un congrès
- Accès au texte intégral et bibtex
-
Rapport
-
- titre
- Combining Montgomery Ladder for Elliptic Curves Defined over $\F_p$ and RNS Representation
- auteur
- Jean-Claude Bajard, Sylvain Duquesne, Nicolas Méloni
- article
- [Research Report] 06041, LIR. 2006
- resume
- In this paper, we combine the RNS representation and the Montgomery ladder on elliptic curves in Weierstrass form. These two techniques are relevant for implementation of elliptic curve cryptogra- phy on embedded devices since they have leak-resistance properties. We optimize formulae for addition and doubling of the Montgomery lad- der in terms of modular reductions to obtain a competitive and secure implementation. Afterwards, we explain the advantages of the RNS rep- resentation, especially in hardware and for embedded devices, and show that, contrary to other approaches, ours takes optimal advantage of a dedicated parallel architecture.
- typdoc
- Rapport
- Accès au texte intégral et bibtex
-
2005
Communication dans un congrès
- titre
- Study of Modular Inversion in RNS
- auteur
- Jean-Claude Bajard, Nicolas Méloni, Thomas Plantard
- article
- SPIE'05: Advanced Signal Processing AlgorithmsArchitectures and Implementations XV, Jul 2005, San Diego, CA (USA)
- typdoc
- Communication dans un congrès
- Accès au bibtex
-
-
- titre
- Efficient RNS Bases for Cryptography
- auteur
- Jean-Claude Bajard, Nicolas Méloni, Thomas Plantard
- article
- 17th IMACS World Congress Scientific Computation, Applied Mathematics and Simulation, Jul 2005, Paris, France
- resume
- 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.
- typdoc
- Communication dans un congrès
- Accès au texte intégral et bibtex
-