-[ 0x05 ]-------------------------------------------------------------------- -[ Generacion de Numeros Aleatorios ]---------------------------------------- -[ by Mortiis ]-------------------------------------------------------SET-22- /================================\ /=========| Generacion de Numeros Aleatorios |========================== || \================================/ || /=\ \=====|·| by MORTIIS \=/ #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*