Présentation

Article

1 - AVANT-PROPOS

2 - DÉFINITIONS

3 - EXEMPLES DE GÉNÉRATEURS PSEUDO-ALÉATOIRES

4 - EXEMPLES DE GÉNÉRATEURS VÉRITABLEMENT ALÉATOIRES

5 - EXEMPLES DE GÉNÉRATEURS ALÉATOIRES HYBRIDES

6 - TESTS DE LA QUALITÉ DE L'ALÉA

7 - UTILISATION DES NOMBRES ALÉATOIRES

8 - CONCLUSION

Article de référence | Réf : H5215 v1

Avant-propos
Circuits électroniques pour la génération de nombres aléatoires

Auteur(s) : Arnaud TISSERAND

Relu et validé le 07 févr. 2020

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

RÉSUMÉ

Deux principaux types de générateurs de nombres aléatoires existent : les générateurs pseudo-aléatoires basés sur des algorithmes déterministes, et les générateurs réellement aléatoires qui utilisent des sources de bruit physique ayant des propriétés stochastiques. Cet article présente leurs principes élémentaires et quelques exemples de générateurs. Le délicat problème de l'évaluation de la qualité de l'aléa est abordé, ainsi que quelques applications typiques qui illustrent les différents besoins.

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

ABSTRACT

Electronic circuit for random-numbers generation

There are two main types of random number generators: the pseudo-random generators based on deterministic algorithms and the true random generators based on physical noise sources with chaotic properties. This document presents their main principles and a few examples of generators, and then discuss the tricky problem of randomness evaluation as well as some typical applications.

Auteur(s)

  • Arnaud TISSERAND : Chargé de recherche au Centre National de la Recherche Scientifique (CNRS), docteur en informatique, HDR - Chercheur dans le laboratoire IRISA et l'équipe-projet CAIRN à Lannion - Enseignant vacataire à l'université Rennes 1 et l'École Nationale Supérieure des Sciences Appliquées et de Technologie (ENSSAT).

INTRODUCTION

Des nombres aléatoires sont nécessaires dans certaines applications : loteries, jeux informatiques, cryptographie, sécurité des systèmes, simulation numérique, algorithmes randomisés, test de programmes et de circuits intégrés, etc. Pour cela, on utilise des générateurs de nombres aléatoires ou RNG (random number generators). Il existe deux principaux types de RNG : d'une part, les générateurs pseudo-aléatoires ou PRNG (Pseudo RNG) basés sur des algorithmes déterministes, et d'autre part, les générateurs de nombres vraiment aléatoires ou TRNG (True RNG) qui exploitent une source de bruit physique ayant des propriétés stochastiques.

Deux caractéristiques principales guident le choix d'un RNG : son débit et la qualité de l'aléa produit. Le débit doit être adapté à l'application cible, mais d'autres caractéristiques existent telles que le coût du générateur, son temps de démarrage et le caractère constant ou variable de son débit dans le temps.

La qualité d'un RNG est probablement sa caractéristique la plus importante, mais aussi la plus complexe à évaluer. La séquence aléatoire engendrée doit présenter une distribution de probabilité uniforme et équiprobable. De plus, chaque nouvel élément de la séquence doit être statistiquement indépendant et non-prédictible par rapport aux éléments précédents. Dans certaines applications, on requiert que la séquence soit non-reproductible, c'est-à-dire totalement différente après chaque redémarrage. Enfin, dans certaines applications sécurisées, rien ou personne ne doit pouvoir prédire ou biaiser les valeurs produites : c'est la résistance aux attaques.

Les PRNG peuvent être implantés en logiciel ou bien en matériel. Il existe des PRNG logiciels performants, c'est-à-dire avec un très haut débit et une bonne qualité d'aléa pour un coût limité, pour la plupart des types de processeurs. En matériel, de nombreux PRNG existent pour des ASIC (Application Specific Integrated Circuits) et des FPGA (Field Programmable Gate Arrays). On sait concevoir des PRNG avec d'excellentes caractéristiques d'uniformité, d'équiprobabilité, d'indépendance et de non-prédictibilité. Mais les PRNG sont déterministes, ils ne peuvent pas assurer la caractéristique de non-reproductibilité des séquences après chaque redémarrage. En pratique, il faut une source vraiment aléatoire pour les initialiser correctement.

Les TRNG nécessitent une implantation matérielle, comme un circuit intégré, pour la source de bruit physique. Cette source de bruit physique présente des propriétés de non-prédictibilité et non-reproductibilité du fait de certains phénomènes physiques stochastiques (par exemple, bruit thermique ou électro- magnétique, mécanique quantique, désintégration radioactive). Mais le bruit physique « idéal » est mélangé, et souvent dilué, à d'autres bruits liés au fonctionnement du circuit intégré et de son environnement (horloge du circuit, perturbations électromagnétiques, variations de la tension d'alimentation ou de la température, etc.). Pour concevoir un bon TRNG, il faut extraire le bruit physique vraiment aléatoire des autres bruits. Cette extraction est complexe et délicate. De plus, la source de bruit physique dépend de nombreux paramètres (température, tension d'alimentation, couplages entre blocs du circuit, vieillissement des matériaux, etc.). Des attaques basées sur des modifications de ces paramètres sont possibles pour réduire la qualité de l'aléa produit.

Les TRNG assurent la non-reproductibilité mais avec un coût souvent plus important qu'un PRNG de débit équivalent. On peut alors associer ces deux types de RNG dans un générateur hybride ou HRNG (Hybrid RND). Ainsi, un TRNG produit un véritable aléa physique utilisé pour initialiser, régulièrement ou parfois, un PRNG qui assure un haut débit et une bonne qualité statistique.

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

KEYWORDS

True random number generator   |   pseudo random number generator   |   physical noise sources   |   randomness quality evaluation   |   Information technology   |   microelectronic   |   integrated circuits   |   digital security

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-h5215


Cet article fait partie de l’offre

Technologies logicielles Architectures des systèmes

(233 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Présentation

1. Avant-propos

1.1 Sources d'information et terminologie

Il existe de nombreuses références sur les générateurs de nombres aléatoires, leur évaluation empirique ou analyse théorique, et leur utilisation dans différentes applications. Les équipes de recherche françaises sont très actives dans le domaine des générateurs aléatoires. Ce n'est donc pas par pur chauvinisme que nous référençons différents travaux, thèses et ouvrages en français, mais parce que de bonnes références sont disponibles naturellement dans cette langue.

Dans l'encyclopédique « The Art of Computer Programming » de D. Knuth, on trouve une très bonne introduction sur les générateurs pseudo-aléatoires, les tests statistiques, quelques utilisations et exemples . Il peut servir de base à ce qui est présenté dans la suite à l'exclusion des aspects électroniques. Sur des aspects plus théoriques, le deuxième chapitre du livre  de J.-P. Delahaye traite de la formalisation des suites aléatoires. Le livre de médiation scientifique  du même auteur donne de nombreux exemples liés à l'utilisation de nombres aléatoires. Enfin, le livre collectif ...

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Technologies logicielles Architectures des systèmes

(233 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Avant-propos
Sommaire
Sommaire

BIBLIOGRAPHIE

  • (1) - KNUTH (D.E.) -   Randm numbers.  -  Chapter 3 in The Art of Computer Programming, Seminumerical Algorithms, 3rd edition, Addison-Wesley, vol. 2 (1997).

  • (2) - DELAHAYE (J.-P.) -   Information complexité et hasard.  -  2e édition. Hermès (1999).

  • (3) - DELAHAYE (J.-P.) -   Complexités : aux limites des mathématiques et de l'informatique.  -  Belin/Pour la Science (2006).

  • (4) - DELAHAYE (J.-P.) (coordinateur) -   Le hasard : une idée, un concept, un outil.  -  L'Harmattan (2005).

  • (5) - L'ECUYER (P.) -   Random number generation.  -  Chapter 2 of the Handbook of Computational Statistics, p. 35-70, Springer (2004) http://www.iro.umontreal.ca/lecuyer/myftp/papers/handstat.pdf

  • (6) - SCHNEIER (B.) -   Applied Cryptography.  -  ...

1 Outils logiciels

DIEHARD : bibliothèque de tests statistiques proposée en 1995 par G. Marsaglia https://github.com/nmondal/diehard.c

DIEHARDER : bibliothèque de tests statistiques plus complète que DIEHARD et maintenue par R. Brown depuis 2003 http://www.phy.duke.edu/rgb/General/dieharder.php

TestU01 : bibliothèque C de P. L'Ecuyer et R. Simard disponible depuis 2007 http://www.iro.umontreal.ca/simardr/testu01/tu01.html

HAUT DE PAGE

2 Sites Internet

L'ECUYER Pierre. Page professionnelle (nombreux publications, logiciels et références sur les PRNG) http://www.iro.umontreal.ca/lecueyer

Page d'un groupe d'informaticiens...

Cet article est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Technologies logicielles Architectures des systèmes

(233 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS