Stochastique et génération de nombres pseudoaléatoires

Cette page sera enrichie quand j'en aurai le temps, le sujet étant d'une grande complexité et mon expertise étant très limitée. La référence en la matière est le monumental ouvrage de Donald E. Knuth, The Art of Computer Programming, dont un volume entier est consacré à la question, et dont vous trouverez un chapitre ici : http://www.informit.com/articles/article.aspx?p=2221790

La stochastique est un sujet important en informatique, en particulier pour ce qui touche à la sécurité et à l'intégrité de systèmes. Un attaquant d'un système de loterie ou d'un casino cherchera à prédire les prochaines actions d'un système sur la base des précédentes; c'est l'objectif des systèmes, services et outils décrits ici de réduire les chances de succès de ces attaquants.

En 2013, John Graham-Cumming explique pourquoi ces systèmes dépendent d'une génération de nombres pseudoaléatoires de qualité : https://blog.cloudflare.com/why-randomness-matters/

Article de 2014 par Cory Doctorow montrant les actions prises par un casino lorsque deux individus ont trouvé un bogue dans sa génération de nombres pseudoaléatoires : http://boingboing.net/2014/10/08/sore-losers-how-casinos-went.html

Général / pédagogie

Comment les ordinateurs génèrent-ils des nombres pseudoaléatoires?

• Survol de deux techniques : http://computer.howstuffworks.com/question697.htm
• Explications de Devan Patel en 2015 : http://www.devanpatel.me/how-pseudorandom-number-generators-work/
• Livre de 1986, maintenant en ligne, par Luv Devroye et portant sur la génération pseudoaléatoire non-uniforme : http://luc.devroye.org/rnbookindex.html
• Génération pseudoaléatoire de nombres à virgule flottante de double précision, par Artur Grabowski en 2015 : http://www.blahonga.org/2015/04/state-of-art-of-random-double-generation.html
• Comment le jeu Doom générait ses nombres pseudoaléatoires... Disons qu'on parle d'une solution très « maison » : https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/m_random.c
• Générer du « vrai » hasard avec du matériel spécialisé, par Charles Platt et Aaron Logue en 2015 : http://makezine.com/projects/really-really-random-number-generator/
• Texte de Jeremy Kun en 2016, qui présente un algorithme de génération de nombres pseudoaléatoires qu'il n'est pas possible de distinguer d'une source de hasard effective par observation des valeurs générées : https://jeremykun.com/2016/07/11/the-blum-blum-shub-pseudorandom-generator/

Générer de véritables nombres aléatoires?

• Utiliser l'entropie de la décrépitude d'un atome, par John Walker : http://www.fourmilab.ch/hotbits/
• Se baser sur l'état initial de la mémoire vive, texte de Thomas S. Heydt-Benjamin en 2007 : http://tshb.livejournal.com/2989.html
• Le Quantum Random Bit Generator Service, qui offre de l'entropie sur demande : http://random.irb.hr/
• Se baser sur l'état d'un laser de semiconducteur, par Laura Mgrdichian en 2008 : http://phys.org/news/2008-12-semiconductor-lasers-random.html
• Se baser sur un « flip-flop métastable », article de 2010 : http://www.sciencedaily.com/releases/2010/02/100222082529.htm
• En 2011, Greg Taylor et George Cox présentent le nouveau générateur de nombres pseudoaléatoires d'Intel et en décrivent les caractéristiques : http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator/0
• Baser la génération de nombres pseudoaléatoires sur des phénomènes quantiques :
  • article de Tom Spears en 2011 : http://www.montrealgazette.com/technology/GENERATING+RANDOM+NUMBERS/5779618/story.html
  • http://photonics.anu.edu.au/qoptics/Research/qrng.php
  • http://150.203.48.55/Matrix.php (si vous voulez piger des nombres là-dedans, allez-y, mais je ne connais pas la qualité de leur générateur)
  • y arriver en utilisant une caméra et un téléphone intelligent, par Vinicius Spader en 2014 : https://medium.com/the-physics-arxiv-blog/quantum-random-number-generator-created-using-a-smartphone-camera-602f88552b64
• Écrire son propre générateur de nombres pseudoaléatoires (note : ne faites pas ça, à moins de vraiment savoir ce que vous faites!) :
  • article de Chris Smith en 2011 : https://cdsmith.wordpress.com/2011/10/10/build-your-own-simple-random-numbers/
• Source d'entropie diffusée par le NIST (National Institute of Standards and Technology) : http://www.nist.gov/itl/csd/ct/nist_beacon.cfm
  • le générateur lui-même est https://beacon.nist.gov/home mais on recommande de ne pas l'utiliser pour générer des clés cryptographiques secrètes
• Démonstration interactive qu'un humain est une mauvaise source d'entropie (c'est amusant) : http://www.loper-os.org/bad-at-entropy/manmach.html
• L'algorithme du Fisher-Yates Shuffle, expliqué par Matt Nedrich en 2014 : http://spin.atomicobject.com/2014/08/11/fisher-yates-shuffle-randomization-algorithm/
• La famille PCG de générateurs de nombres pseudoaléatoires et ses caractéristiques : http://www.pcg-random.org/

Quelques articles de sources externes :

• Tirer à pile ou face est-il réellement un geste honnête, au sens où il est équiprobable d'obtenir pile ou face? Il semble que sur le plan empirique, la réponse soit non, comme le rapporte David Kestenbaum en 2004 : http://www.npr.org/templates/story/story.php?storyId=1697475
• Utiliser $\pi$ en tant que source de nombres pseudoaléatoires est-il raisonnable? C'est pas évident, de l'avis de Chad Boutin en 2005 : http://www.purdue.edu/uns/html4ever/2005/050426.Fischbach.pi.html
• À propos de l.'importance des probabilités et de la stochastique pour la qualité de la science en général, article de Tom Siegfried en 2010 : https://www.sciencenews.org/article/odds-are-its-wrong
• Quel est le sens légal de l'expression Truly Random? Article de Guus Bosman en 2011 : http://www.guusbosman.nl/2011/07/15/court-ruling-strictly-random
• En 1913, Émile Borel aurait prédit par ce qu'on nomme le Infinite Monkey Theorem que si l'on laissait un singe taper aléatoirement sur une dactylo pour un temps infini, celui-ci finirait par reproduire l'oeuvre entière de Shakespeare. Évidemment, le défi a été relevé, comme le rapporte Jesse Anderson en 2011 : http://www.jesse-anderson.com/2011/09/a-few-million-monkeys-randomly-recreate-shakespeare/
• Simuler un dé inéquitable à $n$ faces, par Keith Schwartz : http://www.keithschwarz.com/darts-dice-coins/
• Génération sur la base de XOR et de glissements de bits :
  • article de George Marsaglia : http://www.jstatsoft.org/v08/i14/paper
  • implémentation avec Java, et constat de ses forces et de ses faiblesses, par Neil Coffey en 2014 : http://www.javamex.com/tutorials/random_numbers/xorshift.shtml
• Utiliser rand() pour corriger un bogue... dans une fonction de hashage! Une blague de Russ Cox en 2012 : http://research.swtch.com/randhash
• Témoignage de David Woods, un statisticien qui achète... des billets de loterie, en 2012 : http://simplexify.net/blog/2012/5/6/i-am-a-statistician-and-i-buy-lottery-tickets.html
• À quoi ressemblerait un monde sans hasard? Réflexion informée de Richard Lipton et Ken Regan en 2013 : https://rjlipton.wordpress.com/2013/08/23/a-world-without-randomness/
• Comment tester un générateur de nombres pseudoaléatoires? Chapitre sur du livre Beautiful Testing portant sur le sujet, et écrit par John D. Cook : http://www.johndcook.com/Beautiful_Testing_ch10.pdf
• Distribuer des points pseudoaléatoirement sur une sphère, par Jason Davies : https://www.jasondavies.com/maps/random-points/
• Génération efficace de nombres pseudoaléatoires avec CUDA, par Lee Howes et David Thomas : http://http.developer.nvidia.com/GPUGems3/gpugems3_ch37.html
• Prédire la sortie de générateurs de nombres pseudoaléatoires de moindre qualité, par le brillant Jesse Emond : https://github.com/JesseEmond/random-prediction
• Les recommandations du NIST (National Institute of Standards and Technology) en 2015 pour la génération de nombres pseudoaléatoires sur la base de générateurs de bits déterministes, rapport sous la responmsabilité d'Elaine Barker et John Kelsey : http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf
• Article de 2014 par Scott Aaronson, qui relate l'histoire de la quête du hasard : http://www.americanscientist.org/issues/pub/2014/3/the-quest-for-randomness
• Est-ce grave de ne pas avoir un bon système de génération de nombres pseudoaléatoires? Cas vécu, relaté en 2014 par Laura Diane Hamilton, des conséquences d'un bogue dans un algorithme de brassage de cartes pour un système de poker en ligne : http://www.lauradhamilton.com/random-lessons-online-poker-exploit
• Texte de Paul Lutus en 2010 portant sur le hasard, le sens et la coïncidence : http://arachnoid.com/randomness/index.html
• Faire naître le hasard de la complexité, texte de Lance Fortnow en 2015 : http://blog.computationalcomplexity.org/2015/10/randomness-by-complexity.html
• Comment gâcher une génération de nombres pseudoaéléatoires, et quelles sont les conséquences d' un tel geste, par Mike Malone en 2015 : https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d
• Le sens que donnait Euclide à « aléatoire », réflexion de Richard Lipton et Ken Regan en 2016 : https://rjlipton.wordpress.com/2016/01/12/did-euclid-really-mean-random/
• Texte de 2016 par John D. Cook qui discute des conséquence de mal initialiser un générateur de nombres pseudoaléatoires : http://www.johndcook.com/blog/2016/01/29/random-number-generator-seed-mistakes/
• Quels sont les germes les plus populaires pour les gens qui fixent la valeur du germe? La réponse à cette question ne vous surprendra probablement par... Article d'Aleksey Bilogur en 2016 : http://www.residentmar.io/2016/07/08/randomly-popular.html
• Il y a tant de manières de mal choisir son germe, comme l'illustre ce texte de 2014 : http://www.tedunangst.com/flak/post/random-in-the-wild
• Analyser le comportement des générateurs de nombres pseudoaléatoires, par Michael Hicks en 2016 : http://www.pl-enthusiast.net/2016/11/01/prng-entropy-loss-and-noninterference/

Génération Splittable

La génération Splittable vise à alimenter deux consommateur (ou plus) de nombres pseudoaléatoires s'exécutant de manière concurrente à partir d'une même source :

• Article de Koen Claessen et Michał H. Pałka en 2013 : http://publications.lib.chalmers.se/records/fulltext/183348/local_183348.pdf

Selon les systèmes d'exploitation

Les systèmes d'exploitation sont capables de cumuler de l'entropie basée sur les phénomènes physiques (vibrations du disque rigide, variations de température, fréquence de pression des touches du clavier, etc.) et d'exposer ces données aux générateurs de nombres pseudoaléatoires, typiquement à titre de germe.

Avec Linux

• Une analyse de la qualité des mécanismes offerts par Linux, par Zvi Gutterman, Benny Pinkas et Tzachy Reinman en 2006 : http://www.pinkas.net/PAPERS/gpr06.pdf
• En 2012., Michael Kerrisk recommande de « ne pas jouer aux dés » avec les nombres pseudoaléatoires, au sens où ces mécanismes ne sont vraiment pas des jouets, en rapportant l'essentiel d'une conférence donnée par H. Peter Anvin : http://lwn.net/Articles/525459/
• Quelques mythes à propos de /dev/urandom, l'une des sources d'entropie de Linux, expliqués par Thomas Hühn en 2015 : http://www.2uo.de/myths-about-urandom/

• Selon Stephan Mueller en 2016, /dev/random vieillit et une nouvelle approche (qu'il propose) doit être considérée pour collecter de l'entropie dans le noyau du système d'exploitation : http://lwn.net/Articles/684568/
• Texte de 2016 par Jonathan Corbet sur la génération de nombres pseudoaléatoires et la sécurité sous Linux : https://lwn.net/Articles/685371/

Avec MacOSX

Survol des mécanismes disponibles et de leurs qualités respectives, par Mike Ash en 2011 : https://www.mikeash.com/pyblog/friday-qa-2011-03-18-random-numbers.html

Avec Microsoft Windows

Une analyse de la qualité des mécanismes offerts par Microsoft Windows, par Leo Dorrendorf, Zvi Gutterman et Benny Pinkas en 2007 : http://eprint.iacr.org/2007/419.pdf

Selon les langages de programmation

La vaste majorité des langages de programmation offre des services de génération de nombres pseudoaléatoires. La qualité varie bien sûr en fonction du langage et de la plateforme sous-jacente.

Pour un tour d'horizon multilangages, voir ce texte de 2016 : https://paragonie.com/blog/2016/05/how-generate-secure-random-numbers-in-various-programming-languages

Avec C

Selon ce texte de 2015, rand() est moins mauvais que l'on ne le croit, mais on tend à mal l'utiliser : http://eternallyconfuzzled.com/arts/jsw_art_rand.aspx (cependant, il recommande de passer aux outils de C++ 11).

Avec C#

• En 2012, Matej Zavrsnik cherche à déterminer le biais introduit par un modulo dans le générateur de nombres pseudoaléatoire de la plateforme .NET : http://blog.matejzavrsnik.com/2012/06/attempt-to-find-modulo-bias-in-net-randomization/
• Comment générer des données pseudoaléatoires distribuées de manière non-uniforme avec C#, par Eric Lippert (car il faut savoir que le générateur usuel, Random, génère des données distribuées de manière uniforme) :
  • texte de 2012 : http://ericlippert.com/2012/02/21/generating-random-non-uniform-data/
  • texte de 2013 : http://ericlippert.com/2013/12/16/how-much-bias-is-introduced-by-the-remainder-technique/

Avec C++

• Présentation des mécanismes de génération de nombres pseudoaléatoires contemporains de C++, par Pattabi Raman en 2014 : http://accu.org/content/conf2014/RandomNumberGenerationInC++11-17-annotated.pdf
• Comment utiliser les mécanismes de génération de nombres pseudoaléatoires de C++ depuis C++ 11 : ../../Divers--cplusplus/prng.html
• Générer des nombres pseudoaléatoires plus imprévisibles, un exemple : http://www.cppsamples.com/common-tasks/unpredictable-random-numbers.html
• À propos des difficultés de bien choisir un germe, par M. E. O'Neill en 2015 : http://www.pcg-random.org/posts/cpp-seeding-surprises.html
• Un algorithme rapide pour brasser les éléments d'un intervalle, proposé par Daniel Lemire en 2016 : http://lemire.me/blog/2016/06/30/fast-random-shuffling/

Avec Haskell

• Le paquetage tf-random, pour une génération Splittable de qualité : http://hackage.haskell.org/package/tf-random

Avec Java

• En 2011, Peter Lawrey montre que la qualité du générateur de nombres pseudoaléatoires de Java est fortement influencée par le germe choisi : http://vanillajava.blogspot.ca/2011/10/randomly-no-so-random.html
• Amener le générateur de nombres pseudoaléatoires de Java à ses limites, par Hanz Kabutz en 2012 : hhttp://www.artima.com/weblogs/viewpost.jsp?thread=340484
• Développer un SplittableRandom, pour faciliter la génération Splittable de nombres pseudoaléatoires dans une application parallèle, par Doug Lea en 2013 : http://cs.oswego.edu/pipermail/concurrency-interest/2013-July/011579.html
• Faiblesses du générateur de nombres pseudoaléatoires de Java, selon Kai Michaels, Christopher Meyer et Jörg Schwenk en 2013 : http://armoredbarista.blogspot.com.au/2013/03/randomly-failed-weaknesses-in-java.html
• Prédire la prochaine valeur retournée par Math.random() en Java, par Franklin Ta en 2014 : http://franklinta.com/2014/08/31/predicting-the-next-math-random-in-java/

Avec JavaScript

En 2016, Douglas Goddard s'amuse à démontrer que le générateur de nombres pseudoaléatoires de JavaScript, du moins sous Chrome et sous Firefox, n'est peut-être pas le meilleur outil pour écrire un logiciel de loterie sérieux : https://medium.com/independent-security-evaluators/hacking-the-javascript-lottery-80cc437e3b7f

Avec Kotlin

Rouler un dé avec Kotlin, par Nicolas Frankel en 2016 : https://blog.frankel.ch/rolling-dice-kotlin

Avec Perl

• Texte de Timm Murray en 2014 sur l'importance du hasard dans le chiffrement de données avec Perl : http://www.wumpus-cave.net/2014/03/12/perl-encryption-primer-the-importance-of-randomness/

Avec PHP

Pas facile de générer des nombres pseudoaléatoires. Un bogue soumis en 2015 montre que dans certaines circonstances, cet extrait ne génère que des nombres impairs : http://3v4l.org/dMbat

Avec SQL

• Les distributions normales avec SQL, texte de 2014 : https://periscope.io/blog/beyond-random-normal-distributions-in-sql.html

Avec Swift

• Introduction à la génération de nombres pseudoaléatoires avc Swift, par Matt Gallagher en 2016 : http://www.cocoawithlove.com/blog/2016/05/19/random-numbers.html

Comparatifs

Examen comparatif de la fonction rand(0,1) de PHP et de la fonction rand() d'OpenSSL sur Debian, en 2008 : http://cod.ifies.com/2008/05/php-rand01-on-windows-openssl-rand-on.html

Étude de 2016 par Falko Strenzke, portant sur quelques manques dans la qualité de l'entropie du générateur de nombres pseudoaléatoires d'OpenSSL : https://eprint.iacr.org/2016/367

Considérations historiques

• À propos de la qualité de la gestion des nombres peudoaléatoires du fureteur Netscape en 1996, par Ian Goldberg et David Wagner : http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html
• Bogue de génération de nombres pseudoaléatoires dans Windows XP et Windows 2000, rapporté par Greg Keizer en 2007 : http://www.computerworld.com.au/article/201878/microsoft_xp_contains_random_number_generator_bug/
• Bogue dans random() tel qu'offert par OpenBSD, texte de 2012 : https://banu.com/blog/42/openbsd-bug-in-the-random-function/
• Réflexion d'Alex Klyubin en 2013 sur des problèmes rencontrés avec SecureRandom sur Android depuis l'apparition du Bitcoin : http://android-developers.blogspot.ca/2013/08/some-securerandom-thoughts.html