Le test du chi-2

Présentation

Il s'agit d'un des tests les plus utilisés, qui permet de vérifier l'adéquation d'un ensemble de valeurs à une loi donnée. Par exemple, si on simule le lancer d'un dé à 4 faces avec randint, et que l'on veut savoir si l'on obtient bien "quelque chose" suivant une loi uniforme:

• On pose l'hypothèse que le "dé" ainsi constitué est non biaisé.
• On définit le risque $\alpha$, par exemple 95%.
• $n=4$ : on a 4 valeurs possibles.

Commençons par simuler des valeurs:

  >>> from random import randint
  >>> L=[]
  >>> for k in range(100000):
  ...     L.append(randint(1,4))
  ... 
  >>> [L.count(k) for k in range(1,5)]
  [24929, 25217, 24801, 25053]

On s'intéresse, dans le test du chi-2, à la valeur $\sum \frac{(O_i-T_i)^2}{T_i}$, avec $i=1..n$, où $O_i$ est le nombre de fois que l'on a obtenu la face $i$ quand $T_i$ est le nombre théorique attendu. Comme on a lancé 100000 fois notre dé, on s'attend à T=[25000, 25000, 250000, 25000], et on a observé O=[24929, 25217, 24801, 25053]. La somme ci-dessus vaut donc:

  >>> sum([(L.count(k)-25000.)**2/25000 for k in range(1,5)])
  3.7815999999999996

Il reste à comparer cette valeur à la loi du chi-2, ayant $n-1 = 3$ degrés de liberté, et pour le risque $\alpha = 0.95$:

  >>> sum([(L.count(k)-25000.)**2/25000 for k in range(1,5)])
  3.7815999999999996
  >>> from scipy.stats import chi2
  >>> chi2.ppf(0.95, 3)
  7.8147279032511765

La valeur que l'on calcule étant inférieure à celle retournée par chi2.ppf, on peut donc accepter, au risque $\alpha$, l'hypothèse que les valeurs produites suivent une loi uniforme.

Travaux pratiques: Stéganographie

Utiliser le test du chi2 pour dissimuler une information dans une image (pour manipuler des images, on utilisera PIL):

1. Trouver une image en niveaux de gris, et un message à dissimulé écrit en binaire.
2. Tester si les bits de poids faibles des pixels (leur modulo 2, quoi) s'apparentent à du bruit (bits tirés uniformément) par un test du chi-2.
3. Si le test échoue, remplacez tous les bits de poids faibles par des bits tirés aléatoirement.
4. Faire le ou exclusif bit à bit entre votre message et ces bits aléatoires, en commençant au pixel numéro $k$ (clé secrète de dissimulation). Il s'agit là d'un chiffrement type « masque jetable ».
5. Pour retrouver votre message :
   1. Si vous avez utilisé un générateur de nombres pseudo-aléatoires, utilisez la même graine pour produire la même suite de bits, et faites à nouveau le ou exclusif bit à bit entre ce que vous venez de générer est les bits de poids faibles de l'image.
   2. Sinon, il faut faire le ou exclusif bit à bit entre les bits de poids faible de l'image d'origine, et ceux de l'image trafiquée.
6. On retrouvera notre message en position $k$

Si vous utilisez un générateur cryptographiquement sûr, alors:

1. Il est possible de détecter un bruit anormal dans l'image, de se douter que le canal est trafiqué.
2. Si vous fournissez un ensemble d'images ainsi trafiquées, il est impossible de savoir lesquelles contiennent une information secrète.
3. Si on vous donne une image ainsi trafiquée, il est impossible de retrouver le message. Même, il est impossible de savoir quels pixels contiennent l'information secrète.