Copy Link
Add to Bookmark
Report
SET 022 0x05
-[ 0x05 ]--------------------------------------------------------------------
-[ Generacion de Numeros Aleatorios ]----------------------------------------
-[ by Mortiis ]-------------------------------------------------------SET-22-
/================================\
/=========| Generacion de Numeros Aleatorios |==========================
|| \================================/
|| /=\
\=====|·| by MORTIIS <mortiislord@iname.com>
\=/
#echo "Hello world"
> Permision Denied.
#set |grep USER
> USER=root
.--. !!!!Como estan ustedes!!!!!!!! (lease con entonacion de Circo) .-
.-. Bien!!!!!!
Una vez roto el hielo (ni que fuera mi primera cita...), vamos a ver como
hacemos esto. Como siempre, tengo que aclarar unas cuantas cosas antes de
empezar a soltar lineas y lineas.
La primera es obvia y hace referencia a que este es mi primer
articulo en SET. Esta es la oportunidad que estaba esperando para mostrar
mi ignorancia al mundo entero. Ahora bien, mi ignorancia os podra ser util
a algunos de vosotros. De todas formas, desde aqui doy gracias a las
gentes de SET.
La segunda es el tema del texto. Los numeros aleatorios, pero no
voy a explicaros cual es el ultimo algoritmo de generacion de numeros
aleatorios que han hecho, sino que voy a contaros la base matematica (con
ejemplos clasicos) de lo que son las secuencias aleatorias. Mas que nada
porque es lo que se (hacedme caso, en la primera cita siempre hay que ser
sincero ;)
Tercero. Despues de estas chorradas, decir que cualquier
tipo de comentario lo podeis enviar a mortiislord@iname.com.
Vamos a tratar de hacer un esquema (siempre es util, tanto para
escribir como para leer el articulo):
1.- Que demonios es una secuencia aleatoria?
1.1.- Secuencias realmente aleatorias.
1.2.- Secuencias pseudo-aleatorias.
1.3.- Aplicaciones.
2.- Como se si una secuencia la puedo calificar como aleatoria?
2.1.- Test estadisticos:
2.1.1.- Test de frecuencia.
2.1.2.- Test de autocorrelacion.
2.1.3.- Test "Poker".
2.1.4.- Test de rachas de digitos.
2.1.5.- Test de rachas de maximos / minimos.
2.1.6.- d^2 Test.
2.1.7.- Test visuales.
2.2.- Secuencias seguras criptograficamente hablando.
2.2.1.- Postulados de Golomb.
3.- Metodos aritmeticos clasicos.
3.1.- Middle square method.
3.2.- Generadores Lineales.
3.2.1.- Generador por multiplicacion.
3.3.2.- Generador de congruencia lineal.
4.- Registros de desplazamiento realimentados linealmente.
5.- Despedida.
X.- Referencias y Bibliografia.
/===============================================\
| 1.- Que demonios es una secuencia aleatoria? |
\===============================================/
Por aqui hay que empezar. Por ejemplo, si nosotros dijeramos que
el 9384 es un numero aleatorio, no seriamos precisos, ya que el 9384 es un
numero sin mas. El hecho de ser aleatorio se demuestra en una secuencia o
sucesion de numeros. Una secuencia es realmente aleatoria cuando sus
elementos son independientes entre si, o con otras palabras, no existe una
ley que los relacione. Por eso, cuando me refiera a numeros aleatorios, se
sobreentiende que es dentro de una sucesion.
Pero como estareis pensando, a la hora de implementarlo en un
programa, eso de conseguir que el elemento "i+1" no tenga que ver con los
"i" elementos anteriores es muy complicado. Por eso, a los numeros
generados por algoritmos (tipicas funciones rand() ), se les llama numeros
pseudo-aleatorios.
Se trata de encontrar un algoritmo (que sera la combinacion de
varias funciones y procedimientos), cuya salida sea una serie de numeros
poco previsibles. Yo creo que se entiende, pero vamos, que la serie no
cante mucho. Por ejemplo:
1,2,3,4,5... canta como la de el Mu~on de Van Gogh
Todos nos apostariamos lo que fuera a que el proximo numero es el 6. El
exito no esta asegurado, pero hay bastantes posibilidades de acertar.
1.1.- Secuencias realmente aleatorias.
======================================
Estas secuencias son creadas mediante "True Random Number
Generators" y se caracterizan por ser completamente impredecibles, no ser
deterministas y no poseer un periodo a diferencia de las secuencias
pseudo-aleatorias. Y como podemos crear estas secuencias? Pues los
metodos se pueden clasificar en:
1.- "Dice-like methods", o lo que es lo mismo, secuencias
generadas a partir de dados y ruletas (por favor, que los dados no esten
trucados). Si quereis una sucesion de 1000 terminos no os aconsejo este
metodo. Si aun asi sois masocas u os mola lo de tirar el dado y volverlo a
coger pues teneis a vuestra disposicion dados de 10, 20, 100 caras... etc.
Por ultimo, tener cuidado de donde tirais el dado de 100 caras (le podemos
abrir la cabeza a alguien).
2.- Tambien contamos con tablas de numeros aleatorios. La ventaja
que tenemos es que alguien ya a tirado el dado por nosotros. Deberiamos
darle las gracias. Ademas, contamos con tablas para diferentes
distribuciones. Obviamente, la distribucion que a nosotros nos interesa es
la uniforme, para la cual cada elemento es independiente y todos son
equiprobables. Pero quiza queremos que los elementos se nos ajusten a una
distribucion normal, binomial, exponencial negativa, Poisson etc...
Si no quereis perder el tiempo buscando tablas de este tipo,
cogeros la guia de telefono y pillar los cuatro ultimos digitos de cada
numero de telefono. Conseguireis asi una sucesion bastante maja de numeros
de cuatro digitos.
3.- Dispositivos fisicos. Son aparatos que miden alguna
magnitud/evento que fisicamente se cree aleatorio. Por lo tanto, podremos
asociar una ley fisica a cada uno de ellos.
En la naturaleza existen procesos que se consideran como
aleatorios. Algunos ejemplos son:
1.- Ruido termico en un canal.
2.- Radioactividad. La radioactividad es la descomposicion
espontanea del nucleo de un atomo. Este tipo de
atomos, generalmente pesados, reciben el nombre de
radioactivos. La descomposicion se produce mediante la
emision de una serie de particulas elementales o
conjuntos de ellas, llamadas alpha, beta y gamma. Pues
bien.
3.- En general, los rayos cosmicos que vienen del espacio
(que en realidad no son rayos, simplemente
particulas), tambien se piensa aleatoria.
A partir de estos procesos podemos conseguir una salida aleatoria,
eso si, con alguna que otra fluctuacion estadistica.
Pero parece logico pensar que es muy complicado, por no decir poco
operativo, costoso..., implementar alguno de estos procesos para generar
una sucesion de numeros aleatorios. Es por ello por lo que existen las
secuencias pseudo-aleatorias, que son leyes completamente deterministas,
pero cuya salida se asemeja (aparentemente) a los procesos aleatorios.
1.2.- Secuencias pseudo-aleatorias.
===================================
Entonces nos tenemos que centrar en crear un algoritmo cuya salida
sea una sucesion de numeros poco predecibles. Mas adelante veremos los
ejemplos mas tipicos y los fallos que tienen.
La primera restriccion que tenemos es que dicha sucesion va a
tener un periodo. Efectivamente, esto es un problema, ya que por muy
aleatoria que sea una sucesion que creemos, si se repite cada 10
elementos, esta pierde toda su funcion. Por lo tanto habra que buscar
sucesion con periodo muy grande o maximo. Tambien veremos que un fallo
comun de una sucesion aleatoria "casera" es que dicho periodo dependera
tambien de la semilla o valor inicial del generador, lo cual es bastante
peligroso.
1.3.- Aplicaciones.
===================
Las aplicaciones de los numeros aleatorios son muy variadas, pero
es quiza en la Criptografia donde mas se utilizan. Un ejemplo es quiza el
de los LSFR o Registros de Desplazamiento Realimentados Linealmemte. Se
utilizan para un cifrado en flujo, en base al cifrador de Vernam binario.
Consiste en realizar un or exclusivo entre el texto sin cifrar y una clave
que cumple las siguientes propiedades:
- esta generada a partir de una algoritmo determinista a
partir de una clave mas corta.
- la longitud de la clave debe ser tan larga (como minimo)
como la longitud del texto a cifrar.
Con esta segunda propiedad se cumplira el "Secreto Perfecto" de Shannon,
es decir, que el texto cifrado recibido no nos da informacion alguna sobre
el texto original. No se puede asegurar que la secuencia aleatoria vaya a
ser tan larga como el texto a cifrar (mas que nada porque puede que no
sepamos a priori la longitud de la cadena a cifrar). Es por ello, por lo
que el problema se traslada a encontrar una secuencia cifrante aleatoria
de periodo maximo. Esto lo veremos mas adelante.
Algo mas cercano es quiza el PGP. Por defecto, el PGP utiliza IDEA
un cifrador de bloque con una clave de 128 bits. En cada sesion se crea
una nueva clave de 128 bits, a partir de un algoritmo de generacion de
numeros aleatorios. La semilla de dicho algoritmo, se crea a partir de los
tiempos entre pulsaciones, o a partir del raton, la fecha o la hora
(considerados como "Truly Random Numbers").
Y por ultimo, podemos ver las diferentes implementaciones en los
diferentes S.O. Por ejemplo, en LINUX, tenemos diferentes opciones.
Podemos estudiar las funciones rand() o random() que son bastante
complicadas (ver random.c) o probar con drand48, erand48, lrand48,
nrand48, mrand48, jrand48, srand48, seed48, lcong48. Mas adelante
estudiaremos como actuan estas funciones. A diferencia de las otras, estas
son facilitas, ya que utilizan una simple congruencia lineal.
Pero no voy a terminar esto sin decir otras aplicaciones fuera del
campo de la criptografia. Quiza tenia que haber empezado por aqui, pero
todo proceso que esta asociado a numeros aleatorios se denomina de Monte
Carlo (por que sera...). Las aplicaciones de este tipo de procesos van
desde el analisis numerico hasta la simulacion de fenomenos naturales.
/==================================================================\
| 2.- Como se si una secuencia la puedo calificar como aleatoria? |
\==================================================================/
La forma de estudiar una sucesion de numeros generada de manera
aritmetica es mediante la estadistica. Lo que nosotros pretendemos es
conseguir cierta informacion que nos sirva para predecir o estimar el
siguiente numero. Por otra parte, como una de las aplicaciones mas
importantes es la Criptografia, vamos a ver tambien en que consiste un
numero aleatorio seguro criptograficamente hablando.
Empecemos entonces por el principio.
2.1.- Test estadisticos:
========================
Un punto principal es que la sucesion no nos de informacion
adicional como por ejemplo valores mas esperados..., siga una distribucion
uniforme... Este tipo de test nos diran si se puede sacar algo en claro de
una sucesion de este tipo:
2.1.1.- Test de frecuencia.
===========================
Se trata de estudiar si todos los elementos de la sucesion
aparecen con la misma frecuecia. Es necesario que los diferentes elementos
esten uniformemente distribuidos. No solo hay que hacerlo individualmente
para cada elemento, sino que lo suyo es hacer el estudio de frecuencias
para "n" dimensiones, trabajando con vectores de n elementos, mirando con
que frecuencia aparece cada uno.
Incluso no tenemos por que componer los vectores con elementos
sucesivos. Hay multiples posibilidades. Si nos lo curramos, podemos
realizar graficas en 1, 2 incluso 3 dimensiones de la frecuencia.
Graficamente podremos ver mejor si los elementos estan uniformemente
distribuidos. La representacion grafica se corresponde con el ultimo test
de la lista.
2.1.2.- Test de correlacion.
============================
Los test de correlacion son bastante complicados tanto de
explicar como de entender (por lo menos para mi), asi que lo voy a
explicar de una forma que no es del todo cierta, pero es valida.
Consiste en desplazarla (para la izquierda por ejemplo) un numero
k de veces y ver cuantos elementos coinciden y cuantos difieren de la
original. Esto se mide mediante la correlacion que para este proposito se
podria definir como:
A - F
C(k)=------- , donde A=aciertos, F=fallos y T=periodo.
T
Esta claro que para multiplos del periodo de la sucesion, la
funcion de correlacion valdra 1. Pero lo suyo es que esta funcion sea
constante cuando no ocurra esto ultimo. Si para un k determinado hubiera
por ejemplo, mas aciertos de lo normal, sabriamos como se comporta mas o
menos la sucesion k terminos mas a la derecha.
2.1.3.- Test "Poker".
=====================
Se trata de dividir la sucesion en grupos de cinco
elementos. Ahora nos toca jugar una partidita de poker con los grupos
formados. La probabilidad de que un grupo elegido al azar se corresponda
con una jugada debe coincidir con la de la siguiente tabla, si es que
queremos que siga una distribucion uniforme:
________________________________________
| | Probabilidad |
| Combinacion |-------- Base ----------|
| | 10 | 8 | 2 |
----------------------------------------
| abcde | .3024 | .20518 | - |
----------------------------------------
| aabcd | .5040 | .51270 | - |
----------------------------------------
| aabbc | .1080 | .15381 | - |
----------------------------------------
| aaabc | .0720 | .10254 | - |
----------------------------------------
| aaabb | .0090 | .01709 | .6250 |
----------------------------------------
| aaaab | .0045 | .00854 | .3125 |
----------------------------------------
| aaaaa | .0001 | .00024 | .0625 |
----------------------------------------
Con esta tabla, ya podeis "jugar" un poco. Ademas, sabreis si
vuestro adversario va de farol o no. Ahora que pienso, habra que inventar
una tabla de estas para el Mus...
2.1.4.- Test de rachas de digitos.
==================================
Por gap se entiende la distancia que hay entre dos digitos
iguales. La probabilidad de uno de estos gaps es:
p(r)=(1/b)*(1 - 1/b)^r,
donde b es la base en la que estamos trabajando y r es la distancia de
dicha racha (malditas formulas, el proximo articulo va en LaTeX).
Por otra parte, podemos definir un gap de forma diferente. Podemos
decir que un gap es la distancia entre dos maximos o dos minimos, donde un
maximo es un digito que esta "rodeado" a cada lado por numeros mas
peque~os, y un minimo al contrario. Ahora la probabilidad es (atencion..):
2^(r-1) r-2
p(r) = 3 * --------- * ----- (r=3,4,5,...).
r! r+2
Parece ser que la media es de 4. Con este test si que os podeis entretener
haciendo calculos...
2.1.5.- Test de rachas de maximos / minimos.
============================================
Puestos a definir magnitudes absurdas para muchos (incluso
para mi... ;-), vamos a definir una "racha" de estas, en ingles "run",
como la distancia entre un maximo y un minimo, incluidos estos dos
tambien. De cabeza podeis obtener la relacion de que un gap son dos
"carreras" de estas menos un numero. Ahora la probabilidad de encontrar
una "carrera" de estas de orden r es de:
r^2 + r - 1
p(r) = 3 * ------------- para r > 1.
(r+2)!
En este caso el valor medio de la "carrera" es de 2.5
2.1.6.- d^2 Test.
=================
Joder que pedazo formulas que hay aqui... Bueno, mejor os
digo que con este test se busca lo mismo, comparar una magnitud
caracteristica de nuestra sucesion con unos valores teoricos. Pero que
pedazo formulas. Si el articulo no fuera tipo texto las pondria..., si os
interesa, mandarme un mail y os las digo.
2.1.7.- Test visuales.
======================
Pues como suena. Consiste en agrupar los terminos en
grupos de 1 (tarea absurda), 2, 3, etc... elementos y representarlos
graficamente para ver como se distribuyen, si hay algun punto de
acumulacion, asintota, etc... Mas tarde veremos que este metodo es
eficiente.
2.2.- Secuencias seguras criptograficamente hablando.
=====================================================
2.2.1.- Postulados de Golomb.
=============================
Los postulados de Golomb son tres. Ahora vamos a trabajar
con secuencias binarias (no, con esto no me refiero a secuencias de dos
numeros ;). Las condiciones que tienen que cumplir los 0's y 1's son:
G.1: El numero de unos y ceros debe ser el mismo en la sucesion.
Como maximo puede haber una diferencia de una unidad en todo el periodo.
G.2: Definimos nuevamente las rachas como la sucesion de "n"
digitos iguales, si son ceros seran gaps y si son unos seran blocks. Pues
bien, la mitad de las rachas tendran longitud uno, un cuarto tendran
longitud dos, un octavo tendran longitud tres... (dentro del periodo).
Igualmente, el numero de gaps y blocks sera el mismo.
G.3: La autocorrelacion, tal y como esta definida mas arriba, debe
ser constante para todo valor de k (claro esta, cuando no este en fase).
Los postulados hablan por si solos asi que no hare ningun
comentario.
/==================================\
| 3.- Metodos aritmeticos clasicos |
\==================================/
Vamos ahora con los metodos clasicos y los problemas que pueden
tener (y que tienen).
3.1.- Middle square method.
=================================
Este metodo fue introducido por John Von Neumann. El
resultado es una sucesion que se asemeja bastante a una aleatoria. Pero
posee el problema tipico que nos vamos a encontrar. El periodo de dicha
sucesion queda determinado por la semilla que utilicemos. Pero vamos a
explicar el metodo.
Imaginemos que queremos generar una sucesion de numeros de 4
digitos. Entonces cogemos uno cualquiera que sera la semilla, p.e el 1234.
Lo elevamos al cuadrado: 1522756. Nos quedamos con las cuatro cifras
centrales, en este caso, 5227, obteniendo asi el siguiente numero de la
sucesion. Repitiendo este algoritmo tenemos:
1234 - 5227 - 3215 - 3362 - 3030 - 1809 - 2724 - 4201 ...
Parece algo aleatorio. Y ademas bastante sencillo. Pero imaginad ahora que
en vez de elegir el 1234 como semilla, elegimos el 6100. Si aplicamos el
metodo tendremos:
/-> 6100 -> 37(2100)00
| 2100 -> 4(4100)00
| 4100 -> 16(8100)00
| 8100 -> 65(6100)00
\-> 6100
Como veis, el periodo es un poco corto. El 0 es un numero maldito
en este metodo. Tratar de utilizar como semilla el 0000, o el 1000,
2000...!!!
La conclusion seria que no es nada seguro.
3.2.- Generadores Lineales.
===========================
Aqui se incluyen los generadores mediante una recurrencia
lineal del tipo:
y=A*x mod m (por multiplicacion) o
y=A*x+B mod m (multiplicacion y decimacion)
Ambos tienen la propiedad de que su periodo es como maximo m. Por lo tanto
siempre trataremos de buscar un numero m, que sea alto para asegurar que
la secuencia no se empiece a repetir pronto. Ademas, este numero m debe de
cumplir una serie de propiedades, al igual que los coeficientes a y b,
para asegurar que el periodo sea maximo. Veamos los dos casos por
separado:
3.2.1.- Generador por multiplicacion.
=====================================
En este caso no se puede generar una secuencia aleatoria de
periodo maximo m. Pero para que por lo menos sea grande, debemos ver que
se cumplan dos condiciones:
1.- la semilla es coprimo con el modulo m.
2.- a es un elemento primitivo modulo m.
Un elemento primitivo de un cuerpo (de modulo primo) es un
generador, si mediante las sucesivas potencias de este, obtenemos
el conjunto completo de restos, menos el 0 {1,.,.,.,m-1}.
Ejemplo:
Supongamos que trabajamos modulo 7. El CCR sera
{0,1,2,3,4,5,6}. Esta claro que ni el 0 ni el 1 seran generadores. Veamos
el resto:
2^1=2 3^1=3
2^2=4 3^2=2
2^3=1 3^3=6
2^4=2 3^4=4
2^5=4 3^5=5
2^6=1 ... 3^6=1 ...
Vemos que el dos no lo es, pero el 3 si. Si continuaramos
observariamos que el 5 tambien es un generador.
Visto esto, podriamos intentar montar un generador que trabajara
modulo 7 tal que asi:
y=5*x mod 7 y x(0)=3. Obtendriamos:
y(3)=1 <---\
y(1)=5 |
y(5)=4 |
y(4)=6 |
y(6)=2 |
y(2)=3 |
y(3)=1 <---/
El periodo en este caso es de 6, que es lo maximo que
conseguiremos (modulo - 1).
El metodo de "atacarlo" es simple siempre y cuando sepamos el
modulo en el que estemos trabajando. Con tener dos valores de la sucesion
ya podriamos resolver la ecuacion para hallar el valor de a.
3.3.2.- Generador de congruencia lineal.
========================================
Incluyendo un factor de decimacion "b" en la formula de
recurrencia conseguimos que el periodo maximo sea m, ademas de no depender
de la semilla que utilicemos. Pero al igual que antes, necesitamos que los
coeficientes cumplan unas propiedades:
1.- b es coprimo del modulo.
2.- a-1 es multiplo de todos los divisores propios de m.
3.- a-1 es multiplo de 4 si m es multiplo de 4.
Si cumple estas propiedades, podemos asegurar que el periodo sera
maximo, igual a m, e independiente de la semilla que utilicemos. En este
caso, si conocemos el modulo de trabajo, el generador queda determinado
por dos coeficientes, que son a y b. Por lo tanto necesitamos dos
ecuaciones para resolver el sistema. Eso equivale a tres numeros seguidos
de la sucesion.
Ahora bien, este tipo de generador tiene un fallo 'mu gordo'. En
1960, IBM desarrollo el siguiente algoritmo:
x(n+1)=65539*x(n) mod 2^31.
Parece que la cosa es eficiente, pero en 1968 Marsaglia publico un
resultado que viene a decir que los numeros aleatorios generados se
ajustan a planos. Mande!. Aqui viene un metodo de estudio que cite
anteriormente y que consiste en crear vectores y representarlos. Pues lo
que resulta si cogemos vectores de tres componentes y los representamos
son una serie de planos paralelos. En general, si escogemos vectores de n
componentes, formaran hipersuperficies de n-1 dimensiones, para n mayor
que dos. A esto se le denomina Efecto Marsaglia. La orientacion de los
planos y su numero dependera de los coeficientes que lo caracterizan.
Para que os entretengais un poco, os dejo el extracto del man de
la funcion drand48 (resumido y traducido por mi):
"Todas las funciones generan una secuencia de enteros de 48 bits,
en relacion con la formula:
Xn+1 = (aXn + c) mod m, donde n >= 0
El parametro m = 2^48. A no ser que utilicemos lcong48(), a y c
toman el valor:
a = 0x5DEECE66D
c = 0xB "
Ala, aqui lo teneis. Ya sabeis hasta los valores por defecto.
Ahora bien. Estas funciones ya no se utilizan. En el random.c no vais a
ver nada de esto. Actualmente lo que se utiliza son otro tipo de metodos.
Estos consisten en general en lo siguiente:
-> Se genera lo que se conoce como "pool", que la vamos llenando
de numeros procedentes de fecha, horas, tiempos de procesos, PID`s, tiempo
entre pulsaciones, entre accesos a discos, ... etc... El primer problema
que se presenta es que no todos los S.O permiten el mismo acceso a este
tipo de datos, y ni siquiera de la misma forma. Tener en cuenta que puede
que alguno de estos dispositivos sea virtual, o simplemente que el usuario
no tenga permisos para obtener dichos datos.
-> Se utiliza una funcion hash, tipo MD5 o SHA-1 (Secure Hash)
con los datos de la "pool" para obtener una sucesion de salida.
-> Se van actualizando los valores de la "pool" (mira que queda
mal esto, pero no se como traducirla, diccionario -> charca, estanque!!)
Asi por ejemplo, PGP utiliza MD5 como one-way function y lo aplica
sucesivamente sobre la "charca", cogiendo los primeros 64 bytes como la
semilla de la siguiente serie de MD5's que aplica, y el resto de la
"charca" lo utiliza directamente.
Por lo tanto, la seguridad de este metodo reside en la funcion
hash que se utilice (MD4, MD5, SHA-1), y en los datos que se utilicen para
llenar la "charca". Fallos conocidos afectan a la encriptacion que
utilizaba Netscape, Kerberos, incluso a la MIT-Cookie. El fallo cometido
era que se utilizaban los PID`s y sus tiempos para llenar la pila. Esto
reducia la entropia y el numero de posibles semillas a numeros bastante
peque~os.
Vamos ahora con otro metodo que son los LFSR's.
/===========================================================\
| 4.- Registros de desplazamiento realimentados linealmente |
\===========================================================/
Antes de nada os dire una de las multiples aplicaciones de los
LFSR. Os suena A5?, ... , GSM? Pues el algoritmo de cifra de los GSM
utiliza LFSR. Lo dije para que le pusierais un poco mas de interes.
Veamos como puedo explicar yo estas cosas... Primero, un poco de ASCII
art:
/---\
/-----|XOR|<------------------\
| \---/ |
| /|\ |
| | |
| | |
| /---\ /---\ /---\ /---\ |
\-----|S.1|-|S.2|-|S.3|-|S.4|----------> S
\---/ \---/ \---/ \---/
Contamos con cuatro registros que almacenan un bit cada uno.
Dichos registros se van realimentando con la salida de una operacion entre
los registros. Dicha operacion es un XOR entre alguno de estos registros.
En el caso de arriba, se realiza entre el primer y ultimo registro. Una
vez realizado el XOR, se desplazan los bits al registro de la derecha.
Por ejemplo, si tenemos 0-0-1-1 como semilla:
S = 0 XOR 1 = 1 y los registros quedarian 1-0-0-1.
Una vez explicada la dinamica, decir que el LFSR anterior "posee
cuatro etapas con polinomio X^4+X+1". Entonces, el generador va a quedar
determinado por el numero de etapas o registros, la semilla que utilicemos
y los registros que esten conectados a la puerta XOR. Mediante el
polinomio determinamos estos registros. Asi X y X^4 significa que
conectamos el primer y el cuarto registro.
Las propiedades de los LFSR se reducen a las propiedades de los
polinomios que los caracterizan. Por lo tanto habra que tener en
cuenta que estamos trabajando modulo 2. Antes de explicar los tipos de
polinomios que nos vamos a encontrar veamos algunas cosillas.
La primera que se nos puede ocurrir es que si utlizamos como
secuencia inicial la secuencia nula (todo ceros), nos quedariamos con las
ganas ya que obtendriamos una gran y valiosa serie de ceros. Por lo tanto
el numero de estados posibles de los registros es de:
n
T = 2 - 1 , siendo n el numero de registros.
Este es por lo tanto el periodo maximo de nuestro generador. Dicho
periodo variara segun el polinomio que estemos utilizando. Vamos a ver un
ejemplo, como es el del LFSR del grafico de arriba con la semilla 1111:
Secuencia Bit Salida Resultado XOR
1111 -------> 1 ----------- 0
0111 -------> 1 ----------- 1
1011 -------> 1 ----------- 0
0101 -------> 1 ----------- 1
1010 -------> 0 ----------- 1
1101 -------> 1 ----------- 0
0110 -------> 0 ----------- 0
0011 -------> 1 ----------- 1
1001 -------> 1 ----------- 0
0100 -------> 0 ----------- 0
0010 -------> 0 ----------- 0
0001 -------> 1 ----------- 1
1000 -------> 0 ----------- 1
1100 -------> 0 ----------- 1
1110 -------> 0 ----------- 1
se repite ... 1111 -------> 1 ----------- 0
Vemos que el periodo es de 15, justamente 2^4 - 1, por lo que es
maximo. Veamos por que es esto. Vamos a clasificar los polinomios en :
1.- polinomios factorizables.
2.- polinomios irreducibles.
3.- polinomios primitivos.
Ahora estamos trabajando en los famosos Campos de Galois.
.POLINOMIOS FACTORIZABLES.
--------------------------
Antes de nada pondre un ejemplo de este tipo de polinomios
(recordad que estamos trabajando modulo 2). Es este:
x^4 + x^2 + 1 ya que,
x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 + x + 1)
Las propiedades de los LFSR generados mediante este polinomio son:
1. El periodo depende de la secuencia inicial.
2. El periodo max. se encuentra entre n y 2^n - 1.
Eso de que la longitud de la secuencia dependa de la semilla no
mola, asi que vamos a olvidarnos de este tipo.
.POLINOMIOS IRREDUCIBLES.
-------------------------
Un polinomio irreducible es aquel que no se puede factorizar. Por
ejemplo tomamos el polinomio:
x^4 + x^3 + x^2 + x + 1. Este polinomio es irreducible.
Para este caso, todos los registros estan conectados a la puerta XOR. Las
propiedades son las siguientes:
1. El periodo no depende de la semilla.
2. El periodo maximo es un factor de 2^n - 1.
Hemos conseguido que no dependa de la semilla, pero sin embargo, seguimos
teniendo el problema de que la secuencia sea corta. Todo parece intuir que
el siguiente tipo lo resulve todo...:
.POLINOMIOS PRIMITIVOS.
-----------------------
Este concepto ya lo meti unas lineas mas para atras. Significa que
dicho elemento, en este caso un polinomio, es un generado del cuerpo en
cuestion. Asi bien, si calculamos las potencias del elemento en cuestion,
vamos obtieniendo el Conjunto Completo de Restos o CCR:
{1, x , x+1 , x^2 , x^2 + x , x^2 + x + 1 ,...}
Mediante este tipo de polinomios podemos asegurar que el periodo de la
secuencia no depende de la semilla y que ademas sera maximo e igual a:
n
T=2 + 1 (como ya vimos antes). Otros polinomios
primitivos de orden mayor son:
n=6 x^6 + x + 1
n=7 x^7 + x + 1
n=8 x^8 + x^4 + x^3 + x^2 + 1
n=9 x^9 + x^4 +1
n=10 x^10 + x^3 + 1
Vista esta frenetica explicacion de lo que es un LFSR, vamos a ver
cuales son sus puntos flacos. Pensemos igual que con los generadores por
congruencia. Como determinamos un generador de n etapas?. Mediante los n
coeficientes {0,1} que me dicen si el registro esta conectado o no a la
puerta. Entonces vamos a ver cuantos elementos consecutivos de la sucesion
tengo que saber para formar n ecuaciones y poder resolver asi un sistema
lineal de n incognitas y n ecuaciones. Pues bien, si lo escribis y echais
calculo, y teniendo en cuenta los valores que vais realimentando, el valor
es de 2*n. Es decir, conociendo 2*n elementos de la sucesion, puedo
reconstruir el generador y calcular valores posteriores. A esto se le
llama algoritmo de Berlekamp-Massey.
Esto se resuelve aplicando NLFSR o lo que es lo mismo, lo de antes
pero no lineal. Supongo que podeis intuir que si las relaciones son no
lineales la cosa se complica un poco. Pero tambien se complica el estudio
de las propiedades en relacion a periodos, etc...
/===============\
| 5.- Despedida |
\===============/
Visto lo visto esto se ha acabado. La cosa no ha sido muy dificil.
Ha sido mas que nada un cotenido conceptual para crear una base a partir
de la cual ir investigando. Si teneis algun tipo de comentario, enviarlo a
la direccion de mas arriba.
/================================\
| X.- Referencias y Bibliografia |
\================================/
He hecho referencia a los siguientes textos, donde estan
desarrollados algunos de los metodos expuestos (y la teoria tambien):
(1). "Random Number Generators" 1996
AUTOR: Birger Jansson.
(2). "Computational Physics" 1997
AUTOR: Dean Karlen.
Department of Physics - Carleton University.
(3). "Aplicaciones Criptograficas" (Segunda Edicion)
AUTOR: Jorge Ramio Aguirre.
Escuela Universitaria de Informatica.
Universidad Politecnica de Madrid.
(4). "El Principito"
AUTOR: Antoine de Saint-Exupery.
_______________________________________
"No se ve bien sino con el corazon.
Lo esencial es invisible a los ojos."
El Zorro (Antoine de Saint-Exupery)
*EOF*
