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

Collection

Informatique

Citer ce document

Bernard, Florent, “Étude des algorithmes arithmétiques et leur implémentation matérielle,” Bibliothèque numérique Paris 8, consulté le 29 mars 2024, https://octaviana.fr/document/135519187.

À propos

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.

Sujets

Cryptographie Système binaire (mathématiques) Circuits intégrés à la demande Fourier, Transformations de Multiplication (arithmétique) algorithme de Montgomery

Auteur

Bernard, Florent

Collaborateur

Carlet, Claude (sous la direction de)

Source

Paris 8, BU - Saint-Denis, Magasin 2, 2500TH

Date

2007

Identifiant

135519187

Droits d'accès

Accessible à tous

Conditions d'utilisation

Toute reproduction même partielle est interdite sans accord exprès de l'auteur

Discipline (Thèse)

Informatique

Domaine (Dewey)

004 Traitement des données. Informatique. Généralités. Dictionnaires