Introduction aux tests des générateurs aléatoires

Lorsqu'on a conçu un générateur aléatoire ou un générateur pseudo-aléatoire, il faut lui faire passer une batterie de tests statistiques pour vérifier la qualité de l'aléa produit.

Sommaire :

  1. Les générateurs de nombres aléatoires et pseudo-aléatoires
  2. Le hasard et l'imprévisibilité
  3. Tester un générateur aléatoire
  4. Les propriétés statistiques des générateurs pseudo-aléatoires
  5. Les librairies de tests statistiques

Informations sur le parcours

Titre :
Introduction aux tests des générateurs aléatoires
Profils :
Enseignant & Lycéen, Ingénieur informatique, Enseignant-Chercheur, Etudiant
Thème :
Générateur pseudo-aléatoire
Finalité :
Pédagogique
Difficulté :
niveau 1
Auteur(s) :
Johan Apfeldorfer , Anne Canteaut
Mise à jour :
06/03/2006 à 16h15
 

Les générateurs de nombres aléatoires et pseudo-aléatoires

            Le besoin en nombres aléatoires se fait ressentir dans de nombreuses applications de la cryptographie. Dans des systèmes cryptographiques courants, on utilise des clés (des nombres) qui doivent être produites de façon aléatoire.

            Par exemple lorsque l’on consulte sur Internet ses comptes bancaires ou lorsque l’on effectue une commande par Internet certaines informations « sensibles » (votre code d’accès ou votre numéro de carte bleue) doivent rester confidentielles pour assurer votre authentification :  personne ne doit pouvoir accéder à vos comptes ni commander avec votre carte bancaire. Pour assurer ces fonctions des protocoles Internet ont été mis en place. Ils vous permettent d’entrer vos codes sur une page Web sans risquer qu’une personne extérieure puisse y avoir accès. Ces protocoles utilisent des nombres aléatoires pour chiffrer les données et ainsi empêcher tout espionnage.

            Le besoin en nombre aléatoire est donc particulièrement important dans les domaines de l’informatique et d’Internet. Pour répondre à ce besoin deux types de générateurs existent : les générateurs de nombres aléatoires (RNG pour Random Number Generator) et les générateurs de nombre pseudo aléatoire (PRNG pour PseudoRandom Number Generator). La différence entre ces types de générateur est principalement d’ordre technique :

            Un RNG utilise comme source un ou plusieurs paramètres physiques provenant de son environnement (la température du processeur, le bruit parasite sur une ligne électrique ou le déplacement de la souris par exemple). Ils fournissent une clé unique pour chaque paramètre (ou ensemble de paramètres si le générateur en utilise plusieurs). Le caractère aléatoire provient dans ce cas du hasard des paramètres du générateur et le nombre ne peut pas être reproduit (car on ne peut pas produire deux fois exactement les mêmes paramètres).

            Les PRNG ont été conçus spécialement pour générer des suites aléatoires reproductibles. Une telle suite possède toutes les propriétés d’imprévisibilité de celles qui sont produites par un RNG, mais la production des nombres est déterministe, c’est-à-dire reproductible. On conserve dans ce cas le caractère aléatoire en utilisant comme paramètre un nombre fournit par un RNG. On fournit donc au PRNG un unique paramètre (la graine) et le PRNG calcule par un algorithme la suite de nombres aléatoires correspondante. De manière étonnante lorsqu’on mesure le caractère aléatoire (par des tests statistiques) d’une suite provenant d’un PRNG, on observe souvent qu’elle possède de meilleures propriétés que celles qui sont fournies par un RNG.

Le hasard et l'imprévisibilité

            Nous allons voir ici comment définir une suite (de nombres) aléatoire. Comme les générateurs de nombres aléatoires (ou pseudo aléatoires) sont destinés à un usage informatique, il faut tout d’abord savoir qu’ils génèrent en réalité des suites de 0 et de 1 (pour que cela corresponde directement avec la représentation binaire des nombres dans la machine). On peut donc modéliser le hasard par le résultat d’une série de lancers d’une pièce de monnaie  non-pipée (« tire à pile ou face ») chaque lancer étant indépendant de tous les lancers précédents (i.e un lancer de la pièce n’influence pas le résultat d’un lancer futur). On considère donc qu’une pièce de monnaie constitue un générateur aléatoire parfait. Le caractère aléatoire d’une suite correspond donc à l’imprévisibilité de l’élément suivant, quel que soit le nombre de lancers déjà effectués. C’est donc un caractère probabiliste. 

            Cependant l’imprévisibilité des PRNG est différente de celle des RNG : un RNG est totalement imprévisible puisque qu’il faut connaître la valeur des paramètres qu’il utilise ce qui n’est pas possible. L’imprévisibilité des PRNG est elle toute relative : les algorithmes de calcul étant le plus souvent public, il suffit de connaître la graine de la suite (le nombre fourni par un RNG) pour déterminer l’ensemble de la suite. Il faut souligner ici que cette relativité est non seulement normale mais aussi voulue puisque c’est ce qui permet d’authentifier une personne en observant si elle est capable ou non d’exhiber les valeurs suivantes de la suite (seules les personnes qui possèdent la source de la suite en sont capables).

Tester un générateur aléatoire

Après avoir conçu un générateur que l’on pense aléatoire (ou pseudo aléatoire) il faut le tester. En effet personne ne doit pouvoir prévoir de quelques manières que ce soit les valeurs générées. Il faut donc s’assurer qu’il n’y a aucune redondance dans la suite construite, que la suite construite est effectivement aléatoire. Pour cela on utilise des tests statistiques. Ces tests prennent en paramètre l’ensemble sur lequel on veut vérifier la propriété (ici la suite dont on veut savoir si elle est ou non aléatoire). Dans la pratique on considère deux hypothèses : la première, souvent notée H0 représente le caractère à tester (ici le caractère « est aléatoire ») et le second, souvent notée Ha représente le contraire de H0 (ici le caractère « n’est pas aléatoire »). D’un point de vue théorique, on s’appuie sur la loi mathématique de tendance vers la loi Normale et sur le test du Chi2.

La première difficulté est qu’un test statistique ne peut pas valider l’hypothèse H0 mais seulement conclure qu’elle n’est pas contradictoire avec l’observation (par contre il peut rejeter H0 et valider Ha). Par exemple une de caractéristique de la propriété « est aléatoire » est l’équiprobabilité, c’est-à-dire que chaque valeur de la suite apparaît avec la même fréquence (dans notre cas 0 et 1 apparaissent avec une fréquence  1/2). Un premier test consiste donc à vérifier ce point.

Cependant conclure que la suite est aléatoire si elle passe ce test avec succès est absurde : en effet une suite du type 0101010 etc. passe ce test sans problème, mais ne peut en aucun cas être considéré comme aléatoire. Il est donc nécessaire de prévoir plusieurs tests complémentaires (i.e avec les mêmes hypothèses H0  et Ha mais avec des objectifs différents, par exemple le calcul de la fréquence et la recherche de chaînes périodiques dans la suite).

Par ailleurs un second problème spécifique au test de « est aléatoire » est justement qu’on test quelque chose qui doit être aléatoire : de ce fait il est nécessaire qu’une certaine proportion de tests conduise à des échecs, ce sera par exemple le cas dans le test en fréquence par blocs. Dans ce test, la suite est découpée en blocs sur lesquels un test en fréquence simple est effectué. Même si cela est peu probable un bloc constitué à 70% de 0 (ou de 1) peut apparaître dans la mesure où on test des suites de longueur largement supérieure au million (parfois même de l’ordre du milliard). L’interprétation des résultats est donc particulièrement complexe : il faut que les tests réussissent de manière générale mais il faut aussi qu’une partie échoue, sans toutefois que les échecs soient trop nombreux !

Les propriétés statistiques des générateurs pseudo-aléatoires


Pour qu'un chiffrement à flot résiste aux attaques par distingueur, il faut que le générateur pseudo-aléatoire utilisé possède de bonnes propriétés statistiques. Même si l'existence d'une attaque par distingueur ne remet pas toujours en cause complètement la sécurité du chiffrement (car elle ne permet pas nécessairement de retrouver le texte clair, ou la clef secrète), un critère classique de sécurité est que 2k bits de sortie du générateur pseudo-aléatoire ne puissent pas être distingués d'une suite aléatoire au moyen d'un algorithme dont le coût soit inférieur à 2k, où k correspond ici au nombre de bits de la clef secrète.


Pour les générateurs pseudo-aléatoires utilisés en pratique pour le chiffrement à flot, il n'existe pas de preuve théorique de l'absence de distingueur de complexité polynômiale. Toutefois, on dispose d'un certain nombre de tests statistiques classiques que tout générateur pseudo-aléatoire doit au minimum vérifier pour prétendre à une sécurité raisonnable, mais il ne s'agit évidemment pas d'une condition de sécurité suffisante.

Les premières propriétés statistiques requises pour une suite pseudo-aléatoire ont été décrites par Knuth [2] et Golomb [1]. Elles ont donné lieu à des familles de tests, qui ont été enrichies depuis. On distingue usuellement les tests probabilistes dits de normalité, qui déterminent la probabilité pour qu'une suite tirée aléatoirement vérifie une propriété identique à celle de la suite à tester, et les tests dits de compression qui déterminent si la suite à tester peut être compressée de façon significative.

Les tests de normalité.   Les tests de normalité reposent sur le principe suivant : à toute suite de n bits on associe une certaine quantité dont on peut déterminer la distribution de probabilité pour une suite aléatoire. Par exemple, dans le test de fréquence qui vérifie si l'écart entre le nombre de zéros et le nombre de uns dans une suite binaire de longueur n est raisonnablement faible, on utilise la quantité
X = (n0−n1)2
n
(1)
où n0 (resp. n1) est le nombre de 0 (resp. de 1) dans la suite. Cette quantité suit une distribution du χ2 de degré 1 quand n ≥ 10 (en pratique, il est préférable d'effectuer ce test sur une longueur de l'ordre de quelques milliers de bits).
On calcule ensuite la valeur de cette quantité pour la suite pseudo-aléatoire à tester (ou pour l'ensemble de suites produites par le générateur) et on la compare à la valeur moyenne attendue pour une suite aléatoire. Plus exactement, on détermine, à partir de la distribution de référence, la probabilité d'obtenir un tel écart par rapport à la moyenne. Par exemple, si la suite pseudo-aléatoire à tester est de longueur 100, et possède 38 zéros et 62 uns, on obtient pour la formule (1) la valeur x=5,76. On déduit de la distribution de probabilité du χ2 que la probabilité pour qu'une suite aléatoire possède une valeur de X supérieure à 5,02 est 0,025. Ainsi il y a moins de 2,5 % de chance d'obtenir cette valeur pour une suite aléatoire. On décide donc que la suite testée passe ou ne passe le test en fonction d'un niveau de confiance, c'est-à-dire en fonction de la probabilité que ce test échoue pour une suite aléatoire.
De façon similaire, on peut tester la proportion de zéros et de uns dans des blocs de k bits. Parmi les autres tests de normalité classiques, on peut aussi mentionner le test de répétition, le test d'oscillation, le test du poker...

Les tests de compression.   Ces tests statistiques déterminent si une suite peut être compressée de façon significative sans perte d'information, ce qui la distinguerait d'une suite aléatoire. Parmi ces tests, les plus connus sont le test universel de Maurer [3], le test de compression Lempel-Ziv, le test de l'entropie de Pincus, Singer et Kalman et le test de la complexité linéaire.

Pour plus de précisions sur les tests, voir le parcours "description des tests statistiques

 

Références

[1]
S.W. Golomb. Shift register sequences. Aegean Park Press, 1982.
[2]
D. E. Knuth. The Art of Computer Programming, 2 - Seminumerical Algorithms. Addison Wesley, 1969.
[3]
U.  Maurer. << A universal statistical test for random bit generators >>. Advances in Cryptology - CRYPTO'90, 473 Lecture Notes in Computer Science. Springer-Verlag, 1990.
[4]
NIST SP 800-22. << A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications >>. NIST Special Publication 800-22, 2000. National Institute of Standards and Technology.

Les librairies de tests statistiques

Il existe plusieurs librairies classiques qui fournissent une implémentation de séries de tests statistiques, dont la plus célèbre et la plus utilisée est celle du NIST.



La série de tests du NIST  (National Institute of Standards and Technology), détaillée dans la publication spéciale du NIST 800-22 [4], et dont une description précise et une implémentation est disponible sur http://csrc.nist.gov/rng/. Cette librairie implémente 16 tests différents dont:
  • les tests de normalité classiques comme le test de fréquence global et par blocs, le test de répétition...
  • le test de rang de la matrice binaire,
  • le test spectral (calcul de la transformée de Fourier discrète),
  • le test de la complexité linéaire
  • le test universel de Maurer
  • le test de l'entropie
  • le test de la complexité de Lempel-Ziv.


La série des tests DIEHARD   développée par G. Marsaglia de l'Université de Floride, et disponible sur http://stat.fsu.edu/~geo/diehard.html


La série de tests Crypt-XS   développée par le centre de recherche en sécurité de l'Université du Queensland en Australie, et disponible sur http://www.isrc.qut.edu.au/cryptx/

Pour plus de précisions sur les tests, voir le parcours "description des principaux tests statistiques"

 

Références

[1]
S.W. Golomb. Shift register sequences. Aegean Park Press, 1982.
[2]
D. E. Knuth. The Art of Computer Programming, 2 - Seminumerical Algorithms. Addison Wesley, 1969.
[3]
U.  Maurer. << A universal statistical test for random bit generators >>. Advances in Cryptology - CRYPTO'90, 473 Lecture Notes in Computer Science. Springer-Verlag, 1990.
[4]
NIST SP 800-22. << A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications >>. NIST Special Publication 800-22, 2000. National Institute of Standards and Technology.