Academic literature on the topic 'Générateur de nombres pseudo-aléatoires'

International audience In this article, we investigate the asymptotic occurrence rates of specific subwords in any infinite binary word. We prove that the asymptotic occurrence rate for the subwords is upper- and lower-bounded in the same way for every infinite binary word, in terms of the asymptotic occurrence rate of the zeros. We also show that both of the bounds are best-possible by constructing, for each bound, a concrete infinite binary word such that the bound is reached. Moreover, we apply the result to analyses of recently-proposed pseudorandom number generators that are based on integer-valued variants of logistic maps. Dans cet article, nous étudions les fréquences asymptotiques d’occurrence de suites spécifiques dans tout mot binaire infini. Nous prouvons que la fréquence asymptotique d’occurrence pour ces suites est borné supérieurement et inférieurement de la même façon pour chaque mot binaire infini, en termes des fréquences asymptotiques d’occurrence de zéros. Nous montrons aussi que les deux limites sont les meilleures possibles en construisant concrètement, pour chaque limite, un mot binaire infini tel que la borne est atteinte à la limite. De plus, nous appliquons ce résultat à des analyses de générateurs de nombres pseudo-aléatoires proposés récemment qui sont basés sur des variantes des fonctions logistiques à valeurs entières.

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.

L'utilisation des nombres (pseudo)-aléatoires a pris une dimension importante ces dernières décennies. De nombreuses applications dans le domaine des télécommunications, de la cryptographie, des simulations numériques ou encore des jeux de hasard, ont contribué au développement et à l'usage de ces nombres. Les méthodes utilisées pour la génération des nombres (pseudo)-aléatoires proviennent de deux types de processus : physique et algorithmique. Dans cette thèse, deux classes de générateurs basés sur des principes de mesures physiques et des processus mathématiques sont présentées. Pour chaque classe deux générateurs sont présentés. La première classe de générateurs exploite la réponse d'un système physique qui sert de source pour la génération des séquences aléatoires. Cette classe utilise aussi bien des résultats de simulation que des résultats de mesures interférométriques pour produire des séquences de nombres aléatoires. La seconde classe de générateurs est basée sur deux types de fonctions chaotiques et utilise les sorties de ces fonctions comme indice de permutation sur un vecteur initial. Cette thèse s'intéresse également aux systèmes de chiffrement pour la protection des données. Deux algorithmes de chiffrement d'images utilisant des fonctions chaotiques sont proposés. Ces Algorithmes utilisent un processus de permutation-substitution sur les bits de l'image originale. Une analyse approfondie basée sur des tests statistiques confirme la pertinence des cryptosystèmes développés dans cette thèse
The use of (pseudo)-random numbers has taken an important dimension in recent decades. Many applications in the field of telecommunications, cryptography, numerical simulations or gambling, have contributed to the development and the use of these numbers. The methods used for the generation of (pseudo)- random numbers are based on two types of processes: physical and algorithmic. In this PhD thesis, two classes of generators based on the principles of physical measurements and mathematical processes are presented. For each class two generators are presented. The first class of generators operates the response of a physical system that serves as a source for the generation of random sequences. This class uses both simulation results and the results of interferometric measurements to produce sequences of random numbers. The second class of generators is based on two types of chaotic functions and uses the outputs of these functions as an index permutation on an initial vector. This PhD thesis also focuses on encryption systems for data protection. Two encryption algorithms using chaotic functions are proposed. These algorithms use a permutation-substitution process on the bits of the original image. A thorough analysis based on statistical tests confirms the relevance of the developped cryptosystems in this PhD thesis manuscript

Dans cette thèse, nous nous intéressons à la sécurité de générateurs pseudo-aléatoires et d'implémentations de schémas de signature. Concernant les schémas de signature, nous proposons, dans le cas d'une implémentation répandue de RSA, différentes attaques par injection de faute effectives quelque soit l'encodage du message. Nous présentons par ailleurs une contre-mesure infective prouvée sûre pour protéger le schéma RSA--PSS contre un certain nombre de fautes non aléatoires. Nous étudions également le schéma ECDSA couplé aux techniques d'accélération GLV/GLS. En fonction des implémentations, nous prouvons soit la bonne distribution du nonce utilisé, soit qu'il présente un biais permettant une attaque. Enfin, nous élaborons un outil qui recherche automatiquement des attaques par faute à partir d'une implémentation et d'une politique de faute, outil appliqué avec succès sur des implémentations de RSA et de ECDSA. Concernant les générateurs pseudo-aléatoires algébriques, nous étudions les générateurs non-linéaires et améliorons certaines attaques en diminuant l'information donnée à l'adversaire. Nous nous intéressons également à la sécurité du générateur Micali-Schnorr à travers quelques attaques et une étude statistique de son hypothèse de sécurité. Finalement nous proposons une cryptanalyse de tout schéma à clé publique basé sur la factorisation ou le logarithme discret dont la clé secrète est générée à partir d'un générateur linéaire
In this thesis, we are interested in the security of pseudorandom number generators and of implementations of signature schemes. Regarding the signature schemes, we propose, in the case of a widespread implementation of RSA, various fault attacks which apply to any padding function. In addition we present a proven secure infective countermeasure to protect the RSA--PSS scheme against some non-random faults. Furthermore we study the ECDSA scheme coupled with the GLV/GLS speed-up techniques. Depending on the implementations, we prove either the good distribution of the used nonce, or that it has a bias, thereby enabling an attack. Finally we develop a tool for automatically finding fault attacks given an implementation and a fault policy, which is successfully applied to some RSA and ECDSA implementations. Regarding pseudorandom number generators, we study the nonlinear ones and improve some attacks by reducing the information available to the adversary. We also are interested in the security of the Micali-Schnorr generator through various attacks and a statistical study of its security assumption. Finally we propose a cryptanalysis of any public-key scheme based on the factorization or the discrete logarithm when the secret key is generated using a linear generator

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.

Dans le chapitre 1, nous présentons les congruences linéaires simples et les tests de qualité des nombres pseudo-aléatoires (n.p.a.) congruentiels. L'accent est mis sur le test des treillis, le test spectral et le test sériel. Le test sériel est base sur l'estimation de la discrépance des vecteurs de n.p.a. Partant de cette estimation, on introduit une quantité appelée figure de mérite. Celle-ci nous permet de rechercher, pour m et b fixes, des multiplicateurs a tels que deux termes successifs de la suite (a,b,m,x#0) soient statistiquement indépendants. Nous débutons le chapitre 2 par l'étude des longueurs de cycle et du transitoire des suites engendrées par une congruence linéaire multidimensionnelle (c.l.m.). Ensuite, nous décrivons quelques méthodes de transformation de ces suites en suites de n.p.a. Enfin, nous faisons une discussion sur le choix des paramètres d'une c.l.m. Dans le chapitre 3, nous étudions la période d'un générateur vectoriel base sur le modèle de Daykin et une c.l.m. De période maximale, puis nous faisons un aperçu sur les principaux générateurs non linéaires de n.p.a. Le chapitre 4, réservé a la cryptographie, traite du problème du décryptage de l'ordre et du modulo d'une c.l.m

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'im- plantation au sein du circuit ciblé. Fischer et al. [FD03] ont proposé l'un des premiers TRNG totalement implantable au sein d'un circuit FPGA. Depuis, un grand nombre 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 [AIS01]. 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'uti- lisation. 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 oeuvre. 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 aut 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 et un transfert de technologie vers une société spécialisée dans le domaine de de la sécurité. 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.

Les générateurs de suites binaires aléatoires constituent la partie primordiale d'un système cryptographique. La vitesse, la qualité des suites générées, la sécurité et la consommation jouent un rôle essentiel dans le choix d'un générateur. La sécurité du système cryptographique augmente si un tel système peut être réalisé dans un seul circuit.Le travail de recherche développé consiste donc en la réalisation d'un générateur de nombres aléatoires fonctionnant en basse consommation, basse vitesse. Le circuit proposé est de type analogique et valide l'ensemble des tests NIST assurant le caractère du signal. Une réalisation sur Silicium en technologie 0,35μm a été implémentée et validée via les tests NIST développés sous Matlab. De ce travail de thèse, un certain nombre de publications ont montré la plus-value recherche des résultats
Random binary sequences generators constitute the essential part of a system Cryptographic. The speed, quality of generated suites, safety and consumption play an essential role in the selection of a generator. The security of the cryptographic system increases if such a system can be realized in a single circuit.The developed research work consists in the realization of a random number generator running in low power, low speed. The proposed circuit is analog and Valid all NIST tests ensuring the randomness of a signal.A realization on silicon in 0,35μm technology has been implemented and validated through NIST developed tests Matlab. In this thesis, a number of publications have demonstrated the added value search results

La sécurité et la cryptographie sont des éléments clés pour les dispositifs soumis à des contraintes comme l’IOT, Carte à Puce, Systèm Embarqué, etc. Leur implémentation matérielle constitue un défi en termes de limitation en ressources physiques, vitesse de fonctionnement, capacité de mémoire, etc. Dans ce contexte, comme la plupart des protocoles s’appuient sur la sécurité d’un bon générateur de nombres aléatoires, considéré comme un élément indispensable dans le noyau de sécurité. Par conséquent, le présent travail propose des nouveaux générateurs pseudo-aléatoires basés sur des itérations chaotiques, et conçus pour être déployés sur des supports matériels, à savoir sur du FPGA ou du ASIC. Ces implémentations matérielles peuvent être décrites comme des post-traitements sur des générateurs existants. Elles transforment donc une suite de nombres non-uniformes en une autre suite de nombres uniformes. La dépendance entre l’entrée et la sortie a été prouvée chaotique selon les définitions mathématiques du chaos fournies notamment par Devaney et Li-Yorke. Suite à cela, nous effectuant tout d’abord un état de l’art complet sur les mises en œuvre matérielles et physiques des générateurs de nombres pseudo-aléatoires (PRNG, pour pseudorandom number generators). Nous proposons ensuite de nouveaux générateurs à base d’itérations chaotiques (IC) qui seront testés sur notre plate-forme matérielle. L’idée de départ était de partir du n-cube (ou, de manière équivalente, de la négation vectorielle dans les IC), puis d’enlever un cycle Hamiltonien suffisamment équilibré pour produire de nouvelles fonctions à itérer, à laquelle s’ajoute une permutation en sortie. Les méthodes préconisées pour trouver de bonnes fonctions serons détaillées, et le tout sera implanté sur notre plate-forme FPGA. Les générateurs obtenus disposent généralement d’un meilleur profil statistique que leur entrée, tout en fonctionnant à une grande vitesse. Finalement, nous les implémenterons sur de nombreux supports matériels (65-nm ASIC circuit and Zynq FPGA platform)
Security and cryptography are key elements in constrained devices such as IoT, smart card, embedded system, etc. Their hardware implementations represent a challenge in terms of limitations in physical resources, operating speed, memory capacity, etc. In this context, as most protocols rely on the security of a good random number generator, considered an indispensable element in lightweight security core. Therefore, this work proposes new pseudo-random generators based on chaotic iterations, and designed to be deployed on hardware support, namely FPGA or ASIC. These hardware implementations can be described as post-processing on existing generators. They transform a sequence of numbers not uniform into another sequence of numbers uniform. The dependency between input and output has been proven chaotic, according notably to the mathematical definitions of chaos provided by Devaney and Li-Yorke. Following that, we firstly elaborate or develop out a complete state of the art of the material and physical implementations of pseudo-random number generators (PRNG, for pseudorandom number generators). We then propose new generators based on chaotic iterations (IC) which will be tested on our hardware platform. The initial idea was to start from the n-cube (or, in an equivalent way, the vectorial negation in CIs), then remove a Hamiltonian cycle balanced enough to produce new functions to be iterated, for which is added permutation on output . The methods recommended to find good functions, will be detailed, and the whole will be implemented on our FPGA platform. The resulting generators generally have a better statistical profiles than its inputs, while operating at a high speed. Finally, we will implement them on many hardware support (65-nm ASIC circuit and Zynq FPGA platform)

Les nombres aléatoires sont indispensables dans de nombreuses applications notamment en cryptographie où l’aléa est utilisé dans les protocoles de sécurité. Les générateurs de nombres aléatoires, plus connus sous le nom de RNG comme “Random Number Generator” se déclinent en deux familles, les PRNG (Pseudo RNG) qui sont des générateurs de nombres aléatoires ayant des séquences déterministes et les TRNG (True RNG) qui sont des générateurs d’aléa “vrai”, donc non prédictibles. Les applications cryptographiques utilisent à la fois les TRNG et les PRNG. Un PRNG nécessite une valeur initiale, ou graine, qui peut être la sortie d’un TRNG. Les TRNG tirent profit de l’aléa des phénomènes physiques. Les TRNGs dans les technologies numériques comme les FPGAs font appel à des oscillateurs qui présentent l’inconvénient de pouvoir être attaqués par couplage harmonique. De façon à évaluer la qualité entropique d’un TRNG, des standards basés sur des tests statistiques ont été élaborés par des organismes de certification comme le NIST ou la BSI. Cependant, il est recommandé de formaliser, par le biais d’un modèle, le caractère stochastique de la génération d’aléa. Dans cette thèse, nous étudions une architecture de TRNG, peu coûteuse et robuste face aux attaques harmoniques car elle n’utilise pas d’oscillateurs. Ce TRNG extrait une variable aléatoire en exploitant à la fois les états métastables des bascules et les fluctuations temporelles (ou gigue) des signaux échantillonnés. Nous proposons par la suite un modèle stochastique qui nous permet de décrire le comportement aléatoire du TRNG indépendamment de la technologie ciblée. Les caractérisations et évaluations sur des circuits prototypes en technologies FPGA et ASIC montrent que l’architecture TRNG proposée génère de l’aléa de qualité et est robuste face aux variations environnementales
Random numbers are required in numerous applications namely in cryptography where randomness is used in security protocols. There are two main classes of Random Number Generators (RNG) : The Pseudo RNG (PRNG) which have a deterministic sequence, and the True RNG (TRNG) which generates unpredictable random numbers. Cryptographic applications use both TRNG and PRNG. The PRNG needs an initial value, or seed, which can be the output of a TRNG. In digital technologies, like FPGAs, TRNG are commonly based on oscillators which have the drawback of being biased by harmonic coupling. In order to assess the entropic quality of TRNGs, standards based on statistical tests have been elaborated by certification organisms namely the NIST and the BSI. However, it is recommended to formalize the stochastic behaviour of the randomness generation process. In this Ph.D, we address the design and quality evaluation of TRNGs in digital circuits. We study of a low-cost digital TRNG without oscillators, hence robust against harmonics attacks. The proposed TRNG exploits both the metastability phenomenon and the jitter noise in CMOS digital flip-flops to generate the random numbers. A stochastic model of this TRNG has been formalized. This model describes the random generation process regardless of the targeted technology. The characterization and evaluation on a prototype circuit, in FPGA and ASIC technologies, has shown that the proposed TRNG architecture generates randomness of good quality and is robust against environmental variations