Pimp My Code
Give your code that special "pimp"
Des nombres aléatoires… prédictibles !
Categories: Ordre et Hasard

Un générateur de nombres aléatoire, c’est bien pratique…
Tout développeur a eu besoin un jour ou l’autre de sélectionner un élément “au hasard” dans un tableau, de générer un nombre entre 0 et n, de produire un mot de passe, une chaine de caractères aléatoire…

Les applications sont extrêmement nombreuses.
Le Hic en informatique, c’est que “pile ou face” n’existe pas. Plus exactement, on ne peut pas écrire d’algorithme, de programme, qui génère des suites de nombres VRAIMENT aléatoire.
C’est d’ailleurs pour ça qu’on les appelle des nombre “pseudo”-aléatoires.

On peut s’approcher de nombres idéalement aléatoires, on peut faire semblant, mais on se heurte à de petits soucis.
Par exemple, quand on utilise des nombres aléatoires pour générer des mots de passe; pour ajouter un salt, pour crypter une information, pour négocier un dialogue sécurisé, pour définir une valeur de cookie…
Ce que le développeur pense être aléatoire ne l’est pas, et est parfois source de failles importantes.

En PHP, il existe deux fonctions pour générer un nombre aléatoire : rand(min,max) et mt_rand(min,max).

Chacune de ces fonctions renvoie un nombre entre min et max.
rand() utilise une fonction interne du système, qui dépend de la librairie libc installée. Cette implémentation étant parfois lente et peu sure, mt_rand utilise un algorithme documenté et plus rapide, appellé Mersenne twister[1].

Aucune de ces deux fonctions n’est adaptée à la cryptologie, ou dans le domaine de la sécurité. Les séquences de nombres générés peuvent en effet être prédites.

Dans cet article, on va même plutot faire le contraire.
J’ai eu dernièrement besoin de produire de gros volumes de données aléatoires, simulées, en PHP.
Plutôt que de transmettre des jeux de données complets, j’ai juste transféré le script qui produit ces données.
Autant qu’on veut, toujours “aléatoires”, mais toujours les mêmes dans le même ordre d’un lancement à un autre. Totalement reproductible.

Une autre utilisation de cette technique est d’afficher, sur un site, du contenu “aléatoire” sur chaque page, mais toujours le même sur la même page.
Par exemple, on a une liste de citations, de photos, des vidéos, des extraits de texte, ou un masterspin… et on veut en afficher un extrait différent sur chaque page du site, mais que cela reste persistent dans le temps.

Comment fait-on celà?

Sur le principe, c’est assez facile. Les générateurs de nombre pseudo-aléatoires utilisent une “graine”, un “seed” : c’est un nombre qui sert à initialiser l’algorithme. Il se sert de cette valeur pour commencer son cycle, pour générer le premier nombre aléatoire, et de là modifier le seed pour la demande suivante.
C’est absolument nécessaire : un programme fera toujours deux fois la même chose, strictement.
Si on le lance deux fois de suite, qu’il ne donne pas le même résultat, c’est

1/ Que le cpu est sous une douche de rayons cosmiques et qu’il n’est plus bon à rien
2/ que des données ont changé entre temps.

En fait, il est par exemple courant d’initialiser les générateurs de nombres aléatoires avec la durée depuis le boot de la machine, ou en fonction de mouvements de la souris, de la fréquence de frappe sur le clavier.
Ce n’est pas parfait, mais c’est difficilement reproductible.

Ce qui nous intéresse, c’est donc le contraire, et sur le papier, c’est tout simple : on donne un “seed” connu au générateur, et il fournira toujours la même séquence pseudo-aléatoire, que je demande 1 nobmre ou 153000 à la suite.

Si je veux un résultat “aléatoire” qui sera toujours le même pour une page donnée, il suffit que j’initialise mon générateur avec une propriété inhérente à la page.
On a le choix : l’id de la page, son nombre de mots, ou encore un hash, un checksum d’un texte (url de la page, titre…)

En pratique, le développeur va tomber sur un petit souci.
Exit déjà la fonction rand(), car depuis php 4.2.0, le générateur est initialisé automatiquement, et donc on ne peut plus lui donner de seed. Le résultat est de plus dépendant de libc, donc non parfaitement reproductible.

Reste mt_rand() et sa petite soeur, mt_srand().
Cette dernière procédure initialise le générateur de nombre aléatoires.
Manque de pot, depuis php 5.2.1 , “L’implémentation Mersenne Twister en PHP utilise maintenant un nouvel algorithme d’initialisation[...] Des initialisations identiques ne produisent plus la même séquence de valeurs, comme cela pouvait être le cas dans les versions antérieures.”
Qui plus est, avec certaines versions “durcies” de php (suhosin patch, le défaut sous certaines distributions linux comme la Debian) , c’était déjà le comportement de PHP, il n’est pas possible de prédire ou de reproduire une séquence pseudo-aléatoire.

Bonne nouvelle (enfin, un peu) d’un point de vue sécurité, mais dommage pour ceux qui veulent des séquences reproductibles.

Qu’à cela ne tienne !
Si on veut des séquences reproductibles, qu’on n’a pas de contraintes sécuritaires ou de dispersion des résultats; bref, si on se satisfait d’un “bête” générateur pseudo aléatoire avec seed, autant se le coder soi même, non ?

L’algo simpliste que j’ai utilisé est le suivant[2] :

class RepRandom {

// seed
private static $RSeed = 0;

// Affectation du seed
public static function seed($s = 0) {
self::$RSeed = abs(intval($s)) % 9999999 + 1;
self::num();
}

// genère un nombre pseudo-aléatoire
public static function num($min = 0, $max = 9999999) {
if (self::$RSeed == 0)
self::seed(mt_rand());
self::$RSeed = (self::$RSeed * 125) % 2796203;
return self::$RSeed % ($max - $min + 1) + $min;
}

Cette classe PHP est définie en static, vous pouvez donc l’utiliser comme suit, sans avoir à en créer d’instance :


RepRandom::seed(1414); // initialise le seed à 1414
$alea = RepRandom::num(1,10); // Renvoie un nombre entre 1 et 10 (inclus)

Et voilà; un générateur simple, rapide et reproductible.

J’en vois, au fond, qui vont me demander pourquoi 125 et 2796203 …

Il s’agit d’un “vieil” algorithme de 1966 (ALGORITHM 266, COLLECTED ALGORITHMS FROM ACM. ALGORITHM APPEARED IN CACM, VOL 9, NO. 9, SEP., 1966). Ces nombres permettent en fait d’assurer une bonne distribution des nombres générés.
Ce ne sont pas des nombres “magiques” qui contiennent le secret de l’univers ou la réponse à toutes les questions, “simplement” des nombres qui vont bien pour que la répartition des valeurs soit homogène. Ne les changez donc pas à la légère !

Bien sur, n’utilisez cet algo que pour ce type de besoin. Jamais comme tirage au sort pour un concours, ni pour n’importe quel usage qui suppose que la séquence n’est pas prévisible.

Si vous souhaitez un générateur un peu plus “costaud” (mais aussi plus lent), vous pouvez utiliser une implémentation pure PHP de l’algorithme Mersenne Twister[3].

J’espère que ça vous aura servi, dépanné, ou mieux, donné des idées d’utilisation !

Je suis preneur de vos retours sur votre utilisation de (vrais) générateurs comme de ce type de générateur “reproductible”.


[1] L’algorithme Mersenne Twister.
[2] Implémentation php d’un générateur pseudo aléatoire.
[3] Implémentation Mersenne Twister en pure PHP (5.3)
Crédit photo : http://www.flickr.com/photos/april-mo/

1 Comment to “Des nombres aléatoires… prédictibles !”

  1. cdillat says:

    “Par exemple, on a une liste de citations, de photos, des vidéos, des extraits de texte, ou un masterspin… et on veut en afficher un extrait différent sur chaque page du site, mais que cela reste persistent dans le temps.”

    Ou d’ancre de lien :D

    Perso j’utilise un hash de l’url comme seed dans ce cas ;)

Leave a Reply