Fonctionnement d'un ordinateur/Les circuits de génération d'aléatoire

De nombreuses situations demandent de générer des nombres totalement aléatoires. C'est très utile dans des applications cryptographiques, statistiques, mathématiques, dans les jeux vidéos, et j'en passe. Ces applications sont le plus souvent logicielles, et cette génération de nombres aléatoire s'effectue avec divers algorithmes plus ou moins efficaces. L'aléatoire dans les jeux vidéos en est un bon exemple : pas besoin d'un aléatoire de qualité, un simple algorithme logiciels suffit. Mais dans certaines situations, il arrive que l'on veuille créer ces nombres aléatoires de manière matérielle. Cela peut servir pour sélectionner une ligne de cache à remplacer lors d'un défaut de cache, pour implémenter des circuits cryptographiques, pour calculer la durée d'émission sur un bus Ethernet à la suite d'une collision, et j'en passe. Mais comment créer une suite de nombres aléatoires avec des circuits ? C'est le but de ce tutoriel de vous expliquer comment !

Les registres à décalage à rétroaction

La première solution consiste à utiliser des registres à décalages à rétroaction, aussi appelés Feedback Shift Registers, abréviés LSFR. Ce genre de circuit donne un résultat assez proche de l'aléatoire, mais on peut cependant remarquer qu'il ne s'agit pas de vrai aléatoire. En effet, 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, ce registre ne peut contenir qu'un nombre fini de valeurs, ce qui fait qu'il finira donc par repasser par une valeur qu'il aura déjà parcourue. Lors de son fonctionnement, le compteur 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. Un LSFR ne produit donc pas de « vrai » aléatoire, vu que la sortie d'un tel registre finit par faire des cycles. Ceci dit, si la période d'un cycle est assez grande, 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.

Nonlinear-combo-generator

Si les LSFR sont très intéressants, diverses techniques permettent d'améliorer le fonctionnement de ces registres à décalages à rétroaction. Par exemple, on peut décider d'utiliser des LSFR 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. 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. Cependant, les techniques les plus efficaces consistent à combiner plusieurs LSFR pour obtenir une meilleure approximation de l'aléatoire. Avec cette technique, plusieurs registres à décalages à 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 éviter cela. Pour cela, ces circuits de production de nombres aléatoires sont souvent couplés à des circuits qui corrigent le flux de bits accumulé 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. Pratiquement, des circuits avec trop de bits en entrées sont difficilement concevables.

Pour rendre le tout encore plus aléatoire, 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, alternative step, et à shrinking. Dans le premier, on utilise trois registres à décalages à 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é.

L'aléatoire généré par l'horloge

On vient de voir que les registres à décalage à rétroaction ne permettent pas d'obtenir du vrai aléatoire, compte tenu de leur comportement totalement déterministe. Pour obtenir un aléatoire un peu plus crédible, il est possible d'utiliser d'autres moyens qui ne sont pas aussi déterministes et surtout qui ne sont pas cycliques. Parmi ces moyens, certains d'entre eux utilisent le signal d'horloge. Par exemple, une technique très simple utilise un compteur incrémenté à chaque cycle d'horloge. Si on a besoin d'un nombre aléatoire, il suffit de lire le contenu de ce registre et de l'utiliser directement comme nombre aléatoire. Si le délai entre deux demandes est irrégulier, le résultat semblera bien aléatoire. Mais il s'agit là d'une technique assez peu fiable dans le monde réel et seules quelques applications bien spécifiques se satisfont de cette méthode.

Une solution un peu plus fiable utilise ce qu'on appelle la dérive de l'horloge. Il faut savoir qu'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, mais verra sa fréquence varier de quelques Hz ou Khz de manière irrégulière. 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 et d'utiliser la dérive des horloges pour les désynchroniser.

On peut par exemple prendre deux horloges : une horloge lente et une horloge rapide, dont la fréquence est 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 à 10000 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.

L'aléatoire généré par la tension d'alimentation

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 tensions 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.