Exigences vis à vis d'un générateur de nombres pseudo-aléatoires

Les générateurs de nombres pseudo-aléatoires sont utilisés principalement à deux fins :

  • Simulation : simulation physique, jeux vidéos, etc.
  • Sécurité : générer un secret pour garantir la confidentialité

Dans les deux domaines, la qualité du générateur est importante. Si un générateur est biaisé, c'est-à-dire que la distribution n'est pas équitable entre les différentes valeurs possibles, le résultat de la simulation sera invalide (ou bien simplement imprécis) et la confidentialité peut être comprise. Par contre, la simulation privilégie la vitesse du générateur. Alors que pour la sécurité on se donne les moyens pour qu'il soit difficile de deviner les nombres précédemment générés et les prochains nombres générés (quitte à ce que le générateur soit plus lent), ce qui revient à deviner quel est l'état interne du générateur étant donné qu'un algorithme est déterministe.

Générateur biaisé

Reprenons l'exemple de RANDU, un générateur biaisé (les bits de poids faible sont peu aléatoires). Si on utilise 1 + rand() % 6 pour simuler un lancé de dé, on va obtenir une suite du genre :

  1, 3, 1, 5, 3, 3, 1, 5, ...

Les faces 2, 4 et 6 ne sont jamais tirées !

Inverser un générateur congruentiel linéraire

Il est possible de deviner l'état interne d'un générateur congruentiel linéraire (LCG) en ne connaissant qu'un seul nombre généré. L'algorithme RANDU est :

  x(n+1) = (x(n) * 65539) % 2147483648

Avec x(0) : graine du générateur. On peut exécuter le générateur à l'envers en calculant :

  y(n+1) = (y(n) / 65539) % 2147483648

Sachant que diviser revient à multiplier par l'inverse, x / 65539 <=> x * (1 / 65539), on va calculer l'inverse 65539 modulo 2147483648 avec le théorème des restes chinois. En pratique, on utilise l'identité de Bezout. Fonction Python qui calcule les coefficients u et v tels quel a · u + b · v = 1 :

def bezout(a, b):
  u0 = 1; u1 = 0
  v0 = 0; v1 = 1
  while 1:
    q = a // b
    r = a % b
    u0, u1 = u1, u0 - q*u1
    v0, v1 = v1, v0 - q*v1
    if r != 0:
      a = b
      b = r
    else:
      break
  return (u0, v0)

On calcule alors bezout(65539, 2147483648) = (477211307, -14564), ce qui donne :

  65539 · 477211307 - 2147483648 · 14564 = 1

et

  (477211307 * 65539) % 2147483648 = 1

Finalement, y(n+1) = (y(n) * 477211307) % 2147483648.

Exemple :

 x(0) = 42
 x(1) = 2752638
 x(2) = 16515450
 x(3) = 74318958

On utilisant x(3), on va pouvoir générer les nombres précédents :

 y(0) = 74318958
 y(1) = 16515450
 y(2) = 2752638
 y(3) = 42

On a donc réussi à retrouver les nombres précédents jusqu'à la graine (42). Même si le générateur ne délivre que quelques bits de son état interne (ex: rand() = x(n) & 0xffff), on peut retrouver l'état interne en utilisant une recherche exhaustive (si on dispose de quelques nombres successifs).

Solutions

Pour rééquilibrer la distribution d'un générateur, on peut l'améliorer en utilisant différrentes techniques :

Lire la RFC 1750 pour les sources et les détails sur ces techniques.

Pour empêcher qu'un pirate arrive à deviner l'état interne du générateur, on peut rajouter une fonction de hachage sur la sortie du générateur (ex: MD5, SHA-1, ...). Il est toujours possible d'inverser la fonction de hachage, mais c'est beaucoup plus difficile !