Generatore di numeri pseudo-casuali. Generatori di numeri pseudo-casuali

PRNG deterministici

I PRNG (PRNG) sono generatori di numeri pseudo-casuali. Lo stesso termine è spesso usato per descrivere PRBG - generatori di bit pseudo-casuali, nonché vari cifrari a flusso. I PRNG, come i cifrari a flusso, consistono in uno stato interno (da 16 bit a diversi megabyte), una funzione per inizializzare lo stato interno con una chiave o semi, una funzione di aggiornamento dello stato interno e una funzione di output. I PRNG si dividono in aritmetica semplice, crittografica rotta e crittografica forte. Il loro scopo generale è generare sequenze di numeri che non possono essere distinti da quelli casuali.

Nessun algoritmo deterministico può generare numeri completamente casuali, ma solo approssimare alcune proprietà dei numeri casuali. Come detto, "Chiunque abbia un debole per i metodi aritmetici per ottenere numeri casuali è senza dubbio un peccatore".

Qualsiasi PRNG con risorse limitate prima o poi si blocca. La lunghezza dei cicli PRNG dipende dal generatore stesso e ha una media di circa 2 (n/2) dove n è la dimensione dello stato interno in bit, sebbene i generatori lineari-congruenti e i generatori LFSR abbiano cicli massimi dell'ordine di 2 n . Se un PRNG può convergere in cicli troppo brevi, quel PRNG diventa prevedibile e inutilizzabile.

I generatori aritmetici più semplici, sebbene veloci, soffrono di molte gravi carenze:

• Periodo/periodi troppo brevi
• I valori consecutivi non sono indipendenti
• Alcuni bit sono "meno casuali" di altri
• Distribuzione univariata non uniforme
• reversibilità

In particolare, l'algoritmo RANDU, utilizzato per decenni nei computer, si è rivelato molto scadente. Di conseguenza, molti studi sono meno affidabili di quanto potrebbero essere.

PRNG con sorgente di entropia o RNG

Insieme alla necessità esistente di generare sequenze di numeri casuali facilmente riproducibili, c'è anche la necessità di generare numeri completamente imprevedibili o semplicemente completamente casuali. Tali generatori sono chiamati "generatori di numeri casuali" (generatore di numeri casuali) o RNG in breve. Poiché tali generatori sono più spesso utilizzati per generare chiavi simmetriche e asimmetriche univoche per la crittografia, sono spesso costruiti da una combinazione di un PRNG crittograficamente forte e una fonte esterna. Pertanto, per RNG è ora consuetudine indicare PRNG resistenti alle criptovalute con una fonte esterna di entropia.

Quasi tutti i principali produttori di microchip forniscono RNG hardware con varie fonti di entropia, utilizzando vari metodi per eliminarli dall'inevitabile prevedibilità. Tuttavia, su questo momento la velocità di raccolta di numeri casuali da parte di tutti i microchip esistenti (diverse migliaia di bit al secondo) non corrisponde alla velocità dei moderni processori.

Nei personal computer, gli autori di software RNG utilizzano fonti di entropia molto più veloci, come il rumore della scheda audio o i valori del contatore di clock del processore che possono essere facilmente letti, ad esempio, utilizzando un'istruzione nei processori Intel. Prima della comparsa nei processori della capacità di leggere il valore del contacicli del processore più sensibile ai minimi cambiamenti nell'ambiente, la raccolta di entropia era il punto più vulnerabile dell'RNG. Questo problema non è ancora del tutto risolto in molti dispositivi (es. smart card), che restano così vulnerabili. Molti RNG utilizzano ancora metodi di raccolta dell'entropia tradizionali (obsoleti) come le azioni dell'utente (movimenti del mouse, ecc.), Come in e Achillea o interazione tra thread, come in Java secure random.

Ecco alcuni esempi di RNG con le loro sorgenti e generatori di entropia:

• /dev/casuale in / - source of entropy: , invece, viene raccolto solo durante gli interrupt hardware; PRNG: LFSR, con output hash tramite ; vantaggi: disponibile in tutti gli Unix, una fonte affidabile di entropia; svantaggi: si "scalda" per molto tempo, può "rimanere bloccato" per molto tempo o funziona come un PRNG ( /dev/casuale);
• Achillea da - fonte di entropia: metodi tradizionali (obsoleti); PRNG: AES-256 e piccolo stato interno; vantaggi: design flessibile e resistente alle criptovalute; svantaggi - si "riscalda" per molto tempo, uno stato interno molto piccolo, dipende troppo dalla forza crittografica degli algoritmi selezionati, è lento, è applicabile solo per la generazione di chiavi;
• Generatore da Leonid Yuriev (Leo Yuriev) - fonte di entropia: rumore della scheda audio; PRNG: non ancora noto; vantaggi: molto probabilmente una buona e veloce fonte di entropia; svantaggi: non esiste un PRNG indipendente, ovviamente resistente alle criptovalute, è disponibile solo come DLL per Windows;
• Microsoft CryptoAPI - fonte di entropia: ora corrente, dimensione del disco rigido, dimensione della memoria libera, ID processo e nome del computer NETBIOS; PRNG: hash di stato interno a 128 bit (hash disponibile solo nelle versioni a 128 bit di Windows); vantaggi - integrato in Windows, non "si blocca"; svantaggi: un piccolo stato interno, facilmente prevedibile;
• Java SecureRandom - fonte di entropia: interazione tra thread (thread); PRNG: hash di stato interno (1024 bit); vantaggi - in Java non c'è ancora altra scelta, un grande stato interno; svantaggi: raccolta lenta dell'entropia, sebbene in Java non ci sia ancora altra scelta;
• Caos da Ruptor - fonte di entropia: , viene raccolto continuamente; PRNG: hashing dello stato interno a 4096 bit basato sulla versione non lineare del generatore di Marsaglia; vantaggi: mentre il più veloce di tutti, grande stato interno, non "si blocca".

Hardware PRNG

A parte i noti generatori LFSR obsoleti che sono stati ampiamente utilizzati come PRNG hardware nel secolo scorso, sfortunatamente si sa molto poco sui moderni PRNG hardware (stream cipher), poiché la maggior parte di essi è sviluppata per scopi militari e viene tenuta segreta. Quasi tutti i PRNG hardware commerciali esistenti sono brevettati e anche tenuti segreti. I PRNG hardware sono limitati da requisiti rigorosi per il consumo di memoria (molto spesso, l'uso della memoria è vietato), velocità (1-2 cicli) e area (diverse centinaia di celle FPGA o ASIC). A causa di requisiti così severi per l'hardware PRNG, è molto difficile creare un generatore critto-resistente, quindi, fino ad ora, tutti i PRNG hardware noti sono stati interrotti. Esempi di tali generatori sono Toyocrypt e LILI-128, che sono entrambi generatori LFSR ed entrambi sono stati rotti utilizzando attacchi algebrici.

A causa della mancanza di buoni PRNG hardware, i produttori sono costretti a utilizzare cifrari a blocchi molto più lenti ma ampiamente conosciuti come AES e funzioni hash come

La prima tecnologia ampiamente utilizzata per generare un numero casuale è stata l'algoritmo proposto da Lehmer, noto come metodo congruente lineare. Questo algoritmo è parametrizzato da quattro numeri come segue:

La sequenza di numeri casuali (X n ) si ottiene utilizzando la seguente uguaglianza iterativa:

X n +1 = (a X n + c) mod m

Se m, a e c sono interi, viene creata una sequenza di interi nell'intervallo 0 X n< m.

La scelta dei valori per a, c e m è fondamentale per lo sviluppo di un buon generatore di numeri casuali.

Ovviamente, m deve essere molto grande per poter generare molti numeri casuali. Si ritiene che m debba essere approssimativamente uguale al massimo intero positivo per questo computer. Quindi, di solito m è vicino o uguale a 2 31 .

Ci sono tre criteri utilizzati quando si sceglie un generatore di numeri casuali:

1. La funzione deve creare un periodo intero, ovvero tutti i numeri compresi tra 0 e m prima che i numeri generati inizino a ripetersi.

2. La sequenza generata deve apparire in modo casuale. La sequenza non è casuale poiché è generata deterministicamente, ma vari test statistici che possono essere applicati dovrebbero dimostrare che la sequenza è casuale.

3. La funzione deve essere efficacemente implementata su processori a 32 bit.

I valori di a, c e m devono essere scelti in modo tale da soddisfare questi tre criteri. In accordo con il primo criterio, si può dimostrare che se m è primo e c = 0, allora per un certo valore di a, il periodo creato dalla funzione sarà uguale a m-1. Per l'aritmetica a 32 bit, il valore primo corrispondente è m = 2 31 - 1. Pertanto, la funzione per generare numeri pseudocasuali è:

X n +1 = (a X n) mod (2 31 - 1)

Solo un piccolo numero di valori di a soddisfa tutti e tre i criteri. Uno di questi valori è a = 7 5 = 16807, che è stato utilizzato nella famiglia di computer IBM 360. Questo generatore è ampiamente utilizzato e ha superato più di mille test, più di tutti gli altri generatori di numeri pseudo-casuali.

Il punto di forza dell'algoritmo congruente lineare è che se il fattore e il modulo (base) sono scelti correttamente, la sequenza di numeri risultante sarà statisticamente indistinguibile da una sequenza casuale dall'insieme 1, 2, ..., m- 1. Ma non può esserci casualità nella sequenza ottenuta utilizzando l'algoritmo, indipendentemente dalla scelta del valore iniziale X 0 . Se viene selezionato un valore, i numeri rimanenti nella sequenza saranno predefiniti. Questo è sempre preso in considerazione nella crittoanalisi.

Se l'avversario sa che viene utilizzato l'algoritmo congruente lineare e se i suoi parametri sono noti (a = 7 5 , c = 0, m = 2 31 - 1), allora se viene rivelato un numero, l'intera sequenza di numeri diventa nota . Anche se l'avversario sa solo che viene utilizzato l'algoritmo congruente lineare, conoscere una piccola parte della sequenza è sufficiente per determinare i parametri dell'algoritmo e tutti i numeri successivi. Supponiamo che il nemico possa determinare i valori di X 0 , X 1 , X 2 , X 3 . Quindi:

X 1 \u003d (a X 0 + c) mod mX 2 \u003d (a X 1 + c) mod mX 3 \u003d (a X 2 + c) mod m

Queste uguaglianze ci permettono di trovare a, c e m.

Pertanto, sebbene l'algoritmo sia un buon generatore di una sequenza di numeri pseudo-casuale, è auspicabile che la sequenza effettivamente utilizzata sia imprevedibile, poiché in questo caso la conoscenza di una parte della sequenza non consentirà di determinarne gli elementi futuri . Questo obiettivo può essere raggiunto in diversi modi. Ad esempio, utilizzando l'orologio di sistema interno per modificare il flusso di numeri casuali. Un modo per utilizzare l'orologio è riavviare la sequenza dopo N numeri, utilizzando il valore corrente modulo m dell'orologio come nuovo valore iniziale. Un altro modo è semplicemente aggiungere il valore del tempo corrente a ciascun numero casuale modulo m.

algoritmo per la generazione di numeri pseudocasuali, chiamato Algoritmo BBS(dai nomi degli autori - L. Blum, M. Blum, M. Shub) o generatore di resto quadratico. Ai fini della crittografia, questo metodo è stato proposto nel 1986.

È il seguente. Primo, due numeri primi grandi 1 Viene chiamato un intero positivo maggiore di uno semplice, se non è divisibile per un numero diverso da se stesso e uno. Per ulteriori informazioni sui numeri primi, vedere "I fondamenti della teoria dei numeri utilizzati nella crittografia a chiave pubblica". p e q numeri. I numeri p e q devono essere entrambi comparabile con 3 modulo 4, cioè dividendo p e q per 4 si ottiene lo stesso resto 3. Successivamente si calcola il numero M = p * q, detto intero di Bloom. Quindi si sceglie un altro intero casuale x, coprime (cioè non avendo divisori comuni diversi da uno) con M. Calcola x0= x 2 mod M . x 0 è chiamato il numero iniziale del generatore.

Ad ogni n-esimo passo del generatore si calcola x n+1 = x n 2 mod M. Il risultato dell'n-esimo passaggio è un bit (di solito il meno significativo) di x n+1 . A volte viene preso come risultato il bit di parità, ovvero il numero di unità nella rappresentazione binaria dell'elemento. Se il numero di unità nella voce del numero è pari - il bit di parità è considerato uguale a 0, dispari - il bit di parità è considerato 1.

Per esempio, sia p = 11, q = 19 (ci assicuriamo che 11 mod 4 = 3, 19 mod 4 = 3 ). Allora M = p* q = 11*19=209 . Scegliamo x coprime a M : sia x = 3 . Calcola il numero iniziale del generatore x 0:

x 0 = x 2 mod M = 3 2 mod 209 = 9 mod 209 = 9.

Calcola i primi dieci numeri x i usando l'algoritmo BBS. Prenderemo il bit meno significativo nella rappresentazione binaria del numero x i come bit casuali:

x 1 = 9 2 mod 209= 81 mod 209= 81	bit basso:	1
x 2 \u003d 81 2 mod 209 \u003d 6561 mod 209 \u003d 82	bit basso:	0
x 3 = 82 2 mod 209= 6724 mod 209= 36	bit basso:	0
x 4 = 36 2 mod 209= 1296 mod 209= 42	bit basso:	0
x 5 = 42 2 mod 209= 1764 mod 209= 92	bit basso:	0
x 6 = 92 2 mod 209= 8464 mod 209= 104	bit basso:	0
x 7 \u003d 104 2 mod 209 \u003d 10816 mod 209 \u003d 157	bit basso:	1
x 8 \u003d 157 2 mod 209 \u003d 24649 mod 209 \u003d 196	bit basso:	0
x 9 \u003d 196 2 mod 209 \u003d 38416 mod 209 \u003d 169	bit basso:	1
x 10 \u003d 169 2 mod 209 \u003d 28561 mod 209 \u003d 137	bit basso:	1

La proprietà più interessante di questo metodo ai fini pratici è che per ottenere l'ennesimo numero della successione non è necessario calcolare tutti i precedenti n numeri x i . Si scopre che x n può essere immediatamente ottenuto dalla formula

Ad esempio, calcoliamo x 10 immediatamente da x 0 :

Di conseguenza, abbiamo davvero ottenuto lo stesso valore del calcolo sequenziale, - 137 . I calcoli sembrano piuttosto complicati, ma in realtà sono facili da racchiudere in una piccola procedura o programma e utilizzarli quando necessario.

La possibilità di ottenere xn "direttamente" consente di utilizzare l'algoritmo BBS per la crittografia del flusso, ad esempio per file ad accesso casuale o frammenti di file con record di database.

La sicurezza dell'algoritmo BBS si basa sulla difficoltà di fattorizzare un numero elevato M. Si sostiene che se M è abbastanza grande, potrebbe non essere nemmeno tenuto segreto; fino a quando M non viene scomposto, nessuno può prevedere l'uscita del generatore di PRNG. Ciò è dovuto al fatto che il problema della fattorizzazione di numeri della forma n = pq (p e q sono numeri primi) in fattori è computazionalmente molto difficile se conosciamo solo n, e p e q sono numeri grandi costituiti da diverse decine o centinaia di bit (questo cosiddetto problema di fattorizzazione).

Inoltre, si può provare che un attaccante, conoscendo qualche sequenza generata dal generatore di BBS, non sarà in grado di determinare né i bit precedenti né quelli successivi. generatore di BBS imprevedibile nella direzione sinistra e nella giusta direzione. Questa proprietà è molto utile ai fini della crittografia ed è anche correlata alle peculiarità della fattorizzazione del numero M.

Lo svantaggio più significativo dell'algoritmo è che non è abbastanza veloce, il che non consente di utilizzarlo in molte aree, ad esempio nei calcoli in tempo reale e, sfortunatamente, in crittografia del flusso.

Ma questo algoritmo produce un'ottima sequenza di numeri pseudo-casuali con un periodo ampio (con un'opportuna scelta dei parametri iniziali), che ne consente l'utilizzo a fini crittografici durante la generazione di chiavi di crittografia.

Parole chiave

cifrario a flusso- cifrario a flusso.

Algoritmo BBSè uno dei metodi per generare numeri pseudo-casuali. Il nome dell'algoritmo deriva dai nomi degli autori: L. Blum, M. Blum, M. Shub. L'algoritmo può essere utilizzato in crittografia. Per calcolare il numero successivo x n+1 secondo l'algoritmo BBS, viene utilizzata la formula x n+1 \u003d x n 2 mod M, dove M \u003d pq è il prodotto di due grandi numeri primi p e q.

Generatore di numeri pseudocasuali (PRNG)- qualche algoritmo o dispositivo che crea una sequenza di bit che sembra casuale.

Generatore lineare congruente numeri pseudo-casuali è uno dei PRNG più semplici, che usa la formula k i =(a*k i-1 +b)mod c per calcolare il numero successivo k i , dove a, b, c sono delle costanti, a k i-1 è il precedente numero pseudocasuale.

Metodo di Fibonacci con ritardiè uno dei metodi per generare numeri pseudo-casuali. Può essere utilizzato in crittografia.

Cifra a flussoè una cifra che crittografa il messaggio di input un bit (o byte) per operazione. L'algoritmo di crittografia in linea elimina la necessità di dividere il messaggio in un numero intero di blocchi. I cifrari a flusso vengono utilizzati per crittografare i dati in tempo reale.

Breve sintesi

Un codice di flusso è un codice che crittografa il messaggio di input un bit (o byte) per operazione. L'algoritmo di crittografia in linea elimina la necessità di dividere il messaggio in un numero intero di blocchi. Pertanto, se viene trasmesso un flusso di caratteri, ogni carattere può essere crittografato e trasmesso contemporaneamente. I cifrari a flusso vengono utilizzati per crittografare i dati in tempo reale.

Nei programmi per computer, è spesso necessario emulare la casualità. Ad esempio, durante lo sviluppo di giochi. Se il programma ha un determinato generatore, cioè un produttore, di un numero casuale, allora, usando il numero così ottenuto, si può scegliere uno o un altro ramo di esecuzione del programma, oppure un oggetto arbitrario dalla collezione. In altre parole, la cosa principale è generare un numero. L'emulazione della casualità di tipo diverso si basa su di essa.

Certamente non sappiamo se c'è un incidente in natura, o ci sembra solo a causa della conoscenza limitata della nostra conoscenza. Sappiamo solo che non esiste una vera casualità nella programmazione. Nessun posto dove prendere un numero arbitrario, non puoi programmarne l'aspetto dal nulla. Puoi solo creare un programma che, a seguito dell'applicazione di una formula complessa al "seme", produrrà un numero e ci sembrerà che questo numero sia casuale.

"Grano" è il dato iniziale per la formula. Può essere, ad esempio, il tempo di sistema in millisecondi, che cambia costantemente. Pertanto, il "grano" sarà costantemente diverso. Oppure il programmatore può impostarlo da solo.

Tale programma (in realtà un modulo o una funzione) è chiamato generatore di numeri pseudo-casuali. La libreria standard Python include il modulo random. Contiene molte funzioni relative all'emulazione della casualità (ad esempio, "mischiare" gli elementi di una sequenza) e non solo funzioni per generare numeri pseudo-casuali.

Questo tutorial tratterà le funzioni random(), randrange() e randint() dal modulo random. Si noti che il modulo random contiene la funzione random() con lo stesso nome. Succede.

Per accedere alle funzioni è necessario importare il modulo random:

>>> importa a caso

Oppure importa singole funzioni da esso:

>>> da importazione casuale random , randrange, randint

Funzioni per ottenere numeri interi "casuali" - randint() e randrange()

Le funzioni randint() e randrange() generano interi pseudo-casuali. Il primo è il più semplice e accetta sempre solo due argomenti: i limiti dell'intervallo di interi da cui viene selezionato qualsiasi numero:

>>> casuale .randint (0 , 10 ) 6

oppure (se sono state importate funzioni separate):

>>> randint(100 , 200 ) 110

Nel caso di randint(), entrambi i confini sono inclusi nell'intervallo, ovvero, nel linguaggio della matematica, il segmento è descritto come .

I numeri possono essere negativi:

>>> casuale .randint (-100 , 10 ) -83 >>> casuale .randint (-100 , -10 ) -38

Ma il primo numero deve essere sempre minore o almeno uguale al secondo. Cioè un<= b.

La funzione randrange() è più complicata. Può richiedere un argomento, due o anche tre. Se ne viene specificato solo uno, restituisce un numero casuale compreso tra 0 e l'argomento specificato. Inoltre, l'argomento stesso non è incluso nell'intervallo. Nel linguaggio della matematica, questo è