L'objectif d'un générateur de nombres aléatoires (RNG) est de produire une séquence binaire aléatoire indépendante, imprédictible et uniformément répartie. Les RNG sont nécessaires dans toutes sortes d'applications telles que la cryptographie, les télécommunications, les simulations numériques, le test de circuits VLSI ou encore les algorithmes probabilistes. Ainsi, le nombre d'applications embarquées nécessitant des RNG matériels augmente constamment, spécialement au sein des circuits reconfigurables. En vue de la conception matérielle d'un RNG, la solution est d'utiliser un générateur hybride composé d'un générateur vraiment aléatoire (TRNG) et d'un générateur pseudo-aléatoire (PRNG). Prouver mathématiquement qu'un générateur est aléatoire est généralement difficile, voire impossible. Les RNG sont souvent évalués via des tests statistiques. L'évaluation d'un TRNG est beaucoup plus complexe que celle d'un PRNG car la qualité d'un TRNG est fonction de la source de bruit utilisée, de l'environnement extérieur et de la qualité d'implantation au sein du circuit ciblé. Fischer et al. [1] ont proposé l'un des premiers TRNG totalement implantable au sein d'un circuit FPGA. Depuis, un grand nombre de générateurs a été présenté dans la littérature. Un des objectifs de cette thèse a été de proposer une méthodologie objective analysant la qualité des TRNG sélectionnés au sein de circuits reconfigurables. La méthode d'évaluation, rapide et efficace est basée sur l'utilisation de tests statistiques matériels proposés par l'AIS 31 [2]. L'intérêt de la méthode est d'évaluer les TRNG au sein du même circuit FPGA afin d'analyser ceux-ci dans des conditions similaires d'utilisation. La version matérielle de l'AIS 31 permet d'évaluer des TRNG présentant un débit maximal de 84.2 Mbits/s. Le coût matériel de celle-ci est de 4042 LUT, soit environ 10% d'un FPGA Xilinx Virtex 5 SX50. La méthode proposée permet de trouver facilement le débit optimal des TRNG au sein d'un circuit reconfigurable. Ainsi, l'intérêt d'une pré-caractérisation du fonctionnement d'un TRNG est prouvé. À partir de l'étude précédente, un TRNG est sélectionné pour ses propriétés statistiques. Une architecture de générateur hybride permettant de produire des nombres aléatoires uniformes à très haut débit est ensuite proposée. Cependant, malgré la qualité du générateur sélectionné, l'aléa en sortie du TRNG peut varier au cours du temps à cause d'attaques externes possibles sur le circuit, de la variation des conditions extérieures ou encore du vieillissement des composants. La qualité aléatoire de la séquence de germes produite par un TRNG est primordiale pour assurer l'imprédictibilité d'un PRNG. Afin d'améliorer la robustesse d'un TRNG, des mécanismes de tests statistiques en ligne doivent être mis en œuvre. Ainsi, une évaluation en temps réel du comportement du générateur est réalisée et les séquences défaillances générées par celui-ci sont évitées. Cette étude propose d'utiliser une implantation efficace de la batterie du FIPS 140-2. La surface négligeable du circuit au sein des FPGA actuels et les performances obtenues par le composant permettent de contrôler la qualité du TRNG sélectionné en temps réel. Un RNG hybride à très haut débit implanté sur une cible reconfigurable et au sein d'un circuit VLSI est proposé. L'étude menée sur le RNG hybride a débouché sur un partenariat industriel réalisé avec une entreprise spécialisée en cryptographie à travers le projet pôle images et réseaux SPRING (Shelf Proof Random Integrated Number Generator). Dans certaines applications, il est parfois nécessaire de générer des nombres aléatoires suivant une distribution de probabilité différente d'une loi uniforme. À partir de l'utilisation du RNG hybride proposé, l'implantation d'un générateur de nombres aléatoires gaussiens à très haut débit est présenté. Par ailleurs, le circuit implanté permet de générer efficacement des nombres aléatoires suivant une loi de Rayleigh. Après sélection d'un excellent TRNG, un PRNG à débit très élevé est recherché. La structure parallèle des automates cellulaires fait de ces PRNG une architecture très intéressante en vue d'une implantation matérielle. La seconde partie de la thèse est consacrée à la recherche de la règle optimale d'un automate cellulaire à cinq voisins. Le chapitre étudie, entre autres, le coût matériel engendré par l'implantation de tests statistiques très performants. / The purpose of a random number generator (RNG) is to produce a random binary sequence independent, unpredictable and uniformly distributed. A RNG is needed in all kinds of applications such as cryptography, telecommunications, computer simulations, testing of VLSI circuits or probabilistic algorithms. The number of embedded applications requiring hardware RNG is constantly increasing, especially in the reconfigurable circuits. In view of the physical design of a RNG, the solution is to use a hybrid generator composed of a truly random generator (TRNG) and a pseudo-random number generator (PRNG). Proving mathematically that a generator is random is usually difficult or impossible. RNGs are often evaluated using statistical tests. Evaluation of a TRNG is much more complex than PRNG testing as the TRNG quality is a function of the noise source used in the external environment and the implementation quality within the target circuit. Fischer et al. have proposed one of the first TRNG totally embedded within an FPGA. Then, a large generator number has been presented in the literature. One objective of this thesis was to propose an objective methodology for analyzing the quality of recognized TRNGs in reconfigurable circuits. The evaluation method, fast and efficient, is based on the use of hardware statistical tests proposed by the AIS 31 and the FIPS 140-2. The advantage of the method is to evaluate the TRNGs in the same FPGA chip to analyze them in similar conditions of use. The hardware version of AIS 31 allows the TRNG evaluation with a maximum throughput of 84.2 Mb/s. The material cost of it is 4042 LUTs, about 10 % of a Xilinx Virtex 5 FPGA SX50. Moreover, the method is used to find the optimal TRNG data rate for the targeted reconfigurable circuit, showing the TRNG pre-characterization interest. From the previous study, a TRNG is selected for its statistical properties. A high data rate hybrid generator is then proposed. However, despite the quality of the selected generator, the TRNG randomness can vary in time due to possible external attacks on the circuit, changes in external conditions or aging components. The quality of the seed sequences provided by a TRNG is important to ensure the unpredictability of a PRNG. To improve the robustness of a TRNG, online statistical tests must be implemented. Thus, a real-time evaluation of the generator behavior is performed and the TRNG weaknesses are filtered. This study proposes to use an efficient implementation of the FIPS 140-2 battery. The negligible area and the performance allow to control the TRNG quality in real time. A hybrid RNG implemented on a reconfigurable target and within a VLSI circuit is then proposed. The study conducted on the RNG hybrid resulted in an industry partnership. Then, in some applications, it is sometimes necessary to generate random numbers following a probability distribution different from a uniform distribution. From the use of the proposed hybrid RNG, a very high data rate Gaussian random number generator is proposed. Furthermore, the circuit can generate random numbers according to a Rayleigh law. From previous studies, a hybrid RNG is proposed for FPGA implementation and is embedded into the cryptography solution proposed by a French company. The RNG generates uniform random bits and his innovating by the TRNG real time monitoring realized by embedded the FIPS 140-2 tests. Then, the realization of two ASIC in 130 nm technology are described. The chips will allow to evaluate the performance of ASIC TRNGs. Moreover, the second circuit embeds high throughput Gaussian and Rayleigh noise generators.

Dans cette thèse, nous considérons les générateurs de nombres aléatoires en cryptographie. D'une part, nous avons étudié des générateurs, comme HAVEGE, qui produisent leurs données en se basant sur des événements imprévisibles. D'autre part, nous avons examiné les chiffrements à flots, qui peuvent être vus comme des générateurs de nombre pseudo-aléatoires qui produisent une suite chiffrante à partir d'une courte séquence initiale dépendant de la clé, et du vecteur d'initialisation, l'IV. Nous avons étudié plus particulièrement le chiffrement Dragon, ainsi qu'un modèle utilisant des fonctions aléatoires qui nous a été inspiré par une attaque sur le chiffrement MICKEY. Enfin, nous avons étudié plusieurs aspects des registres à décalages avec retenue (ou FCSR pour "feedback with carry shift register" en anglais) utilisés dans le chiffrement F-FCSR.

Contrairement aux modèles déterministes, le déroulement d'un modèle stochastique est conditionné par la réalisation de variables aléatoires. L'utilisation de hasard permet d'approcher un résultat le plus souvent incalculable de manière déterministe. En contrepartie, il est nécessaire d'estimer les paramètres des distributions associées aux quantités aléatoires en sortie du modèle stochastique. Ce calcul requiert l'exécution de multiples réplications indépendantes de la même expérience et de ce fait, d'une importante quantité de calcul. Toutes les simulations stochastiques comportent par conception un aspect naturellement parallèle. Elles représentent ainsi une des applications phares pour l'utilisation d'environnements de calculs distribués permettant de partager de la puissance de calcul à l'échelle mondiale, appelée grille de calcul. Bien que 50% des cycles des plus gros supercalculateurs de la planète soient consommés par des calculs stochastiques, les techniques de génération parallèle de nombres pseudoaléatoires sont méconnues. Il existe de ce fait un risque bien réel de produire et de publier des résultats de simulations stochastiques erronés. Cette thèse présente l'état de l'art des méthodes pour la distribution des réplications de simulations stochastiques et contribue à leur développement. Elle propose ainsi des méthodes novatrices permettant d'assurer une traçabilité dans le processus complexe de distribution de simulations stochastiques. Elle expose enfin des applications dans les domaines de l'imagerie médicale nucléaire et des simulations environnementales totalisant plus de 70 années de calcul sur un ordinateur séquentiel.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Les nombres aléatoires ont été de tous temps utilisés pour des jeux de hasard, plus récemment pour créer des codes secrets et ils sont aujourd'hui nécessaire à l'exécution de programmes informatiques. Les générateurs de nombres aléatoires sont maintenant bien éloignés de simples dés à lancer et sont constitués de circuits électroniques ou d'algorithmes. Ceci pose des problèmes quant à la reconnaissance du caractère aléatoire des nombres générés. De plus, de la même manière ou autrefois les dés étaient pipés pour augmenter les chances de gagner, il est aujourd'hui possible d'influencer la sortie des générateurs de nombres aléatoires.Ce sujet est donc toujours d'actualité avec des exemples récents très médiatisés. Ceci concernait en effet la console de jeu PS3 qui génère un nombre aléatoire constant où la distribution de clefs secrètes redondantes sur internet.Ce mémoire présente l'étude de plusieurs générateurs ainsi que diverses manières de les perturber. Il montre ainsi des faiblesses inhérentes à leurs conceptions et des conséquences possibles de leur défaillance sur des composants de sécurité. Ces travaux ont de plus permis de mettre en évidence l'importance des problématiques concernant le test des nombres aléatoires ainsi que des retraitements corrigeant des biais dans ces nombres. / Random numbers have been used through the ages for games of chance, more recently for secret codes and today they are necessary to the execution of computer programs. Random number générators have now evolved from simple dices to electronic circuits and algorithms. Accordingly, the ability to distinguish between random and non-random numbers has become more difficult. Furthemore, whereas in the past dices were loaded in order to increase winning chances, it is now possible to influence the outcome of random number generators.In consequence, this subject is still very much an issue and has recently made the headlines. Indeed, there was talks about the PS3 game console which generates constant random numbers and redundant distribution of secret keys on the internet.This thesis presents a study of several generators as well as different means to perturb them. It shows the inherent defects of their conceptions and possible consequences of their failure when they are embedded inside security components. Moreover, this work highlights problems yet to be solved concerning the testing of random numbers and the post-processing eliminating bias in these numbers distribution.

Les générateurs de nombres aléatoires sont des blocs destinés à produire des quantités numériques qui doivent être indépendantes et uniformément distribuées. Ces RNG sont utilisés dans des contextes sécuritaires où l'utilisation de nombres aléatoires est requise (génération de clefs cryptographiques, nonces des protocoles cryptographiques, marqueurs anti-rejeu, contre-mesures face aux attaques par canaux cachés) et où leur qualité est primordiale. Tous les composants électroniques ayant une fonction sécuritaire, comme par exemple les cartes à puces, incluent un ou plusieurs générateurs aléatoires (basés sur des principes physiques). En conséquence, le RNG est une brique centrale des applications sécuritaires et sa défaillance, totale ou partielle met donc en péril la fonctionnalité dans son ensemble. Ce travail de thèse porte sur l'étude des RNG physiques (PTRNG) et la modélisation de l'aléa à partir des caractérisations électroniques et mathématiques du circuit. Cette étude se place essentiellement dans le contexte de la norme AIS 31 du BSI* qui fait référence dans de nombreux pays européens. Cette norme est l‘une des rares qui impose des caractérisations sur les PTRNG, incluant notamment un modèle stochastique de ce dernier. Dans ce contexte, il est crucial de pouvoir valider la méthodologie d'évaluation proposée par ces normes et c'est sur ce point que j'ai focalisé mon travail de thèse.*Bundesamt für Sicherheit in der Informationstechnik, agence fédérale allemande chargée de la sécurité des technologies de l'information / Random number generators (RNG) are primitives that produce independent and uniformly distributed digital values, RNG are used in secure environments where the use of random numbers is required (generation of cryptographic keys, nonces in cryptographic protocols, padding values, countermeasures against side-channel attacks) and where the quality of the randomness is essential. All electronic components with a security function, such as smart cards, include one or more random generators (based on physical principles). Consequently, the RNG is an essential primitive for security applications. A flaw in security of the random number generation process directly impacts the security of the cryptographic system. This thesis focuses on the study of physical RNG (PTRNG), the modeling of its randomness and an electronic characterizations of the circuit. This study is in the context of the AIS-31 standard which is published by the BSI* and followed by many European countries. This standard is one of the few that require a characterizations of the PTRNG and a stochastic model. In this context, it is crucial to validate the evaluation methodology proposed by these standards and l focused on them during my thesis.*Bundesamt fiir Sicherheit in der Informationstechnik, federal agency German responsible for the security of information technology