Génération matérielle de nombres aléatoires

Pour commencer, il faut savoir qu'il existe deux types de registres à décalage à rétroaction :

• les registres à décalage à rétroaction de Fibonacci ;
• les registres à décalage à rétroaction de Gallois.

Dans ce qui va suivre, nous allons commencer par les registres à décalage à rétroaction de Fibonacci.

II-A-1. Registre à rétroaction de Fibonacci▲

Dans ceux-ci, le bit à faire rentrer à gauche change à chaque fois. Ce bit est calculé par un petit circuit combinatoire, qui est couplé au registre à décalage. Ce circuit combinatoire va prendre en entrée le contenu du registre à décalage, et va en déduire le bit à faire rentrer dedans. Ce circuit va donc utiliser tout ou partie des bits du registre à décalage et faire quelques opérations simples dessus pour déduire quel bit faire rentrer à gauche (ou à droite).

Ce circuit combinatoire possède quelques propriétés :

• le résultat en sortie est un simple bit ;
• ce résultat est déduit à partir de tout ou de certains bits de l'entrée.

La fonction qui permet de calculer le bit en sortie est assez spéciale. Dans le cas le plus simple, on dit qu'elle est linéaire. Cette dernière propriété mérite quelques explications. Pour commencer, je tiens à préciser que nous allons nous concentrer uniquement sur les registres à rétroaction linéaire binaire.

Par linéaire, on veut dire que le bit de sortie se calcule en multipliant les bits d'entrée par différents coefficients, et en additionnant le tout. En clair, ce bit de sortie se calcule par une formule du style :

kitxmlcodelatexdvp0 * a3 + 1 * a2 + 1 * a1 + 0 * a0finkitxmlcodelatexdvp

Comme vous le voyez, chacun des bits du nombre est d'abord multiplié par un coefficient qui vaut zéro ou un. Ensuite, les résultats de ces multiplications sont tous additionnés, et on ne garde que le bit de poids faible. Cela revient à choisir certains bits du nombre (ceux dont le coefficient est 1, les autres étant simplement ignorés), à les additionner, et à ne garder que le bit de poids faible du résultat de l'addition.

Penchons-nous un peu sur cette addition qui ne garde que le bit de poids faible : je ne sais pas si vous avez remarqué, mais il s'agit ni plus ni moins que d'un calcul de parité paire. En effet, si on additionne N bits, le bit de poids faible vaut zéro pour un nombre pair, et 1 pour un nombre impair. Cette fameuse addition se résume donc en un simple calcul de parité.

Le circuit combinatoire chargé de calculer le bit de résultat est donc un circuit qui calcule la parité de la somme des bits choisis. Pour cela, il suffit d'effectuer une série de XOR entre tous les bits à additionner. Ce qui fait que ce circuit combinatoire est presque toujours composé de portes XOR.

C'est aussi simple que cela, notre circuit est composé de deux parties :

• un registre à décalage ;
• couplé à un circuit combinatoire composé de portes XOR.

Ce circuit ne paye pas de mine, aussi il vaut mieux regarder celui-ci en fonctionnement :

Il existe une variante de ce genre de registre, qui modifie légèrement son fonctionnement. Il s'agit des registres à décalage à rétroaction affine. Avec ces registres, la fonction qui calcule le bit de résultat n'est pas linéaire, mais affine. En clair, ce bit de sortie se calcule par une formule du style :

kitxmlcodelatexdvp0 * a3 + 1 * a2 + 1 * a1 + 0 * a0 + 1finkitxmlcodelatexdvp

Notez le + 1 à la fin de la formule : c'est la seule différence.

Avec ce genre de registre, le bit de résultat est donc calculé en faisant le calcul d'un bit d'imparité de certains (ou de la totalité) des bits du registre. Un tel circuit est donc composé de portes NXOR, comparé à son comparse linéaire, composé à partir de portes XOR.

Petite remarque : si je prends un registre à rétroaction linéaire dont la fonction est :

kitxmlcodelatexdvp0 * a3 + 1 * a2 + 1 * a1 + 0 * a0finkitxmlcodelatexdvp

et un registre à rétroaction affine avec les mêmes coefficients sur les mêmes bits :

kitxmlcodelatexdvp( 0 * a3 + 1 * a2 + 1 * a1 + 0 * a0 ) + 1finkitxmlcodelatexdvp

le résultat du premier sera égal à l'inverse de l'autre.

II-A-2. Registre à décalage à rétroaction de Gallois▲

Comme je l'ai dit plus haut, il existe un deuxième type de registres à décalage à rétroaction : les registres à décalage à rétroaction de Gallois. Ceux-ci sont un peu l'inverse des registres à décalage à rétroaction de Fibonacci. Dans ces derniers, on prenait plusieurs bits du registre à décalage pour en déduire un seul bit.

Avec les registres à décalage à rétroaction de Gallois, c'est l'inverse :

• on prend le bit qui sort du nombre lors d'un décalage ;
• on en déduit plusieurs bits à partir d'un circuit combinatoire ;
• on fait rentrer ces bits à divers endroits bien choisis de notre registre à décalage.

Bien sûr, la fonction qui calcule les différents bits à partir du bit d'entrée conserve les mêmes propriétés que celles utilisées pour les registres à décalage à rétroaction linéaire : elle est affine ou linéaire, et se calcule avec uniquement des portes XOR pour les fonctions linéaires, ou NXOR pour les fonctions affines.

Ce genre de circuit donne un résultat assez proche de l'aléatoire. Mais il ne s'agit pas de « vrai » aléatoire. C'est un fait : on peut prédire ce qui va sortir d'un de ces registres. En effet, il existe un « théorème » qui nous dit que la sortie d'un tel registre finit par faire des cycles. Mais il n'y a pas besoin de sortir tout un théorème pour comprendre pourquoi un tel circuit finit fatalement par se répéter.

On remarque qu'un tel circuit est déterministe : pour le même résultat en entrée, il donnera toujours le même résultat en sortie. De plus, notre circuit est un registre de n bits : il peut donc compter de 0 à (2^n) - 1. Lors de son fonctionnement, notre circuit finira donc par repasser par une valeur qu'il aura déjà parcourue, vu que le nombre de valeurs possibles est fini. Une fois qu'il repassera par cette valeur, son fonctionnement se reproduira à l'identique comparé à son passage antérieur, vu que le circuit est déterministe.

Un tel registre finit donc par faire des cycles : tous les N cycles d'horloge, il effectuera un cycle. Ceci dit, si ce nombre N de cycles (sa période) est assez grand, le circuit donnera l'illusion de l'aléatoire. Son contenu semblera varier de manière totalement aléatoire, tant qu'on ne regarde pas durant longtemps. Il s'agit d'une approximation de l'aléatoire particulièrement bonne.

La période N dépend fortement de la fonction utilisée pour calculer le bit de sortie, des bits choisis, etc. Dans le meilleur des cas, le registre à décalage à rétroaction passera par presque toutes les kitxmlcodeinlinelatexdvp(2^n)finkitxmlcodeinlinelatexdvp valeurs que le registre peut prendre.

Si je dis presque toutes, c'est simplement qu'une valeur n'est pas possible : suivant le registre, le zéro ou sa valeur maximale sont interdits. Si un registre à rétroaction linéaire passe par zéro (ou sa valeur maximale), il y reste bloqué définitivement. Cela vient du fait que kitxmlcodeinlinelatexdvpx * An + Y * An-1 + \ldots + z * a0finkitxmlcodeinlinelatexdvp donne toujours zéro. Le même raisonnement peut être tenu pour les registres à rétroaction affine, sauf que cette fois-ci, le raisonnement ne marche qu'avec la valeur maximale stockable dans le registre.

Tout le challenge consiste donc à trouver quels sont les registres à rétroaction dont la période est maximale : ceux dont la période vaut kitxmlcodeinlinelatexdvp(2^n) - 1finkitxmlcodeinlinelatexdvp. Qu'on se rassure, quelle que soit la longueur du registre, il en existe au moins un : cela se prouve mathématiquement.

Et d'ailleurs, je ne résiste pas à vous donner quels bits choisir pour obtenir cette période maximale en fonction du nombre total de bits. Voici cette liste, pour des registres à décalage affine :

Les plus curieux pourront compléter cette liste en allant regarder ce lien.

Il n'y a pas vraiment de raison de changer une équipe qui gagne. Nos registres à décalage à rétroaction sont facilement prédictibles à cause de leur circuit combinatoire, qui calcule le bit à faire rentrer dans le registre : ce circuit est linéaire, ou affine. Pour rendre celui-ci plus imprévisible, on peut décider d'utiliser des circuits plus compliqués, non linéaires. La fonction appliquée au bit sur l'entrée est alors plus complexe, mais le jeu en vaut la chandelle.

Autre solution : prendre plusieurs registres à décalage à rétroaction linéaire et utiliser leurs résultats. Avec cette technique, plusieurs registres à décalage à rétroaction sont reliés à un circuit combinatoire non linéaire. Ce circuit prendra en entrée un (ou plusieurs) bit de chaque registre à décalage à rétroaction, et combinera ces bits pour fournir un bit de sortie. Un circuit conçu avec ce genre de méthode va fournir un bit à la fois. Les bits en sortie de ce circuit seront alors accumulés dans un registre à décalage normal, pour former un nombre aléatoire.

Problème : ces circuits ne sont pas totalement fiables. Ils peuvent produire plus de bits à 0 que de bits à 1, et des corrections sont nécessaires. Pour cela, ces circuits de production de nombres aléatoires sont souvent couplés à des circuits qui corrigent le flux de bits accumulés dans le registre pour l'« aléatoiriser ». Une solution consiste à simplement prendre plusieurs de ces circuits, et d'appliquer un XOR sur les bits fournis par ces circuits : on obtient alors un bit un peu moins biaisé, qu'on peut envoyer dans notre registre à décalage.

Il faut noter que seule une faible partie des bits de chaque registre à décalage est prise en compte par notre circuit combinatoire. Pratiquement, des circuits avec trop de bits en entrées sont difficilement concevables.

Une variante de cette technique consiste à prendre la totalité des bits d'un registre à décalage à rétroaction linéaire (ou affine), et à envoyer ces bits dans un circuit non linéaire. La différence, c'est que dans ce cas, tous les bits du registre sont pris en compte.

Ces deux solutions peuvent être améliorées avec une astuce assez simple. Il est possible de cadencer nos registres à décalage à rétroaction linéaire à des fréquences différentes. Ainsi, le résultat fourni par notre circuit combinatoire est encore plus aléatoire. Cette technique est utilisée dans les générateurs stop-and-go, alternating step, et à shrinking.

Dans le premier, on utilise trois registres à décalage à rétroaction linéaire. Le bit fourni par le premier va servir à choisir lequel de deux restants sera utilisé.

Dans le générateur stop-and-go, on utilise deux registres à décalage à rétroaction. Le premier est relié à l'entrée d'horloge du second. Le bit de sortie du second est utilisé comme résultat. Une technique similaire était utilisée dans les processeurs VIA C3, pour l'implémentation de leurs instructions cryptographiques.

Dans le shrinking generator, deux registres à décalage à rétroaction sont cadencés à des vitesses différentes. Si le bit de sortie du premier vaut 1, alors le bit de sortie du second est utilisé comme résultat. Par contre, si le bit de sortie du premier vaut 0, aucun bit n'est fourni en sortie, et le bit de sortie du second registre est oublié.

Première solution : utiliser un simple compteur qui s'incrémente à chaque cycle d'horloge. Si on a besoin d'un nombre aléatoire, il suffit d'aller lire le contenu de ce registre, et de l'utiliser directement comme résultat. Si suffisamment de temps s'écoule entre deux demandes, et que le temps entre deux demandes est irrégulier, le résultat semblera bien aléatoire.

Autre solution, un peu plus fiable : utiliser la dérive de l'horloge. La vérité va vous paraître choquante, mais c'est un fait : un signal d'horloge n'est jamais vraiment très précis. Une horloge censée tourner à 1 Ghz ne tournera pas en permanence à 1Ghz exactement. Le signal d'horloge sera soumis à des variations de quelques Khz, voire moins, qui changeront la fréquence de l'horloge.

Ces variations peuvent venir de variations aléatoires de température, des variations de tension, des perturbations électromagnétiques, ou à des phénomènes assez compliqués qui peuvent se produire dans tout circuit électrique (comme le shot noise).

L'idée consiste à prendre au moins deux horloges. On peut par exemple prendre deux horloges : une rapide, et une lente. On fait en sorte que la fréquence la plus élevée soit un multiple de l'autre. Par exemple, on peut choisir une fréquence de 1 Mhz et une autre de 100 Hz : la fréquence la plus grande est égale à 10 000 fois l'autre. La dérive d'horloge fera alors son œuvre : les deux horloges se désynchroniseront en permanence, et cette désynchronisation peut être utilisée pour produire des nombres aléatoires.

Par exemple, on peut compter le nombre de cycles d'horloge produit par l'horloge rapide durant une période de l'horloge lente. Si ce nombre est pair, on produit un bit aléatoire qui vaut 1 sur la sortie du circuit. Pour information, c'est exactement cette technique qui était utilisée dans l'Intel 82802 Firmware Hub.

Il existe d'autres solutions matérielles. Dans les solutions électroniques, il arrive souvent qu'on utilise le bruit thermique présent dans tous les circuits électroniques de l'univers. Tous nos circuits sont soumis à de microscopiques variations de température, dues à l'agitation thermique des atomes. Plus la température est élevée, plus les atomes qui composent les fils de nos circuits s'agitent. Vu que les particules d'un métal contiennent des charges électriques, ces vibrations font naître des variations de tension assez infimes. Il suffit d'amplifier ces variations pour obtenir un résultat capable de représenter un zéro ou un 1.

C'est sur ce principe que fonctionne le circuit présent dans les processeurs Intel modernes. Comme vous le savez peut-être déjà, les processeurs Intel Haswell contiennent un circuit capable de générer des nombres aléatoires. Ces processeurs incorporent des instructions capables de fournir des nombres aléatoires, instructions utilisant le fameux circuit que je viens de mentionner.