Opérateurs Arithmétiques Parallèles pour la Cryptographie Asymétrique

Protocols for asymmetric cryptography require arithmetic computations in several mathematical structures. In particular, many of them need computations in finite structures, imposing an efficient modular arithmetic. These modular calculations are composed of multiprecision operations between operands of sizes large enough to insure the required level of security (between several hundred and several thousand of bits). Finally, some protocols need arithmetic operations in the group of points of an elliptic curve, which are themselves composed of modular computations. The sizes of the keys used by the protocols make the arithmetic computations expansive in terms of execution time. Nowadays, current architectures have several computing units, which are distributed over the processors and GPU. These resources are now easily programmable using dedicated languages such as OpenMP or CUDA. This thesis focuses on the definition of parallel algorithms to take advantage of all the computing resources of multi-core shared-memory architectures. Parallelism at the lowest arithmetic level gives a moderate speedup since the sizes of the operands are not large enough so that the arithmetic intensity hides the latencies induced by the parallelism. We propose algorithms for parallelization at higher arithmetic: parallel algorithms for modular multiplication and scalar multiplication on elliptic curves. For modular multiplication, we study in particular several schedulings of modular computations. We also propose a two-level parallelization, at modular and multiprecision levels. This "coarse-grained" parallelism allows in practice a more substantial speedup. We also present a parallelization of modular and elliptic curves operations on GPU. Finally, we introduce a method to optimize scalar multiplication on elliptic curves for small scalars.Les protocoles de cryptographie asymétrique nécessitent des calculs arithmétiques dans différentes structures mathématiques. Un grand nombre de ces protocoles requièrent en particulier des calculs dans des structures finies, rendant indispensable une arithmétique modulaire efficace. Ces opérations modulaires sont composées d'opérations multiprécision entre opérandes de tailles suffisamment grandes pour garantir le niveau de sécurité requis (de plusieurs centaines à plusieurs milliers de bits). Enfin, certains protocoles nécessitent des opérations arithmétiques dans le groupe des points d'une courbe elliptique, opérations elles-mêmes composées d'opérations dans le corps de définition de la courbe. Les tailles de clés utilisées par les protocoles rendent ainsi les opérations arithmétiques coûteuses en temps de calcul. Par ailleurs, les architectures grand public actuelles embarquent plusieurs unités de calcul, réparties sur les processeurs et éventuellement sur les cartes graphiques. Ces ressources sont aujourd'hui facilement exploitables grâce à des interfaces de programmation parallèle comme OpenMP ou CUDA. Cette thèse s'articule autour de la définition d'opérateurs arithmétiques parallèles permettant de tirer parti de l'ensemble des ressources de calcul, en particulier sur des architectures multicœur à mémoire partagée. La parallélisation au niveau arithmétique le plus bas permet des gains modérés en termes temps de calcul, car les tailles des opérandes ne sont pas suffisamment importantes pour que l'intensité arithmétique des calculs masque les latences dues au parallélisme. Nous proposons donc des algorithmes permettant une parallélisation aux niveaux arithmétiques supérieurs : algorithmes parallèles pour la multiplication modulaire et pour la multiplication scalaire sur les courbes elliptiques. Pour la multiplication modulaire, nous étudions en particulier plusieurs ordonnancements des calculs au niveau de l'arithmétique modulaire et proposons également une parallélisation à deux niveaux : modulaire et multiprécision. Ce parallélisme à plus gros grain permet en pratique des gains plus conséquents en temps de calcul. Nous proposons également une parallélisation sur processeur graphique d'opérations modulaires et d'opérations dans le groupe des points d'une courbe elliptique. Enfin, nous présentons une méthode pour optimiser la multiplication scalaire sur les courbes elliptiques pour de petits scalaires