El azar en la Criptografía

• 24/03/2003
• Internacional

Tweet

Qué son los números aleatorios?

Las sucesiones de números o bits aleatorias son sucesiones de números o bits seleccionados al azar de forma uniforme, es decir, todo número o bit tiene la misma probabilidad de ser escogido. Formalmente se requiere que sean estadísticamente independientes e insesgados. El ejemplo clásico más utilizado para generarlos es el del lanzamiento repetitivo de una moneda ideal no trucada. Identificando 0 con cara y 1 con cruz, obtenemos una sucesión de bits aleatoria. Es indiferente hablar de números o de bits aleatorios, ya que agrupando bits obtenemos números y seleccionando determinados bits de los números obtenemos sucesiones de bits.

Existen otros dispositivos físicos de los que se supone que generan números aleatorios. Algunos de los que se consideran son la medida del ruido térmico de un diodo semiconductor o de una resistencia, o bien la medida de la inestabilidad en frecuencia de un oscilador libre.

¿Para qué sirven?

En la vida cotidiana se utilizan números aleatorios en situaciones tan dispares como pueden ser los juegos de azar o en el diseño de la caída de los copos de nieve en una animación por ordenador. El mundo tecnológico no está libre de su utilización y por ejemplo se utilizan en tests para localización de errores en chips. En la transmisión de datos desde un satélite también se utilizan números aleatorios. Su utilización en las finanzas es otra de las muchas aplicaciones.

En general cuando se requiere una impredecibilidad en unos determinados datos, se utilizan números aleatorios. Aquí es donde entra en juego la criptografía. Así en la telefonía móvil digital GSM se utilizan para la asignación de una clave aleatoria que sirve para autenticar al usuario o por ejemplo también se utilizan para dar cierta seguridad a la asignación inicial de números secretos a las tarjetas de crédito. Para muchos sistemas criptográficos, como pueden ser DES, RSA, DSA, la utilización de números aleatorios es vital para su seguridad.

En el campo de la Matemática Aplicada también se utilizan en ciertos procesos de Análisis Numérico, o en cualquier algoritmo que precise una elección aleatoria de un dato. Así, destaca el Método de Montecarlo con el que, por ejemplo se puede calcular una aproximación del número PI sólo lanzando aleatoriamente tiros sobre una diana inscrita en un cuadrado, como se puede observar en el experimento de la figura (puede obtenerse en www.iec.csic.es/criptonomicon/articulos/aleat.gif).

Este método se basa en el hecho que el área del círculo dividida por el área del cuadrado es PI/4 y a la vez coincide con el número de tiros acertados dividido entre el número de tiros lanzados (cuando el número de tiros es suficientemente grande). En este ejemplo después de lanzar 44 tiros aleatorios, se han obtenido 35 dentro de la diana que nos proporcionan una aproximación de PI/4 = 0,7954 (el valor exacto es PI/4 = 0,785398...). Con este mismo método se pueden calcular todo tipo de integrales definidas de forma aproximada. El Método de Montecarlo se utiliza en muchas simulaciones, como por ejemplo, en el estudio del paso de neutrones por una placa.

¿Qué son los números pseudoaleatorios?

Son unos números generados por medio de una función (determinista, no aleatoria) y que aparentan ser aleatorios. Estos números pseudoaleatorios se generan a partir de un valor inicial aplicando iterativamente la función. La sucesión de números pseudoaleatorios es sometida a diversos tests para medir hasta qué punto se asemeja a una sucesión aleatoria.

¿Por qué hay que recurrir a los números pseudoaleatorios?

Fundamentalmente porque las sucesiones de números pseudoaleatorios son más rápidas de generar que las de números aleatorios.

Los dos principales inconvenientes de las sucesiones de números pseudoaleatorios es que a partir de un mismo valor inicial se genera la misma sucesión y que, en general, la sucesión es periódica. Estos inconvenientes se solucionan escogiendo generadores con periodos largos. De todas maneras, en muchas aplicaciones son útiles estos defectos, ya que nos irá bien que la sucesión parezca aleatoria, pero a la vez conozcamos que los números se repiten periódicamente y cuál es la longitud del periodo. También cuando se quiere repetir un experimento en las mismas condiciones, nos interesará partir del mismo generador y con el mismo valor inicial.

¿Cómo se generan las sucesiones pseudoaleatorias?

Uno de los primeros métodos conocidos es debido a John von Neumann (1903-57). Una versión de este método consiste en partir de un número inicial de 10 cifras, elevarlo al cuadrado y seleccionar como nuevo número aleatorio las cinco 5 centrales. Siendo cautos en la elección del valor inicial e iterando el proceso se obtiene una sucesión de números pseudoaleatorios. Un método utilizado en criptografía muy relacionado con este último es el debido a L. Blum, M. Blum y M. Shub (1986). En este método la manera de iterar a partir de un valor inicial x(1) viene dada por la fórmula x(i+1) = x(i)^2 + mod (p*q), con p y q primos congruentes con 3 módulo 4. Una generalización es el llamado generador RSA dado por x(i+1) = x(i)^d + mod (p*q), con p, q primos y d un número que verifica que mcd(d, (p-1)*(q-1)) = 1. Se han propuesto otros generadores como pueden ser los basados en sucesiones de registros de desplazamiento, en autómatas celulares o en hashing.

¿Por qué son tan importantes para la criptografía?

La generación de números pseudoaleatorios es necesaria en diversos sistemas criptográficos, como por ejemplo a la hora de generar la clave en los sistemas one-time pad, en el DES, RSA, DSA, etc. Para muchos sistemas criptográficos, la utilización de números pseudoaleatorios es vital para su seguridad. Esto es, fundamentalmente, porque la elección de las claves tiene que ser aleatoria para que así sean impredecibles para un oponente. También se utilizan estos números en los cálculos intermedios que realizan los sistemas criptográficos.

Las razones dadas hasta aquí son las que explotan el parecido de las sucesiones pseudoaleatorias con las aleatorias. Debido a que la transmisión y almacenaje de números aleatorios no es práctica se usan generadores pseudoaleatorios porque sólo se requiere almacenar y transmitir la semilla que genera la sucesión.