Secure shuffles y la función rand ()

Question

Secure shuffles y la función rand ()

#1 de Polynomial (2 votos)

0

Estoy tratando de entender un aspecto de una mezcla segura con Fisher-Yates. Para referencia, aquí está Fisher-Yates para mezclar una matriz x de n elementos (numerados de 0 a n-1) (de Asegurando un algoritmo aleatorio ):

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

No entiendo muy bien a qué se dedica Tom Leeks en su explicación de la función rnd en Asegurando un Shuffle Algoritmo :

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

¿Por qué no se puede usar directamente r y por qué se necesita el if z - r + k <= 2^32 ?

Creo que mi problema es que no aprecio en comprender el sesgo en la reducción.

cryptography random

pregunta jww 23.09.2014 - 23:54

fuente

1 respuesta

Lea otras preguntas en las etiquetas cryptography random

Use TOTP para evitar simular solicitudes ¿Posible amenaza de ingeniería de seguridad?

score 2 · Accepted Answer

La comprobación es para asegurarse de que no se produzca sesgo. Si su generador de números aleatorios tiene un rango de 0 a 9, y simplemente toma un módulo directo, terminará con las siguientes salidas:

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

Esto hace que los valores 4 y 5 sean menos comunes que 0, 1, 2 o 4.

El algoritmo que Tom dio asegura que el rango de los valores de RNG sin procesar se limita a un rango que es divisible por el rango de salida.

Entonces, digamos que queremos un rango de valores de 0 a 15. Eso es un rango total de 16. Nuestro RNG interno genera valores entre 0 y 100, lo que llevaría a un sesgo como el anterior. El diseño del algoritmo rechaza valores mayores o iguales a 96 (porque es el número más grande menor que 100 que es divisible entre 16) porque esos valores podrían desviarse.