Étude des algorithmes arithmétiques et leur implémentation matérielle

About

La multiplication modulaire est l'opération principale de la plupart des protocoles de cryptographie asymétrique (Echange de clé de Diffie-Hellman, RSA, ECDSA). Il est donc important d'accorder un soin particulier à la réalisation matérielle de cette opération. Le travail de thèse consiste à proposer une solution matérielle flexible implémentant la multiplication modulaire pour une cible ASIC. On prend en compte deux niveaux de flexibilité : - L'implémentation doit être réalisable quelque soit la surface matérielle donnée. - Une fois l'architecture réalisée, celle-ci doit pouvoir traiter des données de taille variable. Après une étude algorithmique justifiant le choix de la méthode de Montgomery, l'algorithme de Montgomery est étudié en détail en vu de son implémentation matérielle. La stratégie visant à minimiser le nombre de type d'opérations élémentaires dans l'algorithme conduit à une famille d'architectures flexibles offrant un meilleur compromis temps-surface que dans l'art antérieur. Nous montrons ensuite que l'architecture développée peut être utilisée comme "boîte noire" pour effectuer la réduction modulaire. Nous étudions également la mise en place d'une contre-mesure additive au niveau des données qui permet de se prémunir de certaines attaques basées sur la DPA. Nous montrons en particulier, que la mise en place d'une telle contre-mesure ne provoque qu'une faible augmentation du temps de calcul (moins de 5%). Enfin, nous étudions une version de l'algorithme de Montgomery en représentation de Fourier ce qui permet d'obtenir un algorithme de coût asymptotique O(nlog(n)) mais malheureusement peu efficace en pratique.

Modular multiplication is the main operation in most of asymmetric cryptography protocols (Diffie-Hellman key exchange, RSA, ECDSA). Thus hardware implementation of this operation needs attention. In this work, we propose a hardware implementation of modular multiplication for an ASIC target. We consider two levels of scalability : - Implementation must fit any chip area - Design must be reused for different sizes of moduli. After an algorithmic study we show why Montgomery algorithm is preferred. Then this algorithm is studied in details in order to proceed at its hardware implementation. Strategy used for implementation consists in minimizing the number of kinds of elementary operation in the algorithm. Then we obtain a family of scalable hardware improving time-area tradeoffs in comparison to previous scalable hardware. Then considering the hardware developed as a "black-box", we show how to perform modular reduction with this hardware. We also study how to add an additive countermeasure against DPA attacks with a slow extra-computational time (less than 5%). Finally, a Montgomery algorithm using Fourier representation is studied with an asymptotic cost in O(nlog(n)) but inefficient for practical application.