Pseudo generatore casuale con lo stesso output

Question

Mi sono imbattuto in un articolo sul sistema di accesso remoto per auto all'indirizzo http: //auto.howstuffworks. com / remote-entry2.htm Nel terzo punto, l'autore dice,

  

Sia il trasmettitore che il ricevitore usano lo stesso generatore di numeri pseudo-casuali. Quando il trasmettitore invia un codice a 40 bit, utilizza il generatore di numeri pseudo-casuale per scegliere un nuovo codice, che memorizza in memoria. Dall'altro lato, quando il destinatario riceve un codice valido, usa lo stesso generatore di numeri pseudo-casuali per sceglierne uno nuovo. In questo modo, il trasmettitore e il ricevitore sono sincronizzati. Il ricevitore apre la porta solo se riceve il codice che si aspetta.

È possibile avere due funzioni PRNG che producono gli stessi numeri casuali contemporaneamente?

Answer 1

Nelle funzioni PRNG, l'output della funzione dipende da un valore 'seed', in modo tale che lo stesso output verrà fornito da chiamate successive dato lo stesso valore seed. Quindi sì.

Un esempio (usando C #) potrebbe essere qualcosa del tipo:

// 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());

Ciò dipende ovviamente dal generatore di numeri casuali che utilizza una sorta di formula deterministica per generare i suoi valori. Se si utilizza un cosiddetto generatore di numeri 'true random' che utilizza proprietà di entropia o rumore nella sua generazione, sarebbe molto difficile produrre gli stessi valori dati alcuni input, a meno che non si riesca a duplicare lo stato entropico per entrambi chiamano la funzione - che, naturalmente, vanificherebbe lo scopo di usare un tale generatore ...

Nel caso di sistemi di accesso remoto senza chiave, è molto probabile che utilizzino una funzione PRNG deterministica per sfruttare questa funzionalità. Esistono molti circuiti integrati che offrono questo tipo di funzionalità per produrre numeri casuali per circuiti elettronici.

Modifica: su richiesta, ecco un esempio di un generatore di numeri casuali non deterministico che non si basa su un valore seed specificato: Generatore di numeri casuali quantistici . Naturalmente, come sottolinea Freespace nei commenti, questo non è un generatore di numeri pseudocasuale, poiché genera numeri veramente casuali.

Answer 2

La maggior parte dei PRNG ha uno stato interno sotto forma di seme , che usano per generare i loro valori successivi. La logica interna va in questo modo:

nextNumber = function(seed);
seed = nextNumber;

Quindi ogni volta che generi un nuovo numero, il seme viene aggiornato. Se dai a due PRNG che usano lo stesso algoritmo lo stesso seed, function (seed) valuterà lo stesso numero (dato che sono deterministici, che la maggior parte lo sono).

Applicato direttamente alla tua domanda: il trasmettitore seleziona un codice e lo usa come seme. Il ricevitore, dopo averlo ricevuto, lo usa per seminare il suo generatore. Ora i due sono allineati e genereranno gli stessi valori.

Answer 3

Come hanno detto Erik e Claudiu, se si esegue il seeding del PRNG con lo stesso valore, si otterrà lo stesso output.

Un esempio può essere visto quando si utilizza AES (o qualsiasi altro algoritmo di crittografia) come base del PRNG. Fintanto che continui a utilizzare un input corrispondente su entrambi i dispositivi (trasmettitore e ricevitore), anche le uscite corrisponderanno.