Luca Annunziata

Un generatore di numeri casuali online

Tecnologia quantica per creare autentiche sequenze numeriche random. Già pronta per l'utilizzo su Windows e Linux. Disponibile in rete, gratuitamente

Roma - Arriva dall'altra parte dell'Adriatico, in particolare dall'Istituto Ruder Bo?kovic di Zagabria (RBI), quello che i suoi creatori non esitano a definire un "vero generatore di numeri casuali". Realizzare un'autentica sequenza non ripetitiva è inattuabile con un normale computer: quest'ultimo è un automa a stati finiti, il che rende impossibile calcolare valori infiniti con un elaboratore in grado di gestirne soltanto un numero limitato. Per questo nel corso degli anni si sono moltiplicati i meccanismi per tentare di elaborare algoritmi capaci di produrre sequenze pseudo-casuali.

Gli scienziati croati hanno tuttavia elaborato un nuovo metodo, denominato QRBG (Quantum Random Bit Generator), che pare abbia risolto la questione: utilizzando un LED ed un sensore in grado di rilevare l'emissione di fotoni, gli scienziati sfruttano la luce prodotta da un semiconduttore per generare una sequenza casuale di bit. Il meccanismo quantico che regola questo fenomeno è non-deterministico, e con l'ausilio di avanzati chip che registrano il fenomeno, è possibile costruire un database contenente un'autentica sequenza random.

Il progetto è stato pensato tenendo già in considerazione un suo utilizzo pratico: non solo viene garantita la casualità delle sequenze con i migliori test in circolazione, ma la loro velocità di generazione è molto alta e l'interfaccia per l'utilizzo dei dati estremamente efficiente. Il servizio è anche abbastanza robusto, nonostante sia ancora in fase sperimentale, ed in futuro è anche prevista l'introduzione del protocollo SSH per aumentarne in modo drastico la sicurezza.
Sono molti i campi di applicazione in cui i numeri casuali possono fare comodo: li utilizzano i siti web per creare le diverse istanze di interrogazione ai database, i videogiochi per proporre all'utente condizioni ambientali variabili, le applicazioni scientifiche per studiare l'evoluzione di un sistema fisico. A causa dei limiti degli algoritmi attuali, non sempre questo tipo di impieghi registra un successo pieno.

Per quanti fossero interessati a testare QRBG, è possibile scaricare l'archivio contenente gli strumenti per l'utilizzo su Windows, Linux e MATLAB a questo indirizzo: l'applicazione è scritta in C++. Per il download è necessario registrarsi: per completare l'iscrizione, invece dei soliti captcha, è necessario risolvere una equazione matematica.

Luca Annunziata
70 Commenti alla Notizia Un generatore di numeri casuali online
Ordina
  • Se come computer si intende l'insieme di processore, memorie e periferiche di I/O (Macchina di Von Neumann) è necessario dire che questa è Touring compatibile cioé che essa è in grado di risolvere tutti i problemi che sono computabili dalla macchina di Touring. Come ben saprete la macchina di touring può risolvere classi di problemi ben più ampi rispetto ad un semplice automa a stati finiti.

    Forse sarebbe meglio, per questione di informazione, di correggere il contenuto erroneo dell'articolo
  • e magari evitare di fare il tourista con la macchina di T(o)uring, che si rivolta nella tomba...
    non+autenticato
  • intel dai chipset 810 e superiori ha introdotto un generatore di numeri casuali hardware che si basa sulla campionatura digitale del rumore termico di una gunzione PN di un transistor, e' casuale tanto quanto il loro coso che legge i fotoni emessi da un led, quindi non hanno inventato nulla di utile o di migiore di quello che esistesse gia'.
    non+autenticato
  • - Scritto da: Nome e cognome
    > intel dai chipset 810 e superiori ha introdotto
    > un generatore di numeri casuali hardware che si
    > basa sulla campionatura digitale del rumore
    > termico di una gunzione PN di un transistor, e'
    > casuale tanto quanto il loro coso che legge i
    > fotoni emessi da un led, quindi non hanno
    > inventato nulla di utile o di migiore di quello
    > che esistesse
    > gia'.

    probabilmente, imho, le differenze sostanziali tra i due metodi sono all'incirca due:
    - la lettura del rumore [...] PN prevede l'utilizzo di un ADC. quanti byte produce in uscita questo AD? (pochi imho)
    - la lettura del rumore [...] PN prevede che utlizza un ADC, in due letture con un intervallo di tempo molto piccolo (concetto) tende a fare due letture "identiche" (imho).
    questi due problemi della lettura [...] PN non dovrebbero affliggere il generatore quantico che sforna bit in stream ovvero in continuo, a mò di rubinetto aperto x intenderci...
    non+autenticato
  • - Scritto da: parlo poco e scrivo ancora meno...
    > - Scritto da: Nome e cognome
    > > intel dai chipset 810 e superiori ha introdotto
    > > un generatore di numeri casuali hardware che si
    > > basa sulla campionatura digitale del rumore
    > > termico di una gunzione PN di un transistor, e'
    > > casuale tanto quanto il loro coso che legge i
    > > fotoni emessi da un led, quindi non hanno
    > > inventato nulla di utile o di migiore di quello
    > > che esistesse
    > > gia'.
    >
    > probabilmente, imho, le differenze sostanziali
    > tra i due metodi sono all'incirca
    > due:
    > - la lettura del rumore [...] PN prevede
    > l'utilizzo di un ADC. quanti byte produce in
    > uscita questo AD? (pochi
    > imho)
    > - la lettura del rumore [...] PN prevede che
    > utlizza un ADC, in due letture con un intervallo
    > di tempo molto piccolo (concetto) tende a fare
    > due letture "identiche"
    > (imho).
    > questi due problemi della lettura [...] PN non
    > dovrebbero affliggere il generatore quantico che
    > sforna bit in stream ovvero in continuo, a mò di
    > rubinetto aperto x
    > intenderci...

    Non è necessario un ADC.
    Un circuitino come questo per esempio va molto bene:
    http://www.cryogenius.com/hardware/rng/random.gif

    Con un'opportuna scelta dei componenti probabilmente si riesce a generare qualche MBit al secondo di dati random ma già così com'è secondo me è molto veloce (il 74LS14 ha tempi di salita e discesa massimi di 22 nanosecondi). Sarebbe da prendere un oscilloscopio, attaccarcelo e scoprire l'effettiva velocità.

    Per il discorso che facevi circa le due letture uguali, bé, lì dipende da quanto rumore (e quanto velocemente) genera Q1 ma penso che 1Mbit al secondo sia in grado di generarlo.



    L'eliminare due letture consecutive uguali lo si può fare attraverso il metodo proposto da Schneier nel suo libro "Applied Cryptography (2nd Ed.)" al capitolo 17.14 che è davvero molto semplice e consiste in questo:
    - leggo 1 bit, leggo un secondo bit, se le letture sono diverse, allora tengo il primo bit letto e l'altro lo butto e ricomincio da capo
    - leggo 1 bit, leggo un secondo bit, se le letture sono uguali butto entrambi e ricomincio da capo

    Se la sequenza reale letta è dunque:
    00100100011010101101...
    otterrò:
    1001110...
  • A cosa serve un programma se alla fine deve connettersi a un sito remoto per ottenere il numero ? Non era sufficiente un web service che desse in xml un numero richiesto tramite http ? Trovo un attimo strano che serva un client apposito ecco.
  • Anche il progetto Seti@Home usa un client apposito, cosa c'è di strano?
    non+autenticato
  • va bè, che solo la meccanica quantistica è veramente random dovrebbe essere noto ai più, anche a quelli che non hanno studiato fisica ma hanno letto su Focus (Dio mi scampiSorride ) che un fotone o un elettrone ha solo una certa probabilità di trovarsi in un dato posto in un dato tempo, non può essere determinato esattamente... per il resto del tempo sarà in un'altra dimensione, chi lo sa... magari sapendo la risposta a questa domanda anche la quantistica diventa prevedibile e non random, ma a oggi è così...

    L'unica altra cosa davvero random è l'umore delle donne, ma fino ad ora nessuno è riuscito a trasformare questo effetto in un'applicazione pratica, quindi esula dai nostri scopi Ficoso

    Quello però che non ho capito leggendo i commenti a questa notizia fino a questo momento è quali sono i campi pratici REALI in cui ci serve davvero una sequenza più random di quella che è possibile ottenere con un calcolatore che le ricava dallo stato del suo hardware, movimenti di mouse e tastiera, temperatura della cpu, variazioni di voltaggio, ecc... Quand'è che un buon pseudo-casuale non è realmente sufficiente ?
  • - Scritto da: mmorselli
    > va bè, che solo la meccanica quantistica è
    > veramente random dovrebbe essere noto ai più,
    > anche a quelli che non hanno studiato fisica ma
    > hanno letto su Focus (Dio mi scampiSorride ) che un
    > fotone o un elettrone ha solo una certa
    > probabilità di trovarsi in un dato posto in un
    > dato tempo, non può essere determinato
    > esattamente... per il resto del tempo sarà in
    > un'altra dimensione, chi lo sa... magari sapendo
    > la risposta a questa domanda anche la quantistica
    > diventa prevedibile e non random, ma a oggi è
    > così...
    >
    > L'unica altra cosa davvero random è l'umore delle
    > donne, ma fino ad ora nessuno è riuscito a
    > trasformare questo effetto in un'applicazione
    > pratica, quindi esula dai nostri scopi
    >Ficoso
    >
    > Quello però che non ho capito leggendo i commenti
    > a questa notizia fino a questo momento è quali
    > sono i campi pratici REALI in cui ci serve
    > davvero una sequenza più random di quella che è
    > possibile ottenere con un calcolatore che le
    > ricava dallo stato del suo hardware, movimenti di
    > mouse e tastiera, temperatura della cpu,
    > variazioni di voltaggio, ecc... Quand'è che un
    > buon pseudo-casuale non è realmente sufficiente
    > ?

    In crittografia, ma anche in altre aree della matematica.
  • Ti faccio un esempio pratico va.

    Truecrypt (truecrypt.org) si avvale dell'RNG (fra gli altri) in questi casi:
    - Crea un keyfile
    - Crea il salt
    - Crea la chiave primaria


    La chiave primaria è la parola chiave effettiva con cui viene cifrato il disco. Truecrypt infatti usa la chiave dell'utente SOLO per l'header, mentre il disco è cifrato con una chiave totalmente casuale (memorizzata nell'header cifrato con la chiave scelta dall'utente).
    Questo ha molti vantaggi perché:
    1) l'header è molto piccolo quindi una crittoanalisi dell'header è molto più difficile essendoci pochi byte da studiare (più dati da studiare ci sono e meglio è per l'eventuale intruso)
    2) l'utente può cambiare chiave di cifratura dell'header quando gli pare senza dover ri-cifrare l'intero supporto.

    Però, ovviamente, se la chiave primaria (detta chiave master) non è realmente casuale, succede che la crittoanalisi del disco diventa molto più semplice perché si può cominciare ad escludere interi range di chiavi che è poco probabile siano generati.

    Bene, e questo SOLO per la chiave master (che è poi quella più importante). Se posso quindi stabilire che per esempio tutta una serie di chiavi è molto poco probabile che si vengano a generare sto in pratica abbassando il numeri di chiavi da testare.
    Se per esempio prima avevo 256 bit (e quindi 2^256 combinazioni) e ora grazie a questa conoscenza sono riuscito a ridurle a 60 bit posso effettuare un bruteforce del tuo disco in qualche giornata.

    Siamo quindi passati da diverse volte l'età dell'universo a una manciata di ore.

    Lascio stare poi il discorso sui keyfile e tutto il resto che però è del tutto simile.
  • Bella spiegazione Wakko complimentiOcchiolino Molto chiaro.
    non+autenticato
  • - Scritto da: chess
    > Bella spiegazione Wakko complimentiOcchiolino Molto
    > chiaro.

    Grazie ^_^

    Edit: LOL ogni tanto confondo il grazie con il prego Imbarazzato
    -----------------------------------------------------------
    Modificato dall' autore il 21 luglio 2007 17.22
    -----------------------------------------------------------
  • > In crittografia, ma anche in altre aree della
    > matematica.

    Ti ringrazio per la risposta... ma volevo qualcosa di piùSorride

    Conosco l'uso dei numeri casuali in crittografia, quello che volevo sapere è quando la crittografia non riesce ad assolvere il suo compito con un buon pseudo-casuale. Una pseudo-casuale è virtualmente prevedibile, ma nella pratica lo è davvero ? Dal punto di vista di un hacker 60 minuti di rumore elettrico campionato sono più prevedibili di una vera sequenza casuale ? Esiste insomma almeno una applicazione pratica dove l'avere una sequenza true-random fa la differenza ? Gli hacker non sono Dei con il controllo su ogni evento della meccanica classica, la frequenza con cui ho battuto i tasti per scrivere questo messaggio era altrettanto imprevedibile quanto l'emissione dei fotoni descritta nell'articolo, dal punto di vista umano.... O no ?Sorride
  • - Scritto da: mmorselli
    > > In crittografia, ma anche in altre aree della
    > > matematica.
    >
    > Ti ringrazio per la risposta... ma volevo
    > qualcosa di più
    >Sorride
    >
    > Conosco l'uso dei numeri casuali in crittografia,
    > quello che volevo sapere è quando la crittografia
    > non riesce ad assolvere il suo compito con un
    > buon pseudo-casuale. Una pseudo-casuale è
    > virtualmente prevedibile, ma nella pratica lo è
    > davvero ? Dal punto di vista di un hacker 60
    > minuti di rumore elettrico campionato sono più
    > prevedibili di una vera sequenza casuale ? Esiste
    > insomma almeno una applicazione pratica dove
    > l'avere una sequenza true-random fa la differenza
    > ? Gli hacker non sono Dei con il controllo su
    > ogni evento della meccanica classica, la
    > frequenza con cui ho battuto i tasti per scrivere
    > questo messaggio era altrettanto imprevedibile
    > quanto l'emissione dei fotoni descritta
    > nell'articolo, dal punto di vista umano.... O no
    > ?
    >Sorride

    Son sempre Wakko.
    Il problema lo hai non tanto quando devi generare una manciata di numerelli, ma quando vuoi che quei numerelli capitino con eguale probabilità di tutti gli altri.

    È chiaro che per molte applicazioni un RNG fatto alla razzo va più che bene, ma quando sulla crittografia un RNG fatto alla razzo può costarti la vita (o la libertà).
    Spesso è infatti più semplice craccare l'RNG che l'intero sistema crittografico.

    Ti faccio un altro esempio e lo prendo dalla pagina di Peter Gutmann (http://www.cs.auckland.ac.nz/~pgut001/) qui: http://www.cs.auckland.ac.nz/~pgut001/pubs/usenix9...

    «Unfortunately the advice presented by various authors is
    all too often ignored, resulting in insecure random
    number generators which produce encryption keys
    which are much, much easier to attack than the
    underlying cryptosystems they are used with
    . A
    particularly popular source of bad random numbers is
    the current time and process ID.
    This type of flawed
    generator first gained widespread publicity in late 1995,
    when it was found that the encryption in Netscape
    browsers could be broken in around a minute due to the
    limited range of values provided by this source
    , leading
    to some spectacular headlines in the popular press [14].
    Because the values used to generate session keys could
    be established without too much difficulty, even noncrippled
    browsers with 128-bit session keys carried (at
    best) only 47 bits of entropy in their session keys [15].
    Shortly afterwards it was found that Kerberos V4
    suffered from a similar weakness (in fact it was even
    worse than Netscape since it used random() instead
    of MD5 as its mixing function) [16]. At about the same
    time, it was announced that the MIT-MAGIC-COOKIE-
    1 key generation, which created a 56-bit value,
    effectively only had 256 seed values due to its use of
    rand() (this had been discovered in January of that
    year but the announcement was delayed to allow
    vendors to fix the problem) [17].»


    In altre parole, la scelta di un cattivo RNG, rendeva ESTREMAMENTE più semplice la decifrazione di messaggi che avrebbero dovuto restare segreti (nel caso di Netscape... un sistema a 128bit, per colpa di un cattivo RNG, era divenuto craccabile in qualche minuto!).

    Problematiche simili le hai per esempio nelle case di gioco in cui le macchine DEVONO generare numeri equiprobabili... altrimenti posso puntare sui numeri che escono con più probabilità e avere quindi più probabilità di vincere di uno sprovveduto qualsiasi che che punta a caso.
  • tutto chiaro, però il confronto tra il sistema quantico e un pessimo generatore pseudo è impari, e non risponde al mio quesito, che voleva invece capire se un generatore quantico desse realmente un vantaggio rispetto ad un buon generatore pseudo, che prendesse in considerazione non fattori prevedibili, come il system time o il proces id, ma fortemente imprevedibili, e soprattutto non ripetitivi.
    Ovvero, una volta che i tre porcellini si sono accorti che la casa di paglia non resiste al soffio del lupo, saranno al sicuro in una buona casa di mattoni, o vale la pena farne una sulla luna con pareti di duranio spesse sei metri ?Sorride

    La mia impressione è che questo generatore quantico non sia nulla più che un esercizio mentale...
  • - Scritto da: mmorselli
    > tutto chiaro, però il confronto tra il sistema
    > quantico e un pessimo generatore pseudo è impari,
    > e non risponde al mio quesito, che voleva invece
    > capire se un generatore quantico desse realmente
    > un vantaggio rispetto ad un buon generatore
    > pseudo, che prendesse in considerazione non
    > fattori prevedibili, come il system time o il
    > proces id, ma fortemente imprevedibili, e
    > soprattutto non
    > ripetitivi.
    > Ovvero, una volta che i tre porcellini si sono
    > accorti che la casa di paglia non resiste al
    > soffio del lupo, saranno al sicuro in una buona
    > casa di mattoni, o vale la pena farne una sulla
    > luna con pareti di duranio spesse sei metri ?
    >Sorride
    >
    > La mia impressione è che questo generatore
    > quantico non sia nulla più che un esercizio
    > mentale...


    Beh anche il tuo esempio è piuttosto impari (non sono comunque il tizio al quale rispondevi).

    Non si tratta di far andare i tre porcellini sulla luna, ma di entrare nel bunker che si possono comprare bello e fatto sulla terra.

    Questa tecnologia già esiste, e viene già commercializzata.

    Poi è ovvio che l'uso dovrebbe essere comparato ai propri scopi.
    Per i miei files personali non ne ho certo bisogno, ma preferirei che la mia banca usi questi sistemi.

    Non me ne frega niente se un buon generatore di numeri pseudo casuale può essere abbastanza sicuro, perchè rischiare quando dall'altra parte hai la certezza assoluta?

    Comunque non è solo *questo* il generatore quantico, anzi per dirla tutta la trovo, quella dell'articolo, una cosa non proprio utilissima visto che una cosa così delicata va condivisa con loro e va fatta passare per la rete... Comunque esistono sistemi hardware dedicati allo scopo:
    http://www.idquantique.com/
    non+autenticato
  • Non sono d'accordo.
    La casualità di un utente che muove il mouse per un tempo sufficentemnete lungo è vera casualità (anche se è sicuramente più correlata di un fenomeno quantistico). Quindi per un sistema causale può bastare.
    non+autenticato
  • - Scritto da: user
    > Non sono d'accordo.
    > La casualità di un utente che muove il mouse per
    > un tempo sufficentemnete lungo è vera casualità
    > (anche se è sicuramente più correlata di un
    > fenomeno quantistico). Quindi per un sistema
    > causale può
    > bastare.

    Non per un RNG usato in crittografia. Certo, è sempre meglio che un algoritmo basato unicamente sul software.

    Sta di fatto che il grado di "casualità" di un sistema basato sui movimenti del mouse ti permette di generare solo POCHISSIMI byte casuali al secondo (qualche decina, FORSE, e solo se muovi il mouse). È inoltre suscettibile a problemi che possono capitare se l'utente ha per esempio attivi gli spostamenti automatici del mouse (tipo il posizionare il cursore automaticamente sul pulsante di default, gli "effetti calamita", ecc) che rendono il movimento non più "tanto" casuale.

    Sta di fatto che se ti servono pochi byte allora un sistema come quello che dici va più che bene, ma quando ti servono byte in quantità industriale allora devi per forza affidarti all'hardware. Tant'è che /dev/random, che genera byte casuali di "buona qualità" (da un punto di vista della casualità), per farti un file da 1KByte di dati random ti impiega svariati minuti (a meno che non ci sia hardware dedicato dietro).

    La differenza poi fra un sistema hardware basato sul rumore di una giunzione PN e la scheda Quantis della IDQuantique è, probabilmente (e dico probabilmente perché semplicemente non lo so... bisognerebbe chiedere a qualcuno che studia statistica), solo la velocità con cui tale sistema è in grado di fornire dati casuali. Non ho dati sotto mano circa quanto siano in grado altri sistemi hardware di produrre per secondo, ma la scheda Quantis PCI genera ben 16MBit random al secondo.
  • ...ma inutile.

    Inutile perché mi costringe a fidarmi di loro (e in crittografia vale il principio "ci sono solo due persone al mondo di cui mi fido: una sono io, e l'altra non sei tu"). Inutile perché il numero generato può essere intercettato fra loro e me. Inutile perché se mi serve una grossa quantità di dati random (come spesso capita) non ho certamente una giornata per starmeli a scaricare da Internet.

    Ovviamente i numeri casuali prodotti da algoritmi matematici NON SONO, come si dice, "cryptographically secure" questo perché, conoscendo l'algoritmo usato per generarli e i bit/byte precedenti, è possibile predire la sequenza successiva.
    Pertanto bisogna ricorrere all'hardware.

    Ci sono svariati progetti più o meno buoni, dai più semplici (ma ciò nonostante ottimi) progettini home-made che sfruttano le proprietà elettriche dei transistor (configurati in modo da generare "rumore", purtroppo non ho più il link al progettino) sino a vere e proprie schede professionali in grado di generare diversi MBit al secondo sfruttando proprietà quantistiche (http://www.idquantique.com/products/quantis.htm).

    Ci sono poi schede madri con implementati degli RNG in hardware... per esempio alcune Mini-ITX della VIA.

    Ovviamente è inutile avere un RNG hardware se poi i software che usiamo non ne fanno uso... fortunatamente su Linux esistono due device /dev/random e /dev/urandom che sono usati praticamente da qualunque software ne abbia bisogno.

    /dev/urandom genera grosse sequenze di numeri pseudo-casuali prendendo di tanto in tanto spunto dallo stato del PC (ovvero si "ricarica" osservando la posizione del mouse, i tasti premuti sulla tastiera, ecc.)
    /dev/random invece cerca di essere davvero random basandosi il più possibile sullo stato fisico della macchina. Purtroppo, senza hardware dedicato, è esasperatamente lento.

    Se fate cat /dev/urandom otterre subito un'immensa quantità di dati pseudo-random. Se invece fate cat /dev/random vedrete che i dati vengono generati per lo più quando muovete il mouse (più velocemente muovete il mouse e più svelto genera i numerelli).

    Con hardware dedicato /dev/random sfrutta le schede hardware disponibili ed è quindi in grado di fornire grosse quantità di dati realmente casuali (ovviamente questo dipende dalla scheda).

    Grazie a questa scelta progettuale su Linux gran parte dei software non ha bisogno di algoritmi "nativi" per produrre sequenze pseudo-random e utilizza quindi al meglio eventuali schede RNG hardware senza bisogno di modifica alcuna.
  • Un esempio di applicazione che su Windows usa il suo RNG interno mentre su Linux usa /dev/random è Truecrypt... come si può vedere da linea 640 a linea 656 nella cartella Common/Random.c nella versione 4.3
CONTINUA A LEGGERE I COMMENTI
1 | 2 | 3 | Successiva
(pagina 1/3 - 11 discussioni)