números aleatorios más sabrosos si un poco de pimientaCombinaremos teoría con práctica: mostraremos que es posible mejorar la entropía de secuencias aleatorias, después de lo cual veremos los códigos fuente que hacen esto.
Realmente quería escribir sobre el hecho de que la generación de números aleatorios de alta calidad, es decir, altamente entrópica, es crítica para resolver una gran cantidad de problemas, pero esto probablemente sea superfluo. Espero que todos lo sepan muy bien.
En la búsqueda de números aleatorios de calidad, las personas inventan dispositivos muy ingeniosos (ver, por ejemplo,
aquí y
aquí ). En principio, hay buenas fuentes de aleatoriedad integradas en la API de los sistemas operativos, pero esto es un asunto serio y nos come un poco de duda: ¿es el RNG que uso lo suficientemente bueno y está estropeado ... digamos, por terceros?
Un poco de teoría
Para empezar, mostramos que con el enfoque correcto, la calidad del RNG existente no puede degradarse. El enfoque correcto más simple es superponer cualquier otra secuencia a través de la operación XOR en la secuencia
principal .
La secuencia
principal puede ser, por ejemplo, un RNG sistémico, que ya consideramos bueno, pero todavía hay algunas dudas, y teníamos el deseo de ir a lo seguro.
Una secuencia
adicional puede ser, por ejemplo, un generador de números pseudoaleatorio, cuya salida se ve bien, pero sabemos que su entropía real es muy baja.
La secuencia
resultante será el resultado de aplicar la operación XOR a los bits de las secuencias primaria y secundaria.
Un matiz significativo: las secuencias primaria y secundaria deben ser independientes entre sí. Es decir, su entropía debe tomarse de fuentes fundamentalmente diferentes, cuya interdependencia no puede calcularse.
Denote por
x el siguiente bit de la secuencia principal, e
y - el bit correspondiente de la secuencia adicional. El bit de la secuencia resultante se denota por
r :
r = x⊕y
El primer intento de probar. Intentemos pasar por la entropía informativa de
x ,
y y
r . Denotamos la probabilidad de cero
x como
p x0 , y la probabilidad de cero
y como
p y0 . Las entropías de información
x e
y se calculan según la fórmula de Shannon:
H
x = - (p
x0 log
2 p
x0 + (1 - p
x0 ) log
2 (1 - p
x0 ))
H
y = - (p
y0 log
2 p
y0 + (1 - p
y0 ) log
2 (1 - p
y0 ))
El cero en la secuencia resultante aparece cuando hay dos ceros o dos unidades en la entrada. Probabilidad de cero r:
p
r0 = p
x0 p
y0 + (1 - p
x0 ) (1 - p
y0 )
H
r = - (p
r0 log
2 p
r0 + (1 - p
r0 ) log
2 (1 - p
r0 ))
Para probar la invariabilidad de la secuencia principal, es necesario demostrar que
Hr - Hx ≥ 0 para cualquier valor de
p x0 y
p y0 . No pude probarlo analíticamente, pero el cálculo visualizado muestra que el aumento de la entropía forma una superficie lisa, que no va a ir a menos en ninguna parte:
Por ejemplo, si agregamos una señal adicional muy sesgada con
p y0 = 0.1 a la señal principal sesgada c
p x0 = 0.3 (entropía 0.881), obtenemos el resultado
p r0 = 0.66 con entropía 0.925.
Entonces, la entropía no se puede estropear, pero esto aún no es exacto. Por lo tanto, se necesita un segundo intento. Sin embargo, a través de la entropía también se puede probar. Esquema (todos los pasos son bastante simples, puedes hacerlo tú mismo):
- Probamos que la entropía tiene un máximo en el punto p 0 = 1/2.
- Demostramos que para cualquier p x0 y p y0, el valor de p r0 no puede estar más lejos de 1/2 que p x0 .
El segundo intento de probar. A través de la capacidad de adivinar. Supongamos que un atacante a priori tiene alguna información sobre las secuencias primaria y secundaria. La posesión de información se expresa en la capacidad con cierta probabilidad de adivinar de antemano los valores de
x ,
y y, como resultado,
r . Las probabilidades de adivinar
x e
y se denotan por
g x y
g y , respectivamente (de la palabra adivinar). El bit de la secuencia resultante se adivina cuando ambos valores se adivinan correctamente o cuando ambos son incorrectos, por lo que la probabilidad de adivinar es la siguiente:
g
r = g
x g
y + (1 - g
x ) (1 - g
y ) = 2 g
x g
y - g
x - g
y + 1
Cuando tenemos el adivinador perfecto, tenemos
g = 1. Si no sabemos nada,
g es ... no, no cero, sino 1/2. Esta es exactamente la probabilidad de adivinar que resulta si tomamos una decisión lanzando una moneda. Un caso muy interesante es cuando
g <1/2. Por un lado, un adivinador de este tipo en algún lugar dentro de sí mismo tiene datos sobre el valor predicho, pero por alguna razón invierte su producción, y por lo tanto la
moneda empeora . Recuerde la frase "peor que una moneda", nos será útil a continuación. Desde el punto de vista de la teoría matemática de la comunicación (y, como resultado, la teoría cuantitativa de la información que nos es familiar), esta situación es absurda, ya que no será una teoría de la información, sino una teoría de la desinformación, pero en la vida tenemos esta situación mucho más a menudo de lo que nos gustaría .
Considere los casos limitantes:
- g x = 1 , es decir, la secuencia x es completamente predecible:
g r = g x g y + (1 - g x ) (1 - g y ) = 1 g y + (1−1) (1 - g y ) = g y
Es decir, la probabilidad de adivinar el resultado es igual a la probabilidad de adivinar la secuencia adicional. - g y = 1 : similar a la anterior. La probabilidad de adivinar el resultado es igual a la probabilidad de adivinar la secuencia principal.
- g x = 1/2 , es decir, la secuencia x es completamente impredecible:
g r = 2 g x g y - g x - g y + 1 = 2/2 g y - 1/2 - g y +1 = g y - g y + 1/2 = 1/2
Es decir, la adición de cualquier secuencia adicional no perjudica la imprevisibilidad completa de la principal. - g y = 1/2 : similar a la anterior. Agregar una secuencia extra completamente impredecible hace que el resultado sea completamente impredecible.
Para demostrar que agregar una secuencia adicional a la principal no ayudará al atacante, necesitamos descubrir en qué condiciones
g r puede ser mayor que
g x , es decir
2 g
x g
y - g
x - g
y + 1> g
xMueva g
x desde el lado derecho hacia la izquierda, y g
y y 1 hacia la derecha:
2 g
x g
y - g
x - g
x > g
y - 1
2 g
x g
y - 2 g
x > g
y - 1
Sacamos del lado izquierdo 2g
x entre paréntesis:
2 g
x (g
y - 1)> g
y - 1
Como tenemos g
y menos de uno (el caso límite cuando g
y = 1, ya lo hemos considerado), convertimos g
y −1 en 1 - g
y , sin olvidar cambiar “más” a “menos”:
2 g
x (1 - g
y ) <1 - g
yReduzca "1 - g
y " y obtenga la condición bajo la cual agregar una secuencia adicional mejorará la situación para que el atacante adivine:
2 g
x <1
g
x <1/2
Es decir,
g r puede ser mayor que
g x solo cuando se adivina que la secuencia principal es
peor que una moneda . Entonces, cuando nuestro predictor se dedica al sabotaje consciente.
Algunas consideraciones adicionales sobre la entropía.- La entropía es un concepto extremadamente mitológico. Información - incluida. Esto es muy perturbador. A menudo, la entropía informativa se representa como un tipo de materia sutil que está presente objetivamente en los datos o no. De hecho, la entropía informativa no es algo que está presente en la señal en sí, sino una evaluación cuantitativa de la conciencia a priori del destinatario del mensaje con respecto al mensaje en sí. Es decir, no se trata solo de la señal, sino también del destinatario. Si el receptor no sabe nada de la señal de antemano, la entropía informativa de la unidad binaria transmitida es exactamente de 1 bit, independientemente de cómo se recibió la señal y de qué se trata.
- Tenemos un teorema de adición de entropía según el cual la entropía total de fuentes independientes es igual a la suma de las entropías de estas fuentes. Si combinamos la secuencia principal con la secuencia adicional mediante concatenación, habríamos conservado las entropías de las fuentes, pero habríamos tenido un mal resultado, porque en nuestra tarea no debemos evaluar la entropía total, sino la específica, en términos de un bit separado. La concatenación de fuentes nos da la entropía específica del resultado igual a la media aritmética de la entropía de las fuentes, y la secuencia adicional débil de entropía empeora naturalmente el resultado. La aplicación de la operación XOR lleva al hecho de que perdemos parte de la entropía, pero tenemos la garantía de que la entropía resultante no es peor que la entropía máxima de los términos.
- Los criptógrafos tienen un dogma: usar generadores de números pseudoaleatorios es una arrogancia imperdonable. Porque estos generadores tienen una pequeña entropía específica. Pero acabamos de descubrir que si todo se hace bien, la entropía se convierte en un barril de miel que no puede estropearse con ninguna cantidad de alquitrán.
- Si solo tenemos 10 bytes de entropía real, distribuidos en un kilobyte de datos, desde un punto de vista formal solo tenemos el 1% de entropía específica, lo cual es muy malo. Pero si estos 10 bytes están manchados cualitativamente, y aparte de la fuerza bruta, no hay forma de calcular estos 10 bytes, todo no se ve tan mal. 10 bytes son 2 80 , y si nuestra fuerza bruta por segundo busca entre un billón de opciones, necesitaremos un promedio de 19 mil años para aprender a adivinar el próximo personaje.
Como se mencionó anteriormente, la entropía informativa es un valor relativo. Donde, para un sujeto, la entropía específica es 1, para otro puede ser 0. Además, uno con 1 puede no tener ninguna forma de conocer el verdadero estado de cosas. El sistema RNG produce un flujo indistinguible para nosotros de verdaderamente aleatorio, pero solo podemos esperar que sea realmente aleatorio
para todos . Y cree Si la paranoia sugiere que la calidad del RNG principal puede ser repentinamente insatisfactoria, tiene sentido cubrirse con la ayuda de uno adicional.
Implementando un RNG sumador en Python
from random import Random, SystemRandom from random import BPF as _BPF, RECIP_BPF as _RECIP_BPF from functools import reduce as _reduce from operator import xor as _xor class CompoundRandom(SystemRandom): def __new__(cls, *sources): """Positional arguments must be descendants of Random""" if not all(isinstance(src, Random) for src in sources): raise TypeError("all the sources must be descendants of Random") return super().__new__(cls) def __init__(self, *sources): """Positional arguments must be descendants of Random""" self.sources = sources super().__init__() def getrandbits(self, k): """getrandbits(k) -> x. Generates an int with k random bits."""
Ejemplo de uso:
>>> import random_xe
SystemRandom, que se considera correcto, se toma como la transmisión principal y como una transmisión secundaria: el PRNG Random estándar. El punto en esto, por supuesto, no es mucho. El PRNG estándar definitivamente no es el tipo de suplemento para el que valió la pena comenzar. En cambio, puedes unir dos RNG sistémicos:
>>> myrandom2 = random_xe.CompoundRandom(SystemRandom(), SystemRandom())
El sentido, la verdad en esto es aún menor (aunque por alguna razón Bruce Schneier recomienda esta técnica en Criptografía Aplicada por alguna razón), porque los cálculos anteriores son válidos solo para fuentes independientes. Si el sistema RNG se ve comprometido, el resultado también se verá comprometido. En principio, el vuelo de fantasía en la búsqueda de una fuente de entropía adicional no está limitado por nada (en nuestro mundo, el desorden es mucho más común que el orden), pero como una solución simple ofreceré el PRSP de HashRandom, también implementado en la biblioteca random_xe.
PRSP basados en la transmisión de hashing circular
En el caso más simple, puede tomar una cantidad relativamente pequeña de datos iniciales (por ejemplo, pedirle al usuario que toque el teclado), calcular su hash y luego agregar cíclicamente el hash a la entrada del algoritmo de hash y tomar los siguientes hash. Esquemáticamente, esto se puede representar de la siguiente manera:
La fuerza criptográfica de este proceso se basa en dos supuestos:
- La tarea de restaurar los datos originales del valor hash es insoportablemente complicada.
- Usando el valor hash, es imposible restaurar el estado interno del algoritmo hash.
Después de consultar con un paranoico interno, reconoció la segunda suposición como innecesaria y, por lo tanto, en la implementación final del PRNG, el esquema es un poco complicado:
Ahora, si un atacante logra obtener un valor "Hash 1r", no podrá calcular el valor "Hash 2r" que le sigue, ya que no tiene un valor "Hash 2h" que no pueda reconocer sin calcular la función hash "contra lana". Por lo tanto, la fuerza criptográfica de este esquema corresponde a la fuerza criptográfica del algoritmo de hash utilizado.
Ejemplo de uso:
>>>
Por defecto, se utiliza el algoritmo SHA-256. Si desea algo más, puede transferir el tipo deseado de algoritmo de hash al constructor con el segundo parámetro. Por ejemplo, hagamos un RNG compuesto, resumiendo lo siguiente en un montón:
1. RNG sistémico (esto es sagrado).
2. Entrada del usuario procesada por el algoritmo SHA3-512.
3. El tiempo empleado en esta entrada procesada por SHA-256.
>>> from getpass import getpass >>> from time import perf_counter >>> from hashlib import sha3_512
Conclusiones:- Si no estamos seguros de nuestro generador de números aleatorios, podemos resolver este problema de manera fácil y sorprendente.
- Resolviendo este problema, no podemos hacerlo peor. Solo mejor. Y está matemáticamente probado.
- No debemos olvidar tratar de asegurarnos de que las fuentes de entropía utilizadas sean independientes.
Las fuentes de la biblioteca están en
GitHub .