Ridurre i valori crittografici casuali a un'entropia inutile

Ci sono esattamente 10 ⁸ = 100000000 possibili sequenze di otto cifre. Il meglio che puoi sperare è selezionare uno di questi con probabilità uniforme.

Il modo generico sarebbe simile a questo (nel codice pseudo C):

for (;;) {
    unsigned char buf[4];
    uint32_t val;

    GetRandomBytesFromPRNG(buf, sizeof buf);
    val = (uint32_t)buf[0] | ((uint32_t)buf[1] << 8)
        | ((uint32_t)buf[2] << 16) | ((uint32_t)buf[3] << 24);
    val &= 0x07FFFFFF;
    if (val < 100000000) {
        return val; /* that's your code in the 8-digit range */
    }
}

Fondamentalmente, generiamo valori casuali uniformemente nell'intervallo 0..2 ²⁷ -1:

• Produce quattro byte.
• Decodifica questi in un numero intero a 32 bit (qui con convenzione big-endian, ma è arbitrario).
• Tronca a un numero intero a 27 bit.

Perché 2 ²⁷ ? Perché questa è la più piccola potenza di due che è maggiore di 100000000 (2 ²⁷ è uguale a 134217728).

A quel punto, abbiamo un valore nell'intervallo 0..134217727, con probabilità uniforme. Se rientra nel mio intervallo di target (0..99999999), allora va bene, abbiamo il nostro valore. Converti quello in decimale per ottenere le tue 8 cifre. Se il valore non rientra nell'intervallo, riproviamo. La probabilità di loop è del 25,49% ogni volta, quindi converge rapidamente (meno di una possibilità in un miliardo di loop più di 15 volte).

Questo è il modo in cui le cose sono fatte con Java Random.nextInt(int) . Un argomento di conteggio può essere usato per mostrare che non è possibile raggiungere veramente una selezione uniforme senza un qualche tipo di loop (vale a dire, nessuna potenza di 2 è un multiplo di 10 ⁸ ).

Metodo alternativo: genera un grande numero intero a 160 bit, quindi lo divide per 10 ⁸ ; il resto sarà il tuo codice di 8 cifre. Questo metodo ha un leggero bias, ma inferiore a 2 ^-128 , quindi è trascurabile. Questo metodo garantisce anche una quantità fissa di byte casuali dal tuo PRNG. Tuttavia, i calcoli su numeri interi che non rientrano in un registro macchina possono essere costosi, quindi questo metodo di solito sarà meno efficiente del ciclo precedente.

Ricorda che quello che ottieni come "chiave" non vale proprio quel nome: elencare tutte le possibili sequenze a 8 cifre può essere fatto in una frazione di secondo. Sarà difficile creare una crittografia decente. Tuttavia, tale codice sarà abbastanza buono se utilizzato come, ad esempio, una password di registrazione una tantum.

Non sono sicuro di cosa intendi riducendo a "inutile entropia". Vuoi aumentare l'entropia informativa. L'entropia di una password in un elenco di password comuni con migliaia di voci è lg (1000) ~ 10. L'entropia di una password scelta selezionando in modo uniforme 8 cifre casuali è lg (10 ^ 8) ~ 26,6, dove l'entropia viene calcolata come base -2 logaritmo (lg) del numero totale di possibilità quando tutte le possibilità sono selezionate con la stessa probabilità, come nella risposta di Tom Leek (supponendo che il PRNG a un byte sia distribuito uniformemente). La distribuzione uniforme è importante per molte applicazioni, ma in questo caso rappresenta solo una piccola differenza per l'entropia.

Se hai appena fatto il trattamento più ingenuo e hai appena generato un numero casuale a quattro byte senza segno (tra 0 e 2 ^ 32 - 1 = 4294967295) e hai appena calcolato il suo modulo mod 10 ^ 8:

def generate_password():
    return FourBytePRNG() % (10**8)

perdi solo circa 0,00002 bit di entropia da numeri che rappresentano in eccesso tra 0 e 94967295 (ogni numero si verifica con probabilità 43/2 ^ 32 come 2 ^ 32/10 ^ 8 ~ 42,94) e sotto rappresenta numeri da 94967296 a 99999999 (si verificherebbe con probabilità 42/2 ^ 32).

L'entropia in questo caso può essere calcolata utilizzando la formula generale per l'entropia ( Entropy = Sum( - p lg(p) ) = Sum(p lg (1/p) ) , dove si sommano tutti i singoli casi ciascuno con una probabilità di verificarsi di p. Questo valore è (94967295-0+1)*(43./2**32)* lg(2**32/43) + (99999999-94967296+1)*(42/2^32)*lg(2**32/42) = 26.57540 bit . Nota per la distribuzione uniforme (dove tutti i numeri 10 ^ 8 hanno p = 1/10 ^ 8 come probabilità di essere selezionati), ottieni Sum(p lg (1/p)) = 10**8 * (1/10**8) * lg(10**8/1) = lg(10**8) = 26,57542 bit .

In questo caso direi che questa perdita di 0,00002 bit di entropia sono irrilevanti. Sì, un aggressore ha una probabilità leggermente maggiore di forza bruta se prova prima i numeri da 0 a 94967295, ma in questo caso la differenza non conta. Certo, è probabilmente una buona pratica usare il metodo di Tom Leek quando si costruiscono librerie casuali, ecc. Quando non si conosce il caso d'uso e il piccolo pregiudizio contro i numeri più grandi potrebbe essere molto significativo (per esempio le simulazioni).

Ma per il tuo caso specifico, non mi preoccuperei di avere una distribuzione perfettamente uniforme. Se vuoi maggiore sicurezza, basta rendere la password più lunga / più complessa e fuori dalla gamma che può essere facilmente forzata brutale.

EDIT: Se inizi con un numero a 256 bit da un PRNG crittografico (tra 0 e 2 ^ 256 - 1), prenderei semplicemente il modulo 10 ^ 8 per questo scopo; %codice%. Questo rappresenterà leggermente i numeri da 0 a 29639936 (2 ^ 256% 10 ^ 8 = 29639936), (si sarebbero verificati circa 10 ^ -78 volte di più di quanto previsto dalla distribuzione uniforme), ma questo avrebbe solo l'effetto più banale sul entropia - wolfram alfa dà la differenza in entropia è oltre la capacità di wolfram alpha di distinguere dalla distribuzione uniforme . Ciò presuppone che è possibile eseguire l'aritmetica modulare sul risultato del proprio numero casuale a 256 bit. In alternativa, puoi solo eliminare tutti, ma 32 o 64 bit, e ottenere qualcosa che, di nuovo, per il tuo schema il metodo più semplice fornirà una sicurezza quasi indistinguibile (fuori dalla distribuzione uniforme di 2x10 ^ -5 bit (a partire da 32-bit rand ) e 10 ^ -15 bit (a partire da un rand a 64 bit). Oppure puoi utilizzare il metodo di Tom se ti interessa l'ultimo 2x10 ^ -5 bit di entropia.