Mescola in modo sicuro la stringa grande

0

Ho una grande stringa che ho bisogno di mescolare in modo sicuro. Sarà di circa 4000 caratteri. La permutazione risultante di tale stringa, deve essere una nell'insieme di tutte le possibili permutazioni (4000!). Naturalmente anche le permutazioni risultanti devono essere equamente distribuite tra tutti gli stati possibili. Devo dimostrare ragionevolmente che la mia implementazione soddisfa quei requisiti, ma i metodi formali non sono necessari.

Stavo pensando di usare un semplice Knuth-Fisher-Yates per questo, ma mi preoccupo per il mio RNG. Sono obbligato ad implementarlo in JavaScript, poiché la mia applicazione deve essere eseguita in Thunderbird. Da (cosa posso leggere) [ link , Mozilla può fornire un valore casuale crittograficamente sicuro, e ho intenzione di combinarlo con questo [ link per ottenere numeri casuali nell'intervallo desiderato.

Ora, credo che potrei avere problemi con lo spazio interno dello stato del PRNG. Se ne ha poche, si "avvolge" e produce un pregiudizio per certi numeri. Se ne ha troppi, potrebbe applicare modulo per ridimensionare, producendo anche un bias per i numeri nella gamma inferiore.

Per quanto tempo ho bisogno di inizializzare un PRNG usato per KFY-Shuffle una stringa di 4000 caratteri? Sto pensando troppo a questo, c'è qualcosa a cui non ho pensato?

    
posta Andreas 05.10.2016 - 20:32
fonte

1 risposta

2

Now, I believe I could have issues with the internal state space of the PRNG. If it has to few, it will "wrap around" and produce a bias for certain numbers. If it has too many, it might apply modulo to scale down, thus also producing a bias for numbers in the lower range.

No, lo spazio di stato di un buon PRNG non lo farà apparire di parte nei modi che temete qui. Un buon RNG non crittografico produrrà risultati che appaiono imparziali e indipendenti da alcuni set di test statistici. Uno strumento crittograficamente sicuro, inoltre, produrrà risultati che sembrano imparziali e indipendenti a qualsiasi osservatore efficiente ; Ad esempio, non puoi scrivere un programma efficiente per distinguere la sua uscita da una sequenza veramente casuale.

How long a seed would I need to initialize a PRNG used for KFY-Shuffle a string of 4000 characters? Am I overthinking this, is there something I did not think of?

Il numero di permutazioni distinte di una sequenza di 4.000 elementi è 4.000! (fattoriale), che è qualcosa come 2^43000 , quindi tecnicamente hai bisogno di una stringa di 43.000 bit (5.263 byte) per poter indirizzare in modo univoco una tale permutazione.

Risposta pratica: basta usare un RNG crittografico. Anche se è improbabile che sia in grado di produrre tutte le permutazioni possibili anche quando viene alimentato con l'entropia esterna, la cosa importante è che nessun attaccante della vita reale sarà in grado di distinguere.

    
risposta data 05.10.2016 - 20:51
fonte

Leggi altre domande sui tag