elparaiso.mat.uned.es

¡Pulsa Aquí!

LO DIJO...

Albert Einstein  
 
La mayor parte de las ideas fundamentales de la ciencia son esencialmente sencillas y, por regla general, pueden ser expresadas en un lenguaje comprensible para todos.
 
El Paraíso de las Matemáticas - Criptotaller ~ Números pseudoaleatorios
.: Criptotaller :.
Números pseudoaleatorios

Motivación

    En algunos casos necesitamos más bits aleatorios que los que pueden proporcionarnos nuestras fuentes de entropía tal y como discutíamos en el anterior artículo. En estos casos se recurre a los generadores de números (o bits) pseudoaleatorios (las siglas inglesas son PRNG= pseudo random number generator) que constituyen en definitiva una forma de expandir unos pocos bits realmente aleatorios.

Definiciones

    Un PRNG es una función que toma cierta cantidad de verdadera aleatoriedad (llamada semilla del generador) y genera una secuencia de bits que pueden usarse como si fuesen auténticos números aleatorios, suponiendo que el adversario tiene una cantidad limitada de recursos computacionales y que la semilla es suficientemente grande como para frustrar ataques por fuerza bruta.

    La mayoría de los lenguajes de programación (C, Pascal, BASIC, Fortran...) disponen de funciones para generar números pseudoaleatorios que a menudo satisfacen criterios estadísticos de aleatoriedad pero no son suficientes para utilizar en criptografía. La razón principal es que cuando se ve comprometido uno de los valores inmediatamente se conocen todos los anteriores y posteriores de la secuencia. Un PRNG criptográficamente fuerte en cambio, es un algoritmo del que se ha probado que un oponente que conozca el algoritmo y todos los bits generados hasta cierto punto - pero no la semilla- no puede adivinar el siguiente bit que será generado con probabilidad mayor que 1/2+e donde e suele decrecer exponencialmente de acuerdo con cierto parámetro s que típicamente sería la longitud de la semilla.

Utilización

    Si se elige no usar un PRNG criptográficamente fuerte como modo de expandir una semilla de auténticos números aleatorios hay algunas técnicas que pueden servir en la mayoría de los casos. La utilización descuidada de estos métodos puede producir una reducción catastrófica de la seguridad, en especial debemos prestar atención a no usar una semilla demasiado pequeña o formada por pocos bits realmente aleatorios. Por ejemplo y como ya se hizo notar en otro sitio, la utilización -habitual- de la fecha y hora del sistema sólo proporciona unos pocos bits aleatorios aunque aparentemente y a través del uso de una función hash estemos utilizando 128 o 160 bits.

    Estas técnicas se resumirían en que una función trampa enmascare algunas operaciones fácilmente predecibles y por tanto débiles. La operación podría consistir simplemente en contar o en el uso de un generador de período largo. Algunas combinaciones comunes son:

Una función hash criptográficamente fuerte como MD5 o SHA operando sobre una semilla de auténticos números aleatorios concatenada con un contador que se incrementa en cada paso.

Un algoritmo de cifrado fuerte usando una clave para cifrar una secuencia generada por un generador de periodo suficientemente largo que ha sido inicializado con un verdadero número aleatorio. Por ejemplo podría usarse un generador aditivo de Marsaglia para alimentar un algoritmo triple- DES en modo CBC.

El cifrado de un contador con una clave realmente aleatoria. Se debe tener la precaución de usar un modo CBC y/o usar sólo una fracción del bloque de salida, de otro modo la secuencia de salida se reconocería como no aleatoria al cabo de un número de bits del orden de la raíz cuadrada del período del contador.

    Presumiblemente, predecir valores de una secuencia generada usando una de estas técnicas equivale a romper el algoritmo de cifrado utilizado o a invertir la función hash (que se supone no invertible). Cuanta menos información se revele en cada iteración, tanto más difícil será para el adversario predecir futuros valores. Por ello a menudo se emplea un solo bit de la salida.

    Resumiendo: en general un modo correcto de uso implica empezar con una semilla fuerte, auténticamente aleatoria, realizar uno o más pasos criptográficamente sólidos a partir de dicha semilla y no revelar el estado completo del generador en cada elemento de la secuencia de salida. Naturalmente, si cada valor de la secuencia puede calcularse de forma fija a partir del valor anterior, entonces cuando un sólo valor de la secuencia se ve comprometido, todos los futuros valores pueden ser determinados.

Cosas que debemos evitar

    Algunos errores frecuentes para los interesados en diseñar su propio PRNG o mejorar algunos de los ya existentes:

Sistemas caóticos: existe bastante confusión entre lo que parece complejo para las personas y lo realmente aleatorio.

Generadores aleatorios de las librerías matemáticas: este tipo de generadores es apto para, por ejemplo, simulación pero no son criptográficamente fuertes.

Generadores congruenciales lineales: los más simples y posiblemente peores de los generadores de librería matemática.

Chain adittion (adición en cadena) otro PRNG que se "rompe" con facilidad.

CDROMs, CDs de audio o cintas: El material grabado tiene un gran volumen de bits que a veces se confunde con la aleatoriedad. Sin embargo, el número de bits necesarios para indexar todas las grabaciones existentes en el mundo es suficientemente pequeño como para ser adivinado por fuerza bruta.

Usenet: de nuevo el mismo error anterior. Además las news son públicas y accesibles por cualquier adversario.

E-mail: podría ser una fuente si estuviera tan bien cifrado que el adversario no pueda leerlo pero nunca estamos seguros de lo que el adversario ha visto realmente. Para los textos ingleses utilizados como fuente de entropía, Shannon estima un bit de entropía por carácter como máximo.

Algunos ejemplos de PRNG

El generador lineal congruencial

    Ponemos como ejemplo este generador porque es uno de los más difundidos siendo a la vez uno de los más débiles y no apto para uso criptográfico. Se utiliza en la mayoría de las funciones rand() y similares.

    La forma general de es: Xi+1=(a.Xi + b ) mod m donde X0 sería la semilla del generador. La salida suele ser el número Xi/m, un número en coma flotante en el intervalo [0,1).

    Algunas propiedades de estos generadores:

1.- El módulo m es una cota superior del número de valores diferentes que puede tomar la semilla.

2.- Si Xi vuelve a tomar el valor de la semilla inicial la secuencia se repetirá cíclicamente.

3.- Todas las secuencias producidas por este tipo de generador si se prolongan lo suficiente (periodo) acaban en un ciclo que se repite indefinidamente.

    Un buen generador lineal tendrá un periodo tan largo como sea posible (es decir m). Este máximo se alcanza si y sólo si se cumplen las tres siguientes condiciones [Knuth]

a) b es primo con m

b) a-1 es múltiplo de p para todo primo p que divida a m

c) a-1 es múltiplo de 4 siempre que m sea múltiplo de 4

    Habitualmente se toma como m una potencia de 2 más de 1 de modo que se puede coger por ejemplo b=1 y a un número impar.

    No sólo este tipo de generador sino todos los de tipo polinómico congruencial, es decir:

x= (anxn + ... + a1x + a0) mod m

son predecibles y por tanto inútiles para cualquier cifrado serio.

El generador ANSI X9.17

    Este generador esta pensado como mecanismo para generar claves DES y vectores de inicialización, usando triple- DES como primitiva (podría usarse otro algoritmo de cifrado de bloques). También es ampliamente usado en banca y otras aplicaciones.

1.- K es una clave secreta para triple DES generada de algún modo en el momento de la inicialización. Debe ser aleatoria y usada sólo para este generador. Es parte del estado secreto del PRNG y nunca varía con las entradas.

2.- Cada vez que se desee una salida se hace lo siguiente a) Ti = EK(timestamp)

b) salida[i]= EK(Ti xor semilla[i])
c) semilla[i+1]= EK(Ti xor salida[i])

Existe una variación en Crypto++ la librería de Wei Dai implementada como sigue:

a) Ti = EK(Ti-1 xor timestamp)
b) salida[i]= EK(Ti xor semilla[i])
c) semilla[i+1]= EK(Tii xor salida[i])
    Esto supone encriptar los 'timestamp' en modo CBC en lugar del modo ECB que utiliza el generador X9.17 estándar. El 'timestamp' se basa en el uso de la CPU del programa y su resolución depende de la plataforma utilizada, por ejemplo en Linux tiene una resolución de 0.01 segundos.

El generador de DSA

    DSA (Digital Signature Standard) describe un PRNG basado en SHA pensado para generar parámetros pseudoaleatorios para el algoritmo de firmas DSA. Este generador permite entradas opcionales del usuario Wi mientras se generan las claves. De otro modo el PRNG nunca se recobraría de un estado interno comprometido. Toda la aritmética se puede realizar en módulo 2N donde 160<= N <= 512.

1.- El generador mantiene un estado interno Xi que varía constantemente.
2.- El generador admite una entrada opcional Wi, se asumirá que es cero cuando no se produzca.

3.- Cada salida se produce de la siguiente manera:

a) salida[i]= hash(Wi + Xi mod 2160)
b) Xi+1= Xi + salida[i] + 1 mod 2160

El generador RSAREF

    Este PRNG se basa en dos operaciones: hash con MD5 y adición módulo 2128 con un diseño relativamente simple. Consiste en lo siguiente:

1.- Un contador de 128 bits Ci

2.- Un método de procesar entradas Xi que hace lo siguiente
Ci+1= Ci + MD5(Xi) mod 2128

3.- Un método de producir salidas así:

a) salida[i]= MD5(Ci) mod 2128
b) Ci+1= Ci+1 mod 2128
El generador de Cryptolib

    Cryptolib es una librería criptográfica desarrollada por Lacy, Mitchell, Schnell y Blaze. La fuente principal de aleatoriedad de esta librería es TrueRand un mecanismo para extraer valores presumiblemente impredecibles a partir de los sesgos existentes entre diferentes relojes del sistema. Estos valores pueden ser utilizados directamente (no se recomienda utilizar más de 16 bits de cada palabra de 32) o ser usados para alimentar los dos PRNG disponibles: fsrRand y desRand.

fsrRand posee un estado secreto consistente en una clave DES que llamaremos K y un array de siete valores de 32 bits, X0... X6, organizados como un registro de desplazamiento (shift register). Cada vez que se requiere una salida, dos de los valores de 32 bits se concatenan formando un número de 64 bits. Este número se cifra con DES usando K. El resultado se divide en dos mitades de 32 bits, se realiza un XOR con una de ellas y uno de los valores de 32 bits modificando así uno de los registros, mientras que la otra mitad es la salida del algoritmo. Se desplaza entonces el registro de modo que se utilizan dos nuevos valores cada vez que se produce una nueva salida.

desRand posee un estado secreto consistente en un contador C de 64 bits, una clave secreta de triple DES que llamamos K un prefijo secreto de 20 bits, P, y un sufijo secreto de 20 bits, S. Cada nueva salida de 32 bits se produce de la siguiente manera:

1.- Usar la función hash SHA1 para calcular hash(P,C,S)

2.- Con triple- DES se calcula EK(C)

3.- Se hace un XOR de los bits de mayor peso del valor hash con el resultado del cifrado, se ofrecen como salida los cuatro bytes de mayor peso de dicho número.

4.- C=C+1

El generador Blum Blum Shub

    Este generador que suele piadosamente abreviarse BBS es el que actualmente tiene una prueba más sólida de fortaleza. Es también muy simple, se basa en residuos cuadráticos y su única desventaja es que requiere bastante cálculos en comparación con otros generadores clásicos.

    Se empieza eligiendo dos grandes primos p y q que al ser divididos entre 4 den resto 3. Sea n el producto de p por q. Se elige entonces un número aleatorio x primo con n. La semilla inicial para el generador y el método de calcular los siguientes valores de la secuencia son:

S0=x2 mod n
Si+1=Si2 mod n

    Deben emplearse sólo unos pocos bits del final de cada Si. Siempre es seguro utilizar solamente el bit menos significativo. Si se usan no más de log2(log2 Si) de los bits de menos peso, se demuestra que predecir bits adicionales es tan difícil como la factorización de n, un problema tenido por intratable actualmente y base de métodos tan sólidos como RSA.

    Otro detalle interesante de este generador es que se puede calcular directamente cualquier valor Si sin tener que calcular los anteriores. En concreto:

    Esto significa que en aplicaciones que generan muchas claves de esta manera, no es necesario almacenarlas todas, cada clave puede ser reconstruida a partir de su índice y los S y n iniciales.

Generadores de G. Marsaglia

    Coge aquí mismo una lista de generadores de números aleatorios pequeños y listos para usarse (lenguaje C) propuestos por el gurú George Marsaglia.

Referencias

  • Computer Generated Random Numbers, David W. Deley
  • RFC1750, Randomness Recommendations for Security, Estlake,Crocker & Schiller
  • Cryptoanalytic Attacks on Pseudorandom Number Generators, Kelsey, Schneier,Wagner & Hall (www.counterpane.com)
  • Randomness resources for Dr. Dobb's Journal readers, (www.cs.b erkeley.edu/~daw/netscape-randomness.html)

Area On-Line
  Todo tipo de material, para disfrutar de él completamente On-Line, sin necesidad de descargar archivos ni tener que andar descomprimiendo estos. No te olvides de pasar por el Diccionario, y las secciones Origami y Geointeractiva. Son de lo más interesante.

Criptotaller

Criptografía (clásica y moderna), criptoanálisis (primos, primos de Mersenne, etc.) y otras técnicas.

Material para descargar

Código Fuente C

Método Hill
Método Jefferson
Exponenciación Modular
Cálculo números primos
Test de Lucas-Lehmer
Factores num. Mersenne
Verificación FIPS 140.2
Teorema chino del resto
+ Códigos Fuente C

Código Fuente Python

Generación de claves

Artículos

La máquina Enigma
Criptografía y seguridad
    M. J. Lucena
Seguridad Informática
   y Criptografía PDF PPT
    J. Ramió
Criptografía clásica PDF
    J. Ramió

Programas
Cripto1 ZIP 2391 KB
    J. L. Rubio

Enlaces

Página personal de Jaime Suárez Martínez, colaborador de esta sección.

Munitions, colección de programas para Linux.

Kriptopolis, toda una referencia en castellano.

Ciphersaber

Criptonomicón: la página de Gonzalo Alvarez Marañón.

Página de Chris Caldwell, una página bien elaborada sobre números primos.

Colección de links de Peter Gutmann.

www.gnupg.org es la página original de GPG, un programa libre alternativo a PGP.

Domingo, 21 / 07 / 2019
   BUSCADOR
 

   TU CORREO
Usuario
Contraseña

   MATRACAS
Lista de correo gratuita
.: Chismes de Adán y Eva :.
Adios a Elisenda Fo...
WolframAlpha: El mo...
WIRIS para Mac...
Third CEU Summersch...
¡Más y más actualiz...
Cerca de 500 MB de ...
Ha llegado el momen...
WIRIS, matemáticas ...
El Universo Matemát...
Segundas Jornadas d...
Los Elementos de Eu...
VI Semana de la Cie...
Tras varios meses d...
¡Chiflados por los ...
Otro verano más, to...

 

Todos los derechos reservados. El Paraíso de las Matemáticas 2015Información Legal Política de PrivacidadAyudaEmail