Les générateurs
de nombres aléatoires

Décembre 2022

Avant de regarder les sources d'entropie, nous allons jeter un œil aux post-traitements, post-process en anglais, parfois utiles, histoire de savoir de quoi il retourne.

On peut inclure ces traitements dans la case "correcteur d'entropie", ou pas, c'est le concepteur du TRNG qui vous le dira.

Von Neumann

Si jamais vos bits aléatoires n'ont pas une distribution uniforme, et si vous êtes sûr qu'il n'existe pas de corrélation entre deux bits successifs, alors un moyen simple de redresser la situation est d'utiliser l'algorithme de Von Neumann :

  • Prenez deux bits successifs
  • S'ils sont égaux (00 ou 11), vous les jetez
  • Si c'est 10, vous les remplacez par 1
  • Si c'est 01, vous les remplacez par 0

Oui, c'est aussi simple que cela. Mais efficace. Et oui, vous perdez des bits, donc du débit.

Ajout d'un bloc pseudo-aléatoire

Les paranoïaques ajouteront au cul du TRNG un PRNG, autrement dit on chaine un TRNG avec un générateur pseudo-aléatoire, la sortie du TRNG servant de graine au PRNG. Il sera éventuellement considéré comme un "correcteur d'entropie".

Pourquoi faire simple alors qu'on peut faire compliqué ?

On fait cela quand on a des doutes sur le TRNG, et que, par contre, on connait bien le générateur pseudo-aléatoire parce qu'on a pu l'étudier profondément, s'agissant d'un algorithme. Et qu'il est parfaitement reproductible. L'imprédictibilité sera assurée par l'imprédictibilité de la graine.

D'autres utiliseront un hachoir une fonction de hachage, pourquoi pas ? Son côté aléatoire est très attractif, encore faut-il en montrer l'intérêt.

À côté de cela, on peut ajouter des générateurs pseudo-aléatoires très simples à réaliser en logique, pour donner un exemple, voici un registre à décalage rebouclé :

Linear Feedback Shift Register

De nombreuses solutions existent, limitées par notre imagination. Mais au moins, dans ce domaine, c'est sûr que l'intelligence artificielle ne viendra pas nous pourrir la vie, je ne vois pas comment elle se dépêtrera avec des suites aléatoires imprédictibles...

Allez, maintenant on va regarder le cœur battant des générateurs aléatoires, les sources d'entropie.