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

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

Dans de nombreuses situations, il peut être utile de pouvoir générer des nombres totalement aléatoires. C'est très utile dans des applications cryptographiques, statistiques, mathématiques, 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. 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 cache miss, 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 !

Registres à décalage à rétroaction[modifier | modifier le wikicode]

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.

Exemple avec un registre à rétroaction linéaire de 4 bits.

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 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. La raison à cela est simple : un XOR sur des zéro donnera toujours 0. 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 chalenge consiste donc à trouver quels sont les registres à rétroaction dont la période est maximale : ceux dont la période vaut . Qu'on se rassure, quelle que soit la longueur du registre, il en existe au moins un : cela se prouve mathématiquement, même si nous ne vous donnerons pas la démonstration.

Combinaisons de LSFR[modifier | modifier le wikicode]

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, alternating 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é.

Vrai aléatoire[modifier | modifier le wikicode]

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 du vrai aléatoire, il existe des moyens pour obtenir de l'aléatoire un peu plus crédible. Certains de ces moyens utilisent l'horloge des circuits électronique.

Aléatoire généré par l'horloge[modifier | modifier le wikicode]

La première technique utilise 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 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 horloge 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.

Aléatoire généré par la tension d'alimentation[modifier | modifier le wikicode]

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.