Wikilivres

« Fonctionnement d'un ordinateur/Les circuits de génération d'aléatoire » : différence entre les versions

Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
Ligne 9 :
===Combinaisons de LSFR===
 
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: 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. 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.
 
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é.
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é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==
Récupérée de « https://fr.wikibooks.org/wiki/Fonctionnement_d%27un_ordinateur/Les_circuits_de_génération_d%27aléatoire »