Mesurer la qualité d'un générateur de nombres aléatoires [Résolu]

[fourchette]

je mets au point un programme dont la solidité/fiabilité dépend de la génération de nombres aléatoires. une des applications dans le programme est la génération de clés.

je sais que par nature le "vrai" hasard n'existe pas sur un ordinateur.
je me souviens encore avec un frisson dans le dos de la célèbre vunérabilité introduite dans le package openssl dans debian qui est resté indétectée entre 2006 et 2008 (un bug dans l'algo de random a eu pour effet de bord de réduire l'espace des clés à seulement ~32000 possibilités...), appelons-ce "désir de couvrir tout l'espace des clés de manière homogène" le probleme #A. J'ai également entendu parler de temps en temps de casino online qui se font dépouiller parce que leur "hasard" peut en fait etre prédit avec une marge d'erreur faible. Appelons "désir de non prédictibilité" probleme #B.
J'aimerais bien me résoudre A et B.

Mon probleme principal n'est pas vraiment l'absence d'idée mais plutot : comment spécifier mathématiquement les propriétés que je cherche à valider pour ensuite les convertir en tests scriptés (unitaires) et enfin utiliser ces tests scriptés pour comparer les différentes implémentation de génération de nombre aléatoire.

je précise tt de suite : les math/stats j'aimais bien ca à l'école, mais 10 ans plus tard j'ai bcp de mal à re-rentrer dans.

D'intuition B me parait +délicat et +inaccessible. Alors je préfère commencer par A.

Je pensais à générer un nombre "grand" de clés de 1024 bits (100k ou 1M) et vérifier que le nombre de doublon est quasi nul. Le ratio qualité/cout/délai de cette vérif me semble bon, mais c'est pas très élégant. Du coup, je comptais y aller plus finement : cad générer 1 000 000 octets aléatoires et faire des controles statistiques.
Par exemple : compter et comparer le nombre d’occurrences de chacune des 256 possibilités après ce million de tirages

L'évènement X251 "obtenir le nombre 251 après un tirage" n'a que deux issues : le succès (proba = 1/256) et l'échec (255/256). La question "quelle est la probabilité d'obtenir au moins K succès sur N tirages" est typiquement une loi binomiale (en avant les gros mots )
=> http://fr.wikipedia.org/wiki/Loi_binomiale
avec un écart type :
or d'après cette page, avec un tirage grand -- le cas ici -- ca tent vers la loi normale.



donc
score moyen = 1 000 000 / 256 = 3906,25
écartype = sqrt( 1 000 000 * (1/256) * (255/256) ) = 62,37781024

En gros au bout d'un million de tirages, si on prend l'intervalle +/- 2 écarts-type, j'ai 95.4% de chances de tirer entre
3782 (3906.25 - 2 * 62.37781024 = 3781,49438
et
4031 (3906.25 + 2 * 62.37781024 = 4031,00562)
fois le nombre 251

Mes questions
1. est-ce que ce raisonnement se tient jusque là ou je me suis déjà vautré avant ?
1.a si c'est correct, ai-je donc une probabilité de 0.954 ^ 256 ~= 5.8E-6 (cad quasi nulle) que tous les scores soient dans l'intervale 3782 -> 4031 (attention aux arrondis) ? ou est-ce qu'il faut alors parler de proba conditionnelle ?
1.b en suivant la mmeme idée, je crois avoir de l'ordre de 35% de chances d'avoir tous les scores dans l'intervalle +/- 3 écart-type. est-ce exact?

2. est-ce que je ferai mieux de m'interesser aux centiles ou déciles de ces 256 scores plutot que chercher à vérifier qu'ils sont tous dans tel ou tel intervalle ?

3. en m'attaquant au probleme B, est-il pertinent de chercher à déterminer (tjs avec un nombre élevé de tirages) la probabilité d'observer ensuite 0, 1, 2, 3, ... 255 sachant qu'on a eu X au tirage précédent ? cad observer les 256 * 256 = 65 536 successions possibles de deux tirages pour déterminer si avoir précédemment obtenu telle valeur influe sur le tirage suivant)

4. quelle autre mesure me permettrait de tester le caractère non prédictible d'une fonction de génération de nombre aléatoire ? (j'ai entendu parlé des fonctions acf et pacf dans R pour détecter un pattern dans une séquence de nombres, mais là je me sens largué)


les idées sont bienvenues

[Aleph69]

Bonjour,

on évalue un rng en examinant sa période et sa discrépance :
http://math.univ-lyon1.fr/~jberard/genunif-www.pdf
N'hésite pas à contacter l'auteur, il est sympa.

Par ailleurs, il existe déjà des méthodes assez robustes dont les propriétés théoriques sont bien connues, par exemple Mersenne-Twister :
http://fr.wikipedia.org/wiki/Mersenne_Twister
J'imagine que cela devrait amplement te suffire.

Une dernière remarque : n'utilise pas les fonctions "rand" des langages de programmation, ils sont en général peu performants.

[fourchette]

Envoyé par Aleph69

on évalue un rng en examinant sa période et sa discrépance :
http://math.univ-lyon1.fr/~jberard/genunif-www.pdf
N'hésite pas à contacter l'auteur, il est sympa.

Par ailleurs, il existe déjà des méthodes assez robustes dont les propriétés théoriques sont bien connues, par exemple Mersenne-Twister :
http://fr.wikipedia.org/wiki/Mersenne_Twister
J'imagine que cela devrait amplement te suffire.

voilà qui va m'assurer de la lecture pour ces prochains jours. le pdf a l'air de traiter exactement du sujet. je l'ai survolé très rapidement (scollé en fait), mais je ne crois pas avoir reperé le nom de l'auteur.
jberard est l'hebergeur ou l'auteur justement ?

Envoyé par Aleph69

Une dernière remarque : n'utilise pas les fonctions "rand" des langages de programmation, ils sont en général peu performants.

J'avais précisément fait cette observation. mais avant de considérer le critère de rapidité (au moment de comparer les options), je voulais surtout m'assurer de rester intransigeant sur la qualité (faire les tests unitaires d'abord)


j'ai noté dans randtest.c du source de openssl (le fichier qui visiblement teste le générateur de openssl) le comment suivant

Code :

1
2
/* some FIPS 140-1 random number test */
/* some simple tests */

dois-je comprendre que la qualité d'un PRNG est normalisée ?

[Aleph69]

Il s'agit de Jean Bérard :
http://math.univ-lyon1.fr/~jberard/

Pour les fonctions rand, je parle bien des performances en terme de qualité.

Il existe effectivement des normes pour les rng qui sont appliquées dans les domaines sensibles (sécurité) et commerciaux (distribution des mains dans les sites en ligne de poker, etc).

[fourchette]

ok. merci.

Envoyé par Aleph69

Il existe effectivement des normes pour les rng qui sont appliquées dans les domaines sensibles (sécurité) et commerciaux (distribution des mains dans les sites en ligne de poker, etc).

etre conforme à de telles normes serait un vrai plus.
Typiquement FIPS 140 est dans mes projets, mais je ne comptais pas m'y attaquer tt de suite et je ne savais pas que ça couvrait la génération de hasard.
tu as une autre référence qui fait autorité en matière (le truc qui te vient immediatement à l'esprit dans demander à google) ?

merci

[Aleph69]

Bonjour,

je ne suis pas expert en la matière mais pour moi le problème se pose différemment. Si tu récupères une boîte noire censée générer des nombres pseudo-aléatoires, alors la seule solution pour toi pour vérifier la performance de cette boîte est d'utiliser des tests statistiques pour évaluer la période et la discrépance de l'algorithme. En revanche, si tu connais l'algorithme implémenté, il y a de bonnes chances pour que des résultats théoriques soient connus ou démontrables. Dans ce cas, les tests sont seulement utiles pour valider ton implémentation et rassurer les futurs utilisateurs que ce que tu proposes est bien robuste.

En ce qui concerne les normes proprement dites, je n'y connais absolument rien. La seule chose qui me vienne à l'esprit sont les tests de Marsaglia :
http://en.wikipedia.org/wiki/Diehard_tests
Ils sont plutôt réputés dans le domaine mais je ne prétends pas du tout que ce sont les plus pertinents : j'imagine que des progrès ont été faits depuis le temps.

[fourchette]

je repasse par hasard sur ce post.

merci aleph69 pour le clin d'oeil sur diehard. ca semble effectivement un standard "de facto"
par ricochet je suis tombé sur dieharder, une implémentation libre plus évoluée, qui m'a permis justement de me sentir bien plus à l'aise sur mes implémentations (et celles des autres)
==> http://www.phy.duke.edu/~rgb/General/dieharder.php

bonus: il est directement disponible à l'apt-get

bémol : pour que les résulats soient valides, il faut baser le calcul sur de grands jeux d'essais (des Go de data random de mémoire)
et du coup, les passes de calcul d'évaluation du caractère aléatoire des Go de données générées sont très très longs (ex: une pleine nuit sur mon PC, soit quasi une belle semaine pour comparer des implémentations qd mm)

ce qui du coup n'est plus du tout applicable pour des tests unitaires. mais c'est résolu qd mm

merci

ps : le papier de jbernard est tres tres bien.

[Aleph69]

Bonjour,

merci pour ton message, je suis ravi d'avoir pu t'aider un peu!

Pense à mettre ce topic en résolu si ce n'est pas déjà fait.

A la prochaine!