Theoretical study and hardware implementation of arithmetical units in Residue Number System (RNS) for Elliptic Curve Cryptography (ECC)

Ces travaux de thèse portent sur l'accélération de calculs de la cryptographie sur courbes elliptiques (ECC) grâce à une représentation peu habituelle des nombres, appelée représentation modulaire des nombres (ou RNS pour residue number system). Après un état de l'art de l'utilisation du RNS en cryptographie, plusieurs nouveaux algorithmes RNS, plus rapides que ceux de l'état de l'art, sont présentés. Premièrement, nous avons proposé un nouvel algorithme d'inversion modulaire en RNS. Les performances de notre algorithme ont été validées via une implantation FPGA, résultant en une inversion modulaire 5 à 12 fois plus rapide que l'état de l'art, pour les paramètres cryptographiques testés. Deuxièmement, un algorithme de multiplication modulaire RNS a été proposé. Cet algorithme décompose les valeurs en entrée et les calculs, afin de pouvoir réutiliser certaines parties lorsque c'est possible, par exemple lors du calcul d'un carré. Il permet de réduire de près de 25 % le nombre de pré-calculs à stocker et jusqu'à 10 % le nombre de multiplications élémentaires pour certaines applications cryptographiques (p. ex. le logarithme discret). Un algorithme d'exponentiation reprenant les mêmes idées est aussi présenté, réduisant le nombre de multiplications élémentaires de 15 à 22 %, contre un surcoût en pré-calculs à stocker. Troisièmement, un autre algorithme de multiplication modulaire RNS est proposé, ne nécessitant qu'une seule base RNS au lieu de 2 pour l'état de l'art, et utilisable uniquement dans le cadre ECC. Cet algorithme permet, pour certains corps bien spécifiques, de diviser par 2 le nombre de multiplications élémentaires et par 4 les pré-calculs à stocker. Les premiers résultats FPGA donnent des implantations de notre algorithme jusqu'à 2 fois plus petites que celles de l'algorithme de l'état de l'art, pour un surcoût en temps d'au plus 10 %. Finalement, une méthode permettant des tests de divisibilités multiples rapides est proposée, pouvant être utilisée en matériel pour un recodage de scalaire, accélérant certains calculs pour ECC.The main objective of this PhD thesis is to speedup elliptic curve cryptography (ECC) computations, using the residue number system (RNS). A state-of-art of RNS for cryptographic computations is presented. Then, several new RNS algorithms, faster than state-of-art ones, are proposed. First, a new RNS modular inversion algorithm is presented. This algorithm leads to implementations from 5 to 12 times faster than state-of-art ones, for the standard cryptographic parameters evaluated. Second, a new algorithm for RNS modular multiplication is proposed. In this algorithm, computations are split into independant parts, which can be reused in some computations when operands are reused, for instance to perform a square. It reduces the number of precomputations by 25 % and the number of elementary multiplications up to 10 %, for some cryptographic applications (for example with the discrete logarithm). Using the same idea, an exponentiation algorithm is also proposed. It reduces from 15 % to 22 % the number of elementary multiplications, but requires more precomputations than state-of-art. Third, another modular multiplication algorithm is presented, requiring only one RNS base, instead of 2 for the state-of-art. This algorithm can be used for ECC and well-chosen fields, it divides by 2 the number of elementary multiplications, and by 4 the number of precomputations to store. Partial FPGA implementations of our algorithm halves the area, for a computation time overhead of, at worse, 10 %, compared to state-of-art algorithms. Finally, a method for fast multiple divisibility tests is presented, which can be used in hardware for scalar recoding to accelerate some ECC computations