La génération de nombres aléatoires a souvent posé des soucis avec des algorithmes. Cette génération se fait le plus souvent en fonction de l’heure de la machine sur laquelle la fonction permettant de générer un nombre aléatoire est exécutée. Dès lors, il se pose un souci majeur : si les algorithmes sont fonction du temps, il peut être possible de prévoir le nombre aléatoire que va sortir la machine. On s’intéresse à ce risque en cryptographie et le but est de produire un algorithme rapide à exécuter, qui ne génère pas des nombres aléatoires périodiquement et dont on ne puisse pas prévoir les résultats.
Voici quelques tests que j’ai réalisé pour tester la qualité de deux fonctions permettant de générer aléatoirement des nombres en PHP rand et mt_rand.
Voici ce que dit la documentation de PHP à propos de ces fonctions.
“De nombreux générateurs de nombres aléatoires provenant de vieilles bibliothèques libcs ont des comportements douteux et sont très lents. Par défaut, PHP utilise le générateur de nombres aléatoires de libc avec la fonction
rand().mt_rand()est une fonction de remplacement, pour cette dernière. Elle utilise un générateur de nombres aléatoire de caractéristique connue, le “Mersenne Twister” qui est 4 fois plus rapide que la fonction standard libc.”
Création d’une image
Ce test permet de se représenter visuellement les résultats donnés par les fonctions. Voici le principe : on part sur une base d’une image complètement noire et on demande aux fonctions de colorier des coordonnées de l’image, calculées aléatoirement, en blanc. On balaie l’intégralité des coordonnées de l’image (en x et en y) et on regarde si certains pixels n’ont pas été coloriés plusieurs fois ou si on peut observer des formes, ce qui montre le caractère non parfaitement aléatoire de la fonction.
Voici le code PHP pour réaliser ceci :
Voici l’image que l’on obtient (lien vers l’image taille réelle) : 
Et voici un zoom au centre de l’image, pour pouvoir comparer la nette différence entre
rand et mt_rand : 
Le résultat est assez bluffant : on remarque sur l’image générée par la fonction rand des formes qui ressemblent à des lignes discontinues tandis que l’image générée par mt_rand ressemble bien à une image de bruit, ce qui est la représentation qu’on pouvait attendre.
Vérification de l’équiprobabilité
Nous allons maintenant nous intéresser à la vérification de la règle de l’équiprobabilité d’un tirage de chiffres. Le test est le suivant : on demande à l’algorithme de générer un chiffre aléatoire entre 0 et 9 inclus, soit 10 possibilités. Pour un grand nombre de tirages, la probabilité est de 10 % par chiffre. Vérifions ce résultat avec les fonctions rand et mt_randet regardons les différences. Le code PHP pour ce test, pour la fonction rand est le suivant :
Le test est le même pour la fonction mt_rand, sauf que l’on change le nom de la fonction permettant de générer le nombre à la ligne 44.
Voici les résultats que l’on obtient. Pour rand :
Et pour mt_rand :
Ouf, l’équiprobabilité est vérifiée pour les deux fonctions ! Résultat étrange en revanche, l’erreur moyenne et le temps de calcul sont plus grands pour la fonction mt_rand alors que la documentation PHP indique que cette fonction est “4 fois plus rapide”. Il faudrait réaliser plusieurs fois ce test pour s’assurer de ce résultat.
Le précédent test ne permet donc pas de dire que la fonction rand est “mauvaise” et elle génère quand même bien des nombres aléatoires, malgré ce que l’image obtenue pouvait laisser penser.