Comprensione dei PRG: come possiamo espandere la casualità?

Question

Comprensione dei PRG: come possiamo espandere la casualità?

#1 da (7 voti)
#2 da (3 voti)

5

Mi sto un po 'confondendo con i PRG utilizzati in crittografia.

Fondamentalmente, un PRG è usato per espandere una sequenza casuale (principalmente una chiave) di lunghezza s a una lunghezza n > s , ancora con un aspetto casuale. Ora, anche se questo non è ovviamente possibile in senso matematico, l'idea è di ottenere una casualità ragionevole, nel senso che un distinguo efficiente non può distinguere la sequenza più ampia da quella casuale (quindi otteniamo la casualità in senso computazionale). La mia domanda è davvero?

Considera questo esempio:
Input: k: {0,1} ^ 2
PRG G: {0,1} ^ 2 - > {0,1} ^ 4
Output: k '= G (k): {0,1} ^ 4

Ciò significa che la nostra chiave iniziale può assumere 4 valori possibili. Sebbene la nostra chiave derivata copre un intervallo di 16 valori, può assumere solo 4 di questi 16 valori, poiché il PRG è deterministico. Quindi cosa mi impedisce di mappare le chiavi iniziali e le chiavi di uscita come un attacco? Sarei quindi in grado di ridurre lo spazio di ricerca da 16 a 4 valori. Quindi in pratica inverti l'espansione?

Vorrei ora sostenere che non otteniamo alcuna espansione della casualità, a patto che abbiamo memoria per memorizzare questi mapping. Dato che ci sono alcuni PRG che sono comunemente usati, questo fornirebbe un incentivo per i progetti collaborativi per mappare tutte o almeno parte delle chiavi per infrangere la sicurezza per molte applicazioni.

Sono certo che devo aver trovato qualcosa di sbagliato sopra, ma non riesco a capire dove si trova il mio errore. Potresti aiutarmi?

Grazie mille

random key-generation

posta Karl Hardr 20.07.2013 - 12:19

fonte

2 risposte

3

I would now argue that we do not achieve any expansion of randomness, as long as we have memory to store these mappings.

Sei corretto se ti aspetti solo un output a 4 bit dal tuo PRG.

Ricorda la definizione di un PRG sicuro - dati due input, uno veramente casuale e uno generato usando un PRG, non esistono avversari in grado di distinguere in modo efficiente tra i due.

Dato un PRG che può produrre un output di una lunghezza arbitraria di n bit, come è comune con i cipri di flusso, penso che stiate seriamente sottovalutando la quantità di memoria necessaria per mappare completamente tutti i possibili output di un PRG.

risposta data 20.07.2013 - 12:36

fonte

Leggi altre domande sui tag random key-generation

Strane richieste GET al mio server Web Apache? Crittografia delle intestazioni nella modalità tunnel IPsec

score 7 · Accepted Answer

Un PRNG crittograficamente sicuro inizia con uno stato iniziale (spesso chiamato "seme") che è sconosciuto all'attaccante. Possiamo considerare lo stato come una sequenza di bit n . Da quello stato, il PRNG funziona in modo deterministico e genera molti bit, lo stato interno viene aggiornato continuamente.

C'è un attacco generico che può essere teoricamente applicato a tutti i PRNG, che è chiamato "ricerca esaustiva" o "forza bruta": vale a dire, prova tutti i possibili valori per il seme, fino a quando una corrispondenza si trova con l'output osservato. Il costo di questo attacco è, in media, 2 ^n-1 "tentativi" (in media, devi provare metà dei possibili valori seme prima di colpire quello giusto ). Questo attacco generico viene ostacolato rendendo n abbastanza grande che 2 ^n-1 è un valore ridicolmente grande. I buoni algoritmi usano tradizionalmente n = 128 o più, che è abbastanza grande .

Naturalmente, con uno stato iniziale a 2 bit, la ricerca esauriente è molto veloce: sono possibili solo 4 valori di seme!

Quindi abbiamo bisogno di un grande stato iniziale. La parte difficile è quindi progettare un PRNG in modo tale che l'attacco generico sia anche l'attacco migliore; cioè che non esiste una "scorciatoia" usando la struttura PRNG che consente di potare in modo efficiente una grande percentuale di semi candidati senza provarli tutti. Questo è difficile e non è ben supportato dalla teoria matematica: matematicamente, non vi è alcuna prova che possa esistere un PRNG sicuro; quindi mettiamo insieme un sacco di "operazioni di scrambling" che mescolano i dati e speriamo per il meglio. Ancora più difficile è progettare una tale miscela in modo che il risultato non sia solo sicuro, ma anche veloce. Attualmente, il meglio che possiamo fare è avere alcuni crittografi che pensano molto in un progetto, e poi lo sottopongono a molti crittografi che cercano di romperlo per alcuni anni. I progetti sopravvissuti sono quindi considerati "probabilmente sicuri". Vedi il portfolio di eSTREAM per un tale sforzo.