Informatique et aléatoire

Sur les deux manières de produire de l'aléa en informatique

Il n’y a pas de hasard dans les générateurs algorithmiques de nombres dits pseudo-aléatoires. Comme tout programme informatique, quand on fournit les mêmes entrées au générateur, il produira les mêmes sorties, puisqu'il s'agit de machines de Turing déterministes. Ces paramètres en entrée s'appellent la graine ou le germe, et ces générateurs sont souvent basés sur des suites récurrentes : relancer deux fois de suite avec le même germe produit deux fois de suites la même séquence "pseudo-aléatoire".

Il y a donc reproductibilité chez les générateurs de nombres pseudo-aléatoires, et ces derniers sont appelés ainsi car, quoique déterministes, ce qu'ils produisent ressemble à de l'aléa. Plus précisément :

1. Les diverses propriétés statistiques de l'aléa doivent se retrouver dans la suite : même fréquence de 0 et de 1 dans des générateurs binaires, les motifs répétés (e.g., 11111) apparaissent avec la bonne probabilité, etc.
2. Les générateurs se basant sur des suites récurrentes, on a accès à une formulation mathématique, et donc on peut faire des preuves, garantir par exemple que ces fréquences tendent vraiment vers ce qui est attendu, etc.
3. Outre des preuves sur les propriétés d'aléa, on peut aussi faire des preuves de sécurité. Et donc concevoir des générateurs cryptographiquement sûrs, utiles en sécurité informatique à maints endroits.
4. Le caractère reproductible peut s'avérer utile à maintes occasions :
   1. Si l'on veut comparer la performance de deux systèmes sur des nombres tirés aléatoirement, pour que la comparaison soit équitable, il faut que les deux systèmes soient analysés sur le même aléa.
   2. A l'aide d'un générateur de bits sûr et reproductible, on peut faire un chiffrement symétrique par masque jetable. Alice veut envoyer un message à Bob. Les deux parties génèrent la même suite de bits aléatoires. Alice effectue le ou exclusif bit à bit entre son message binaire et sa suite aléatoire, elle envoie le résultat à Bob. Ce dernier effectue à nouveau le ou exclusif bit à bit entre le message chiffré et sa suite de bits aléatoires, et retrouve le message d'origine.

Au besoin, on peut accéder à des générateurs de nombres réellement aléatoires, au moins sur certains systèmes, comme suit :

  >>> SystemRandom().random()

Cette fois-ci, Python ne va pas utiliser un algorithme de type suite récurrente, mais va mixer des données captées (température du processeur, etc.) à diverses autres données "aléatoires", telles que le résidu mémoire, la position de la souris, etc.

1. Les nombres ainsi produits sont, d'une certaine manière, plus aléatoires, car ils ne sont pas issus d'un algorithme déterministe.
2. On perd le caractère reproductible.
3. On perd aussi la possibilité de faire des preuves, n'ayant plus de formulation mathématique. On ne peut donc pas établir que des propriétés attendues d'aléa ou de sécurité sont effectivement présentes.

Travaux pratiques

Programmez le chiffrement dit du masque jetable, présenté ci-dessus.

Suite pseudo-aléatoire

Une suite pseudo-aléatoire est une suite de nombres entiers $x_0$, $x_1$, $x_2$, etc. prenant ses valeurs dans l’ensemble {0, 1, 2, ..., m-1}.

Le plus souvent, chaque terme est le résultat d’un calcul sur le (ou les) terme(s) précédent(s). Il s'agit donc, comme on l'a évoqué, de suites récurrentes.

Le premier terme $x_0$ est appelé le germe de la suite.

Dans le cas où chaque terme de celle-ci n’est déterminé qu’à l’aide de son prédécesseur, la seule donnée du germe fixe logiquement la totalité de la suite. En d'autres termes, fournir deux fois de suite le même germe (avec la fonction seed de random) conduit à deux fois de suite l'obtention des mêmes nombres "pseudo-aléatoires" :

  >>> from random import random, seed
  >>> for k in range(5):
  ...     seed(0)
  ...     for l in range(5):
  ...         print random(),
  ...     print
  ... 
  0.844421851525 0.75795440294 0.420571580831 0.258916750293 0.511274721369
  0.844421851525 0.75795440294 0.420571580831 0.258916750293 0.511274721369
  0.844421851525 0.75795440294 0.420571580831 0.258916750293 0.511274721369
  0.844421851525 0.75795440294 0.420571580831 0.258916750293 0.511274721369
  0.844421851525 0.75795440294 0.420571580831 0.258916750293 0.511274721369

De plus, dans ce cas, on rencontre forcément parmi les m+1 premiers termes deux valeurs égales... et alors les termes se répètent indéfiniment à l’identique (on est bien loin du hasard.)

Choix du germe

Pour que ce phénomène gênant ne se fasse pas trop sentir, on prend en pratique des valeurs de $m$ très élevées ($m = 10^7$ pour excel.)

Si le germe est toujours le même, on retombe invariablement sur la même suite.

Pour cette raison, les générateurs de nombres aléatoires introduisent un soupçon de hasard « authentique » dans le choix du germe (en prenant, par exemple, les décimales de l’heure d’exécution du programme.)

Un exemple

On a par exemple utilisé m = 2147483647 et, après avoir choisi un germe x, e.g. en utilisant l’horloge système :

  >>> from time import time
  >>> x = int(100*time())
  >>> print x

on calculait le reste de $16807x$ (multiplication de 16807 par $x$) dans la division par $m$, pour obtenir le terme suivant. En d'autres termes, $x_0$ est le germe, et $x_{n+1}= 16807 x_n % m$.

Cette suite passe avec succès bon nombre de tests statistiques. Cependant, avec cette méthode :

• on boucle forcément un jour,
• le but est donc de boucler le plus tard possible.

Travaux pratiques

Générez la suite de nombres pseudo-aléatoires proposée ci-dessus.

Les générateur congruentiel linéaires (1948)

Présentation

On a déjà expliqué la différence entre générateurs de nombres pseudo-aléatoires et source d'aléa physique (bruit matériel), et l'on a donné un premier exemple, désuet, de tels générateurs pseudo-aléatoires. Nous présentons dans ce qui suit quelques générateurs réellement utilisés, en commençant par les générateurs congruentiels linéaires.

Ces derniers sont définis ainsi : $X_{n+1} = ( a \cdot X_n + c ) \% m$, où $a$, $c$ et $m$ sont les paramètres du générateur.

Ces générateurs sont évidemment périodiques, et certains paramètres produisent de meilleures suites que d'autres, dans le sens où leurs périodes sont maximales. Pour obtenir de tels paramètres, il faut et il suffit que:

• $c$ et $m$ soient premiers entre eux (leur pgcd vaut 1).
• Pour chaque nombre premier $p$ divisant $m$, $(a-1)$ est un multiple de $p$.
• $m$ multiple de 4 $\Rightarrow (a-1)$ multiple de 4.

(valable pour $c\neq 0$).

On choisit ordinairement pour $m$ une puissance de 2, et les conditions ci-dessus se simplifient alors grandement. La première condition, par exemple, devient "$c$ impair".

Travaux pratiques

1. Programmer ce générateur
2. Trouver de bons paramètres $a, c, m$. Ils devront:
   1. Avoir une fréquence d'apparition des entiers de 0 à $m-1$ proche de $\frac{1}{m}$.
   2. Avoir une période supérieure à un seuil que vous prédéfinirez.
   3. Avoir la bonne fréquence des mots de taille 2. Ainsi, le mot 21 doit apparaître avec la fréquence $\frac{1}{m^2}$.
   4. Avoir la bonne fréquence des mots de taille $k$.
   5. On s'intéressera ensuite aux runs, via le test de Wald-Wolfowitz et deux de ses implémentations en python : ici et là.

Le XORshift

Présentation

Ce générateur a été proposé il y a peu par Marsaglia, il possède à la base trois paramètres entiers $a,b,c$. On peut résumer son fonctionnement de la manière suivante:

1. On part d'un vecteur de 32 bits, qui sert de graine.
2. Pour calculer le nouveau terme à partir du terme actuel $x$:
   1. On remplace x par le résultat du ou exclusif bit à bit entre x et sa version décalée de $a$ bits vers la droite (décalage circulaire, les bits sortant à droite rentrent à gauche).
   2. On remplace x par le résultat du ou exclusif bit à bit entre x et sa version décalée de $b$ bits vers la gauche (décalage circulaire).
   3. On remplace x par le résultat du ou exclusif bit à bit entre x et sa version décalée de $c$ bits vers la droite (décalage circulaire).
3. La valeur obtenue après ces trois opérations est le nouveau terme de la suite, à produire en sortie.

Un bout de code en C détaillant le XORshift avec (12, 25, 27) comme paramètres serait donc :

  x ^= x >> 12; // a
  x ^= x << 25; // b
  x ^= x >> 27; // c

Travaux pratiques

1. Réaliser ce générateur
2. Trouver de bons paramètres en reprenant les tests du générateur congruentiel linéaire.

Eléments de réponse

D'autres générateurs

Si le sujet vous intéresse, vous pourrez programmer, puis tester, les générateurs suivants :

1. Le Blum Blum Shub, un générateur cryptographiquement sûr, mais lent. Application : le cryptosystème de Blum-Goldwasser
2. Les Registres à décalage à rétroaction linéaire
3. Le Mersenne-twister, générateur par défaut dans Python, R, Ruby, Maple, etc.
4. ISAAC, un autre générateur cryptographiquement sûr, qui ne possède pour l'instant pas d'implémentation en python.