Generare sequenze casuali con una data legge di probabilità e verificarne l'adeguatezza è uno dei problemi più importanti della moderna crittografia. I generatori di sequenze casuali vengono utilizzati nei sistemi crittografici esistenti per generare informazioni chiave e impostare una serie di parametri del sistema crittografico. Il significato scientifico e pratico di questo problema è così grande che ad esso sono dedicate monografie separate nel campo della crittografia, le sezioni sono organizzate nelle riviste scientifiche "Journal of Cryptology", "Cryptologia" e sessioni speciali in conferenze scientifiche internazionali "Eurocrypt" , "Asiacrypt", "Crypto" e così via.

All'inizio del XX secolo, le sequenze casuali venivano simulate utilizzando i più semplici esperimenti casuali: lancio di una moneta o di un dado, rimozione di palline da un'urna, disposizione delle carte, roulette, ecc. Nel 1927, L. Tippett pubblicò per la prima volta tabelle contenenti oltre 40.000 numeri casuali, "estratti arbitrariamente dai rapporti del censimento". Nel 1939, utilizzando un dispositivo meccanico appositamente progettato - un generatore di numeri casuali, M.J. Kendall e B. Babington-Smith crearono una tabella contenente 10 5 numeri casuali. Nel 1946, il matematico americano John von Neumann propose per la prima volta un algoritmo informatico per la generazione di numeri casuali. Nel 1955, la RAND Corporation pubblicò un foglio di calcolo molto popolare contenente 10 6 numeri casuali generati su un computer.

Attualmente, la domanda di generatori di sequenze casuali con date distribuzioni di probabilità, così come per le sequenze casuali stesse, è cresciuta così tanto che sono apparse all'estero società di ricerca e produzione, impegnate nella produzione e vendita di grandi matrici di numeri casuali. Ad esempio, dal 1996 è stato distribuito in tutto il mondo il CD "The Marsaglia random number CDROM", che contiene 4,8 miliardi di bit "veramente casuali".

La stragrande maggioranza dei moderni sistemi crittografici utilizza algoritmi a flusso oa blocchi basati su vari tipi di cifrari a sostituzione e permutazione. Sfortunatamente, quasi tutti gli algoritmi utilizzati nei crittosistemi di streaming, si sono concentrati sull'uso nei sistemi di comunicazione militari e governativi, nonché, in alcuni casi, per proteggere le informazioni di natura commerciale, il che le rende naturalmente segrete e inaccessibili per la conoscenza. Gli unici algoritmi standard per la crittografia del flusso simmetrico sono lo standard americano DES (modalità CFB e OFB) e lo standard russo GOST 28147-89 (modalità gamma).

Le basi del funzionamento dei crittosistemi di streaming sono generatori di sequenze casuali o pseudo-casuali. Consideriamo questo problema in modo più dettagliato.

2 Generatore di numeri pseudo-casuali

Le chiavi segrete sono alla base delle trasformazioni crittografiche, per le quali, secondo la regola di Kerkhoffs, la forza del crittosistema è determinata solo dalla segretezza della chiave. Per molto tempo, il problema principale della crittografia classica è stata la difficoltà di generare una chiave segreta. La simulazione fisica della casualità utilizzando fenomeni fisici come radiazioni o rumore di sparo in un tubo a vuoto è piuttosto complessa e costosa, e l'uso di sequenze di tasti e movimenti del mouse richiede uno sforzo da parte dell'utente e, inoltre, non fornisce processi casuali completamente veri. Pertanto, invece della modellazione fisica, vengono utilizzati metodi di modellazione matematica della casualità e della generazione di sequenze casuali sotto forma di programmi per computer o dispositivi specializzati.

Sebbene questi programmi e dispositivi siano chiamati generatori di numeri casuali, in realtà generano sequenze deterministiche che sembrano solo casuali nelle loro proprietà e sono quindi chiamate sequenze pseudo-casuali. Si richiede che, pur conoscendo la legge di formazione, ma non conoscendo la chiave nella forma delle date condizioni iniziali, nessuno sarebbe in grado di distinguere la sequenza generata da quella casuale, come se fosse ottenuta lanciando un dado ideale .

Generatore di numeri pseudo-casuali(PRNG, generatore di numeri pseudocasuali inglese, PRNG) - un algoritmo che genera una sequenza di numeri, i cui elementi sono quasi indipendenti l'uno dall'altro e obbediscono a una data distribuzione (solitamente uniforme).

Ci sono tre requisiti di base che i generatori crittografici pseudo-casuali o gamma devono soddisfare.

1. Il periodo gamma deve essere sufficientemente ampio da crittografare messaggi di varie lunghezze.

2. La gamma dovrebbe essere difficile da prevedere. Ciò significa che se il tipo di generatore e il blocco gamma sono noti, è impossibile prevedere il successivo bit gamma dopo questo blocco o il bit gamma che lo precede.

3. La generazione gamma non deve essere associata a grandi difficoltà tecniche e organizzative.

La caratteristica più importante di un generatore di numeri pseudo-casuali è la lunghezza informativa del suo periodo, dopo il quale i numeri si ripeteranno semplicemente o possono essere previsti. Questa lunghezza determina praticamente il numero possibile di chiavi nel crittosistema. Più lunga è questa lunghezza, più difficile è trovare la chiave.

Il secondo dei requisiti di cui sopra è legato al seguente problema: su quali basi si può concludere che la gamma di un particolare generatore sia davvero imprevedibile? Finora nel mondo non esistono criteri universali e praticamente verificabili per testare questa proprietà. Intuitivamente, la casualità è percepita come imprevedibilità. Perché una gamma sia considerata casuale e imprevedibile, è almeno necessario che il suo periodo sia molto lungo e che varie combinazioni di bit di una certa lunghezza siano equamente distribuite lungo tutta la sua lunghezza. Questo requisito può essere interpretato statisticamente come la complessità della legge di generazione di una sequenza pseudocasuale di numeri. Se questa legge di generazione non può essere determinata statisticamente o analiticamente da un segmento sufficientemente lungo di questa sequenza, allora in linea di principio può essere soddisfatta.

E, infine, il terzo requisito dovrebbe garantire la possibilità di implementazione pratica di generatori di sequenze pseudo-casuali, tenendo conto della velocità richiesta e della praticità dell'uso pratico. Diamo ora un'occhiata ad alcuni metodi pratici per ottenere numeri pseudo-casuali.

3 Metodi per ottenere numeri pseudo-casuali

Uno dei primi metodi di questo tipo fu il metodo proposto nel 1946 da D. von Neumann. Questo metodo si basava sul fatto che ogni numero successivo in una sequenza pseudo-casuale veniva formato elevando al quadrato il numero precedente e scartando le cifre da entrambe le estremità. Tuttavia, questo metodo si è rivelato inaffidabile ed è stato rapidamente abbandonato. Un altro metodo è il cosiddetto metodo congruente.

3.1 Metodo lineare congruente

Il metodo della congruenza lineare è uno degli algoritmi per la generazione di numeri pseudo-casuali. Viene utilizzato in casi semplici e non ha forza crittografica. È incluso nelle librerie standard di vari compilatori.

Questo algoritmo consiste nell'applicare in modo iterativo la seguente formula:

dove a> 0, c> 0, m> 0 sono alcune costanti intere. La sequenza risultante dipende dalla scelta del pettorale X 0 e per diversi valori di esso si ottengono diverse sequenze di numeri casuali. Allo stesso tempo, molte proprietà della sequenza X j sono determinati dalla scelta dei coefficienti nella formula e non dipendono dalla scelta del numero di partenza. È chiaro che la sequenza di numeri generata da tale algoritmo è periodica con un periodo non superiore m... In questo caso, la durata del periodo è m se e solo se:

· MCD (c, m) = 1 (cioè c e m sono coprimi);

· A - 1 multiplo di p per tutti i primi p - divisori di m;

A - 1 è un multiplo di 4 se m è un multiplo di 4.

Le proprietà statistiche della sequenza risultante di numeri casuali sono completamente determinate dalla scelta delle costanti un e C a una data profondità di bit e... Per queste costanti vengono scritte le condizioni che garantiscono la qualità soddisfacente dei numeri casuali ottenuti.

La tabella seguente elenca i parametri più comunemente usati per i generatori congruenziali lineari, in particolare nelle librerie standard di vari compilatori (la funzione rand()).

3.2 Metodo di Fibonacci

Un'interessante classe di generatori di sequenze pseudo-casuali si basa sull'uso delle sequenze di Fibonacci. Un classico esempio di tale sequenza (0,1,1,2,3,5,8,13,21,34 ...) - ad eccezione dei primi due dei suoi membri, ogni termine successivo è uguale al somma delle due precedenti.

Le peculiarità della distribuzione dei numeri casuali generati dall'algoritmo lineare congruente rendono impossibile utilizzarli in algoritmi statistici che richiedono alta risoluzione.

A questo proposito, l'algoritmo lineare congruente perse gradualmente la sua popolarità e il suo posto fu preso dalla famiglia di algoritmi di Fibonacci, che può essere raccomandato per l'uso in algoritmi critici per la qualità dei numeri casuali. Nella letteratura in lingua inglese, i sensori di Fibonacci di questo tipo sono generalmente chiamati "generatori di sottrazione con prestito" (SWBG).

Gli encoder Fibonacci più popolari sono dovuti al fatto che la velocità di esecuzione delle operazioni aritmetiche con i numeri reali è uguale alla velocità dell'aritmetica intera e gli encoder Fibonacci sono naturalmente implementati nell'aritmetica reale.

Uno dei sensori Fibonacci più diffusi si basa sulla seguente formula iterativa:

dove X k sono numeri reali dell'intervallo)