Pseudo Random Generator avec même sortie

Question

Je suis tombé sur un article concernant le système d’entrée à distance pour voitures à l'adresse http: //auto.howstuffworks. com / remote-entry2.htm Dans la troisième puce, l'auteur dit:

  

L'émetteur et le récepteur utilisent le même générateur de nombres pseudo-aléatoires. Lorsque l'émetteur envoie un code de 40 bits, il utilise le générateur de nombres pseudo-aléatoires pour sélectionner un nouveau code, qu'il stocke en mémoire. À l’autre extrémité, lorsque le destinataire reçoit un code valide, il utilise le même générateur de nombre pseudo-aléatoire pour en choisir un nouveau. De cette façon, l'émetteur et le récepteur sont synchronisés. Le récepteur n’ouvre la porte que s’il reçoit le code attendu.

Est-il possible d'avoir deux fonctions PRNG produisant les mêmes nombres aléatoires au même moment?

Answer 1

Dans les fonctions PRNG, la sortie de la fonction dépend d’une valeur "d’origine", de sorte que la même sortie sera fournie à partir d’appels successifs ayant la même valeur d’origine. Alors oui.

Un exemple (en utilisant C #) serait quelque chose comme:

// Provide the same seed value for both generators:
System.Random r1 = new System.Random(1);
System.Random r2 = new System.Random(1);

// Will output 'True'
Console.WriteLine(r1.Next() == r2.Next());

Tout dépend naturellement du générateur de nombres aléatoires qui utilise une sorte de formule déterministe pour générer ses valeurs. Si vous utilisez un générateur de nombres dit 'véritablement aléatoire' qui utilise des propriétés d'entropie ou de bruit dans sa génération, il sera alors très difficile de produire les mêmes valeurs avec certaines entrées, à moins que vous ne puissiez dupliquer l'état entropique. les deux appels à la fonction - ce qui, bien sûr, irait à l'encontre de l'utilisation d'un tel générateur ...

Dans le cas des systèmes d'entrée sans clé à distance, ils utilisent très probablement une fonction PRNG déterministe afin de tirer parti de cette fonctionnalité. De nombreux circuits intégrés fournissent ce type de fonctionnalité pour produire des nombres aléatoires pour les circuits électroniques.

Éditer: sur demande, voici un exemple de générateur de nombres aléatoires non déterministe qui ne repose pas sur une valeur de départ spécifiée: Générateur de nombres aléatoires Quantum . Bien entendu, comme le souligne Freespace dans les commentaires, il ne s’agit pas d’un générateur de nombres pseudo-aléatoires, car il génère des nombres réellement aléatoires.

Answer 2

La plupart des PRNG ont un état interne sous la forme d'une graine , qu'ils utilisent pour générer leurs valeurs suivantes. La logique interne ressemble à ceci:

nextNumber = function(seed);
seed = nextNumber;

Ainsi, chaque fois que vous générez un nouveau numéro, la graine est mise à jour. Si vous donnez la même graine à deux PRNG utilisant le même algorithme, la fonction (graine) sera évaluée au même nombre (étant donné qu'ils sont déterministes, la plupart le sont).

Appliqué directement à votre question: le transmetteur sélectionne un code et l’utilise comme une graine. Le récepteur, après l'avoir reçu, l'utilise pour ensemencer son générateur. Maintenant, les deux sont alignés et généreront les mêmes valeurs.

Answer 3

Comme l'ont dit Erik et Claudiu, tant que vous semez votre PRNG avec la même valeur, vous obtenez le même résultat.

Vous pouvez voir un exemple en utilisant AES (ou tout autre algorithme de cryptage) comme base de votre PRNG. Tant que vous continuez à utiliser des entrées qui correspondent sur les deux appareils (émetteur et récepteur), les sorties correspondent également.