Accettabile di fare affidamento su elementi casuali come unici?

Fai attenzione al paradosso dei compleanni .

Supponi di generare una sequenza di valori casuali (uniformemente, indipendentemente) da un insieme di dimensioni N (N = 2 ^ 32 nel tuo caso).

Quindi, la regola del pollice per il compleanno paradosso afferma che una volta generato su sqrt (N) valori, esiste almeno il 50% di possibilità che si sia verificata una collisione, ovvero che ci siano almeno due valori identici nella sequenza generata.

Per N = 2 ^ 32, sqrt (N) = 2 ^ 16 = 65536. Quindi, dopo aver generato circa 65k identificatori, è più probabile che due di essi si scontrino piuttosto che non! Se si genera un identificatore al secondo, ciò avverrebbe in meno di un giorno; inutile dire che molti protocolli di rete funzionano molto più velocemente di così.

È ampiamente accettato che fare affidamento su numeri casuali sia univoco se questi numeri hanno abbastanza bit. Esistono protocolli crittografici in cui la ripetizione di un numero casuale interromperà l'intera sicurezza. E fino a quando non ci sono gravi vulnerabilità nel generatore di numeri casuali in uso, non è stato un problema.

Uno degli algoritmi per generare UUID genererà effettivamente un ID composto da 122 bit casuali e assumerà che sarà unico. E due degli altri algoritmi si basano su un valore di hash troncato a 122 bit che è unico, che ha grosso modo lo stesso rischio di collisioni.

Quindi esistono standard che si basano su 122 bit sufficienti a rendere un ID casuale univoco, ma 32 bit non sono decisamente sufficienti. Con ID a 32 bit ci vogliono solo circa 2¹⁶ ID prima che il rischio di una collisione raggiunga il 50%, perché con gli ID 2¹⁶ ci saranno quasi 2 ¹ di coppie ciascuna delle quali potrebbe essere una collisione.

Anche 122 bit sono meno di quanto suggerirei in qualsiasi nuovo progetto. Se seguire un po 'di standardizzazione è importante per te, quindi utilizzare UUID. Altrimenti usa qualcosa di più grande di 122 bit.

La funzione di hash SHA1 con un'uscita di 160 bit non è più considerata sicura, in parte perché 160 bit non sono sufficienti per garantire l'univocità delle uscite. Le moderne funzioni hash hanno uscite da 224 a 512 bit. Gli ID generati casualmente devono mirare alle stesse dimensioni per garantire univocità con un buon margine di sicurezza.

Chiamerei questa cattiva pratica. Il numero casuale genera semplicemente non creare numeri univoci, ma solo creare numeri casuali. È probabile che una distribuzione casuale includa alcuni duplicati. Puoi rendere questa circostanza accettabilmente improbabile aggiungendo un elemento di tempo. Se si ottiene l'ora corrente dall'orologio di sistema in millisecondi. Qualcosa del genere:

parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))

Farò molta strada. Ovviamente per garantire veramente unicità è necessario utilizzare UUID / GUID. Ma possono essere costosi da generare, quanto sopra è probabilmente sufficiente, poiché l'unica possibilità di sovrapposizione è se il generatore casuale avesse un duplicato nello stesso millisecondo.

Dipende sia dalla probabilità di fallimento che dalle conseguenze del fallimento.

Ricordo un dibattito tra persone del software e dell'hardware in cui le persone dell'hardware consideravano accettabile un algoritmo con una bassa probabilità di risultati errati (qualcosa come 1 errore in 100 anni) e il software pensava che fosse un anatema. Si è scoperto che la gente dell'hardware calcolava regolarmente i tassi di fallimento previsti, ed era molto abituata all'idea che ogni tanto darebbe risposte errate, ad es. a causa di disturbi causati dai raggi cosmici; hanno trovato strano che la gente del software si aspettasse un'affidabilità del 100%.

Certo, hai probabilità piuttosto basse di due interi casuali a 32 bit sequenziali, ma non è completamente impossibile. La decisione ingegneristica appropriata si basa su quali sarebbero le conseguenze delle collisioni, una stima del volume di numeri che stai generando, la durata di vita su cui è richiesta l'unicità e amp; cosa succede se un utente malintenzionato inizia a tentare di provocare collisioni.

Può essere accettabile assumere che i numeri casuali siano unici ma bisogna stare attenti.

Supponendo che i tuoi numeri casuali siano equamente distribuiti, la probabilità di una collisione è approssimativamente (n ² / 2) / k dove n è il numero di numeri casuali generati e k è il numero di possibili valori che un numero "casuale" può assumere.

Non imponi un numero astronomicamente improbabile, quindi prendilo come 1 su 2 ³⁰ (circa su un miliardo). Diciamo inoltre che generi 2 pacchetti ³⁰ (se ogni pacchetto rappresenta circa un kilobyte di dati, allora questo significa circa un terabyte di dati totali, grande ma non in modo inimmaginabile). Troviamo che abbiamo bisogno di un numero casuale con almeno 2 ⁸⁹ valori possibili.

Innanzitutto i tuoi numeri casuali devono essere abbastanza grandi. Un numero casuale a 32 bit può avere al massimo 2 ³² valori possibili. Per un server impegnato che non è mai abbastanza vicino.

In secondo luogo il generatore di numeri casuali deve avere uno stato interno sufficientemente grande. Se il tuo generatore di numeri casuali ha solo uno stato interno a 32 bit, non importa quanto sia grande il valore che generi da esso, otterrai comunque solo 2 possibili valori ³² .

In terzo luogo, se hai bisogno che i numeri casuali siano unici attraverso le connessioni anziché solo all'interno di una connessione, il tuo generatore di numeri casuali deve essere ben seminato. Questo è particolarmente vero se il tuo programma viene riavviato frequentemente.

In generale i generatori di numeri casuali "regolari" nei linguaggi di programmazione non sono adatti a tale uso. I generatori di numeri casuali forniti dalle librerie di crittografia generalmente sono.

integrato in alcune delle risposte sopra riportate è l'ipotesi che il generatore di numeri casuali sia effettivamente "piatto" - che la probabilità che qualsiasi due numeri sia il successivo generato è la stessa.

Probabilmente non è vero per la maggior parte dei generatori di numeri casuali. Molti di questi usano un polinomio di alto ordine ripetutamente applicato a un seme.

Detto questo, ci sono molti sistemi là fuori che dipendono da questo schema, di solito con gli UUID. Ad esempio, ogni oggetto e risorsa in Second Life ha un UUID a 128 bit, generato in modo casuale, e raramente si scontrano.

Molte persone hanno già fornito risposte di alta qualità, ma vorrei aggiungere alcuni punti minori: in primo luogo, il punto @nomadictype sul paradosso del compleanno è eccellente .

Un altro punto: la casualità non è così semplice da generare e definire come le persone potrebbero assumere. (In realtà, ci sono in realtà test statistici per casualità disponibili).

Detto questo, è importante essere a conoscenza della Fallacia del giocatore , che è un errore statistico in cui le persone supponiamo che gli eventi indipendenti si influenzino a vicenda. Gli eventi casuali sono in genere statisticamente indipendenti l'uno dall'altro, ad esempio se generate casualmente un "10" non cambia la probabilità futura di generare più "10" in meno. (Forse qualcuno potrebbe inventare un'eccezione a questa regola, ma mi aspetterei che ciò si verifichi per quasi tutti i generatori di numeri casuali).

Quindi la mia risposta è che se potessi assumere che una sequenza sufficientemente lunga di numeri casuali fosse unica, non sarebbero in realtà numeri casuali perché sarebbe un chiaro modello statistico. Inoltre, implicherebbe che ogni nuovo numero non è un evento indipendente perché se si genera, ad esempio, un 10 che significherebbe che la probabilità di generare futuri 10s sarebbe 0% (non potrebbe accadere), più ciò significherebbe aumentare le probabilità di ottenere un numero diverso da 10 (cioè più numeri generi, maggiore è la probabilità che ciascuno dei numeri rimanenti diventi).

Un'altra cosa da considerare: la possibilità di vincere il Powerball per giocare una singola partita è, a quanto ho capito, circa 1 su 175 milioni. Tuttavia, le probabilità di vincita di qualcuno sono notevolmente superiori. Sei più interessato alle probabilità di qualcuno "vincere" (cioè essere un duplicato) rispetto alle probabilità di qualsiasi numero specifico "vincente" / essere un duplicato.

Non importa quanti bit usi - NON PUOI garantire che due numeri "casuali" saranno diversi. Invece, suggerisco di usare qualcosa come l'indirizzo IP o altro indirizzo di rete del computer e un numero sequenziale, preferibilmente un numero sequenziale HONKIN 'BIG - 128 bit (ovviamente senza segno) suona come un buon inizio, ma 256 sarebbe meglio.

No, certo che no. A meno che tu non stia usando campioni senza sostituzione, c'è una possibilità, per quanto piccola, di duplicazione.