Générateurs de nombre pseudo-aléatoires

« La génération de nombres aléatoires est trop importante pour être confiée au hasard. »
Robert R. Coveyou

Un rapport sur la génération de nombre pseudo-aléatoires (PRNG : Pseudo-Random Number Generator), c'est à dire les techniques pour produire des suites de nombres “au hasard”, ce hasard étant par définition imparfait du fait des algorithmes déterministes employés.

• Le document décrit un certain nombre de généralités sur les PRNG et présente plusieurs formes de générateur à congruence linéaire/matricielle (LFSR, GFSR, TGFSR et Mersenne Twister). Ces générateurs sont très rapide mais ne sont cependant pas suffisamment aléatoire pour être utilisés en cryptographie. Les nombres aléatoires sont en effet la base de tout système cryptographique, si le générateur n'est pas sûr (i.e., si les prochains nombres peuvent être devinés à l'avance) alors le chiffrement est compromis.
• Deux PRNG cryptographiques sont exposés dans la suite du document : Blum Blum Shub et Blum-Micali (qui utilise le même principe que le chiffrement El Gamal).
• Dans une seconde partie, le document décrit plusieurs méthodes mathématiques pour l'analyse de la qualité des PRNG (analyse de la distribution, test spectral, test du X², test de Monte Carlo, etc.).

Le document a été rédigé en 2010, si vous remarquez des erreurs merci de me contacter. Certaines parties mériteraient d'être retravaillée (ce que j'espère pouvoir faire un jour) et je voudrais compléter le document avec d'autres algorithmes, comme Fortuna. Il serait aussi intéressant de parler du cas de Dual_EC_DRBG, un PRNG dans lequel la NSA avait introduit une backdoor.

Document principal : http://benjaminbillet.fr/media/prng_mathreport.pdf
Présentation : http://benjaminbillet.fr/media/prng_mathreport_presentation.pptx