Reducir los valores cripto-aleatorios a una entropía inútil

Hay exactamente 10 ⁸ = 100000000 secuencias posibles de ocho dígitos. Lo mejor que puede esperar es seleccionar uno de estos con probabilidad uniforme.

La forma genérica se vería así (en pseudo código 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 */
    }
}

Básicamente, generamos valores aleatorios uniformemente en el rango 0..2 ²⁷ -1:

• Produce cuatro bytes.
• Descodifíquelos en un entero de 32 bits (aquí con la convención big-endian, pero eso es arbitrario).
• Truncar a un entero de 27 bits.

¿Por qué 2 ²⁷ ? Debido a que es la potencia más pequeña de dos, que es mayor que 100000000 (2 ²⁷ es igual a 134217728).

En ese punto, tenemos un valor en el rango de 0..134217727, con probabilidad uniforme. Si cae dentro de mi rango objetivo (0..99999999), entonces eso es bueno, tenemos nuestro valor. Convierte eso a decimal para obtener tus 8 dígitos. Si el valor no cae dentro del rango, lo intentamos nuevamente. La probabilidad de un bucle es del 25,49% cada vez, por lo que converge rápidamente (menos de una posibilidad entre mil millones para realizar un bucle más de 15 veces).

Así es como se hacen las cosas con de Java. Random.nextInt(int) . Se puede usar un argumento de conteo para mostrar que no es factible alcanzar realmente una selección uniforme sin algún tipo de bucle (es decir, que ninguna potencia de 2 es un múltiplo de 10 ⁸ ).

Método alternativo: genere un entero grande de 160 bits, luego divídalo por 10 ⁸ ; El resto será su código de 8 dígitos. Este método tiene un ligero sesgo, pero menos de 2 ^-128 , por lo que es insignificante. Este método también garantiza una cantidad fija de bytes aleatorios desde su PRNG. Sin embargo, los cálculos sobre enteros que no caben en un registro de máquina pueden ser costosos, por lo que este método generalmente será menos eficiente que el bucle anterior.

Recuerda que lo que obtienes como una "clave" difícilmente vale ese nombre: enumerar todas las posibles secuencias de 8 dígitos se puede hacer en una fracción de segundo. Será difícil hacer algo de criptografía decente con eso. No obstante, dicho código será bastante bueno si se usa como, por ejemplo, una contraseña de registro de una sola vez.

No estoy seguro de lo que quieres decir al reducir a "entropía inútil". Quieres que la entropía informativa aumente. La entropía de una contraseña en una lista de contraseñas comunes con miles de entradas es lg (1000) ~ 10. La entropía de una contraseña elegida al seleccionar uniformemente 8 dígitos aleatorios es lg (10 ^ 8) ~ 26.6, donde la entropía se calcula como base -2 logaritmo (lg) del número total de posibilidades cuando todas las posibilidades se seleccionan con la misma probabilidad, como en la respuesta de Tom Leek (suponiendo que un byte PRNG se distribuye uniformemente). La distribución uniforme es importante para muchas aplicaciones, pero en este caso solo hace una diferencia trivial a la entropía.

Si acaba de hacer el tratamiento más ingenuo y generó un número de cuatro bytes sin signo al azar (entre 0 y 2 ^ 32 - 1 = 4294967295) y simplemente calculó su módulo mod 10 ^ 8:

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

solo pierdes alrededor de 0,00002 bits de entropía por sobre representación de números entre 0 y 94967295 (cada número ocurriría con probabilidad 43/2 ^ 32 como 2 ^ 32/10 ^ 8 ~ 42.94) y bajo representando números desde 94967296 a 99999999 (ocurriría con probabilidad 42/2 ^ 32).

La entropía en este caso se puede calcular utilizando la fórmula general para la entropía ( Entropy = Sum( - p lg(p) ) = Sum(p lg (1/p) ) , donde se suman todos los casos individuales, cada uno con una probabilidad de que ocurra p. Esto se evalúa como (94967295-0+1)*(43./2**32)* lg(2**32/43) + (99999999-94967296+1)*(42/2^32)*lg(2**32/42) = 26.57540 bits . Nota para la distribución uniforme (donde todos los 10 ^ 8 números tienen p = 1/10 ^ 8 como la probabilidad de ser seleccionados), obtener Sum(p lg (1/p)) = 10**8 * (1/10**8) * lg(10**8/1) = lg(10**8) = 26.57542 bits .

En este caso, argumentaría esta pérdida de 0.00002 los bits de entropía son irrelevantes. Sí, un atacante es un poco más propenso a la fuerza bruta si intenta primero los números del 0 al 94967295, pero la diferencia no importa en este caso. Por supuesto, es probablemente una buena práctica usar el método de Tom Leek cuando se crean bibliotecas aleatorias, etc. cuando no se conoce el caso de uso y el pequeño sesgo contra los números más grandes podría ser muy significativo (por ejemplo, simulaciones).

Pero para su caso específico, no me preocuparía tener una distribución perfectamente uniforme. Si desea más seguridad, solo haga que la contraseña sea más larga / más compleja y fuera del rango que se pueda forzar con facilidad.

EDITAR: Si comienzas con un número de 256 bits de un PRNG criptográfico (entre 0 y 2 ^ 256 - 1), simplemente tomaría el módulo 10 ^ 8 para este propósito; %código%. Esto representará un poco más de los números 0 a 29639936 (2 ^ 256% 10 ^ 8 = 29639936), (ocurrirían aproximadamente 10 ^ -78 veces más de lo que predeciría la distribución uniforme) pero esto tendría solo el efecto más trivial en el entropía: wolfram alfa da la diferencia de que la entropía está más allá de la capacidad de wolfram alfa para diferenciar la distribución uniforme . Esto supone que puede tomar la aritmética modular sobre el resultado de su número aleatorio de 256 bits de manera conveniente. Alternativamente, puede simplemente soltar todos menos 32 o 64 bits, y obtener algo que nuevamente, para su esquema, el método más simple proporcionará una seguridad casi indistinguible (fuera de la distribución uniforme en 2x10 ^ -5 bits (comenzando con un rand de 32 bits ) y 10 ^ -15 bits (comenzando con un rand de 64 bits). O puede usar el método de Tom si le importa eso último 2x10 ^ -5 bits de entropía.