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

Autrefois réservée à des applications militaires ou diplomatiques, la cryptographie est de nos jours tellement courante que nous n’y prêtons guère attention. Acheter en ligne, payer par carte bleue, téléphoner, échanger des courriers électroniques, voire ouvrir ou démarrer sa voiture… derrière tous ces gestes quotidiens se cachent des protocoles de sécurité, parfois simples à déjouer, souvent invulnérables. C’est cette invulnérabilité qui est au cœur des enjeux de la cryptologie. Avec la multiplication des échanges, la cryptographie historique qui consistait à chiffrer un message avec un secret connu uniquement des deux parties communicantes a trouvé sa limite : comment échanger les secrets de manière fiable, en particulier à l’heure actuelle où des milliards d’humains cherchent à communiquer ? La résolution de ce problème par Diffie et Hellman en 1976 a ouvert la voie aux protocoles de cryptographie asymétrique. En utilisant des fonctions mathématiques bien choisies, les deux parties souhaitant communiquer fabriquent un secret commun connu d’eux seuls. L’invulnérabilité de ces protocoles repose sur une ou plusieurs opérations dans des structures mathématiques particulières, qui sont généralement elles-mêmes constituées d’opérations dans d’autres structures arithmétiques. Cette hiérarchie de niveaux arithmétiques pour les protocoles classiques est représentée par la figure 1. Des cryptosystèmes comme RSA ou El Gamal sont composés d’opérations arithmétiques modulaires, elles mêmes composées d’opérations d’arithmétique entière. Pour garantir un niveau de sécurité suffisant, les opérandes utilisés doivent être de grande taille et ces opérations ne peuvent pas être traitées directement par le processeur. Elles sont donc composées d’appels aux instructions atomiques de l’unité de calcul. Les protocoles de cryptographie basés sur les courbes elliptiques sont aujourd’hui de plus en plus utilisés, car ils permettent des niveaux de sécurité identiques à RSA ou El Gamal mais avec des paramètres de taille réduite. Ces cryptosystèmes nécessitent une nouvelle couche arithmétique : celle des opérations entre points d’une courbe elliptique.

Introduction au parallélisme

Si le parallélisme existe depuis un demi-siècle, il apparaît dans les architectures grand public en 2005 avec les premiers processeurs multicœurs, qui bénéficient ainsi de 50 ans de recherches dans ce domaine. Le parallélisme a pour but d’augmenter la vitesse d’applications en multipliant les ressources de calcul d’un système. Pour en bénéficier, l’application doit être pensée en termes de tâches indépendantes qui pourront être exécutées de manière concurrente par les différentes unités de calcul. Définition 1 (Tâche). Une tâche est une partie d’une application exécutée de manière indépendante par une unité de calcul. Elle a son propre espace de données et a accès à l’ensemble des mémoires du système. On peut supposer en théorie qu’en multipliant le nombre d’unités de calcul par M les temps de calcul sont divisés par M. Cette vision néglige deux points essentiels : le passage à l’échelle (scalabilité) de l’application sur l’architecture parallèle et le surcoût (overhead) lié au parallélisme, c’est-à-dire le coût pratique lié aux seules instructions permettant de lancer, synchroniser, stopper, etc. des processus concurrents.

La loi d’Amdahl [3] permet d’exprimer le gain potentiel d’une application lancée sur un système multiprocesseur à M cœurs en considérant une proportion d’activité parallélisable s (sans considérer l’overhead) par rapport à l’application séquentielle.

Le surcoût dû au parallélisme est lui lié à la fois à l’architecture et au système d’exploitation. Si ses causes peuvent être établies, elles sont difficiles à contourner sans maîtrise totale de la plateforme. Une proportion non négligeable provient des instructions propres au parallélisme : lancement des tâches parallèles (instructions système clone() ou fork () sur un système Unix) mais surtout des synchronisations nécessaires entre ces différentes tâches (instruction wait()). Dans la conception d’une application parallèle, il est donc primordial de minimiser les dépendances entre tâches. Une mauvaise utilisation de la mémoire peut également causer des surcoûts importants. Nous définissons par la suite les bonnes pratiques à adopter sur les deux architectures considérées.

En 1966, Flynn propose une classification des architectures selon quatre grands types [32] :
– SISD (Single instruction simple data) : une instruction agit sur une donnée. Ce type d’architecture correspond à une machine de von Neumann classique.
– SIMD (Single instruction multiple data) : la même instruction agit sur différentes données. C’est une architecture qui exploite un parallélisme de données, à l’instar des cartes graphiques.
– MISD (Multiple instructions single data) : plusieurs instructions agissent sur une même donnée. C’est le cas des architectures de type pipeline.
– MIMD (Multiple instructions multiple data) : plusieurs instructions agissent sur plusieurs données. Ce type d’architecture se divise en deux catégories : les architectures à mémoire distribuée et les architectures à mémoire partagée. Dans le premier cas chaque processeur a sa propre zone mémoire et aucune connaissance sur les mémoires des autres processeurs. Les unités de calcul communiquent via des systèmes de messagerie comme MPI (Message Passing Interface). Dans le second cas, que nous détaillons plus bas, les processeurs partagent la mémoire centrale via le bus système.

Modèles de parallélisme

Le parallélisme de données, réalisé par les architectures SIMD, consiste à faire appliquer par un ensemble de tâches la même série d’instructions sur des données différentes. Sur architecture MIMD, on peut distinguer deux grands types de parallélisme de tâches. Le premier modèle, qui a été utilisé dans nos travaux sur architecture SMP à mémoire partagée, est un modèle de parallélisme synchrone [100] (figure 1.1a) : toutes les tâches sont globalement séquentialisées : les lancements, synchronisations et fusions sont communes.

Le second modèle de parallélisme consiste à lancer, synchroniser ou fusionner les tâches localement et dynamiquement (figure 1.1b). Les tâches sont représentées par une structure de DAG (Directed Acyclic Graph) qui permet de hiérarchiser les différences tâches en fonction des tâches antérieures qu’elles nécessitent. Ce parallélisme asynchrone peut être réalisé par différents langages, comme Cilk [14], NESL [13], KAAPI [38] ou encore JADE [79]. Ces langages se différencient en fonction des algorithmes d’ordonnancement ou d’accès à la mémoire qu’ils utilisent [75]. Par exemple, Cilk et KAAPI utilisent des techniques de vol de travail (work-stealing [15]) et NESL un parallélisme imbriqué : les tâches lancent les sous-tâches qu’elles peuvent paralléliser.

Architecture SMP à mémoire partagée

L’architecture SMP (pour Symmetric MultiProcessing) consiste à multiplier les unités de calcul au sein d’une même plate-forme. Tous les processeurs se partagent un unique BUS système, et donc l’accès à la mémoire centrale et aux différents périphériques.

Dans les systèmes multicœurs qui équipent aujourd’hui la plupart des machines grand public, les processeurs regroupent plusieurs unités de calcul, nommées cœurs. Généralement, l’architecture SMP considère chacun de ces cœurs comme un processeur à part entière. Ce double niveau de parallélisme (plusieurs processeurs possédant chacun plusieurs cœurs) doit cependant être pris en compte pour développer des applications performantes.

Ordonnancement 

Toutes les unités de calcul d’une architecture SMP ont le même statut et se partagent les différentes tâches. La répartition des processus est à la discrétion de l’ordonnanceur du système d’exploitation. Ainsi, si le débit de l’ordonnanceur est augmenté proportionnellement au nombre d’unités de calcul présentes sur l’architecture, chaque processus sera exécuté séquentiellement par une seule unité de calcul et son temps d’exécution sera au moins aussi important que sur un système monocœur.

Il est cependant possible dans le cas d’applications parallèles d’affecter les tâches à une unité de calcul en particulier. En OpenMP que nous présentons plus bas, cette affectation est réalisée via la variable d’environnement GOMP_CPU_AFFINITY qui prend comme valeur la liste des cœurs ordonnée selon les tâches : le premier cœur de la liste correspondra à la première tâche, le second à la seconde tâche et ainsi de suite. Sur une architecture à M cœurs, ces derniers sont représentés par un entier entre 0 et M − 1.

Ces identifiants peuvent être obtenus par des programmes dédiés comme hwloc . Ces nœuds sont composés de deux processeurs Intel Xeon X5650 (architecture Westmere) cadencés à 2.67 GHz. Les processing units (PU) correspondent aux processeurs logiques et sont numérotés dans l’ordre naturel (de 0 à 5 sur un processeur, de 6 à 11 sur le second). Pour nos applications arithmétiques, il sera donc fondamental de grouper les tâches qui communiquent le plus sur un même processeur car les caches de type L3 présents sur les processeurs sont de taille suffisamment grande (12 Mo) pour stocker l’ensemble des données nécessaires aux calculs.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction
1 Introduction aux architectures parallèles
1.1 Introduction au parallélisme
1.2 Modèles de parallélisme
1.3 Architecture SMP à mémoire partagée
1.3.1 Ordonnancement
1.3.2 Implémentation de codes parallèles dans le modèle synchrone
1.4 Processeurs graphiques
1.4.1 Les cartes Tesla
1.4.1.1 Architecture
1.4.1.2 CUDA
1.4.1.3 Exécution d’une grille
1.4.1.4 Mémoires
1.4.1.5 Optimisations et bonnes pratiques .
1.4.2 Un exemple concret : les requêtes par fredonnement sur GPU
1.4.2.1 Requête par fredonnement
1.4.2.2 Alignement de séquences
1.4.2.3 Implémentation sur GPU
1.4.2.4 Résultats expérimentaux
2 Arithmétique pour la cryptographie
2.1 La cryptographie à clé publique
2.2 Arithmétique multiprécision
2.2.1 Représentations des entiers multiprécision
2.2.2 Addition et soustraction
2.2.3 Multiplication
2.2.3.1 Version scolaire
2.2.3.2 Karatsuba
2.2.3.3 Toom-3
2.2.3.4 Toom-Cook r
2.2.3.5 Algorithmes à complexité quasi-linéaire
2.2.4 Division
2.2.5 Résumé des complexités
2.2.6 L’arithmétique multiprécision en pratique
2.3 Arithmétique modulaire
2.3.1 Addition et soustraction
2.3.2 Multiplication
2.3.2.1 L’algorithme classique
2.3.2.2 Multiplication de Blakely
2.3.2.3 Multiplication de Montgomery
2.3.2.4 Méthode FIOS
2.3.2.5 Multiplication modulaire de Barrett
2.3.2.6 Multiplication modulaire bipartite
2.4 Arithmétique des courbes elliptiques
2.4.1 La cryptographie basée sur les courbes elliptiques
2.4.2 Définition des courbes elliptiques
2.4.3 Projections et équations de courbes
2.4.4 La multiplication scalaire
2.4.4.1 Algorithmes à fenêtre : représentation en base 2w
2.4.4.2 Non-adjacent form
2.4.4.3 Double-Base number system
3 Arithmétiques parallèles
3.1 Parallélisme sur architecture SMP à mémoire partagée
3.1.1 Arithmétique entière
3.1.1.1 Addition et soustraction entières
3.1.1.2 Ensemble d’additions
3.1.1.3 Multiplication entière
3.1.1.4 Résultats expérimentaux
3.1.2 Arithmétique modulaire
3.1.3 Courbes elliptiques
3.1.3.1 Approche naïve
3.1.3.2 Répartition homogène des calculs
3.1.3.3 Résultats expérimentaux
3.2 Parallélisme sur les processeurs graphiques
3.2.1 Représentation des entiers multiprécision
3.2.2 Gestion de la mémoire
3.2.3 Arithmétique modulaire
3.2.3.1 Addition et soustraction
3.2.3.2 Multiplication
3.2.3.3 Résultat expérimentaux
3.2.4 Arithmétique des courbes elliptiques
3.2.4.1 Courbes elliptiques sur GPU
3.2.4.2 Addition et doublement dans E(Fp)
3.2.4.3 Multiplication scalaire
3.3 Conclusion et perspectives
3.3.1 Architecture SMP
3.3.2 Processeurs graphiques
4 La multiplication modulaire multipartite
5 Optimisation des formules pour la multiplication scalaire
Conclusion

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *