¿Es posible crear un algoritmo generador de números aleatorios más seguro al XORingar dos o más algoritmos de números aleatorios menos seguros?

Dado que esto no parece haberse hecho todavía, voy a sugerir una respuesta desde un punto de vista puramente teórico:

Sean X, Y dos variables aleatorias en {0,1} ^ n. Sea f (x, y) = x XOR y

Ahora, H (X, Y) = H (X) + H (Y | X) = H (Y) + H (X | Y), y dado que la información de la entropía es siempre negativa, tenemos H (X , Y) > = H (X) y H (X, Y) > = H (Y). Así que la variable aleatoria de unión (X, Y) tiene al menos tanta entropía como cada variable aleatoria individual sola (la igualdad se produce cuando una variable aleatoria depende perfectamente de la otra).

Sin embargo, cuando aplica una función a una variable aleatoria, reduce su entropía (no hay reducción si f es biyectivo, pero esto no es cierto para nuestro caso), por lo que tenemos H (f (X, Y)) < H (X, Y). Una prueba es aquí (pregunta dos).

Ahora, la pregunta de OP es si es posible hacer que H (f (X, Y)) sea más grande que H (X) y H (Y). La respuesta es sí.

Escribimos X como (X_1, ..., X_n) e Y como (Y_1, ..., Y_n). Ahora considere un caso extremo donde X_1 es constante y el resto de los bits son iid Bernoulli con p = 0.5, y Y_1 es Bernoulli con p = 0.5 e independiente de X, mientras que los otros bits de Y son constantes, entonces H (X) = n-1, H (Y) = 1, y H (f (X, Y)) = n, mayor que H (X) y H (Y).

Puede que esta no sea una respuesta muy interesante, pero creo que responde exactamente a lo que pregunta el OP.

EDIT:

Creo que una pregunta que también tiene en mente el OP es: ¿es posible obtener un número aleatorio peor que ambas entradas cuando hacemos esto? La respuesta también es sí. Considere X Bernoulli con p = 0.5. Y Y = NO X. Antes de combinar X e Y, obtenemos H (X) = H (Y) = 1. Pero, X XOR Y == 1, entonces H (f (X, Y)) = 0! Ups ... Así que definitivamente no solo arbitrariamente XOR dos números aleatorios y esperamos obtener uno mejor.

EDIT 2:

Una discusión interesante a continuación trajo una pregunta importante: si X e Y son independientes, ¿es X XOR Y al menos tan aleatorio como X e Y? Mark tiene toda la razón: la respuesta es sí.

Aquí es por qué:

Primero, note que para cualquiera de las dos variables aleatorias U y V, tenemos H (U) > = H (U | V). La igualdad se mantiene cuando U y V son independientes. Intuitivamente, esto significa que saber algo acerca de V nunca duele si estamos tratando de averiguar dónde está U. Una prueba formal reduce H (U) -H (U | V) a una divergencia KL, que siempre es no negativa.

Ahora, usando la misma notación que la anterior, tenemos:

H (f (X, Y), X) = H (f (X, Y) | X) + H (X) = H (X | f (X, Y)) + H (f (X) Y))

Ya que para cualquier x fija, tenemos H (f (x, Y)) = H (Y) (advertencia: no es cierto para f arbitraria, pero tenemos esto ya que definimos f (x, y) como x XOR y), tenemos H (f (X, Y) | X) = H (Y), y esto nos da:

H (X) + H (Y) = H (X | f (X, Y)) + H (f (X, Y))

Pero como H (X) > = H (X | f (X, Y)), tenemos:

H (Y) < = H (f (X, Y))

y por simetría:

H (X) < = H (f (X, Y))

Así que esa es la buena noticia. La mala noticia es que: probar la independencia probablemente no sea más fácil que probar la aleatoriedad, si no más difícil. Así que no nos ayuda tanto como parece.

por cierto, ¿cómo se sienten todos al pedirle a SE que habilite MathJax aquí para que podamos hacer algunos cálculos serios cuando sea necesario?

No recomendaría combinar generadores de números aleatorios de esta manera sin tener una teoría subyacente que respalde su caso.

Una forma sencilla de ilustrar los problemas es considerar el comportamiento de los algoritmos LCG de gama baja, los esquemas populares de "una sola línea" para generar números aleatorios.

Se pueden hacer para producir secuencias que pasarán ciertas pruebas estadísticas, pero no son adecuadas para aplicaciones criptográficas. Un defecto conocido en tales generadores es que los bits de orden inferior no son aleatorios. Por ejemplo, he observado que el bit bajo oscila entre 0/1, y si tiene dos generadores como este y XOR ese bit bajo, y los generadores están en fase o fuera de fase, en cualquier caso el resultado de El XOR es bastante predecible. No está claro si ha mejorado la situación, pero puede haber empeorado la situación.

En la discusión de Knuth sobre la generación de números aleatorios, presenta un ejemplo cómico de sus intentos de construir un generador "super deluxe".

Probablemente esto parezca un snark, pero su solución solo mejora la situación si los dos PRNG se eligen con suficiente aleatoriedad. Piense en la razón por la que consideramos que un PRNG débil es inseguro: el resultado es estadísticamente fácil de adivinar algunos / todos, lo que resulta en criptografía y otras operaciones que pueden ser atacadas al conocer parte de los datos de entrada. Si pasa de un PRNG a dos PRNG, el atacante simplemente necesita conocer ambos PRNG (o adivinarlos varias veces) antes de que puedan reducir la fuerza potencial de cualquiera de los dos (proporcionar más datos de entrada aleatorios) a la debilidad del otro ( proporcionando datos de entrada adivinables Probablemente pueda mejorar la fuerza estadísticamente si desarrolla un algoritmo alimentado por PRNG para elegir qué PRNG de dos (o, mejor aún, más) al azar, pero está solo a un factor de la misma debilidad con la que comenzó. Mejor, probablemente, para analizar un solo PRNG más seguro.

Es bastante posible crear un RNG más fuerte utilizando el método sugerido, sin embargo, también es posible crear un RNG más débil, o uno que no mejore. El resultado final depende de las propiedades de los RNG más débiles. La distribución de bits y el sesgo tienen tanto efecto como el nivel de entropía. Solo un análisis cuidadoso y el conocimiento de todo el esquema pueden indicar si la fortaleza mejora, y si existen problemas potenciales que podrían comprometer la seguridad.

Considere los siguientes 2 RNG débiles, A y B .
A produce un flujo de bits donde cada bit impar es 0, y cada bit par es pseudoaleatorio criptográficamente.
B produce un flujo de bits donde cada bit par es 0, y cada bit impar es pseudoaleatorio criptográficamente.
El flujo XOR resultante C tiene pseudoaleatoriedad criptográfica completa, y es obviamente más fuerte que los demás, asumiendo semillas independientes.

Ahora considere lo siguiente.
A es la salida del flujo de bits de Dual_EC_DRBG con constantes backdoored NSA. Las salidas futuras son predecibles para un atacante que puede observar la salida bruta del flujo de bits.
B es la salida del flujo de bits de un hash MD5 cíclico en un número aleatorio, donde la salida futura es el hash de la salida de corriente. Las salidas futuras son predecibles para un atacante que puede observar la salida sin procesar del flujo de bits.
El flujo XOR resultante C ya no es predecible de la misma manera que sus componentes. Si un atacante puede ver la salida de A o B por su cuenta, C ya no es seguro. La recuperación de la semilla para MD5 hace que todas las salidas futuras sean predecibles de inmediato, debe ser lo suficientemente grande como para evitar un ataque de fuerza bruta. La seguridad del flujo no es mejor que el esfuerzo de trabajo para recuperar y verificar la semilla MD5, o uno de los valores hash iterados.

Y finalmente.
A es la salida del flujo de bits de AES-CTR, donde la NSA conoce la clave.
B es la salida del flujo de bits de AES-CTR donde la clave es conocida por la KGB.
El flujo XOR resultante C es seguro e impredecible para cualquiera de las agencias en ausencia de colusión, lo que haría que la salida fuera completamente predecible.

Estos ejemplos muestran que las secuencias de bits con entropía débil o salida predecible se pueden hacer más seguras al juntarlas, dadas las propiedades y condiciones correctas. Eso no necesariamente los hace completamente seguros.

A menos que uno sea perfectamente aleatorio, los resultados finales no están claros . Pero si uno fuera perfectamente aleatorio, ya no sería débil.

Editar: a menos que esté seguro de que los dos son completamente independientes entre sí, los beneficios pueden no estar claros.

La respuesta rápida pero demasiado vaga a tu pregunta original es: Sí.

Sin embargo, como la mayoría de las personas han indicado: ¡más seguro! = seguro.

El propósito de RNGs / PRNGs es producir una entropía suficiente para que sea imposible que un atacante adivine la información suficiente para recuperar suficiente datos protegidos.

La mayoría de las fuentes de entropía se prueban para determinar si contienen una secuencia suficientemente mezclada de 0 y 1 binarios, de modo que simplemente "adivinar" el siguiente dígito binario sería incorrecto aproximadamente el 50% del tiempo.

Hay un par de elementos subyacentes que determinan lo que significa "lo suficientemente mezclado".

Primero , es la proporción real de 1 a 0 en la salida:

Por ejemplo, si el PRNG produjo 11011010101010101, entonces, de los 15 bits que generamos, hubo 10 de ellos configurados en 1, que es el 66% del espacio de entropía. Un atacante que anticipa este tipo de PRNG estaría "en mejor situación" suponiendo que en general hay más de 1 que 0, así que por cada bit favorecerían configurarlo en 1 y 2/3 del tiempo que serían correctos.

A la inversa, un PRNG que produjo 011011000100110 tiene ocho 0 y 7 1, lo que favorece un 0-bit contra un 1 bit al 53%: 47%. Por lo tanto, el atacante que intenta derrotar a este sistema básicamente tiene poco beneficio al adivinar un 0 sobre un 1 (... aproximadamente un 6% de probabilidades mejores).

Lo ideal es que cuanto más cerca de las 50:50 tenga más protección para esta primera característica de protección.

Segundos , es la aleatoriedad de la entropía, de manera que no se puede discernir un patrón . Por ejemplo, si el PRNG genera una relación de bits perfecta de 0 a 1 de 50:50, pero se observa un patrón, entonces hay un beneficio reducido del sistema.

Considere la siguiente entropía de 16 bits: 101010101010101010 Bueno, seguro que pasamos el primer requisito de tener una perfecta distribución de bits del 50% 0's y 50% 1's; Sin embargo, como se puede observar trivialmente, esto no es seguro. Lo mismo puede decirse de: 0011001100110011 o 0000000011111111.

Hay un patrón discernible en la salida de entropía. Los patrones son la perdición de las operaciones criptográficas porque filtran información que reduce la efectividad general del algoritmo.

Ahora, como mejor ejemplo, veamos la siguiente secuencia PRNG de 16 dígitos: 0001011011000111 Esa salida es mucho más "aleatoria" que los varios ejemplos anteriores en esta sección. Seguro que hay 2 secuencias donde hay tres 0 seguidos, pero dados estos primeros 16 dígitos, ¿puedes adivinar de manera trivial cuándo aparecería la tercera secuencia de tres 0? No es tan fácil.

Entonces, para volver a su pregunta original: si combinó dos fuentes de entropía débiles y luego se aseguró de que su XOR resultante produjera una proporción casi igual de 0 a 1 Y no hubo patrones obvios en la salida, entonces PODRÍA producir un generador de números pseudoaleatorios más fuerte de lo que cualquiera de los dos hubiera estado por su cuenta.

Nota: para solucionar algunos de los problemas que otros han citado (como el estado de bit inferior predecible), puede cambiar uno o ambos weak_random1 y < em> weak_random2 por un cierto número de bits antes de realizar el XOR. Por ejemplo, desplace work_random1 en posiciones de 3 bits y desplace weak_random2 en posiciones de 5 bits. Excepto por el hecho de que revelé los valores de cambio (3 y 5, respectivamente), esto habría "mezclado" los valores que tradicionalmente se adivinaban / predecían a diferentes ubicaciones en sus cadenas PRNG respectivamente antes del La operación XOR hace que la previsibilidad sea mucho más difícil.

¡Dicho todo esto, sugiero usar una mejor fuente aleatoria para empezar! Si bien es posible lograr lo que está preguntando, conozco a pocos matemáticos que dirían que es fácil de lograr y que menos lo consideraría una solución segura.

Buena suerte :)

Un problema potencial que veo es si el primer generador de números aleatorios genera números aleatorios iguales o similares a los del segundo. Si los números producidos por los algoritmos coinciden exactamente, el número resultante sería 0, lo que no es muy seguro. Mientras los algoritmos sean lo suficientemente diferentes, esta dificultad probablemente no debería ocurrir. Doy la bienvenida a más discusión sobre esto.