Il y a `Math.random()`, et puis il y a `Math.random()`

Math.random() retourne une valeur Number avec un signe positif, supérieure ou égale à 0 mais inférieure à 1, choisie de manière aléatoire ou pseudo-aléatoire avec une distribution approximativement uniforme sur cette plage, en utilisant un algorithme ou une stratégie dépendant de l’implémentation. Cette fonction ne prend aucun argument.

— ES 2015, section 20.2.2.27

Math.random() est la source de hasard la plus connue et la plus utilisée en JavaScript. Dans V8 et la plupart des autres moteurs JavaScript, elle est implémentée à l’aide d’un générateur de nombres pseudo-aléatoires (PRNG). Comme pour tous les PRNG, le nombre aléatoire est dérivé d’un état interne, modifié par un algorithme fixe pour chaque nouveau nombre aléatoire. Ainsi, pour un état initial donné, la séquence de nombres aléatoires est déterministe. Étant donné que la taille des bits n de l’état interne est limitée, les nombres qu’un PRNG génère finiront par se répéter. La limite supérieure de la période de ce cycle de permutation est 2ⁿ.

Il existe de nombreux algorithmes PRNG différents; parmi les plus connus figurent Mersenne-Twister et LCG. Chacun a ses caractéristiques particulières, avantages et inconvénients. Idéalement, il utiliserait le moins de mémoire possible pour l’état initial, serait rapide à exécuter, aurait une période longue et offrirait une répartition aléatoire de haute qualité. Alors que l’utilisation de la mémoire, les performances et la longueur de la période peuvent facilement être mesurées ou calculées, la qualité est plus difficile à déterminer. Il existe une grande quantité de mathématiques derrière les tests statistiques pour vérifier la qualité des nombres aléatoires. La suite de tests PRNG standard de facto, TestU01, implémente beaucoup de ces tests.

Jusqu’à fin 2015 (jusqu’à la version 4.9.40), le choix de PRNG de V8 était MWC1616 (multiplication avec retenue, combinant deux parties 16 bits). Il utilise 64 bits d’état interne et ressemble à peu près à ceci :

uint32_t state0 = 1;
uint32_t state1 = 2;
uint32_t mwc1616() {
  state0 = 18030 * (state0 & 0xFFFF) + (state0 >> 16);
  state1 = 30903 * (state1 & 0xFFFF) + (state1 >> 16);
  return state0 << 16 + (state1 & 0xFFFF);
}

La valeur 32 bits est ensuite convertie en un nombre à virgule flottante entre 0 et 1 conformément à la spécification.

MWC1616 utilise peu de mémoire et est assez rapide à calculer, mais offre malheureusement une qualité médiocre :

• Le nombre de valeurs aléatoires qu’il peut générer est limité à 2³² par opposition aux 2⁵² nombres entre 0 et 1 que la représentation à virgule flottante de double précision peut représenter.
• La moitié supérieure significative du résultat dépend presque entièrement de la valeur de state0. La longueur de la période serait au maximum de 2³², mais au lieu de quelques grands cycles de permutation, il y a de nombreux cycles courts. Avec un état initial mal choisi, la longueur du cycle pourrait être inférieure à 40 millions.
• Il échoue à de nombreux tests statistiques de la suite TestU01.

Cela nous a été signalé, et après avoir compris le problème et fait quelques recherches, nous avons décidé de réimplémenter Math.random sur la base d’un algorithme appelé xorshift128+. Il utilise 128 bits d’état interne, a une longueur de période de 2¹²⁸ - 1 et réussit tous les tests de la suite TestU01.

L’implémentation a été intégrée dans V8 v4.9.41.0 quelques jours après que le problème ait été porté à notre attention. Elle est devenue disponible dans Chrome 49. Firefox (voir ici) et Safari (voir ici) ont également adopté xorshift128+.

Dans V8 v7.1, l’implémentation a été à nouveau ajustée CL en se basant uniquement sur state0. Veuillez consulter plus de détails sur l’implémentation dans le code source.

Ne vous y trompez pas cependant : même si xorshift128+ représente une énorme amélioration par rapport à MWC1616, il n'est toujours pas cryptographiquement sûr. Pour des cas d'utilisation tels que le hachage, la génération de signatures et le chiffrement/déchiffrement, les PRNG ordinaires sont inappropriés. L'API Web Cryptography introduit window.crypto.getRandomValues, une méthode qui retourne des valeurs aléatoires cryptographiquement sécurisées, au prix d'une diminution de performance.

Veuillez garder à l'esprit que si vous trouvez des domaines d'amélioration dans V8 et Chrome, même ceux qui — comme celui-ci — n'affectent pas directement la conformité au standard, la stabilité ou la sécurité, veuillez soumettre un problème sur notre traqueur de bugs.