Fonction de nombre aléatoire Arduino. Utilisation d'un générateur de nombres aléatoires dans Arduino : fonctions Random et RandomSeed

Beaucoup de choses ont été écrites sur les générateurs de nombres aléatoires, mais presque toujours, lorsqu'il s'agit de mise en œuvre, il est implicite (ou explicitement déclaré) que nous parlons de x86/x64 et d'autres architectures « adultes ». En parallèle, les forums dédiés au développement de dispositifs sur microcontrôleurs regorgent de questions « comment puis-je générer un nombre aléatoire sur %controllername% ? De plus, l’éventail des réponses s’étend de « regarder Google/Wikipedia » à « utiliser la fonction standard ». Cette « fonction standard » n'existe pas toujours et convient à tous égards au développeur ; le plus souvent, c'est l'inverse : parfois les nombres sont loin d'être aléatoires, parfois la vitesse de fonctionnement est trop faible, ou encore parfois le code résultant ne fonctionne pas. s'intégrer dans la mémoire libre du tout.
Essayons de comprendre ce que sont les algorithmes de génération de nombres aléatoires, comment choisir le bon et, surtout, quelles sont les caractéristiques de la mise en œuvre de ces algorithmes sur les contrôleurs.

Évaluer le « caractère aléatoire »

Les applications du RNG peuvent être très différentes, des jouets à la cryptographie sérieuse. En conséquence, les exigences relatives au générateur varient également considérablement. Il existe des tests spéciaux pour évaluer la qualité (niveau de « caractère aléatoire ») du générateur. Voici les plus basiques d’entre eux :

• Test de fréquence. Consiste à compter le nombre de zéros et de uns dans une séquence de bits. Il devrait y avoir un nombre à peu près égal de uns et de zéros.
• Testez une séquence de bits identiques. Les lignes de bits identiques sont recherchées, comme 000...0 ou 111...1. La répartition des fréquences avec lesquelles se produisent les séries, en fonction de leur longueur, doit correspondre à cette répartition pour un signal véritablement aléatoire.
• Essai spectral. Une transformée de Fourier discrète est appliquée à la séquence originale. Le spectre résultant ne doit pas présenter de pics significatifs qui indiqueraient la présence de propriétés périodiques de la séquence.
• Test d'autocorrélation. La valeur de corrélation entre des copies de séquence décalées les unes par rapport aux autres est calculée. Le test vous permet de trouver des régions répétitives dans une séquence.

Il existe des kits spéciaux qui comprennent des dizaines de tests similaires :
NIST - utilisé dans le cadre du concours AES pour évaluer les algorithmes de chiffrement.
DIEHARD est l'un des ensembles les plus rigoureux qui existent.

Algorithmes PRNG

Toute séquence générée selon un algorithme strictement défini ne peut être considérée comme véritablement aléatoire, c'est pourquoi, lorsqu'on parle de générateurs algorithmiques, ils utilisent le terme pseudo-aléatoire sous-séquence. Tout générateur de nombres pseudo-aléatoires (PRNG) entrera en boucle tôt ou tard, l'autre problème est que ce « retard » peut arriver en quelques millisecondes, ou peut-être en quelques années. La durée du cycle dépend de la taille de l'état interne du générateur N (en fait, il s'agit de la quantité de mémoire nécessaire au générateur), et varie de 2 (N/2) à 2 N bits.
Une grande variété d'algorithmes PRNG ont été inventés, mais tous ne sont pas faciles à mettre en œuvre sur des microcontrôleurs. Nous sommes sévèrement limités en vitesse et en mémoire disponible ; de nombreux contrôleurs ne prennent pas en charge les véritables instructions arithmétiques ou même de multiplication. En gardant ces limitations à l’esprit, examinons quelques algorithmes bien connus.

Méthode congruente linéaire

Le membre suivant de la séquence est calculé à l'aide de la formule
X je+1 = (aX je + c) mod m
Nombre m définit la période maximale de la séquence, nombres entiers un Et c- des coefficients « magiques ». Nombre m Il est raisonnable de choisir égal à une puissance de deux ; dans ce cas, l'opération de conversion modulo se réduit à écarter les bits de poids fort. Afin d’obtenir la durée maximale, les conditions suivantes doivent être remplies :
- c et m doit être relativement premier,
- a-1 doit être un multiple p pour tous les facteurs premiers p Nombres m,
- Si m est un multiple de 4 (et dans notre cas ce sera un multiple), alors a-1 doit être un multiple de 4.
Il y a encore une subtilité : seuls les bits les plus significatifs de la variable d'état X doivent être pris comme résultat, car pour les bits les plus bas, les paramètres statistiques du hasard sont bien pires. L'algorithme de congruence linéaire est couramment implémenté en tant que rand() standard dans de nombreuses bibliothèques.

Avantages:

• la période maximale possible pour une taille donnée de la variable d'état ;
• assez rapide;
• souvent déjà implémenté dans la bibliothèque du compilateur.

Inconvénients :

• une opération de multiplication est nécessaire ;
• tous les bits ne sont pas également aléatoires.

Résumé: un algorithme simple et rapide pour des applications peu exigeantes.

Méthode de Fibonacci avec décalages

Cet algorithme utilise la relation
X je = X i-a - X i-b ,
où est la variable d'état X- entier non signé. Valeurs de retard un Et b pas n'importe lesquels, mais ceux strictement définis sont pris ; pour obtenir une qualité maximale, les paires (17,5), (55,24) ou (97,33) sont recommandées. Plus le retard est grand, plus la période est longue et meilleures sont les propriétés spectrales de la séquence. En revanche, pour que le générateur fonctionne, il est nécessaire de stocker max(a,b) des nombres précédents, ce qui n'est pas toujours acceptable. De plus, pour exécuter le générateur, vous avez besoin de nombres max(a,b), qui sont généralement obtenus à l'aide d'un PRNG plus simple.

Avantages:

• ne nécessite pas d'opérations de multiplication ;
• tous les bits d'un nombre aléatoire sont équivalents en propriétés statistiques.

Inconvénients :

• nécessite une grande quantité de mémoire ;
• nécessite un large éventail de nombres pour s'exécuter.

Résumé: un algorithme de très haute qualité, mais gourmand en ressources.

Registre à décalage à rétroaction linéaire

La variable d'état est stockée dans un registre de longueur N. La génération de l'état suivant implique deux étapes :

1. La valeur du bit est calculée C = X i1 xor X i2 xor… X ik, où i1, i2…ik- enregistrer les numéros de bits, appelés virages.
2. Le registre est décalé d'1 bit vers la droite, le bit le plus à gauche prend la valeur AVEC.

La sortie du générateur est le bit le plus à droite (ou le plus à gauche, ou autre) du registre, c'est-à-dire que la séquence pseudo-aléatoire est générée un bit par itération. Avec des numéros de prise correctement sélectionnés, la période du générateur sera de 2 N - 1. « Moins un », car il existe un état zéro interdit du registre. Numéros de succursales pour N de 3 à 168 se trouvent dans ce document.
En plus de la configuration décrite ci-dessus, qui d'ailleurs s'appelle la configuration de Fibonacci (à ne pas confondre avec la méthode PRNG du même nom !), il existe ce qu'on appelle. Configuration galoise.


Au lieu d'utiliser la somme des bits de la séquence de prises pour générer un nouveau bit le plus à gauche, il effectue un XOR de chaque bit de la séquence de prises avec le bit le plus à droite, puis fait pivoter l'ensemble du registre vers la droite. Ce schéma est plus difficile à comprendre, mais plus facile à mettre en œuvre, puisque toutes les opérations XOR peuvent être effectuées simultanément. En termes de durée de période et de qualité des nombres pseudo-aléatoires, les schémas de Fibonacci et de Galois sont équivalents.

Avantages:

• implémentation très simple, ne nécessite même pas d'arithmétique, seulement des opérations et des décalages sur les bits ;
• algorithme très rapide (notamment le schéma de Galois) ;
• bonnes propriétés statistiques.

Inconvénients :

• vous devez vérifier la valeur initiale de l'inégalité à zéro.

Résumé: algorithme très rapide et d'assez bonne qualité.

Algorithmes cryptoprouvés

Pour une utilisation en cryptographie, les PRNG ont une autre exigence essentielle : irréversibilité. Tous les algorithmes listés ci-dessus n'ont pas cette propriété : connaissant plusieurs valeurs de sortie du PRNG, vous pouvez, en résolvant un système d'équations simple, retrouver les paramètres de l'algorithme (les mêmes constantes « magiques » une, b, c etc). Et connaissant les paramètres, vous pouvez reproduire l'intégralité de la séquence pseudo-aléatoire.
Tout chiffrement par bloc suffisamment puissant peut être utilisé comme algorithme PRNG cryptographiquement fort. En choisissant une clé secrète, vous pouvez obtenir des blocs de nombres pseudo-aléatoires en appliquant l'algorithme à des nombres naturels séquentiels. Pour un chiffrement par bloc de N bits, la période ne dépassera pas 2 N. La sécurité d'un tel système dépend entièrement du secret de la clé.
Tous les algorithmes cryptographiques modernes sont testés pour être utilisés en tant que PRNG, c'est-à-dire qu'en utilisant un algorithme certifié, il n'est pas nécessaire de se soucier particulièrement des propriétés statistiques et spectrales du flux de sortie. Vous n’avez qu’à vous soucier de la « gourmandise » informatique des algorithmes de cryptographie. Si vous devez effectuer un grand nombre d'opérations de chiffrement, il est judicieux de choisir un contrôleur doté de blocs cryptographiques matériels. Souvent, ces contrôleurs disposent également d’un très bon PRNG matériel crypto-résistant.

Sources d'entropie

Comme déjà indiqué, en utilisant uniquement des algorithmes déterministes, il est impossible de générer un nombre véritablement aléatoire. Par conséquent, une combinaison de PRNG + externe est généralement utilisée source d'entropie. La source d’entropie est utilisée pour définir la valeur initiale du PRNG, et la tâche de ce dernier est d’assurer la pureté spectrale et statistique de la séquence. Que peut-on utiliser comme source d’entropie ? Oui, presque n'importe quoi.

Activité de l'utilisateur

Si l'appareil interagit avec l'utilisateur de quelque manière que ce soit, une très bonne solution serait d'utiliser l'utilisateur lui-même comme source d'entropie. Par exemple, le temps d'appui sur un bouton, mesuré avec une précision d'une microseconde (ou plutôt ses chiffres les moins significatifs), est totalement imprévisible. Cependant, l’appareil doit souvent fonctionner de manière autonome, ce qui nous prive de ce merveilleux canal d’information.

Convertisseur analogique-numérique

De nombreux contrôleurs ont des CAN intégrés. Et dans de nombreux contrôleurs, ils sont de qualité très médiocre, faits juste pour « être ». Les bits de poids faible du résultat ADC contiennent presque toujours un bruit important, même lors de la mesure de la tension continue. Cela peut être utilisé : connectez l'entrée ADC à la tension d'alimentation via un diviseur, prenez quelques dizaines de mesures, prenez les bits les moins significatifs - vous avez ici un grand nombre aléatoire. Si l'ADC contient un préampli intégré, allumez-le, il est également bruyant.

Générateurs asynchrones

Vous pouvez utiliser la différence de périodes de deux générateurs d'horloge non synchronisés. La plupart des contrôleurs contiennent, par exemple, une minuterie de surveillance. Pour augmenter la fiabilité, il est cadencé à partir d'un générateur séparé, qui n'est en aucun cas connecté au signal d'horloge principal. Il suffit de compter le nombre de cycles du signal d'horloge principal pendant une période du temporisateur de surveillance. Si vous choisissez des périodes pour que le compteur déborde plusieurs fois pendant la mesure, vous pouvez obtenir un nombre assez aléatoire. L'inconvénient de cette méthode est qu'elle prend beaucoup de temps, jusqu'à plusieurs secondes.

Horloge en temps réel

Si le diagramme a horloge en temps réel, vous pouvez utiliser leurs lectures actuelles pour initialiser le PRNG. Par exemple, en convertissant la date/heure actuelle au format d'heure Unix, nous obtenons immédiatement 32 bits, ce qui jamais ne se reproduira plus à moins que vous ne preniez des lectures plus d'une fois par seconde. L'utilisation du temps réel fournit des valeurs uniques, mais n'apporte aucune imprévisibilité, il est donc préférable de combiner cette méthode avec d'autres.

Circuit RC

Si le contrôleur ne dispose pas de périphériques autres que les ports E/S, vous pouvez procéder comme suit : l'une des pattes est connectée via un condensateur à la masse et via une résistance à la tension d'alimentation. Si les entrées du contrôleur ont des résistances de rappel internes, une résistance externe n'est pas nécessaire.

Nous émettons un signal « 0 » sur ce port - le condensateur est déchargé. Nous passons le port en mode d'entrée - le condensateur commence à se charger. Lorsque la tension à ses bornes atteint le seuil, l'entrée passe de l'état « 0 » à « 1 ». Le temps de charge dépend fortement de nombreux facteurs : tension d'alimentation, dérive des paramètres du circuit RC, instabilité du seuil, température, fuites, interférences. En le mesurant avec suffisamment de précision et en prenant les bits les moins significatifs, vous pouvez obtenir un bon caractère aléatoire.

Générateur de bruit matériel

Pour de nombreuses applications sérieuses (notamment la cryptographie), une source d'entropie plus fiable que celles répertoriées ci-dessus est requise. Dans de tels cas, ils utilisent la numérisation du signal issu d'un générateur de bruit basé sur des effets thermiques, de tir, voire quantiques. L'élément de bruit est généralement une diode spéciale ou une diode Zener, dont le signal est amplifié et transmis à un comparateur qui génère un flux binaire binaire.

Pour garantir que le seuil de réponse du comparateur n'affecte pas les propriétés statistiques du signal reçu, deux générateurs de bruit sont utilisés, fonctionnant sur un comparateur :

Conclusion

Enfin, je vais vous raconter une histoire de ma vie. Tout a commencé avec une autre question posée sur le forum : « comment puis-je générer un nombre aléatoire sur la manette ? L'auteur de la question a expliqué que, dans le cadre d'un projet de cours, il fabrique un appareil qui émule le lancer de dés. Après plusieurs tentatives infructueuses pour comprendre les algorithmes, l'auteur du sujet a partagé sa solution : il a simplement lancé un vrai dé 1000 fois et a rempli toute la mémoire libre du contrôleur avec les nombres résultants. Le générateur a brillamment passé tous les tests de « hasard », étant donné que lors de la démonstration il a utilisé moins d'un tiers de sa « réserve ».
Par conséquent, une telle solution a également droit à la vie, surtout si des exigences très strictes sont imposées concernant le caractère aléatoire des nombres, mais elles ne sont pas exigées trop souvent. Avec la chute des prix de la mémoire, il peut être judicieux d'équiper un appareil d'une « réserve de chaos » qui durera toute la durée de vie de l'appareil.
Merci de votre attention!

MISE À JOUR1 : Comme cela a été noté à juste titre dans les commentaires, si une attaque est prévue sur le RNG et que l'attaquant a un accès matériel à l'appareil, les sources externes d'entropie doivent être utilisées avec une grande prudence, car il n'est pas très difficile de remplacer le signal d'un source externe. Des sources internes doivent être utilisées, en plus des sources externes.
C'est également une bonne idée d'accumuler de l'entropie pendant tout votre temps libre et de l'utiliser lorsque vous avez besoin de générer le prochain nombre aléatoire. Habituellement, dans de tels cas, ce qu'on appelle Piscine d'entropie- un tableau sur lequel l'une des fonctions PRNG est exécutée périodiquement, et dans lequel les données provenant des sources d'entropie sont constamment mélangées.

UPD2 : Dans de nombreux cas, il est utile de sauvegarder le contenu du pool d'entropie (désolé, je ne connais pas la traduction russe normale) dans l'EEPROM afin qu'après avoir éteint et rallumé l'appareil, il ne l'accumule plus. Il s'agit tout d'abord de l'obtention de l'entropie par la méthode des générateurs asynchrones : dans des conditions suffisamment stables, la même séquence peut être générée après chaque mise sous tension.
Si une attaque est attendue, prenez des précautions contre la falsification de l'EEPROM. Si le contrôleur le permet, bloquez la lecture/effacement/écriture à l'aide de bits de verrouillage, et lors de la mise sous tension, surveillez l'intégrité de l'EEPROM, au moins en utilisant de simples sommes de contrôle.

Mots clés:

• RNG
• gpsch
• microcontrôleurs
• algorithmes

Ajouter des balises

Lors de la programmation d'un Arduino, il arrive parfois que vous ayez besoin d'obtenir un numéro qui ne sera connu à l'avance ni du programmeur qui écrit le croquis, ni de l'utilisateur qui utilisera l'Arduino avec un tel programme. Dans ce cas, un générateur de nombres aléatoires (ou plutôt pseudo-aléatoires) vient à la rescousse.

Pour activer ce générateur, utilisez simplement les fonctions random() ou randomSeed(). Ce matériel vous montrera comment utiliser ces fonctions, ainsi que comment vous débarrasser du pseudo-aléatoire lors de la génération de nombres.

En général, un générateur de nombres pseudo-aléatoires simule l'apparition chaotique ou aléatoire de nombres, mais en fait, si vous analysez une série de ces nombres sur une période suffisamment longue, vous pouvez remarquer une certaine tendance.

Ainsi, la fonction aléatoire permettant de générer des nombres pseudo-aléatoires peut avoir jusqu'à deux paramètres et s'écrit random(max) ou random(min, max). Ici, le paramètre max, qui est obligatoire, fixe la limite supérieure de la plage de génération de nombres pseudo-aléatoires. À l'aide du paramètre min supplémentaire, vous pouvez définir la limite inférieure de la plage. En conséquence, la fonction renverra un nombre pseudo-aléatoire compris entre min et max-1.

Il est important de comprendre que lors de l’utilisation de la fonction random(), exactement la même liste de nombres pseudo-aléatoires sera générée à chaque fois. Par exemple, si vous créez une machine à sous et que la première fois que vous appuyez sur la poignée, elle affiche une combinaison gagnante, alors vous pouvez être sûr que si vous réinitialisez l'Arduino et appuyez à nouveau sur la poignée, cette machine à sous affichera la même combinaison gagnante. . En effet, il n'est pas facile d'implémenter une machine de jeu avec une génération de nombres complètement aléatoires sur Arduino, comme c'est par exemple le cas dans les machines de jeu www.igrovye-apparati-vulcan.com/, mais vous pouvez partiellement résoudre le problème en utilisant le randomSeed () fonction.

Cette fonction prend une valeur (comme un entier) et utilise le nombre pour modifier la liste aléatoire générée par la fonction random(). Vous pouvez mettre randomSeed() dans la fonction de configuration et utiliser la fonction random() de manière infinie. boucle. Mais même dans ce cas, le problème est que même si la séquence de nombres aléatoires sera différente lors de l'utilisation de la fonction randomSeed(), elle sera toujours la même à chaque fois que l'esquisse est exécutée.

La seule solution dans ce cas peut être d'utiliser des périphériques analogiques (ADC) et la fonction analogRead() correspondante. Si l'entrée analogique n'est connectée à rien, c'est-à-dire laissée « suspendue » en l'air, alors grâce au bruit sur cette ligne, vous pouvez obtenir des nombres vraiment aléatoires. Ensuite, dans les paramètres de configuration, vous pouvez écrire randomSeed(analogRead(A0)). À condition que le port analogique A0 ne soit connecté nulle part.

Temps et hasard. Réaction

Cette fois, nous apprendrons ce que sont les valeurs « aléatoires » et apprendrons également à travailler avec le temps.

Nous aurons besoin:

• Bouton tactile
• Couineur
• Fils de connexion «MALE-MALE»

Réaction

Notre tâche pour aujourd'hui est d'assembler un diagramme qui nous permet de connaître la vitesse de notre réaction.

Lorsque vous appuyez sur le bouton gauche, un signal retentit après un temps « aléatoire ». Et lorsque vous appuyez sur le bouton droit, il est noté combien de temps s'est écoulé entre le grincement et l'appui sur le bouton droit.

Ceux qui sont expérimentés l'essaient eux-mêmes et nous regardons le schéma.

#define BUZ 8 #define START 9 #define STOP 7 temps int; //Variable pour la synchronisation void setup() ( Serial.begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START) == 0) // Lorsque vous appuyez sur le bouton START.. ( int start_time = millis(); // Mémorisez l'heure d'appui sur time = start_time; // Écrivez-le dans une variable globale. int Rand = random (0, 4000 ); // Générons un temps de retard "aléatoire" = temps + Rand; //Ajoutez le temps de retard delay(Rand); //Attendez la tonalité(BUZ, 3000, 500); //Bip! ) if(digitalRead( STOP) == 0 && digitalRead( START) == 1) // Lorsque vous appuyez sur le bouton STOP... ( int stop_time = millis(); // Mémorisez l'heure d'arrêt. time = stop_time - time; // Calculez l'heure d'arrêt. décalage horaire. Serial.println("Time: "); // Sortie de l'heure sur Serial. Serial.println(time); delay(1000); ) ) // Avant la deuxième tentative, appuyez à nouveau sur le bouton START.

Explications

int temps; Les variables (pas toutes), lorsqu'elles sont désignées, ne doivent recevoir aucune valeur. Nous avons utilisé cette variable pour lier deux instructions if.

En C++, les variables déclarées dans une boucle ne seront pas accessibles dans les autres boucles, puisqu'elles n'ont d'effet que dans cette boucle. Ceci est fait pour éviter les erreurs de programmation. Lorsque le code du programme grandira, vous comprendrez de quoi je parle.

Pour rendre une variable disponible pour plusieurs instructions, vous devez la rendre globale. Ceux. déclarer une variable en dehors des fonctions.

millis(); Renvoie le nombre de millisecondes écoulées depuis le lancement du programme.

Nous en avons besoin pour mesurer le temps qui s'est écoulé entre le signal donné et l'appui sur le bouton.

aléatoire(min,maximum); Il s'agit d'un générateur de nombres aléatoires. Prend deux valeurs. Il génère un nombre compris entre le minimum et le maximum.

Nombres « aléatoires » car il s’agit d’une séquence spécifique de valeurs. Très long, mais pareil. Afin d'obtenir différentes séquences, vous devez utiliser AléatoireGraine();

Cette fonction initialise le générateur. Et si nous définissons le paramètre sur aléatoire, nous obtiendrons les séquences dont nous avons besoin. La séquence sera la même si le paramètre est fixe.

Conclusion

Vous pouvez désormais entraîner votre réaction à l'aide d'un appareil que vous avez fabriqué vous-même. Ou vous pouvez continuer à étudier davantage.

Liste des radioéléments

Désignation	Taper	Dénomination	Quantité	Note	Boutique	Mon bloc-notes
	Carte Arduino	Arduino Uno	1			Vers le bloc-notes
	Planche à pain	Demi-planche à pain	1			Vers le bloc-notes
	Émetteur piézo	Passif	1			Vers le bloc-notes
	Bouton tactile	Sans serrure	2			Vers le bloc-notes
	Fils de connexion	"Papa-Papa"	1