Vero generatore di numeri casuali [chiuso]

Question

Mi dispiace che questa non sia una domanda "reale", ma qualche tempo fa ricordo di aver visto un post qui sulla randomizzazione casuale di un randomizzatore per generare numeri veramente casuali, non solo pseudo casuali.Non lo vedo se lo cerco.

Qualcuno sa di quell'articolo?

Answer 1

Credo che fosse acceso thedailywtf.com - cioè.non qualcosa che vuoi fare.

Non è possibile ottenere un numero veramente casuale da numeri pseudocasuali, non importa quante volte chiami randomize().

Voi Potere ottieni numeri casuali "veri" da speciali hardware.Potresti anche raccogliere entropia dai movimenti del mouse e cose del genere.

Answer 2

Non sono d’accordo con molte delle risposte a questa domanda.

È possibile raccogliere dati casuali su un computer.SSL, SSH e VPN non sarebbero sicuri se non potessi.

Il modo in cui funziona il generatore di numeri casuali del software è che esiste un piscina di dati casuali raccolti da molti luoghi diversi, come la deriva del clock, i tempi di interruzione, ecc.

Il trucco di questi schemi sta nella stima corretta del entropia (il nome elegante per la casualità).Non importa se la fonte è distorta, purché si stimi correttamente l'entropia.

Per illustrare questo, la possibilità che io colpisca la lettera e in questo commento è molto superiore a quello di z , quindi se dovessi utilizzare gli interrupt chiave come fonte di entropia sarebbe un pregiudizio, ma c'è ancora una certa casualità in quell'input.Non puoi prevedere esattamente quale sequenza di lettere verrà dopo in questo paragrafo.Puoi estrarre entropia da questa incertezza e usarla come parte di un byte casuale.

Generatori casuali reali di buona qualità come Achillea hanno una stima dell'entropia piuttosto sofisticata incorporata e emetteranno solo tanti byte quanti può dire in modo affidabile di avere nel suo "pool di casualità".

Answer 3

Alla fine del post, risponderò alla tua domanda sul perché potresti voler utilizzare più generatori di numeri casuali per "più casualità".

Ci sono dibattiti filosofici su cosa significhi casualità.Qui intendo "indistinguibile sotto ogni aspetto da una distribuzione iid uniforme (0,1) sui campioni prelevati". Sto ignorando totalmente le domande filosofiche su cosa sia casuale.

Knuth nel volume 2 contiene un'analisi in cui tenta di creare un generatore di numeri casuali come suggerisci, quindi analizza il motivo per cui fallisce e quali sono i veri processi casuali.Il volume 2 esamina gli RNG in dettaglio.

Gli altri consigliano di utilizzare processi fisici casuali per generare numeri casuali.Tuttavia, come possiamo vedere nell’interazione Espo/vt, questi processi possono avere sottili elementi periodici e altri elementi non casuali, in parte dovuti a fattori esterni con comportamento deterministico.In generale, è meglio non dare mai per scontato la casualità, ma sempre testarla, e di solito puoi correggere tali artefatti se ne sei consapevole.

È possibile creare un flusso "infinito" di bit che appare del tutto casuale, in modo deterministico.Sfortunatamente, tali approcci aumentano la memoria con il numero di bit richiesti (come dovrebbero, per evitare cicli ripetitivi), quindi il loro ambito è limitato.

In pratica, è quasi sempre meglio utilizzare un generatore di numeri pseudo-casuali con proprietà note.I numeri chiave da cercare sono la dimensione dello spazio delle fasi (che è approssimativamente compensata tra campioni su cui puoi ancora contare su una distribuzione uniforme) e la larghezza di bit (il numero di bit in ciascun campione che sono uniformemente casuali l'uno rispetto all'altro ) e la dimensione del ciclo (il numero di campioni che è possibile prelevare prima che la distribuzione inizi a ripetersi).

Tuttavia, poiché i numeri casuali di un determinato generatore si trovano deterministicamente in una sequenza nota, la procedura potrebbe essere esposta da qualcuno che effettua una ricerca nel generatore e trova una sequenza di allineamento.Pertanto, è possibile evitare che la distribuzione venga immediatamente riconosciuta come proveniente da un particolare generatore di numeri casuali se si mantengono due generatori.Dal primo, si campiona i, quindi lo si mappa uniformemente da uno a n, dove n è al massimo la dimensione della fase.Quindi, nel secondo, campioni i volte e restituisci il i-esimo risultato.Ciò ridurrà la dimensione del ciclo a (dimensione del ciclo originale/n) nel caso peggiore, ma per quel ciclo genererà comunque numeri casuali uniformi e lo farà in un modo che rende esponenziale la ricerca dell'allineamento in n.Ridurrà anche la lunghezza della fase indipendente.Non utilizzare questo metodo se non si comprende il significato del ciclo ridotto e delle lunghezze di fase indipendenti per la propria applicazione.

Answer 4

Un algoritmo per numeri veramente casuali non può esistere come definizione di numeri casuali è:

Avere risultati imprevedibili e, nel caso ideale, tutti i risultati ugualmente probabili;risultante da tale selezione;priva di correlazione statistica.

Esistono generatori di numeri pseudocasuali (PRNG) migliori o peggiori, ad es.sequenze di numeri completamente prevedibili che sono difficili da prevedere senza conoscere un'informazione, chiamata il seme.

Ora, i PRNG di cui è estremamente difficile dedurre il seme lo sono crittograficamente sicuro.Potresti volerli cercare su Google se è quello che cerchi.

Un altro modo (se questo sia veramente casuale o meno è una questione filosofica) è utilizzare fonti di dati casuali.Ad esempio, quantità fisiche imprevedibili, come il rumore, o la misurazione del decadimento radioattivo.

Questi sono ancora soggetti ad attacchi perché possono essere misurati in modo indipendente, presentano pregiudizi e così via.Quindi è davvero complicato.Questo viene fatto con hardware personalizzato, che di solito è piuttosto costoso.Non ho idea di quanto sia buono /dev/random lo è, ma scommetto che non è abbastanza buono per la crittografia (la maggior parte dei programmi di crittografia viene fornita con il proprio RNG e Linux cerca anche un RNG hardware all'avvio).

Answer 5

Secondo Wikipedia /dev/random, nei sistemi operativi simili a Unix, è un file speciale che funge da vero generatore di numeri casuali.

Il driver /dev/random raccoglie il rumore ambientale da varie fonti non deterministiche incluse, ma non limitate a, le temporizzazioni tra tastiere e inter-interrupt che si verificano all'interno dell'ambiente del sistema operativo.I dati di rumore vengono campionati e combinati con una funzione di miscelazione simile a CRC in un "pool entropico" in continuo aggiornamento.Le stringhe di bit casuali si ottengono eseguendo un hash MD5 del contenuto di questo pool.La funzione hash unidirezionale distilla i veri bit casuali dai dati del pool e nasconde lo stato del pool agli avversari.

La routine /dev/random mantiene una stima della reale casualità nel pool e la diminuisce ogni volta che vengono richieste stringhe casuali per l'uso.Quando la stima scende a zero, la routine si blocca e attende il verificarsi di eventi non deterministici per aggiornare il pool.

Il modulo del kernel /dev/random fornisce anche un'altra interfaccia, /dev/urandom, che non attende che il pool di entropia si ricarichi e restituisce tutti i byte richiesti.Di conseguenza /dev/urandom è notevolmente più veloce nella generazione rispetto a /dev/random che viene utilizzato solo quando si desidera una casualità di altissima qualità.

Answer 6

John von Neumann una volta disse qualcosa del tipo "chiunque tenti di generare numeri casuali tramite mezzi algoritmici vive, ovviamente, nel peccato".

Nemmeno /dev/random è casuale, nel senso della parola matematico o fisico.Nemmeno la misurazione del decadimento dei radioisotopi è casuale.(Il tasso di decadimento è.La misurazione no.I contatori Geiger hanno un breve tempo di ripristino dopo ogni evento rilevato, durante il quale non sono in grado di rilevare nuovi eventi.Ciò porta a sottili pregiudizi.Esistono modi per mitigarlo sostanzialmente, ma non eliminarlo completamente.)

Smetti di cercare la vera casualità.Un buon generatore di numeri pseudocasuali è davvero quello che stai cercando.

Answer 7

Se credi in un universo deterministico, la vera casualità non esiste.:-) Ad esempio, qualcuno ha suggerito che il decadimento radioattivo lo sia veramente casuale, ma IMHO, solo perché gli scienziati non hanno ancora elaborato lo schema, non significa che non ci sia uno schema da elaborare.Di solito, quando si vogliono numeri "casuali", ciò di cui si ha bisogno sono numeri per la crittografia che nessun altro sarà in grado di indovinare.

Il massimo che puoi ottenere al casuale è misurare qualcosa di naturale che nessun nemico sarebbe in grado di misurare.Di solito si eliminano i bit più significativi dalla misurazione, lasciando i numeri con maggiori probabilità di essere distribuiti uniformemente.Gli utenti più irriducibili dei numeri casuali ottengono hardware speciale che misura gli eventi radioattivi, ma puoi ottenere un po' di casualità dall'essere umano che usa il computer da cose come gli intervalli di pressione dei tasti e i movimenti del mouse, e se il computer non ha utenti diretti, dai sensori di temperatura della CPU, e dal traffico di rete.Potresti anche usare cose come web cam e microfoni collegati a schede audio, ma non so se qualcuno lo fa.

Answer 8

Per riassumere parte di ciò che è stato detto, la nostra definizione operativa di cosa sia una fonte sicura di casualità è simile alla nostra definizione di crittografia sicura:appare casuale se persone intelligenti lo guardano e non sono in grado di dimostrare che non è completamente imprevedibile.

C'è NO sistema per generare numeri casuali che non potrebbero essere previsti, così come non esiste cifra crittografica che non possa essere violata.Le soluzioni affidabili utilizzate per lavori importanti sono semplicemente quelle che finora si sono rivelate difficili da sconfiggere.Se qualcuno ti dice il contrario, ti sta vendendo qualcosa.

L'intelligenza è raramente premiata nella crittografia.Scegli soluzioni provate e vere.

Answer 9

Un computer di solito ha molte fonti fisiche di rumore casuale facilmente disponibili:

• Microfono (si spera in un luogo rumoroso)
• Video compresso da una webcam (puntata su qualcosa di variabile, come una lampada lavica o una strada)
• Temporizzazione della tastiera e del mouse
• Contenuto e tempistica dei pacchetti di rete (contribuisce tutto il mondo)

E qualche volta

• Hardware basato sulla deriva dell'orologio
• Contatori Geiger e altri rilevatori di eventi rari
• Tutti i tipi di sensori collegati ai convertitori A/D

Ciò che è difficile è stimare l'entropia di queste fonti, che nella maggior parte dei casi è bassa nonostante l'elevata velocità di trasmissione dei dati e molto variabile;ma l’entropia può essere stimata con ipotesi prudenti, o almeno non sprecata, per alimentare sistemi come Yarrow o Fortuna.

Answer 10

Non è possibile ottenere numeri casuali "veri", un computer è un costrutto logico che non può creare nulla "veramente" casuale, solo pseudo-casuale.Tuttavia, esistono algoritmi pseudo-casuali migliori e peggiori.

Per ottenere un numero "veramente" casuale è necessaria una fonte fisica casuale, alcune macchine da gioco in realtà le hanno integrate - spesso si tratta di una fonte radioattiva, il decadimento radioattivo (che per quanto ne so è veramente casuale) viene utilizzato per generare i numeri.

Answer 11

Uno dei metodi migliori per generare un numero casuale è attraverso Deriva dell'orologio.Funziona principalmente con due oscillatori.

Un'analogia di come funziona è immaginare un'auto da corsa su un semplice circuito ovale con una linea while all'inizio del giro e anche una linea while su uno dei pneumatici.Quando l'auto completa un giro, verrà generato un numero in base alla differenza tra la posizione della linea bianca sulla strada e sul pneumatico.

Molto facile da generare e impossibile da prevedere.