Generatore di numeri pseudocasuali crittograficamente sicuro

Nella sicurezza informatica un generatore di numeri pseudocasuali crittograficamente sicuro (detto in genere CSPRNG da Cryptographically Secure Pseudo-random Number Generator) è un generatore di numeri pseudo-casuali le cui proprietà lo rendono adatto all'uso in crittografia.

Molti aspetti della crittografia richiedono numeri casuali, ad esempio:

• Generazione di chiavi
• Generazione di chiavi di sessione (detti nonce)
• salt casuali richiesti da alcuni schemi di firma, come ECDSA, RSASSA-PSS
• One-time pad

La "qualità" della casualità per queste applicazioni è varia. Per la generazione di un nonce può essere richiesta solo l'unicità del numero generato. Per la creazione di una chiave è richiesta una qualità maggiore. Nel caso di one-time pad, la garanzia che il testo crittografato non sia violabile dipende unicamente dal fatto che la sorgente casuale utilizzata sia totalmente impredicibile.

Idealmente la generazione di numeri casuali utilizza l'entropia ottenuta da un'altra sorgente, come un generatore di numeri casuali hardware o qualche processo impredicibile, anche se sono state trovate correlazioni inaspettate in processi di questo tipo. Da un punto di vista teorico la quantità di casualità — l'entropia — che può essere generata da un sistema è uguale all'entropia che è entrata nel sistema. Nella pratica però spesso sono necessari più numeri casuali di quelli che possono essere recuperati da una fonte di entropia. In questi casi vengono utilizzati i CSPRNG, che "spalmano" l'entropia su più bit.

Specifiche

Le specifiche richieste da un normale generatore di numeri pseudocasuali (PRNG) sono soddisfatte anche da un CSPRNG, ma non è vero l'inverso. Le specifiche soddisfatte da un CSPRNG si dividono in due gruppi: il primo è che abbiano buone proprietà statistiche (cioè che passino i test di casualità), il secondo è che resistano bene agli attacchi, anche nel caso in cui vengano scoperte parte delle variabili che dovrebbero rimanere segrete.

• Un CSPRNG deve soddisfare il "test del prossimo bit" (o next-bit test). Il test è il seguente: dati i primi k bit di una sequenza casuale non esiste alcun algoritmo eseguibile in tempo polinomiale che possa predire il bit k+1 con una probabilità di successo maggiore di ½. Andrew Yao ha dimostrato nel 1982 che un generatore casuale che passi il next-bit test passerà anche tutti gli altri test statistici di casualità eseguibili in tempo polinomiale.

• Un CSPRNG può dirsi tale se nel caso in cui parte o tutto lo stato interno del generatore è stato rilevato (o indovinato) sia impossibile ricostruire i bit casuali generati prima della scoperta. Inoltre se c'è una sorgente di entropia deve essere computazionalmente insostenibile usare la conoscenza dello stato per predirne i cambiamenti futuri.

Esempio: se il CSPRNG in considerazione produce output usando come fonte di entropia le cifre di π può essere casuale, essendo le cifre di π casuali, ma non soddisfa il next-bit test.

La maggior parte dei generatori di numeri pseudocasuali non sono utilizzabili come CSPRNG poiché, pur soddisfacendo i test statistici, non sono progettati per resistere ad attacchi matematici appositamente studiati.