En quoi les nombres pseudo-aléatoires et les nombres véritablement aléatoires sont-ils différents et pourquoi est-ce important ?

La réponse courte est que généralement Les gens exigent le "vrai hasard" pour une mauvaise raison, à savoir qu'ils ne comprennent rien à la cryptographie.

Les primitives cryptographiques telles que chiffrement par flux y CSPRNGs sont utilisés pour produire d'énormes flux de bits imprévisibles après avoir été alimentés par quelques bits imprévisibles.

Le lecteur attentif aura compris qu'il s'agit d'un problème d'amorçage : nous devons rassembler quelques éléments d'entropie pour commencer. Nous pouvons ensuite les introduire dans un CSPRNG qui, à son tour, fournira avec bonheur tous les bits imprévisibles dont nous avons besoin. Ainsi, Un RNG matériel est nécessaire pour ensemencer un CSPRNG. . C'est le seul cas où l'entropie est nécessaire à la vérité.

(Je pense que cela aurait dû être posté dans Sécurité ou Cryptographie).

Edit : En fin de compte, il faut choisir un générateur de nombres aléatoires qui soit suffisamment bon pour la tâche envisagée et en ce qui concerne la génération de nombres aléatoires, matériel n'est pas nécessairement synonyme de bon. Tout comme les mauvais PRNGs, les sources aléatoires matérielles ont généralement des biais.

Edit : Certaines personnes ici supposent un modèle de menace dans lequel un attaquant pourrait lire l'état interne d'un CSPRNG et en déduire que les CSPRNGs ne sont pas une solution sûre. C'est un exemple de mauvais modèle de menace. Si un attaquant possède votre système, la partie est terminée, purement et simplement. A ce stade, cela ne fait aucune différence que vous utilisiez un TRNG ou un CSPRNG.

Edit : Donc, pour résumer tout ça... L'entropie est nécessaire pour ensemencer un CSPRNG. Une fois cela fait, un CSPRNG fournira tous les bits imprévisibles dont nous avons besoin pour les applications de sécurité beaucoup plus rapidement que nous pouvons (généralement) collecter l'entropie. Si l'imprévisibilité n'est pas nécessaire, comme pour la simulation, un Mersenne Twister fournira des nombres avec de bonnes propriétés statistiques à un rythme beaucoup plus rapide.

Edit : Toute personne désireuse de comprendre le problème de la génération sécurisée de nombres aléatoires devrait lire ceci : http://www.cigital.com/whitepapers/dl/The_Importance_of_Reliable_Randomness.pdf

Tous les PRNG ne conviennent pas à toutes les utilisations. Par exemple, Java.util.SecureRandom utilise le hachage SHA1, dont la taille de sortie est de 160 bits. Cela signifie qu'il y a 2 160 les flux possibles de nombres aléatoires qui peuvent en découler. C'est aussi simple que cela. Vous ne pouvez pas obtenir plus de 2 160 les valeurs de l'état interne. Ainsi, vous ne pouvez pas obtenir plus de 2 160 des flux uniques de nombres aléatoires à partir d'une seule graine, quelle que soit l'origine de cette dernière. Windows CryptGenRandom est censé utiliser un état de 40 octets, il a 2 320 flux possibles de nombres aléatoires.

Le nombre de façons de mélanger un jeu standard de 52 cartes est de 52, soit environ 2. 226 . Ainsi, indépendamment de l'ensemencement, vous ne pourriez pas utiliser Java.util.SecureRandom pour mélanger un jeu de cartes. Il y a environ 2 66 les mélanges possibles qu'il ne peut pas produire. Bien sûr, nous ne savons pas lesquels ils sont...

Ainsi, si je disposais d'une source de, disons, 256 bits de véritable caractère aléatoire (par exemple, à partir d'une carte RNG Quantis), je pourrais ensemencer un PRNG comme CryptGenRandom() avec cette graine, puis utiliser le PRNG pour mélanger un jeu de cartes. Si je réensemence avec un véritable caractère aléatoire à chaque mélange, tout ira bien : imprévisible et statistiquement aléatoire. Si je faisais la même chose avec Java.util.SecureRandom, il y aurait des mélanges qui ne pourraient pas être produits, parce qu'il ne peut pas être ensemencé avec 256 bits d'entropie, et son état interne ne peut pas représenter tous les mélanges possibles.

Notez que les résultats de java.util.SecureRandom seraient à la fois imprévisibles et statistiquement aléatoires. Aucun test statistique ne permettrait d'identifier un problème ! Mais la sortie du RNG n'est pas assez grande pour couvrir le domaine complet de toutes les sorties possibles nécessaires pour simuler un jeu de cartes.

Et rappelez-vous, si vous ajoutez les jokers, c'est 54 ! que vous devez couvrir, ce qui nécessite environ 2 238 possibilités.

Les nombres pseudo-aléatoires sont générés en utilisant une fonction mathématique et une valeur initiale (appelée le graines ), alors que les nombres aléatoires ne le sont pas. Leur prévisibilité les rend incroyablement utile pour les reprises de jeu, car il suffit de sauvegarder la graine et l'entrée du joueur - l'IA répondra exactement de la même manière "aléatoire" à chaque fois.

La différence entre un "vrai" nombre aléatoire et un "pseudo" nombre aléatoire est la prévisibilité. Cette réponse a déjà été fournie.

Toutefois, la prévisibilité n'est pas nécessairement une mauvaise chose comme le montrent la plupart des exemples. Voici un exemple concret de l'un des rares cas où la prévisibilité est bonne : Le système de positionnement global.

Chaque satellite utilise un code PRN distinct (le code d'identification du satellite). Codes d'or ) convenant à l'autocorrélation ou à la corrélation croisée qui est nécessaire pour la mesure du temps de propagation du signal. Pour ces codes Gold, la corrélation entre eux est particulièrement faible, ce qui rend possible une identification sans équivoque du satellite, mais permet le calcul de la distance par la corrélation entre la séquence émise et le récepteur.

Pour vérifier rapidement le caractère aléatoire, on prend des points dont les coordonnées sont aléatoires dans [0;1] et on les place dans un cube à k dimensions. Ensuite, vous effectuez une procédure pour découper ce cube en sous-cubes - chaque volume de sous-cube (ou de sous-sphère) doit être mesuré correctement par cette procédure avec des fluctuations selon un théorème bien connu.

La qualité du hasard est importante là où vous rencontrez...

1. à des fins de sécurité. Lorsque vous générez un nombre à utiliser comme paramètre pour la génération de votre clé, et qu'il est bien prévisible, l'ennemi le découvrira avec une probabilité de 100% et rendra le champ de recherche beaucoup plus petit.

2. à des fins scientifiques. En science, il faut non seulement que la moyenne soit en bon état, mais aussi que les corrélations entre les différents nombres aléatoires soient éliminées. Ainsi, si vous prenez (a_i - a)(a_{i+1}-a) et trouvez sa distribution, cela doit correspondre aux statistiques.

La corrélation entre paires est ce qu'on appelle un "hasard faible". Si vous voulez un véritable caractère aléatoire, vous devez avoir une corrélation d'ordre élevé avec plus de 2 variances.

Aujourd'hui, seuls les générateurs de la mécanique quantique fournissent un véritable caractère aléatoire.