Vrai générateur de nombres aléatoires [fermé]

Je dois être en désaccord avec beaucoup de 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 le générateur de nombres aléatoires logiciel fonctionne est il y a un pool de données aléatoires qui sont recueillies à 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 consiste à estimer correctement l'entropie (le nom chic pour le l'aléatoire). Peu importe que la source soit biaisée, tant que vous estimez correctement l'entropie.

Pour illustrer cela, la chance que je frappe la lettre e dans ce commentaire est beaucoup plus élevée que celle de z , donc si je devais utiliser des interruptions clés comme source d'entropie, ce serait un biais - mais il y a encore un peu de hasard à avoir 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 partie d'un octet aléatoire.

Les générateurs aléatoires réels de bonne qualité comme Yarrow ont une estimation d'entropie assez sophistiquée intégrée à eux et n'émettront que autant d'octets qu'il peut dire de manière fiable qu'il a dans son " pool aléatoire."

À la fin du post, 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 y a des débats philosophiques sur ce que signifie le hasard. Ici, je veux dire "indiscernable à tous égards d'une distribution uniforme(0,1) iid sur les échantillons tirés" j'ignore totalement les questions philosophiques de ce qu'est le hasard.

Knuth volume 2 a une analyse où 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 vrais 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 avoir des éléments périodiques subtils et d'autres éléments non aléatoires, en partie en raison de facteurs extérieurs avec un comportement déterministe. En général, il est préférable de ne jamais supposer le hasard, mais toujours de tester pour cela, et vous habituellement peut corriger pour de tels artefacts si vous êtes au courant d'eux.

Il est possible de créer un flux "infini" de bits qui apparaît complètement aléatoire, déterministe. Malheureusement, de telles approches se développent en mémoire avec le nombre de bits demandés (comme il le faudrait, pour éviter de répéter des cycles), de sorte que leur portée est 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 chiffres clés à rechercher est le la dimension de l'espace de phase (qui est approximativement décalée entre les échantillons sur lesquels vous pouvez toujours compter) et la largeur de bit (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 prendre avant que la distribution commence à se répéter).

Cependant, puisque 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 cherchant dans le générateur et trouver 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 maintenez deux générateurs. Dès le premier, vous échantillonnez i, puis mappez ceci de manière uniforme 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 de cycle originale / n) dans le pire des cas, mais pour ce cycle toujours générer des nombres aléatoires uniformes, et le faire d'une manière qui rend la recherche d'alignement exponentielle dans N. cela réduira également la longueur de phase indépendante. N'utilisez pas cette méthode à moins de comprendre ce que signifient les longueurs de cycle et de phase indépendantes réduites pour votre application.

Un algorithme pour les nombres vraiment aléatoires ne peut pas exister car la définition des nombres aléatoires est:

Ayant des résultats imprévisibles et, dans le cas idéal, tous les résultats aussi probable; résultant de tels sélection; manque de statistiques corrélation.

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

Maintenant, les PRNGs pour lesquels il est extrêmement difficile de déduire la graine sont cryptographiquement sécurisés. Vous voudrez peut-être chercher dans Google, si c'est ce que vous cherchez.

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

Ceux-ci sont toujours soumis à des attaques car ils peuvent être indépendamment mesurée, ont des biais, et ainsi de suite. Donc c'est vraiment délicat. Ceci est fait avec du matériel personnalisé, ce qui est généralement assez cher. Je n'ai aucune idée de la qualité de /dev/random, mais je parie que ce n'est pas assez bon pour la cryptographie (la plupart des programmes de cryptographie viennent avec leur propre RNG et Linux cherche également un RNG matériel au démarrage).

Selon Wikipedia /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 rassemble le bruit ambiant provenant de diverses sources non déterministes, y compris, mais sans s'y limiter, les timings inter-clavier et les timings inter-interruption 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"de mise à jour continue. Les chaînes de bits aléatoires sont obtenues en prenant un hachage MD5 du contenu de ce pool. La fonction de hachage unidirectionnelle distille les vrais bits aléatoires des données du pool et masque l'état du pool des adversaires.

La routine/dev / random maintient une estimation du caractère aléatoire réel 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 verrouille et attend l'apparition d'événements non déterministes pour actualiser le piscine.

Le module/dev / random kernel fournit également une autre interface, /dev / urandom, qui n'attend pas la recharge du pool entropy et renvoie autant d'octets que demandé. Par conséquent, /dev/urandom est considérablement plus rapide à la génération par rapport à /dev/random qui n'est utilisé que lorsque le caractère aléatoire de très haute qualité est souhaité.

John von Neumann a dit quelque chose à l'effet de "toute personne essayant de générer des nombres aléatoires par des moyens algorithmiques est, bien sûr, vivant dans le péché."

Même pas / dev / random est aléatoire, dans le sens du mot par un mathématicien ou un physicien. Même la mesure de la désintégration des radio-isotopes n'est pas aléatoire. (Le taux de décroissance est. 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 à subtil préjugés. Il existe des moyens d'atténuer considérablement cela, mais pas de l'éliminer complètement.)

Arrêtez de chercher le vrai hasard. Un bon générateur de nombres pseudorandom est vraiment ce que vous cherchez.

Si vous croyez en un univers déterministe, le vrai 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, Juste parce que les scientifiques n'ont pas encore élaboré le modèle, ne signifie pas 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 chiffrement que personne d'autre ne pourra deviner.

Le plus proche que vous pouvez obtenir au hasard est de mesurer quelque chose 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 sont plus susceptibles d'être répartis uniformément. Les utilisateurs de nombres aléatoires de noyau dur obtiennent du matériel spécial qui mesure les événements radioactifs, mais vous pouvez obtenir un peu de hasard de l'humain en utilisant l'ordinateur à partir de choses comme les intervalles de pression sur les touches et les mouvements de la souris, et si l'ordinateur n'a pas d'utilisateurs directs, des capteurs de température Vous pourrait également utiliser des choses comme les webcams et les microphones connectés aux cartes son, mais je ne sais pas si quelqu'un le fait.

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 cryptographiquement sécurisé: il semble aléatoire si les gens intelligents l'ont regardé et n'ont pas été en mesure de montrer qu'il n'est pas complètement imprévisible.

Il n'y a Pas de système pour générer des nombres aléatoires qui ne pourraient pas être prédits, tout comme il n'y a pas de chiffrement cryptographique qui ne pourrait pas être fissuré. Les solutions de confiance utilisé pour un travail important sont simplement ceux qui se sont révélés difficiles à vaincre jusqu'à présent. Si quelqu'un vous dit le contraire, ils vous vendent quelque chose.

L'Intelligence est rarement récompensée en cryptographie. Aller avec des solutions éprouvées.

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

• Microphone (espérons dans un endroit bruyant)
• vidéo compressée à partir 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 calendrier 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 de rares les événements
• toutes sortes de capteurs attachés aux convertisseurs A/N

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

Il n'est pas possible d'obtenir des nombres aléatoires "vrais", un ordinateur est une construction logique qui ne peut pas créer "vraiment" quelque chose de Aléatoire, seulement pseudo-aléatoire. Il y a de meilleurs et de pires algorithmes pseudo-aléatoires là-bas, cependant.

Afin d'obtenir une "vraiment" nombre aléatoire vous avez besoin d'un physique source aléatoires, certaines machines ont en réalité ces construit en: c'est souvent une source radioactive, la désintégration radioactive (qui, autant que je sais, c'est véritablement aléatoire) est utilisé pour générer les chiffres.

L'une des meilleures méthodes pour générer un nombre aléatoire consiste à utiliser Clock Drift . Cela fonctionne principalement avec deux oscillateurs.

Une analogie de la façon dont cela fonctionne est d'imaginer une voiture de course sur un simple circuit ovale avec une ligne au début du tour et aussi un tout en ligne sur l'un des pneus. Lorsque la voiture termine un tour, un nombre 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édire.