Générateur de nombres aléatoires matériel

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En informatique, un générateur de nombres aléatoires matériel (aussi appelé générateur de nombres aléatoires physique ; en anglais, hardware random number generator ou true random number generator) est un appareil qui génère des nombres aléatoires à partir d'un phénomène physique, plutôt qu'au moyen d'un programme informatique.

De tels appareils sont souvent basés sur des phénomènes microscopiques qui génèrent de faibles signaux de bruit statistiquement aléatoires, tels que le bruit thermique ou l'effet photoélectrique. Ils impliquent souvent un miroir semi-réfléchissant ou d'autres phénomènes quantiques. Ces processus stochastiques sont, en théorie, totalement imprévisibles.

Un générateur de nombres aléatoires matériel consiste typiquement en

En échantillonnant de façon répétée les nombres obtenus, on obtient une suite de nombres aléatoires.

La principale application des générateurs de nombres aléatoires matériels est en cryptographie, où ils sont utilisés pour générer des clés cryptographiques aléatoires servant à transmettre des données en toute sécurité. Ils sont largement utilisés dans les protocoles de chiffrement Internet tels que le protocole Secure Sockets Layer (SSL).

Les générateurs de nombres aléatoires matériels peuvent également être construits à partir de processus macroscopiques aléatoires, en utilisant des dispositifs tels que le jeu de pile ou face, les dés, les roulettes et les diverses machines de loterie. La présence de l'imprévisibilité dans ces phénomènes s'appuie sur la théorie des systèmes dynamiques instables et la théorie du chaos. Même si les processus macroscopiques sont déterministes selon la mécanique newtonienne, en pratique, la sortie d'un dispositif bien conçu comme une roulette ne peut pas être prédite, car elle dépend des micro détails des conditions initiales de chaque utilisation et ces micro détails ne peuvent pas être mesurés et contrôlés.

Bien que les dés aient été surtout utilisés dans les jeux de hasard et, plus récemment, comme des éléments de randomisation dans les jeux (par exemple, les jeux de rôle), le savant victorien Francis Galton a décrit une façon d'utiliser des dés pour générer des nombres aléatoires explicitement à des fins scientifiques en 1890[1].

Les générateurs de nombres aléatoires matériels produisent généralement un nombre limité de bits aléatoires par seconde. Afin d'augmenter le débit de bits aléatoires, ils sont souvent utilisés pour générer une graine aléatoire pour un générateur de nombres pseudo-aléatoires plus rapide.

Utilisations[modifier | modifier le code]

Des suites de nombres aléatoires ont d'abord été étudiées dans le contexte des jeux de hasard. De nombreux dispositifs de randomisation tels que les dés, le brassage de cartes à jouer et les roues de roulette, ont été développés pour de telles utilisations. Les suites de nombres aléatoires sont vitales pour les jeux de hasard électroniques et les manières de les produire sont souvent réglementées par des commissions gouvernementales de jeu.

Les nombres aléatoires sont également utilisés à des fins autres que le jeu, comme l'échantillonnage pour les sondages d'opinion et dans les cas où l'équité est obtenue par la randomisation, comme le choix des membres d'un jury ou des personnes qui doivent joindre une armée pour prendre part à une guerre.

Cryptographie[modifier | modifier le code]

Article connexe : Cryptographie.

L'utilisation principale des générateurs de nombres aléatoires matériels est le chiffrement des données, par exemple pour créer des clés cryptographiques pour chiffrer les données. Ils constituent une alternative plus sûre aux générateurs de nombres pseudo-aléatoires logiciels couramment utilisés dans les ordinateurs pour générer des nombres aléatoires.

Les générateurs de nombres pseudo-aléatoires utilisent un algorithme déterministe pour produire des séquences de nombres aléatoires. Bien que ces séquences pseudo-aléatoires passent des tests de modèles statistiques confirmant que les nombres sont aléatoires, en connaissant l'algorithme et la graine utilisée pour l'initialiser, la suite de nombres aléatoires peut être prédite.

Comme la séquence de nombres produits par un générateur de nombres pseudo-aléatoires est prévisible, les données chiffrées avec des nombres pseudo-aléatoires sont potentiellement vulnérables à la cryptanalyse. Les générateurs de nombres aléatoires matériels produisent des séquences de nombres qui ne sont pas prévisibles et fournissent donc un plus haut niveau de sécurité lorsqu'ils sont utilisés pour chiffrer des données.

Premiers travaux[modifier | modifier le code]

Un des premiers outils matériels pour produire des nombres aléatoires était une variation des machines utilisées pour jouer au keno ou sélectionner les numéros gagnants d'une loterie. Dans ces machines, des balles de ping-pong numérotées étaient mélangées par de l'air soufflé, elles étaient aussi parfois agitées mécaniquement, puis elles étaient retirées de la chambre de mélange par un procédé quelconque (voir brevet US 4 786 056).

Cette méthode donne des résultats acceptables, mais les nombres aléatoires générés par ce moyen sont coûteux. La méthode est intrinsèquement lente et inutilisable par la plupart des applications informatiques.

Le 29 avril 1947, la RAND Corporation a commencé à générer des nombres aléatoires avec une roue de roulette électronique, constituée d'une source d'impulsions de fréquence aléatoire d'environ 100 000 impulsions par seconde échantillonnée une fois par seconde par une impulsion de fréquence constante qui déclenchait la copie de 5 impulsions dans une mémoire de cinq bits.

Un peu plus tard, Douglas Aircraft a construit un générateur de nombres aléatoires appelé machine RAND, en mettant en œuvre une suggestion de Cecil Hasting[2] pour une source de bruit (très probablement le comportement bien connu du tube miniature de gaz thyratron 6D4, placé dans un champ magnétique[3]). Vingt des 32 bits de la mémoire recueillant la suite de bits aléatoires produite étaient convertis en un nombre de 10 chiffres décimaux et les 12 autres bits étaient ignorés[4].

La longue suite de nombres aléatoires de la machine RAND, filtrée et testée, a été convertie en une table, qui a été publiée en 1955 dans le livre A Million Random Digits avec 100 000 Normal Deviates (en). La table RAND a été une percée significative dans la fourniture de nombres aléatoires parce qu'une table si longue et si soigneusement préparée n'avait jamais été disponible.

La table a été une source utile pour les simulations, la modélisation et pour dériver les constantes arbitraires dans les algorithmes cryptographiques. Les algorithmes de chiffrement par bloc Khufu et Khafre sont parmi les applications qui utilisent la table RAND[5],[note 1].

Phénomènes physiques avec propriétés aléatoires quantiques[modifier | modifier le code]

Deux types de phénomènes physiques quantiques exhibant des caractéristiques aléatoires sont utilisés pour générer des nombres aléatoires : les phénomènes quantiques au niveau atomique ou sous-atomique et les phénomènes liés au bruit thermique (dont certains, mais pas tous, sont d'origine quantique). La mécanique quantique prédit que certains phénomènes physiques, tels que la désintégration nucléaire des atomes, sont fondamentalement aléatoires et ne peuvent être prédits (pour une analyse de la vérification empirique de l'imprévisibilité quantique, voir les expériences sur les inégalités de Bell). Et, parce que nous vivons à une température au-dessus du zéro absolu, chaque système a une variation aléatoire dans son état. Par exemple, les molécules de gaz qui composent l'air rebondissent constamment les unes sur les autres de façon aléatoire (voir mécanique statistique). Ce hasard est aussi un phénomène quantique[note 2].

Parce que le résultat des événements quantiques ne peut pas être prédit, ces événements sont des sources idéales pour la génération de nombres aléatoires. Voici quelques phénomènes quantiques utilisés pour la génération de nombres aléatoires :

Phénomènes physiques avec propriétés aléatoires non quantiques[modifier | modifier le code]

Parmi les phénomènes physiques avec propriétés aléatoires non quantiques, les phénomènes thermiques sont plus faciles à détecter. Ils sont quelque peu vulnérables aux attaques par un abaissement de la température du système, bien que la plupart des systèmes cesseront de fonctionner à des températures suffisamment basses pour réduire le bruit par un facteur de deux (par exemple, ~ 150 K). Les phénomènes thermiques utilisés comprennent :

Un autre phénomène qui peut être utilisé est la dérive d'horloge (en).

Utilisation d'événements observés[modifier | modifier le code]

Les informaticiens sans véritables générateurs de nombres aléatoires matériels tentent souvent de générer des nombres aléatoires en mesurant des événements physiques disponibles à un logiciel. Un exemple consiste à mesurer le temps entre deux frappes sur les touches du clavier d'un ordinateur, puis à prendre les bits les moins significatifs de la mesure comme un nombre aléatoire. Des approches similaires mesurent l'ordonnancement des tâches, les accès au réseau, les temps de recherche de la tête de disque et d'autres événements à l'intérieur d'un ordinateur.

Ces méthodes, basées sur la mesure d'événements, sont risquées lorsqu'elles utilisent des événements contrôlés par ordinateur, car un attaquant intelligent pourrait prédire une clé cryptographique en contrôlant les événements. Ces méthodes sont également risquées parce que l'événement supposément généré par l'utilisateur (par exemple, les frappes sur les touches du clavier) peut être falsifié par un attaquant suffisamment ingénieux, permettant le contrôle des mesures aléatoires utilisées pour générer les nombres aléatoires.

Toutefois, en y consacrant suffisamment de soin, il est possible de concevoir un système produisant des nombres aléatoires cryptographiquement sûrs à partir d'événements aléatoires disponibles dans un ordinateur moderne. Le concept de base est de générer une suite de bits aléatoires qui sont supposément inconnus d'un attaquant. Un nouveau bit est ajouté à la suite chaque fois qu'il est possible de le faire (par exemple, lorsque l'utilisateur frappe une touche du clavier) et un compte du nombre de bits dans la suite est maintenu. Lorsque des bits aléatoires sont demandés, des bits sont extraits de la suite de bits aléatoires et le compteur est décrémenté. Si un nombre suffisant de bits n'est pas disponible, le système attend qu'un nombre suffisant de nouveaux bits aléatoires deviennent disponibles.

Problèmes[modifier | modifier le code]

Il est très facile de mal construire des systèmes matériels ou logiciels qui tentent de générer des nombres aléatoires. En outre, la plupart de ceux-ci « brisent » silencieusement, produisant souvent des nombres de moins en moins aléatoires à mesure qu'ils se dégradent.

Un exemple de cette dégradation lente est la radioactivité décroissante d'une source radioactive ayant une courte demi-vie. De nombreux autres facteurs peuvent réduire graduellement la qualité d'un générateur et ces facteurs sont complexes et difficiles à détecter.

Parce que les dispositifs contenant des sources de phénomènes aléatoires sont souvent très fragiles et se dégradent silencieusement, des tests statistiques sur leurs sorties doivent être effectués en continu. Plusieurs, mais pas tous, de tels dispositifs incluent de tels tests dans le logiciel qui fournit les nombres aléatoires.

Attaques[modifier | modifier le code]

Tout comme pour les autres composants d'un système cryptographique, un générateur de nombres aléatoires doit être conçu pour résister à des attaques. Toutefois, se défendre contre des attaques est difficile.

Par exemple, le générateur de nombres aléatoires utilisé à des fins cryptographiques dans la version 1.1 du navigateur Netscape était vulnérable et a été rapidement corrigé dans la version 2.0.

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hardware random number generator » (voir la liste des auteurs).
  1. Voir aussi « Nothing up my sleeve numbers (en) ».
  2. Voir « phonon».

Références[modifier | modifier le code]

  1. (en) Francis Galton, « Dice for statistical experiments », Nature, vol. 42,‎ , p. 13–14 (DOI 10.1038/042013a0, lire en ligne)
  2. (en) « P-113 », Rand Corporation
  3. (en) Curry Cobine, « Electrical Noise Generators », Proceedings of the I.R.E.,‎ , p. 875–9
  4. (en) « Monograph report », Rand Corporation.
  5. (en) Bruce Schneier, Applied Cryptography, John Wiley & Sons, Inc. (ISBN 0-471-11709-9), « Other Stream Ciphers and Real Random-Sequence Generators », p. 423
  6. (en) A. Marandi, N. C. Leindecker, K. L. Vodopyanov et R. L. Byer, « All-optical quantum random bit generation from intrinsically binary phase of parametric oscillators », Opt. Express, vol. 20,‎ , p. 19322–19330 (DOI 10.1364/OE.20.019322, lire en ligne)
  7. (en) T. Symul, S. M. Assad et P. K. Lam, « Real time demonstration of high bitrate quantum random number generation with coherent laser light », Appl. Phys. Lett., vol. 98,‎ (DOI 10.1063/1.3597793, arXiv 1107.4438)