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

Les compteurs peuvent aussi être utilisés pour générer des nombres "aléatoires". Je dis aléatoires entre guillemets car ils ne sont pas vraiment aléatoires, mais s'en rapprochent suffisamment pour être considérés comme tels. Pour mettre en avant cela, on parle aussi de nombres "pseudo-aléatoires". De nombreuses situations demandent de générer des nombres pseudo-aléatoires. C'est très utile dans des applications cryptographiques, statistiques, mathématiques, dans les jeux vidéos, et j'en passe. L'aléatoire dans les jeux vidéos est un bon exemple : pas besoin d'un aléatoire de qualité, un simple algorithme pseudo-aléatoire suffit.

Dans certaines situations, il est nécessaire de générer des 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. Voyons comment faire.

Les registres à décalage à rétroaction

La première solution utilise 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, avec cependant quelques réserves. Un LSFR finira donc par repasser par une valeur qu'il aura déjà parcourue. Et une fois qu'il repasse par cette valeur, son fonctionnement se reproduira à l'identique comparé à son passage antérieur. Un LSFR ne produit donc pas de « vrai » aléatoire, mais ce n'est pas un problème si la période d'un cycle est assez grande. Il s'agit d'une approximation de l'aléatoire particulièrement bonne.

Nonlinear-combo-generator

Il est possible de 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. Nous l’appellerons l'accumulateur.

Exemple avec trois LSFR différents, de taille différentes : le bit envoyé à l'accumulateur est un XOR du bit sortant des trois LSFR.

Pour rendre le tout encore plus aléatoire, il est possible de cadencer les LSFR à des fréquences différentes. Cette technique est utilisée dans les générateurs stop-and-go, alternative step, et à shrinking.

• Dans le générateur alternative step, on utilise trois LSFR. Le premier commande un multiplexeur qui choisit la sortie parmi les deux restants.
• Dans le générateur stop-and-go, on utilise deux LSFR. Le premier est relié à l'entrée d'horloge du second et 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 LSFR 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, le bit de sortie du second registre est oublié.

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

Les LSFR 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 des moyens non-déterministes. Et 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 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 la plus simple utilise 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 son œuvre, les deux horloges seront très légèrement désynchronisées 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 , il vaut 0 si ce nombre est pair. 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 qui utilisent le bruit thermique. Tous les circuits électroniques de l'univers 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 métalliques des 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. Ce principe a été utilisé sur des anciens processeurs Intel qui géraient l'instruction RDRAND, une instruction qui produisait un nombre aléatoire.