Secure shuffles e la funzione rand ()

Question

Secure shuffles e la funzione rand ()

#1 da (2 voti)

0

Sto cercando di capire un aspetto di un rimescolamento sicuro usando Fisher-Yates. Per riferimento, ecco Fisher-Yates per mescolare un array x di n elementi (numerati da 0 a n-1) (da Securing a Shuffle Algorithm ):

for all i from 0 to n-1
    let j = rnd(n - i) + i
    swap x[i] with x[j]

Non capisco cosa stia succedendo Tom Leeks nella sua spiegazione della funzione rnd su Protezione di uno Shuffle algoritmo :

rnd(k):
    while true
        let z = next-random-word
        let r = z mod k
        if z - r + k <= 2^32
            return r

Perché non è possibile utilizzare direttamente r e perché è necessario if z - r + k <= 2^32 ?

Penso che il mio problema sia che non apprezzo capire il pregiudizio nella riduzione.

random cryptography

posta jww 23.09.2014 - 23:54

fonte

1 risposta

Leggi altre domande sui tag random cryptography

Identificazione delle regole di composizione memorabili [chiuso] Chiunque abbia accesso alla chiave privata CA di root decodifica il traffico HTTPS?

score 2 · Accepted Answer

Il controllo serve a garantire che non si verifichino fenomeni di distorsione. Se il tuo generatore di numeri casuali ha un intervallo compreso tra 0 e 9, e prendi semplicemente un modulo lineare, ti ritroverai con i seguenti output:

0 % 6 = 0
1 % 6 = 1
2 % 6 = 2
3 % 6 = 3
4 % 6 = 4
5 % 6 = 5
6 % 6 = 0
7 % 6 = 1
8 % 6 = 2
9 % 6 = 3

Ciò porta a valori 4 e 5 meno comuni di 0, 1, 2 o 4.

L'algoritmo fornito da Tom garantisce che l'intervallo dei valori RNG non elaborati sia limitato a un intervallo che è equamente divisibile per l'intervallo di output.

Quindi, diciamo che vogliamo un intervallo di valori compreso tra 0 e 15. Si tratta di un intervallo totale di 16. Il nostro RNG interno emette valori compresi tra 0 e 100, il che comporterebbe l'inclinazione come sopra. Il design dell'algoritmo rifiuta i valori maggiori o uguali a 96 (perché è il numero più grande inferiore a 100 che è divisibile per 16) perché quei valori porterebbero a inclinare.