WikiMath

---

Présentation générale

Comme on l'a expliqué, les générateurs de nombres aléatoires et pseudo-aléatoires sont une des bases de la sécurité informatique. Rentrons un peu plus dans les détails...

Les premiers sont basés sur le matériel:

• Ils utilisent une source physique d'entropie, en utilisant notamment les capteurs du dispositif : k-ième décimale de la température du processeur, bruit de fond capté par le micro, pression, valeurs captées par l'accéléromètre, etc.
• Ces derniers peuvent être mélangés au résidu mémoire, éventuellement à l'action de l'utilisateur...
• Basé sur un bruit physique, il s'agit d'un aléa "vrai", mais non prouvable : on ne peut par exemple pas montrer que la variable aléatoire correspondant à cette génération physique suit une loi normale.
• Cet aléa n'est pas reproductible.
• En cryptographie, de tels générateurs sont nécessaires à la génération des clés pour les cryptosystèmes.
• Avec pyboard, on a accès a un tel générateur : pyb.rng().

Les seconds sont basés sur des algorithmes:

• La plupart du temps, le point de départ est une suite récurrente modulo N.
• La suite est choisie de sorte que les nombres produits lors des itérations ressemblent beaucoup à des nombres aléatoires.
• Par "ressembler", on entend par exemple : aucun test statistique ne devrait être en mesure de faire la distinction entre une suite réellement aléatoire et une suite produite par cet algorithme.
• Le premier terme de la suite constitue la graine du générateur pseudo-aléatoire. Fournir deux fois de suite la même graine conduit à engendrer deux fois de suite les mêmes nombres pseudo-aléatoires.
• Cette reproductibilité est intéressante en cryptographie : elle permet de réaliser aisément du chiffrement symétrique par masquage dans du bruit, comme on l'a vu précédemment.

Dans ce qui suit, nous nous intéresserons plus en détails aux algorithmes de génération de nombres pseudo-aléatoires.

Les générateur congruentiel linéaires

Présentation

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 (LCG, 1948):

• leur très faible complexité les rend utilisables dans l'internet des objets, même à très faible ressource;
• ils ne sont cependant pas sûr, aussi d'autres générateurs sont par la suite introduits.

Ces LCG 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$).

Travaux pratiques

1. Programmer ce générateur sur le pyboard.
2. Trouver de bons paramètres $a, b, m$.
3. Vérifier que les nombres produits ressemblent à du hasard. Par exemple, regarder la fréquence d'apparition des nombres pairs et impairs.
4. Intégrer cet outil de génération d'aléa au masque jetable précédemment programmé.

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 sur pyboard
2. Comparer le temps nécessaire à de la génération d'aléa suivant les deux techniques.

D'autres générateurs classiques

Suivant votre avancée, vous pouvez compléter votre bibliothèque avec les générateurs suivants:

1. Les Registres à décalage à rétroaction linéaire
2. Le Mersenne-twister, générateur par défaut dans Python, R, Ruby, Maple, etc.

Vous pouvez ensuite comparer les temps d'exécution sur la pyboard, et discuter de la possibilité d'utiliser de tels générateurs sur un tel composant.

Des générateurs cryptographiques

Les générateurs tels que le LCG sont rapides et nécessitent peu de ressources, on peut donc raisonnablement les utiliser dans le cadre de l'internet des objets, quand un besoin d'une source d'aléa se fait sentir. Cependant l'aléa engendré par de tels générateurs est d'une qualité assez mauvaise : ils ne passent par exemple pas des batteries de tests d'aléa tels que ceux présents dans la bibliothèque TestU01. De même, ils ne respectent pas la condition demandée par Shannon pour faire du masque jetable une technique cryptographiquement sûre.

On peut en effet formuler proprement, en termes mathématiques, le fait pour un générateur pseudo-aléatoire d'être cryptographiquement sûr. Sans rentrer dans les formules, cela signifie que si l'adversaire a n bits produits par un tel générateur, il ne peut pas, en temps raisonnable (polynomial) prédire le prochain bit sans, en moyenne, se tromper une fois sur 2. Il ne peut pas produire d'algorithme polynomial apte à compléter notre suite de bit, qui fasse moins d'erreurs qu'une simple prédiction aléatoire. A nouveau, tout cela se formalise via les théories des probabilités et de la complexité.

Il existe des générateurs cryptographiquement sûrs, tels que :

1. Le Blum Blum Shub
2. ISAAC.

Nous vous proposons d'implémenter sur pyboard au moins le BBS, voire les deux.

Signalons maintenant que :

• le BBS nécessite une élévation au carré, et est donc bien moins adapté à l'internet des objets que le LCG, qui est linéaire.
• sa sécurité est, en gros, reliée à la difficulté de remonter aux nombres premiers dont le produit constitue le modulo.
• la sécurité de tout cryptosystème actuellement utilisé revient au fait que le problème de la factorisation d'un nombre devient difficile quand ce dernier devient grand.

On trouve ici le problème fondamental de la sécurité dans le cadre de l'internet des objets : plus la taille des nombres premiers augmente...

• plus la sécurité augmente
• plus les calculs demandent du temps, donc consomment de l'énergie.
• plus la taille des nombres à manipuler augmente, donc nécessitent de la mémoire.
• plus la taille des cryptogrammes augmente, augmentant pareillement la taille des données à transmettre.

Et le coût de transmission est ce qui coûte le plus cher, en termes de batterie. Bref, le mot-clé de l'internet des objets, quand il s'agit de sécurité, est le compromis : plus grande sera la sécurité, plus grand le besoin d'énergie, et plus petite la durée de vie du réseau. Il s'agit donc de bien positionner le curseur...