3 A3. Générateurs pseudo-aléatoires

La génération de nombres ressemblant par certaines propriétés à des nombres aléatoires n'est pas une question nouvelle : deux récents articles de synthèse [20,39] recensent près de 300 références... Il convient de distinguer soigneusement l'utilisation des nombres pseudo-aléatoires comme support des simulations sur ordinateurs de leur utilisation pour le chiffrement.

3.1 pour la simulation

Dans ce premier cas, on connaît un certain nombre de générateurs, utilisant par exemple des propriétés congruentielles comme :

$$x:=41358 x\mod \left( 2^{31}-1\right)$$

qui donnent des suites très longues imitant assez bien les propriétés de variance et d'auto-corrélation linéaire que possèderaient des nombres réellement tirés au sort. Mais, déjà dans ce cas, il ne semble pas que les implémentations soient toujours bonnes, même quand il ne serait pas coûteux de les améliorer. En particulier, il n'est pas toujours vrai que l'on puisse les utiliser pour simuler les coordonnées d'un point aléatoirement uniformément réparti dans un hypercube de dimension donnée.

3.2 pour le chiffrement

Si l'on veut maintenant faire du "chiffrement au vol", en XORant le flot à chiffrer avec un flot "imprévisible", il est clair que l'on ne peut pas utiliser ce genre de générateurs. Il s'agirait au contraire du pire choix possible, car la formule en question est déterministe. Il suffit d'une suite très peu longue pour pouvoir inférer la formule utilisée (module et multiplicateur). Il est à peine meilleur de ne garder que les derniers bits (et de faire tourner l'algorithme plusieurs fois pour fabriquer un nombre complet) [51]

Par contre un algorithme quadratique avec pour module $n=p q$, produit de deux "grands" nombres premiers résiste à l'analyse si l'on ne publie que les bits de poids faible. Mais il est alors nécessaire de choisir soigneusement n et la valeur initiale [7], sinon on obtient un cycle très court, qui n'a plus besoin d'être analysé : il suffit de l'observer pour pouvoir le prédire. La Table 14 donne des conditions nécessaires de ce choix.

Table: Générateur "imprévisible".

D'autres techniques encore sont possibles. Par exemple le résultat du compactage d'un texte quelconque (amputé du préfixe qui consiste en la table de traduction code de Huffman <-> code Ascii) donne une suite de bits dont l'entropie n'est pas loin d'être maximale, et qui semble définir un flot de nombres pseudo-aléatoires satisfaisant. Il reste à transporter ce flot ... (valise diplomatique ?)

3.3 omniprésence de la question

En tout cas, cette question de génération de nombres pseudo-aléatoires est très importante, et ne se pose pas uniquement pour le chiffrement par flot. Bien au contraire : à peu près tous les algorithmes utilisent des nombres aléatoires ou bien comme clefs ou bien comme preuve de fraîcheur d'un message (cf paragraphe 4). Par conséquent, si l'état interne du générateur peut être analysé, et son résultat calculé ou inféré, l'ensemble du protocole est compromis.