Aleatoriedad y Pseudoaleatoriedad

La aleatoriedad es el alma de la criptografía —las claves, los nonces y los desafíos deben ser impredecibles— y la pseudoaleatoriedad permite que una semilla corta verdaderamente aleatoria se extienda en secuencias largas indistinguibles de las aleatorias para cualquier adversario eficiente.

Definition

La pseudoaleatoriedad es la propiedad de ser computacionalmente indistinguible de la aleatoriedad verdadera; un generador pseudoaleatorio expande determinísticamente una semilla aleatoria corta en una salida más larga que ningún algoritmo eficiente puede distinguir de la aleatoria.

Scope

Este tema abarca el papel de la aleatoriedad en la criptografía: los requisitos de las fuentes de entropía y los generadores de números aleatorios verdaderos, las definiciones y construcciones de generadores pseudoaleatorios y funciones pseudoaleatorias criptográficamente seguras, y las consecuencias catastróficas de una aleatoriedad débil o reutilizada. Aborda cómo los objetos pseudoaleatorios formalizan las primitivas simétricas. Excluye los cifrados específicos y los supuestos de dificultad, tratados en temas relacionados.

Core questions

• ¿Por qué la criptografía requiere una aleatoriedad impredecible y qué sale mal sin ella?
• ¿Qué distingue a un generador criptográficamente seguro de uno estadístico?
• ¿Cómo se puede extender una semilla corta verdaderamente aleatoria en una salida pseudoaleatoria larga?
• ¿Qué son las funciones y permutaciones pseudoaleatorias, y cómo modelan los cifrados?
• ¿Cómo se recolecta y acondiciona la entropía de alta calidad en sistemas reales?

Key concepts

• entropía y aleatoriedad verdadera
• generadores de números aleatorios
• generador pseudoaleatorio (PRG)
• función pseudoaleatoria (PRF)
• permutación pseudoaleatoria (PRP)
• indistinguibilidad computacional
• derivación de semillas y claves
• fallos por reutilización de aleatoriedad
• acondicionamiento de entropía

Key theories

Generadores pseudoaleatorios

Un generador pseudoaleatorio expande una semilla corta en una cadena más larga indistinguible de la aleatoriedad uniforme para cualquier discriminador eficiente; tales generadores existen si y solo si lo hacen las funciones unidireccionales, vinculando la pseudoaleatoriedad con los fundamentos de la criptografía.

Funciones y permutaciones pseudoaleatorias

Una familia de funciones pseudoaleatorias, construible a partir de cualquier generador pseudoaleatorio, es indistinguible de una función verdaderamente aleatoria para un adversario que la consulta; este objeto subyace al modelado de seguridad de los cifrados de bloque y los códigos de autenticación de mensajes.

Mechanisms

Un generador de números aleatorios verdadero recolecta entropía física (ruido térmico, fluctuación de tiempo), que se acondiciona y se utiliza para sembrar un generador pseudoaleatorio criptográficamente seguro que produce determinísticamente todos los bits de apariencia aleatoria que un sistema necesita. Las funciones pseudoaleatorias se construyen a partir de generadores (la construcción GGM) y modelan primitivas con clave; un cifrado de bloque se trata como una permutación pseudoaleatoria. Las definiciones de seguridad requieren que ningún adversario eficiente, dadas las salidas, pueda predecir bits adicionales o distinguirlos de los aleatorios.

Clinical relevance

Los fallos de aleatoriedad son una fuente recurrente de rupturas catastróficas en el mundo real: el error de Debian OpenSSL de 2008 paralizó la generación de claves, los nonces ECDSA predecibles filtraron claves privadas (Sony PlayStation 3, algunas carteras de Bitcoin), y la entropía débil de dispositivos embebidos produjo claves adivinables a escala. Por lo tanto, una aleatoriedad robusta —una recolección de entropía adecuada y generadores pseudoaleatorios verificados— es esencial para cada implementación criptográfica.

Evidence & guidelines

NIST SP 800-90A/B/C especifican generadores de bits aleatorios determinísticos aprobados, validación de fuentes de entropía y guía de construcción. La mejor práctica utiliza el RNG criptográfico verificado del sistema operativo (en lugar de crear uno propio), asegura suficiente entropía antes de generar claves y nunca reutiliza nonces. Los conjuntos de pruebas estadísticas ayudan a detectar fallos graves, pero no pueden establecer la fuerza criptográfica.

History

La teoría computacional de la pseudoaleatoriedad fue fundada por Blum y Micali y por Yao alrededor de 1982, definiendo la impredecibilidad y la indistinguibilidad. Goldreich, Goldwasser y Micali mostraron cómo construir funciones pseudoaleatorias a partir de generadores en 1986, y Hastad, Impagliazzo, Levin y Luby demostraron más tarde que los generadores pseudoaleatorios existen si lo hacen las funciones unidireccionales. Los repetidos desastres prácticos debidos a una aleatoriedad débil han mantenido la calidad de la entropía y del RNG como una preocupación central de la ingeniería.

Key figures

• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali
• Manuel Blum
• Andrew Yao

Seminal works

• goldreich1986
• goldreich2001
• katz2020

Frequently asked questions

¿Por qué no puedo usar una función aleatoria normal como rand() para criptografía?

Los generadores de números aleatorios ordinarios están construidos para la uniformidad estadística y la velocidad, no para la impredecibilidad; su salida puede predecirse a partir de unas pocas muestras. La criptografía necesita generadores cuya salida futura sea inviable de predecir incluso dada la salida pasada, lo que requiere un RNG criptográficamente seguro sembrado con entropía real.

¿Cuál es la diferencia entre aleatoriedad verdadera y pseudoaleatoriedad?

La aleatoriedad verdadera proviene de una fuente física e impredecible y su suministro es limitado. La pseudoaleatoriedad se genera determinísticamente a partir de una semilla corta verdaderamente aleatoria y puede producirse en grandes cantidades; solo necesita ser indistinguible de la aleatoriedad verdadera para cualquier adversario eficiente, lo cual es suficiente para el uso criptográfico.