Depuis l'apparition des premiers ordinateurs, l'arithmétique flottante a énormément évolué. La norme IEEE 754 a permis de fixer les caractéristiques de l'arithmétique des ordinateurs modernes, mais les scientifiques perdent de plus en plus vite le contrôle de la validité de leurs calculs. Malgré l'énorme travail associé à la définition des opérations, la validation des calculs ne peut toujours pas être assurée de façon certaine par l'arithmétique implantée sur les ordinateurs. Je présente dans la première partie de cette étude deux prolongements qui visent à augmenter la marge de validité des opérations : un nouveau mode d'arrondi pour les fonctions trigonométriques et un codage efficace des intervalles accessible facilement à l'utilisateur. Je présente aussi dans cette partie une étude détaillée de la fonction unit in the last place et la probabilité d'absorption ou de propagation des erreurs dans une chaîne de multiplication. Ces travaux, qui viennent s'ajouter aux travaux antérieurs d'autres équipes de recherche et aux solutions que j'ai proposées dans ma thèse de master montrent les bénéfices que l'on pourra tirer des deux extensions présentées. L'arithmétique en-ligne permet de gérer efficacement les problèmes de précision, mais les opérateurs élémentaires utilisés sont peu adaptés aux architectures modernes de 32 ou 64 bits. L'implantation efficace d'un opérateur en-ligne ne peut que passer par la description d'un circuit de bas niveau. Les prédiffusés actifs, terme français utilisé pour Field Programmable Gate Array, sont des composants spéciaux programmables au niveau des portes logiques. Ils permettent d'abaisser les coûts de production en évitant de fabriquer un prototype. Nous avons implanté grâce à ces technologies les opérateurs simples de calcul en-ligne : addition, normalisation, etc...Le Noyau Arithmétique de Calcul En-Ligne (Nacel) décrit dans ce mémoire permet d'implanter les opérations arithmétiques usuelles telles que la multiplication, la division, l'extraction de racine carrée et les fonctions élémentaires trigonométriques et hyperboliques par une approximation polynômiale. Les architectures à flots de données sont insensibles aux difficultés sur lesquelles butent les concepteurs des ordinateurs modernes : temps d'accès à la mémoire, latence de communication, occupation partielle du pipeline d'instructions. Je décris dans ce document le mode de fonctionnement d'une machine virtuelle appelée Petite Unité de Calcul En-ligne (Puce). Par une gestion adaptée des étiquettes inspirée pour le contrôle des données de celle utilisée par la Manchester Data Flow Machine, Puce reproduit le comportement complet d'une machine à flot de données. Elle comprend de plus les opérations en-ligne de calcul scientifique. Nous présentons afin de valider le modèle d'évaluation de Puce les résultats de simulations logicielles pour une ou plusieurs unités fonctionnelles.

Les machines actuelles offrent de plus en plus de fonctionnalités arithmétiques au niveau matériel. Les générations actuelles de processeurs proposent des opérateurs matériels rapides pour le calcul des divisions, des racines carrées, des sinus, des cosinus, des logarithmes... La littérature du domaine montre qu'en changeant notre façon de représenter les nombres et/ou en utilisant des algorithmes spécifiques de calcul, il est possible de réaliser des opérateurs matériels particulièrement efficaces. Le but de cette thèse est d'étudier et d'illustrer les liens profonds existants entre l'arithmétique et l'architecture des ordinateurs à travers quatre problèmes. Les Opérateurs Arithmétiques Asynchrones permettent de calculer les fonctions arithmétiques (addition, multiplication, division) avec un délai variable. En particulier, nous avons développé un additionneur asynchrone dont le temps moyen de calcul est O(sqrt(\log n)). L'Arithmétique En-Ligne permet de réaliser des architectures où les nombres circulent en série, chiffre par chiffre, les poids forts en tête. L'intérêt de cette arithmétique est de pouvoir calculer toutes les fonctions (en arithmétique série poids faibles en tête, il n'est pas possible de calculer les divisions et les maximums) et d'obtenir des opérateurs de petite taille avec un nombre d'entrées/sorties plus faible que leur équivalents parallèles. L'Arrondi Exact des Fonctions Elémentaires consiste à déterminer la précision intermédiaire permettant de toujours pouvoir arrondir "exactement" les résultats du calcul des fonctions élémentaires (sinus, cosinus, exponentielle...). Nous proposons dans cette thèse une méthode qui permet d'arrondir exactement les fonctions élémentaires assez rapidement. Le Système Semi-Logarithmique de Représentation des Nombres est un système permettant d'effectuer rapidement les calculs de problèmes dont le nombre de multiplications/divisions est grand devant le nombre d'additions/soustractions.

Les processeurs graphiques (GPU) actuels offrent une importante puissance de calcul disponible à faible coût. Ce fait a conduit à détourner leur emploi pour réaliser du calcul non graphique, donnant naissance au domaine du calcul généraliste sur processeur graphique (GPGPU). Cette thèse considère d'une part des techniques logicielles pour tirer parti de l'ensemble des opérateurs arithmétiques spécifiques aux GPU dans le cadre du calcul scientifique, et d'autre part des adaptations matérielles aux GPU afin d'exécuter plus efficacement les applications généralistes. En particulier, nous identifions la régularité parallèle comme une opportunité d'optimisation des architectures parallèles, et exposons son potentiel par la simulation d'une architecture GPU existante. Nous considérons ensuite deux alternatives permettant d'exploiter cette régularité. D'une part, nous mettons au point un mécanisme matériel dynamique afin d'améliorer l'efficacité énergétique des unités de calcul. D'autre part, nous présentons une analyse statique opérée à la compilation permettant de simplifier le matériel dédié au contrôle dans les GPU.

De nos jours, la présence de réseaux à grande échelle dans notre société bouleverse nos habitudes avec l'apparition de nouveaux services distants avec des besoins en matière de sécurité de plus en plus important. Nous abordons dans cette thèse la problématique de la composition des protocoles de sécurité, nous nous focalisons notamment sur les protocoles cryptographiques ainsi que sur les politiques de contrôle d'accès. La première partie de la thèse est consacrée à la composition des protocoles cryptographiques ainsi que leurs intégration avec d'autres types de protocoles. Nous introduisons notamment la notion de mécanismes cryptographiques qui sont des protocoles cryptographiques simples qui peuvent être composés pour obtenir des protocoles plus complexes sous réserve de faire les preuves nécessaires. Nous proposons également une méthode pour la reconstitution d'éventuelles attaques. La seconde partie de la thèse est consacrée à l'implémentation des politiques de contrôle d'accès par le raffinement, l'idée consiste à partir de politiques de sécurité abstraites et de les raffiner afin d'obtenir des politiques plus concrètes. Nous proposons également de combiner la technique de raffinement avec la technique de composition pour rendre plus efficace la procédure d'implémentation des politiques de contrôle d'accès.

Les couplages sont des primitives cryptographiques qui interviennent désormais dans de nombreux protocoles. Dès lors, il est nécessaire de s'intéresser à leur calcul et à leur implémentation efficace. Pour ce faire, nous nous reposons sur une étude algorithmique et arithmétique de ces fonctions mathématiques. Les couplages sont des applications bilinéaires définies sur des courbes algébriques, plus particulièrement, dans le cas qui nous intéresse, des courbes elliptiques et hyperelliptiques. Nous avons choisi de nous concentrer sur une sous-famille de celles-ci : les courbes supersingulières dont les propriétés permettent d'obtenir à la fois des couplages symétriques et des algorithmes efficaces pour leur calcul. Nous décrivons alors une approche unifiée permettant d'établir une large variété d'algorithmes calculant des couplages. Nous l'appliquons notamment à la construc- tion d'un nouvel algorithme pour le calcul de couplages sur des courbes supersin- gulières de genre 2 et de caractéristique 2. Les calculs nécessaires aux couplages que nous décrivons s'appuient sur l'implé- mentation d'une arithmétique rapide pour les corps finis de petite caractéristique : la multiplication est l'opération critique qu'il convient d'optimiser. Nous présen- tons donc un algorithme de recherche exhaustive de formules de multiplication. Enfin, nous appliquons toutes les méthodes précédentes à la conception et l'im- plémentation de différents accélérateurs matériels pour le calcul de couplages sur différentes courbes dont les architectures ont été optimisées soit pour leur rapidité, soit pour leur compacité.

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.

<p align="justify">The main contribution of this thesis is the emphasis made on the reusability concept, on one side, for designing a simulation environment, and on the other side, for defining two different levels of granularity for reusable network component libraries.</p> <p align="justify">The design of our simulation environment, called AMS for Atelier for Modeling and Simulation, was based on existing pieces of software, which proved their usefulness in their respective fields. In order to carry out this integration efficiently, a modular structure of the atelier was proposed. The structure has been divided into four phases. Each phase is responsible of a part of the performance evaluation cycle. The main novelty of this structure is the usage of a dedicated language as a means to define a clear border between the editing and simulation phases and to allow the portability of the atelier upon different platforms. A prototype of the atelier has been developed on a SUN machine running the SunOs operating system. It is developed in C language.</p> <p align="justify">The kernel of the AMS is its library of Detailed Basic Models (DBMs). Each DBM was designed in order to comply with the most important criterion which is reusability. Indeed, each DBM can be used in aeveral network architectures and can be a component of generic and composite models. Before the effective usage of a DBM, it is verified and validated in order to increase the model credibility. The most important contribution of this research is the definition of a methodology for modeling protocol entities as DBMs. We then tried to partly bridge the gap between specification and modeling. This methodology is based on the concept of function. Simple functions are modeled as reusable modules and stored into a library. The Function Based Methodology was designed to help the modeler to build efficiently and rapidly new protocols designed for the new generation of networks where several services can be provided. These new protocols can be dynamically tailored to the user' s requirements.</p>

Ce travail présente quelques résultats d'arithmétique des ordinateurs. Dans une première partie, on fait une brève présentation des systèmes les plus classiques de représentation des nombres et on présente une modification de l'algorithme d'Avizienis d'addition en temps constant avec des conditions moins restrictives. La seconde partie traite du probleme de la multiplication de grands entiers: on preséente une implantation efficace de l'algorithme de Pollard que l'on compare a d'autres algorithmes. La troisième partie est consacrée au calcul en-ligne (bit série poids forts en tête): on reprend les résultats de la première partie pour obtenir des bornes sur le délai des fonctions calculables en-ligne. Enfin on présente un codage original des nombres complexes, qui permet entre autre de réaliser des additions en temps constant ainsi que des opérations arithmétiques en-ligne

Le codage et le comportement de l'arithmétique à virgule flottante disponible dans les ordinateurs sont spécifiés par la norme IEEE-754. Cette norme impose au système de rendre comme résultat de l'une des quatre opérations (+, *, /, sqrt), l'arrondi du résultat exact. Cette propriété que l'on appelle <>, permet de garantir la qualité du résultat. Elle permet également la construction de preuves d'algorithmes, quelles que soient les machines sur lesquelles l'opération est executée. Toutefois cette norme présente des limites, puisque les fonctions élémentaires (sinus, cosinus, exponentielle...) en sont absentes. Cette abscence est liée au <> : il est, contrairement aux opérations de base, difficile de connaître la précision nécessaire pour garantir l'arrondi correct des fonctions élémentaires. Cependant, si l'on fixe le format de représentation, il est alors possible par une recherche exhaustive de déterminer cette borne; ce fut le travail de thèse de Lefèvre pour la double précision. <br /><br />L'objectif de ce mémoire est d'exploiter les bornes associées à chaque fonction, pour certifier l'arrondi correct des fonctions élémentaires en double précision pour les quatre modes d'arrondi. À cet effet, nous avons implémenté les évaluations en deux étapes : l'une rapide et juste la plupart du temps, basée sur les propriétés de l'arithmétique IEEE double précision, et l'autre juste tout le temps, composé d'opérateurs multiprécision. Pour cette deuxième phase, nous avons développé une bibliothèque d'opérateurs multiprécision optimisés pour les précisions données par ces bornes et les caractéristiques des processeurs en 2003.

.