La pseudoaleatoriedad mide el grado en que una secuencia de números, aunque producida por un proceso completamente determinista y repetible, parece no tener patrones . [1]
La aparente aleatoriedad del patrón es el quid de gran parte de la seguridad en línea y de otro tipo. [2] Dado que la secuencia es repetible, es importante que la semilla que, junto con un generador produce los números, se elija bien y se mantenga oculta. [3]
Historia
La generación de números aleatorios tiene muchos usos (principalmente en estadística , para muestreo aleatorio y simulación ). Antes de la informática moderna, los investigadores que requerían números aleatorios los generaban a través de varios medios ( dados , cartas , ruedas de ruleta , [4] etc.) o usaban tablas de números aleatorios existentes.
El primer intento de proporcionar a los investigadores un suministro listo de dígitos aleatorios fue en 1927, cuando Cambridge University Press publicó una tabla de 41.600 dígitos desarrollada por LHC Tippett . En 1947, RAND Corporation generó números mediante la simulación electrónica de una rueda de ruleta; [4] los resultados se publicaron finalmente en 1955 como Un millón de dígitos aleatorios con 100.000 desviaciones normales .
Impredecibilidad como "casi aleatorio"
Utilizando una sustancia radiactiva que arroja electrones y rayos gamma cuya desintegración es aleatoria, u obteniendo secuencias impredecibles de datos utilizando una radio sintonizada entre estaciones, la recolección del ruido atmosférico produce imprevisibilidad a corto plazo. [1] La inversión de tiempo necesaria para obtener estos números llevó a un compromiso: usar algunas de estas lecturas físicas como una "semilla" para generar más. Cuantos menos números "aleatorios" que no sean semilla, más verdaderamente aleatorios parecen. Un compromiso es mezclar los tiempos entre las pulsaciones de teclas de las personas. [5]
Se ha demostrado que las acciones de las personas son útiles para la repetibilidad detrás de la autenticación multifactor , [6] y los estudios del movimiento browniano han demostrado cómo las estadísticas y los modelos probabilísticos pueden predecir lo que hará un grupo, incluso si un movimiento en particular es aleatorio. [7]
La predictibilidad de las secuencias de números pseudoaleatorios producidas por un algoritmo determinista son, en grupos cortos, aparentemente aleatorias. [8]
En complejidad computacional
En la informática teórica , una distribución es pseudoaleatoria contra una clase de adversarios si ningún adversario de la clase puede distinguirla de la distribución uniforme con una ventaja significativa. [9] Esta noción de pseudoaleatoriedad se estudia en la teoría de la complejidad computacional y tiene aplicaciones en la criptografía .
Formalmente, sean S y T conjuntos finitos y F = { f : S → T } sea una clase de funciones. Una distribución D sobre S es ε- pseudoaleatoria contra F si para cada f en F , la distancia estadística entre las distribuciones f ( X ), donde X se toma como muestra de D , yf ( Y ), donde Y se toma como muestra de la distribución uniforme. en S , es como máximo ε.
En aplicaciones típicas, la clase F describe un modelo de computación con recursos acotados y uno está interesado en el diseño de las distribuciones D con ciertas propiedades que son pseudo contra F . La distribución D a menudo se especifica como la salida de un generador pseudoaleatorio . [10]
Ver también
Referencias
- ↑ a b George Johnson (12 de junio de 2001). "Los conocedores del caos ofrecen un producto valioso: la aleatoriedad" . The New York Times .
- ^ "Los defectos inherentes de Proof-of-Stake" .
- ^ Mark Ward (9 de agosto de 2015). "Los números aleatorios de Web son demasiado débiles, advierten los investigadores" . BBC .
- ^ a b "Un millón de dígitos aleatorios" . Corporación RAND . Consultado el 30 de marzo de 2017 .
- ^ Jonathan Knudson (enero de 1998). "Javatalk: herraduras, granadas de mano y números aleatorios". Sun servidor . págs. 16-17.
- ^ Eze Vidra (6 de noviembre de 2007). "¿Ciencia ficción? Autenticación biométrica de ClassifEye para teléfonos móviles" .
- ^ 1880,papel de Thorvald N. Thiele , usando mínimos cuadrados (la base del análisis de regresión)
- ^ SP Vadhan (2012). Pseudoaleatoriedad .
pseudoaleatoriedad, la teoría de la generación eficiente de objetos que "parecen aleatorios" a pesar de haber sido construidos con poca o ninguna aleatoriedad
- ^ Oded Goldreich. Complejidad computacional: una perspectiva conceptual. Prensa de la Universidad de Cambridge. 2008.
- ^ "Pseudoaleatoriedad" (PDF) .
Otras lecturas
- Donald E. Knuth (1997) El arte de la programación informática , Volumen 2: Algoritmos seminuméricos (3ª edición) . Addison-Wesley Profesional, ISBN 0-201-89684-2
- Oded Goldreich. (2008) Complejidad computacional: una perspectiva conceptual . Prensa de la Universidad de Cambridge. ISBN 978-0-521-88473-0 . [ página necesaria ] (vista previa limitada en Google Libros)
- Vadhan, SP (2012). "Pseudoaleatoriedad". Fundamentos y Tendencias en Informática Teórica . 7 (1-3): 1-336. doi : 10.1561 / 0400000010 .
enlaces externos
- HotBits: números aleatorios genuinos, generados por desintegración radiactiva
- Uso y creación de números aleatorios de calidad criptográfica
- En RFC 1750, el uso de secuencias de números pseudoaleatorios en criptografía se analiza en profundidad.