Véritable générateur de nombres aléatoires [fermé]

Question

Désolé, ce n'est pas une "vraie" question, mais il y a quelque temps, je me souviens avoir vu un article ici sur la randomisation aléatoire d'un randomiseur pour générer des nombres vraiment aléatoires, pas seulement pseudo-aléatoires.Je ne le vois pas si je le recherche.

Est-ce que quelqu'un connaît cet article ?

Answer 1

Je crois que c'était allumé thedailywtf.com - c'est à dire.pas quelque chose que vous voulez faire.

Il n'est pas possible d'obtenir un nombre véritablement aléatoire à partir de nombres pseudo-aléatoires, quel que soit le nombre de fois que vous appelez randomize().

Toi peut obtenez de "vrais" nombres aléatoires à partir de spéciaux matériel.Vous pouvez également collecter l'entropie des mouvements de la souris et des choses comme ça.

Answer 2

Je dois être en désaccord avec de nombreuses réponses à cette question.

Il est possible de collecter des données aléatoires sur un ordinateur.SSL, SSH et VPN ne seraient pas sécurisés si vous ne le pouviez pas.

La façon dont fonctionne le générateur de nombres aléatoires est la suivante : piscine de données aléatoires collectées à partir de nombreux endroits différents, tels que la dérive de l'horloge, les horaires d'interruption, etc.

L’astuce de ces schémas est d’estimer correctement le entropie (le nom chic du hasard).Peu importe que la source soit un biais, tant que vous estimez correctement l'entropie.

Pour illustrer cela, la chance que je frappe la lettre e dans ce commentaire est bien supérieur à celui de z , donc si je devais utiliser des interruptions clés comme source d'entropie, ce serait un biais - mais il y a toujours un certain caractère aléatoire dans cette entrée.Vous ne pouvez pas prédire exactement quelle séquence de lettres viendra ensuite dans ce paragraphe.Vous pouvez extraire l'entropie de cette incertitude et l'utiliser dans le cadre d'un octet aléatoire.

Générateurs aléatoires réels de bonne qualité comme Achillée ont une estimation d'entropie assez sophistiquée intégrée et n'émettront que autant d'octets qu'ils peuvent le dire de manière fiable dans leur "pool aléatoire".

Answer 3

À la fin de l'article, je répondrai à votre question de savoir pourquoi vous pourriez vouloir utiliser plusieurs générateurs de nombres aléatoires pour « plus de hasard ».

Il existe des débats philosophiques sur ce que signifie le hasard.Ici, je veux dire "indiscernable à tous égards d'une distribution iid uniforme (0,1) sur les échantillons tirés". J'ignore totalement les questions philosophiques sur ce qu'est le hasard.

Knuth volume 2 contient une analyse dans laquelle il tente de créer un générateur de nombres aléatoires comme vous le suggérez, puis analyse pourquoi il échoue et quels sont les véritables processus aléatoires.Le volume 2 examine les RNG en détail.

Les autres vous recommandent d'utiliser des processus physiques aléatoires pour générer des nombres aléatoires.Cependant, comme nous pouvons le voir dans l’interaction Espo/vt, ces processus peuvent comporter des éléments périodiques subtils et d’autres éléments non aléatoires, en partie dus à des facteurs extérieurs au comportement déterministe.En général, il est préférable de ne jamais présumer du caractère aléatoire, mais de toujours le tester, et vous pouvez généralement corriger ces artefacts si vous en êtes conscient.

Il est possible de créer un flux « infini » de bits qui semble complètement aléatoire, de manière déterministe.Malheureusement, de telles approches augmentent en mémoire avec le nombre de bits demandés (comme elles devraient le faire pour éviter de répéter des cycles), leur portée est donc limitée.

En pratique, il est presque toujours préférable d’utiliser un générateur de nombres pseudo-aléatoires avec des propriétés connues.Les nombres clés à rechercher sont la dimension de l'espace de phase (qui est à peu près décalée entre les échantillons sur lesquels vous pouvez toujours compter sur une distribution uniforme) et la largeur de bits (le nombre de bits dans chaque échantillon qui sont uniformément aléatoires les uns par rapport aux autres. ) et la taille du cycle (le nombre d'échantillons que vous pouvez prélever avant que la distribution ne commence à se répéter).

Cependant, étant donné que les nombres aléatoires d'un générateur donné sont déterministes dans une séquence connue, votre procédure peut être exposée par quelqu'un qui recherche dans le générateur et trouve une séquence d'alignement.Par conséquent, vous pouvez probablement éviter que votre distribution soit immédiatement reconnue comme provenant d'un générateur de nombres aléatoires particulier si vous conservez deux générateurs.À partir du premier, vous échantillonnez i, puis mappez-le uniformément sur un à n, où n est au plus la dimension de phase.Ensuite, dans la seconde, vous échantillonnez i fois et renvoyez le ième résultat.Cela réduira la taille de votre cycle à (taille du cycle d'origine/n) dans le pire des cas, mais pour ce cycle, cela générera toujours des nombres aléatoires uniformes, et ce, de manière à rendre la recherche d'alignement exponentielle en n.Cela réduira également la longueur de la phase indépendante.N'utilisez pas cette méthode à moins que vous compreniez ce que les longueurs de cycle réduites et de phases indépendantes signifient pour votre application.

Answer 4

Un algorithme pour des nombres véritablement aléatoires ne peut exister car définition des nombres aléatoires est :

Avoir des résultats imprévisibles et, dans le cas idéal, tous les résultats tout aussi probables;résultant d'une telle sélection;manquant de corrélation statistique.

Il existe des générateurs de nombres pseudo-aléatoires (PRNG) meilleurs ou pires, c'est-à-diredes séquences de nombres complètement prévisibles et difficiles à prédire sans connaître une information, appelées les graine.

Or, les PRNG pour lesquels il est extrêmement difficile de déduire la graine sont sécurisé cryptographiquement.Vous voudrez peut-être les rechercher sur Google si c'est ce que vous recherchez.

Une autre façon (que cela soit vraiment aléatoire ou non est une question philosophique) consiste à utiliser des sources de données aléatoires.Par exemple, des grandeurs physiques imprévisibles, comme le bruit, ou la mesure de la désintégration radioactive.

Ceux-ci sont toujours sujets à des attaques parce qu’ils peuvent être mesurés de manière indépendante, comportent des biais, etc.C'est donc vraiment délicat.Cela se fait avec du matériel personnalisé, qui est généralement assez coûteux.Je n'ai aucune idée à quel point /dev/random c'est le cas, mais je parierais que ce n'est pas assez bon pour la cryptographie (la plupart des programmes de cryptographie sont livrés avec leur propre RNG et Linux recherche également un RNG matériel au démarrage).

Answer 5

D'après Wikipédia /dev/random, dans les systèmes d'exploitation de type Unix, est un fichier spécial qui sert de véritable générateur de nombres aléatoires.

Le pilote /dev/random collecte le bruit ambiant provenant de diverses sources non déterministes, y compris, sans s'y limiter, les timings entre claviers et les timings entre interruptions qui se produisent dans l'environnement du système d'exploitation.Les données de bruit sont échantillonnées et combinées avec une fonction de mélange de type CRC dans un « pool d'entropie » mis à jour en permanence.Des chaînes de bits aléatoires sont obtenues en prenant un hachage MD5 du contenu de ce pool.La fonction de hachage unidirectionnel distille les véritables bits aléatoires des données du pool et cache l’état du pool aux adversaires.

La routine /dev/random maintient une estimation du véritable caractère aléatoire dans le pool et la diminue chaque fois que des chaînes aléatoires sont demandées.Lorsque l'estimation descend à zéro, la routine se verrouille et attend l'apparition d'événements non déterministes pour actualiser le pool.

Le module noyau /dev/random fournit également une autre interface, /dev/urandom, qui n'attend pas que le pool d'entropie se recharge et renvoie autant d'octets que demandé.En conséquence, /dev/urandom est considérablement plus rapide à générer que /dev/random qui n'est utilisé que lorsqu'un caractère aléatoire de très haute qualité est souhaité.

Answer 6

John von Neumann a dit un jour quelque chose à l'effet que « quiconque tente de générer des nombres aléatoires via des moyens algorithmiques vit, bien sûr, dans le péché ».

Même /dev/random n'est pas aléatoire, au sens du terme mathématicien ou physicien.Même la mesure de la désintégration des radio-isotopes n’est pas aléatoire.(Le taux de décomposition est.La mesure ne l'est pas.Les compteurs Geiger ont un petit temps de réinitialisation après chaque événement détecté, pendant lequel ils sont incapables de détecter de nouveaux événements.Cela conduit à des préjugés subtils.Il existe des moyens d’atténuer considérablement ce problème, mais pas de l’éliminer complètement.)

Arrêtez de chercher le vrai hasard.Un bon générateur de nombres pseudo-aléatoires est vraiment ce que vous recherchez.

Answer 7

Si vous croyez en un univers déterministe, le véritable hasard n’existe pas.:-) Par exemple, quelqu'un a suggéré que la désintégration radioactive est vraiment aléatoire, mais à mon humble avis, ce n'est pas parce que les scientifiques n'ont pas encore élaboré le modèle qu'il n'y a pas de modèle à élaborer.Habituellement, lorsque vous voulez des nombres « aléatoires », vous avez besoin de chiffres pour le cryptage que personne d’autre ne pourra deviner.

Le plus proche du hasard est de mesurer quelque chose de naturel qu’aucun ennemi ne serait également capable de mesurer.Habituellement, vous jetez les bits les plus significatifs de votre mesure, laissant les nombres avec plus de chances d'être répartis uniformément.Les utilisateurs de nombres aléatoires purs et durs disposent d'un matériel spécial qui mesure les événements radioactifs, mais vous pouvez obtenir un certain caractère aléatoire de la part de l'humain utilisant l'ordinateur à partir de choses comme les intervalles de pression des touches et les mouvements de la souris, et si l'ordinateur n'a pas d'utilisateurs directs, à partir des capteurs de température du processeur, et du trafic réseau.Vous pouvez également utiliser des éléments tels que des webcams et des microphones connectés à des cartes son, mais je ne sais pas si quelqu'un le fait.

Answer 8

Pour résumer une partie de ce qui a été dit, notre définition de travail de ce qu’est une source sécurisée de hasard est similaire à notre définition de la sécurité cryptographique :cela semble aléatoire si des gens intelligents l'ont examiné et n'ont pas été en mesure de montrer que ce n'est pas complètement imprévisible.

Il y a Non système pour générer des nombres aléatoires qui ne pourraient pas être prédits, tout comme il n'existe aucun chiffre cryptographique qui ne puisse être déchiffré.Les solutions fiables utilisées pour des travaux importants sont simplement celles qui se sont révélées difficiles à vaincre jusqu’à présent.Si quelqu'un vous dit le contraire, il vous vend quelque chose.

L'intelligence est rarement récompensée en cryptographie.Optez pour des solutions éprouvées.

Answer 9

Un ordinateur dispose généralement de nombreuses sources physiques de bruit aléatoire facilement disponibles :

• Microphone (espérons-le dans un endroit bruyant)
• Vidéo compressée provenant d'une webcam (pointée vers quelque chose de variable, comme une lampe à lave ou une rue)
• Synchronisation du clavier et de la souris
• Contenu et timing des paquets réseau (le monde entier contribue)

Et parfois

• Matériel basé sur la dérive d'horloge
• Compteurs Geiger et autres détecteurs d'événements rares
• Toutes sortes de capteurs connectés aux convertisseurs A/D

La difficulté est d'estimer l'entropie de ces sources, qui est dans la plupart des cas faible malgré des débits élevés et très variable ;mais l'entropie peut être estimée avec des hypothèses prudentes, ou du moins pas gaspillée, pour alimenter des systèmes comme Yarrow ou Fortuna.

Answer 10

Il n'est pas possible d'obtenir de « vrais » nombres aléatoires, un ordinateur est une construction logique qui ne peut pas créer quoi que ce soit « vraiment » aléatoire, seulement du pseudo-aléatoire.Il existe cependant de meilleurs et de pires algorithmes pseudo-aléatoires.

Afin d'obtenir un nombre « véritablement » aléatoire, vous avez besoin d'une source aléatoire physique. Certaines machines à sous les intègrent - il s'agit souvent d'une source radioactive, la désintégration radioactive (qui, à ma connaissance, est vraiment aléatoire) est utilisé pour générer les nombres.

Answer 11

L'une des meilleures méthodes pour générer un nombre aléatoire consiste à Dérive de l'horloge.Cela fonctionne principalement avec deux oscillateurs.

Une analogie avec la façon dont cela fonctionne est d'imaginer une voiture de course sur un simple circuit ovale avec une ligne while au début du tour et également une ligne while sur l'un des pneus.Lorsque la voiture termine un tour, un numéro sera généré en fonction de la différence entre la position de la ligne blanche sur la route et sur le pneu.

Très facile à générer et impossible à prévoir.