Fonti entropiche alternative

StackOverflow https://stackoverflow.com/questions/300854

  •  08-07-2019
  •  | 
  •  

Domanda

Okay, immagino che sia del tutto soggettivo e quant'altro, ma stavo pensando alle fonti di entropia per i generatori di numeri casuali. Va che la maggior parte dei generatori sono seminati con l'ora corrente, giusto? Beh, ero curioso di sapere quali altre fonti potevano essere utilizzate per generare numeri casuali perfettamente validi (La definizione libera).

Usando più fonti (come il tempo + il tempo di ricerca dell'HDD corrente [Qui siamo fantastici]) creeremo insieme un "più casuale" numero di una singola fonte? Quali sono i limiti logici della quantità di fonti? Quanto è davvero abbastanza? Il tempo è scelto semplicemente perché è conveniente?

Mi scusi se questo genere di cose non è permesso, ma sono curioso di sapere la teoria alla base delle fonti.

È stato utile?

Soluzione

L'articolo di Wikipedia su Generatore di numeri casuali di hardware elenca un paio di fonti interessanti per numeri casuali usando Proprietà fisiche.

I miei preferiti:

  • Una sorgente di radiazioni a decadimento nucleare rilevata da un contatore Geiger collegato a un PC.
  • Fotoni che viaggiano attraverso uno specchio semitrasparente. Gli eventi reciprocamente esclusivi (riflessione & # 8212; trasmissione) vengono rilevati e associati a "0". o " 1 " valori di bit rispettivamente.
  • Disturbo termico da un resistore, amplificato per fornire una sorgente di tensione casuale.
  • Rumore di valanga generato da un diodo a valanga. (Che bello?)
  • Rumore atmosferico, rilevato da un ricevitore radio collegato a un PC

La sezione problemi dell'articolo Wikipedia descrive anche la fragilità di molti di questi sorgenti / sensori. I sensori producono quasi sempre numeri casualmente decrescenti man mano che invecchiano / degradano. Queste fonti fisiche dovrebbero essere costantemente controllate da test statistici in grado di analizzare i dati generati, assicurando che gli strumenti non si siano rotti silenziosamente.

Altri suggerimenti

SGI una volta usava le foto di una lampada di lava in varie "fasi glob". come fonte di entropia, che alla fine si è evoluta in un generatore di numeri casuali open source chiamato LavaRnd .

Uso Random.ORG , forniscono dati casuali gratuiti dal rumore atmosferico, che utilizzo per re-seminare periodicamente un Mersene-Twister RNG. È quasi casuale come puoi ottenere senza dipendenze hardware.

Non preoccuparti di un " buono " seme per un generatore di numeri casuali. Le proprietà statistiche della sequenza non dipendono da come viene eseguito il seeding del generatore. Ci sono altre cose, comunque. preoccuparsi di. Vedi Insidie ??nella generazione di numeri casuali .

Per quanto riguarda i generatori di numeri casuali hardware, è necessario misurare queste fonti fisiche e il processo di misurazione presenta errori sistematici. Potresti trovare " pseudo " numeri casuali di qualità superiore a "reale" numeri casuali.

Il kernel Linux utilizza il timing di interruzione del dispositivo (mouse, tastiera, dischi rigidi) per generare entropia. C'è un bel articolo su Wikipedia sull'entropia.

I RNG moderni sono entrambi controllati rispetto alle correlazioni nei semi vicini ed eseguono diverse centinaia di iterazioni dopo la semina. Quindi, la risposta purtroppo noiosa ma vera è che in realtà non importa molto.

In generale, utilizzando processi fisici casuali è necessario verificare che siano conformi a una distribuzione uniforme e che siano altrimenti penalizzati.

Secondo me, spesso è meglio usare un generatore di numeri pseudo-casuali molto ben compreso.

Ho usato un programma di crittografia che utilizzava il movimento del mouse dell'utente per generare numeri casuali. L'unico problema era che il programma doveva mettere in pausa e chiedere all'utente di spostare il mouse in modo casuale per alcuni secondi per funzionare correttamente, il che potrebbe non essere sempre pratico.

Ho trovato HotBits diversi anni fa - i numeri sono generati dal decadimento radioattivo, sinceramente numeri casuali.

Ci sono limiti al numero di numeri che puoi scaricare al giorno, ma mi sono sempre divertito a usarli come semi davvero, davvero casuali per RNG.

Alcuni TPM (Trusted Platform Module) " chips " avere un RNG hardware. Sfortunatamente, il TPM (Broadcom) nel mio laptop Dell non ha questa funzionalità, ma molti computer venduti oggi sono dotati di un RNG hardware che utilizza processi meccanici quantistici davvero imprevedibili. Intel ha implementato la varietà del rumore termico.

Inoltre, non utilizzare il solo tempo corrente per eseguire il seeding di un RNG a scopi crittografici o qualsiasi applicazione in cui l'imprevedibilità è importante. L'uso di alcuni bit di basso ordine del tempo insieme a diverse altre fonti probabilmente va bene.

Una domanda simile può esserti utile.

Mi spiace di essere in ritardo a questa discussione (che età ha 3 anni e mezzo adesso?), ma ho un interesse riacceso per la generazione di PRN e fonti alternative di entropia. Lo sviluppatore del kernel Linux Rusty Russell ha recentemente discusso sul suo blog su fonti alternative di entropia (altro di / dev / urandom ).

Ma non sono così colpito dalle sue scelte; l'indirizzo MAC di una scheda NIC non cambia mai (sebbene sia univoco rispetto a tutti gli altri) e il PID sembra una dimensione del campione troppo piccola.

Mi sono dilettato con un Mersenne Twister (sulla mia scatola di Linux) che è seminato con il seguente algoritmo. Chiedo eventuali commenti / feedback se qualcuno è disposto e interessato:

  1. Crea un buffer di array di 64 bit + 256 bit * numero di file / proc di seguito.
  2. Posiziona il valore del contatore timestamp (TSC) nei primi 64 bit di questo buffer.

  3. Per ciascuno dei seguenti file / proc , calcola la somma SHA256:

    • / proc / meminfo
    • / proc / self / mappe
    • / proc / self / smaps
    • / proc / interrupts
    • / proc / diskstats

    • / proc / self / stat

      Posiziona ciascun valore hash a 256 bit nella sua area dell'array creata in (1).

  4. Crea un hash SHA256 di questo intero buffer. NOTA: potrei (e probabilmente dovrei) usare una diversa funzione di hash completamente indipendente dalle funzioni SHA - questa tecnica è stata proposta come "salvaguardia". contro funzioni hash deboli.

Ora ho 256 bit di HOPEFULLY dati entropici casuali (sufficienti) per seminare il mio Mersenne Twister. Uso quanto sopra per popolare l'inizio dell'array MT (624 numeri interi a 32 bit), quindi inizializzo il resto dell'array con il codice dell'autore MT. Inoltre, potrei utilizzare una diversa funzione hash (ad esempio SHA384, SHA512), ma avrei bisogno di un buffer di array di dimensioni diverse (ovviamente).

Il codice Mersenne Twister originale richiedeva un singolo seed a 32 bit, ma ritengo che sia terribilmente inadeguato. Esecuzione di "solo" 2 ^ 32-1 MT diversi in cerca di infrangere la criptovaluta non vanno oltre il regno delle possibilità pratiche in questi tempi.

Mi piacerebbe leggere il feedback di chiunque su questo. La critica è più che benvenuta. Difenderò il mio uso dei file / proc come sopra perché cambiano costantemente (specialmente i file / proc / self / * e il TSC produce sempre un diverso valore (risoluzione dei nanosecondi [o migliore], IIRC). Ho eseguito Test di Diehard su questo (per diverse centinaia di miliardi ), e sembra passare a pieni voti. Ma questo è probabilmente più testimonianza della solidità del Mersenne Twister come PRNG che di come sto seminando esso.

Naturalmente, questi non sono totalmente impermeabili a qualcuno che li ha hackerati, ma non vedo tutti questi (e SHA *) essere hackerati e rotti a nella mia vita.

Alcuni usano l'input da tastiera (timeout tra i tasti), di cui ho sentito parlare penso in un romanzo che la ricezione radio statica può essere usata - ma ovviamente che richiede altro hardware e software ...

Rumore in cima allo spettro cosmico di fondo a microonde. Ovviamente devi prima rimuovere anisotropia, oggetti in primo piano, rumore del rivelatore correlato, velocità della galassia e del gruppo locale, polarizzazioni ecc. Molti rimangono insidie ??.

La fonte del seme non è molto importante. Più importante è l'algoritmo del generatore di pseudo numeri. Tuttavia qualche tempo fa ho sentito parlare della generazione di seed per alcune operazioni bancarie. Hanno preso insieme molti fattori:

  • tempo
  • temperatura del processore
  • velocità della ventola
  • tensione della CPU
  • Non ricordo di più :)

Anche se alcuni di questi parametri non cambiano molto nel tempo, puoi metterli in una buona funzione di hashing.

Come generare un buon numero casuale?

Forse possiamo prendere in considerazione un numero infinito di universi? Se questo è vero, ogni volta che vengono creati nuovi universi paralleli, possiamo fare qualcosa del genere: 

int Random() {
    return Universe.object_id % MAX_INT;
}

In ogni momento dovremmo essere su un altro ramo di universi paralleli, quindi dovremmo avere un ID diverso. L'unico problema è come ottenere l'oggetto Universo :)

Che ne dici di girare un thread che manipolerà alcune variabili in un ciclo stretto per un determinato periodo di tempo prima che venga ucciso. Ciò che finirai dipenderà dalla velocità del processore, dal carico del sistema, ecc ... Molto hokey, ma migliore del semplice srand (time (NULL)) ...

  

Non preoccuparti di un " buono " seme per un generatore di numeri casuali. Le proprietà statistiche della sequenza non dipendono da come viene eseguito il seeding del generatore.

Non sono d'accordo con i consigli di John D. Cook . Se esegui il seeding del Mersenne Twister con tutti i bit impostati su zero tranne uno, inizialmente genererà numeri tutt'altro che casuali. Il generatore impiega molto tempo a trasformare questo stato in qualsiasi cosa possa superare i test statistici. La semplice impostazione dei primi 32 bit del generatore su un seme avrà un effetto simile. Inoltre, se l'intero stato è impostato su zero, il generatore produrrà zero infiniti.

Il codice RNG correttamente scritto avrà un algoritmo di seeding scritto correttamente che accetta diciamo un valore a 64 bit e semina il generatore in modo da produrre numeri casuali decenti per ogni possibile input. Quindi, se stai usando una libreria affidabile, qualsiasi seme lo farà. Ma se comprometti la tua implementazione, devi fare attenzione.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top