Dato un algoritmo RNG e una serie di numeri è possibile determinare quale seme produrrebbe la serie?

Question

Il codice è in Objective C ma dovrebbe essere comprensibile se lo si guarda anche se non si conosce l'obiettivo C. Fondamentalmente si tratta di un oggetto RNG, si istanzia una nuova istanza, si imposta il seed se lo si desidera e si inizia ad afferrare casualmente numeri.

Quindi è possibile tornare indietro di una determinata serie di numeri per determinare il seme utilizzato per generare i numeri? Suppongo che un dato algoritmo non possa generare solo un insieme casuale di numeri, o no?

Dire faccio la seguente:

rng.seed = 1024; 
for (int i=1; i<11; i++) 
    DLog(@"%lu", [rng randomBetween:0 and:10]); 

che mi dà la sequenza 10, 10, 8, 10, 2, 10, 9, 9, 7, 4. C'è un metodo o un algoritmo che potrei usare, data la sequenza, per ottenere il numero 1024? So che questa è la sequenza valida per il 1024 visto, ma in cosa consiste solo una sequenza ... 10, 1, 9, 6, 3, 9, 10, 3, 5, 2. C'è un modo per sapere se questa è una sequenza valida per questo algoritmo e, in caso affermativo, qual è il seme?

RNG.h:

@interface RNG : NSObject 
@property (assign) unsigned long seed; 
- (unsigned long)random; 
- (long)randomBetween: (long)min and: (long)max; 
@end 

RNG.m:

#define A 16807   /* a relatively prime number -- also M div Q */ 
#define M 2147483647L /* 0xFFFFFFFF/2 */ 
#define Q 127773L  /* M div A */ 
#define R 2836   /* M mod A */ 

@implementation RNG 
@synthesize seed = _seed; 

- (id)init { 
    self = [super init]; 
    if (self) { 
     self.seed = 0; 
    } 
    return self; 
} 


- (unsigned long)random { 
    self.seed = A * (self.seed % Q) - R * (self.seed/Q); 
    if (self.seed > M) 
     return (self.seed -= M); 
    else if (self.seed) 
     return (self.seed); 
    else 
     return (self.seed = 1L); 
} 


- (long)randomBetween: (long)min and: (long)max { 
    return ([self random] % (max - min + 1) + min); 
} 


- (void)seed: (unsigned long)new_seed { 
    if (new_seed == 0) 
     new_seed = 1; 
    while (new_seed > M) 
     new_seed -= M; 

    self.seed = new_seed; 
} 
@end 

Answer 1

Questo appare come un "generatore di congruenziale lineare", vedi http://en.wikipedia.org/wiki/Linear_congruential_generator "

Questi offrono nessuna buona sicurezza crittografica? quindi sì, dovrebbe essere possibile calcolare un seme che produce la sequenza

Answer 2

il codice che pubblichi è fondamentalmente lo stesso del openbsd srandom - è un generatore congruenziale lineare implementato per evitare l'arrotondamento (che è il motivo per cui contiene Q).

here is a paper on how to crack such a generator, ma si aspetta che l'intero output (non il valore "tra") sia disponibile.

Immagino che dovresti essere in grado di estendere l'approccio nella carta per lavorare con "tra" usando il modulo aritmetico del campo (presumibilmente avresti bisogno di più campioni).

Answer 3

La soluzione migliore è probabilmente creare un array (o un file su disco) che ha il primo valore restituito dall'algoritmo scelto per ciascun seme. Quindi passa attraverso quelli che corrispondono al primo valore cercando una corrispondenza più lunga. In effetti, una tabella di database sarebbe ottima - mi vengono in mente gdbm o bsddb o sqlite.

Questo mi sembra uno di quei problemi "È computabile, ma ...". IOW, può essere fatto, ma non è particolarmente carino.