¿Por qué necesitamos números "perfectamente" aleatorios?

Question

Periódicamente veo artículos sobre físicos u otras personas que han dado con una técnica que genera un número ligeramente más aleatorio de lo que era posible antes, y cómo esto es útil para el cifrado. Pero nunca he visto una explicación de por qué necesitamos números aleatorios tan increíblemente "perfectos". Entiendo que rand() es pseudoaleatorio, pero si lo siembro con alguna combinación del tiempo del sistema, el tiempo de ping recién medido a algún servidor en el otro lado del mundo, y el hash del 217º artículo más popular en Google News en este momento, ¿no es el resultado aleatorio para todos los propósitos prácticos (particularmente si quien está tratando de adivinar el número no tiene el algoritmo)?

Aunque se conozca el algoritmo, parece que se podrían añadir suficientes variables que varíen en el tiempo y en la ubicación (como he intentado mostrar en mi ejemplo) para que sea imposible recrearlo en la vida real, independientemente de la potencia de cálculo que se tenga.

Entonces, ¿por qué necesitamos cada vez más números aleatorios "puros"?

Answer 1

Hay una diferencia entre aleatorizar la semilla (que es lo que describes arriba) y que la secuencia resultante sea aleatoria. Además, estos temas con buenos generadores de números aleatorios no es para evitar que otras personas adivinen los números (a menos que tal vez en ciertas cuestiones con la criptografía). Más bien, tiene que ver con, por ejemplo, los algoritmos que emplean la aleatoriedad. En muchas situaciones puede mejorar mucho un algoritmo si los cálculos incluyen algunos componentes aleatorios. Cuando se analizan y diseñan estos algoritmos, se suele considerar que el componente aleatorio tiene una determinada distribución, digamos gaussiana. La distribución particular de cada componente aleatorio puede afectar tanto a la validez del algoritmo como a su eficiencia. Supongamos, por ejemplo, que un determinado algoritmo produce el resultado correcto con una probabilidad de 0,999999 si su componente aleatoria es precisamente normalmente distribuido con tales y tales parámetros. Si el componente aleatorio difiere de la distribución normal, el comportamiento del algoritmo puede diferir significativamente de esa probabilidad. Así que ahora, cuando se ejecuta el algoritmo es necesario generar el tipo correcto de aleatoriedad. Cuanto mejor sea el generador de números aleatorios, mejores serán los resultados.

Answer 2

Aunque se conozca el algoritmo, parece que se podrían añadir suficientes variables que varíen en el tiempo y en la ubicación (como he intentado mostrar en mi ejemplo) para que sea imposible recrearlo en la vida real, independientemente de la potencia de cálculo que se tenga.

Su ejemplo utilizó

• la hora del sistema,
• el tiempo de ping recién medido a algún servidor del otro lado del mundo,
• el hash del 217º artículo más popular en Google News a partir de este segundo

Sin embargo, la criptografía pretende encontrar esquemas que le proporcionen seguridad contra un atacante que pueda espiar su conexión a Internet . Este atacante puede conocer tus tres entradas con un número de opciones lo suficientemente pequeño como para forzar el resultado. Sabe qué hora es, puede ver los paquetes que envías y recibes y medir los tiempos de ping tan bien como tú mismo, y puede leer la respuesta que obtienes de Google para ver qué artículo dice ser el 217º más popular.

Si usas HTTPS para hablar con Google, es un poco más difícil para el atacante ver a qué artículo apuntas, pero (a) la seguridad de HTTPS depende críticamente de ti ya tener una fuente segura de números aleatorios; (b) de todos modos, el atacante podría consultar Google News por su cuenta y probar todos los 1000 primeros artículos con la esperanza de que alguno de ellos hubiera sido el 217 de la respuesta obtenida.

Answer 3

Creo que hay algo fundamentalmente interesante en la desafío de crear un pequeño sistema con un estado interno finito que sea capaz de producir un flujo de salida que

1. Parece ser independiente, idénticamente distribuido
2. No es periódica ni se repite y no puede ser comprimida por los algoritmos normales
3. Tiene la mayor entropía posible (cuando el estado es desconocido), y es impredecible
4. No se puede predecir la longitud de su salida

No es precisamente trivial hacer un sistema de este tipo, pero tampoco es tan difícil hacerlo bastante bien.

Lo que más me fascina es que tales complejidad aparente es posible a partir de unas pocas líneas de código informático.

En cierto modo, es similar a la exigencia de trituradores de átomos que funcionan a energías cada vez más altas, o Detectores de CMB que sean cada vez más sensibles: si haces usos cada vez más finos de los números aleatorios como parte de experimentos complicados, querrás eliminar en lo posible la posibilidad de que los pequeños efectos que buscas detectar se deban a un artefacto de tu sistema, y en el caso de usar números aleatorios para ayudar a las simulaciones querrás que se comporten de forma tan aleatoria que sea como si la naturaleza estuviera creando la simulación por ti. A continuación, prueba las partes del experimento que te interesan.

Algo increíblemente genial es que, si es posible crear un gran subconjunto de todos los mensajes posibles utilizando estos generadores de números aleatorios que operan a partir de un pequeño estado finito, ¿no sería posible algún día encontrar el estado que genera cualquier secuencia posible, digamos la secuencia de bits de un vídeo?

La compresión hasta la tupla de un estado pequeño y un algoritmo concreto elegido de una familia de algoritmos podría superar el ahorro indicado por los cálculos de entropía basados en la distribución de símbolos, ya que es posible crear secuencias de muchos megabytes de longitud que, basándose en su distribución de símbolos, tengan la máxima entropía y, sin embargo, se hayan creado con 64 bits de estado y unas pocas líneas de código informático.

Éstas son algunas de las razones por las que creo que los números aleatorios son geniales y por las que buscar mejores formas de crearlos, o mejores formas de entender las formas en que los creamos es impresionante.

Tal vez la mejor analogía para explicar por qué esta es una búsqueda muy interesante es que la salida de estos generadores es realmente una metáfora del universo en su conjunto ( o al menos, de lo que esperanza el universo es como ) : un sistema de inmensa complejidad aparente, pero con un estado interno que podemos intentar medir cada vez más y unas reglas que podemos esperar deducir.

Answer 4

Este wiki artículo debería ser útil.

Donde dice:

Los números verdaderamente aleatorios son absolutamente necesarios para garantizar la seguridad teórica proporcionada por el almohadilla de un solo uso - el único algoritmo de encriptación indescifrable. Además, esas secuencias aleatorias no pueden ser reutilizadas y nunca deben estar disponibles para ningún atacante, lo que implica un generador continuamente operable. Véase Venona para un ejemplo de lo que ocurre cuando se violan estos requisitos violados cuando se utiliza una almohadilla de un solo uso.

y:

Dado que un requisito de la criptografía es la alta entropía (es decir imprevisible para un atacante), cualquier secuencia aleatoria publicada es una una mala elección, al igual que las secuencias de los dígitos de un número irracional irracional como el φ o incluso en números trascendentales como π, o e. Todas están disponibles para un atacante emprendedor. Dicho de otro modo, en criptografía, las secuencias de bits aleatorias deben ser no sólo aleatorias, sino también secreto y, por tanto, imprevisible. Las fuentes públicas o de terceros de o valores aleatorios calculados a partir de fenómenos observables públicamente observables públicamente (el tiempo, los resultados de los partidos deportivos, los precios de las acciones), casi nunca son nunca son aceptables desde el punto de vista criptográfico, aunque a menudo son tentadoras y demasiado a menudo se utilizan por los incautos. Permiten ataques más fáciles que atacar la criptografía. Dado que la mayoría de las aplicaciones criptográficas requieren unos pocos miles de bits como máximo, los generadores de números aleatorios lentos sirven bien si son realmente aleatorios. Este uso de generadores aleatorios es importante; muchos observadores informados creen que cada ordenador debería tener una forma de generar verdaderos números aleatorios.

Answer 5

También se utilizan números aleatorios para el Método Monte Carlo :

Los métodos de Montecarlo (o experimentos de Montecarlo) son una amplia clase de algoritmos computacionales que se basan en el muestreo aleatorio para obtener resultados numéricos. Suelen utilizarse en problemas físicos y matemáticos y son los más adecuados para ser aplicados cuando es imposible obtener una expresión de forma cerrada o es inviable aplicar un algoritmo determinista. Los métodos de Montecarlo se utilizan principalmente en tres problemas distintos: la optimización, la integración numérica y la generación de muestras a partir de una distribución de probabilidad.

Tenga en cuenta que los métodos de Monte Carlo utilizan grandes cantidades de números aleatorios que siguen determinadas distribuciones. Intentar obtener unos pocos megabytes de números aleatorios utilizando el escenario propuesto en la pregunta anterior dará como resultado números aleatorios que "no son suficientemente aleatorios".

Quizás también quiera leer sobre quasirandom números y en pseudoaleatorio números.