[ GRIPTOGRAFÍA ]
Evaluación de generadores de secuencias pseudoaleatorios utilizadas en telemática e ingeniería criptográfica


Prof. Dr. Javier Areitio Bertolín Director de Redes y Sistemas.
ESIDE. Facultad de Ingeniería. Universidad de Deusto.

En el presente artículo se describen diferentes generadores de secuencias binarias pseudoaleatorias y se presenta un esquema de evaluación del grado de robustez en base a una batería de tests. Entre los diferentes parámetros utilizados para medir la robustez de un generador destacan la complejidad lineal de la secuencia, su perfil de crecimiento, la aleatoriedad, la inmunidad a la correlación, etc. Una elevada complejidad lineal en una secuencia no garantiza que este parámetro sea estable. Es decir, la modificación de unos pocos bits de la secuencia original comporta un crecimiento o decrecimiento notable en la complejidad lineal de la secuencia resultante.

Para que un generador de secuencias binarias pseudoaleatorias sea robusto, su secuencia debe verificar diferentes características: (1) La secuencia debe parecer aleatoria de forma que la estadística del mensaje quede enmascarada. (2) El periodo T de la secuencia debe ser muy elevado. (3) El espacio de claves ha de ser suficientemente grande para hacer impráctico un ataque por búsqueda exhaustiva. (4) La secuencia ha de ser fácil de generar. (5) El conocimiento de una parte de la secuencia no debe permitir a un criptoanalista generar la secuencia completa.

Generadores: NLFSR, de umbral, de Rueppel, stop-and-go básico y alternado, de producto interno.

Entre los generadores NLFSR basados en un solo registro, la figura 1 representa uno con una no linealidad de tercer orden. Es posible obtener con un NLFSR secuencias de la misma longitud que las de un LFSR con unas propiedades muy similares, pero con una impredecibilidad añadida. El Generador Umbral de Bruer (1984), figura 2 intenta evitar la dependencia directa de la salida con alguno de los subgeneradores internos como es el caso del generador de Geffe. La función de combinación es una regla de voto por mayoría, que hace al generador más robusto. El número de subgeneradores debe ser impar y la salida es el valor binario que más se repite. Este nuevo esquema, sin embargo, todavía presenta algunos problemas de correlación al igual que en el caso del generador de Geffe. Para mejorar este problema común, Rueppel propuso utilizar funciones combinatorias con memoria y realizó el generador de Rueppel basado en un sumador real para mezclar varios LFSRs, figura 3. El sumador toma "n" bits resultantes de los "n" LFSRs subgeneradores y cuenta cuantos de estos bits son "1". El valor de la suma se almacena en un registro de llevada, cuyo bit de menor peso se toma como salida y el resto de los bits del registro se añaden a los de los LFSRs para calcular la siguiente llevada. Los esquemas controlados por reloj son especialmente interesantes por su capacidad de obtener elevadas complejidades. Por otra parte, sus periodos disminuyen y es necesario usar longitudes de claves algo más grandes de lo que sería estrictamente necesario. En general, hay dos modalidades: los esquemas donde el reloj del subgenerador es controlado por otro subgenerador, y aquellos donde el reloj de un generador es gobernado por su propia salida (o una función de su estado interno). En la primera modalidad, se encuentra la gran familia de los "generadores de parada y arranque" (stop-and-go). En la figura 4(a) se representa un generador de parada y arranque básico y en la figura 4(b) un generador de parada y arranque alternado. Dentro de la segunda modalida, hay otra gran familia de generadores: "los generadores autodecimados". Básicamente, utilizan un FSR (Feedback Shift Register) que funciona normalmente, pero dependiendo de una condición especial, el reloj del FSR no avanza una vez, sino dos o más veces. Los dos generadores autodecimados más famosos son los construidos por Rueppel (en 1986) y por Chambers & Gollmann (en 1988). Un caso especial de los generadores controlados por reloj es cuando los relojes de dos o más generadores no dependen de ningún otro generador, pero tienen diferentes frecuencias. Por ejemplo, este es el caso del "Generador del Producto Interno" diseñado por Massey&Rueppel (en 1985), figura 5. Tiene una función de combinación que suma los productos internos de cada bit con los dos estados, de ahí el nombre del generador, pero adicionalmente, los dos generadores (por ejemplo LFSRs) pueden tener diferentes tasas de reloj. Por ejemplo, el primer generador puede ver como su reloj marca tres impulsos mientras el reloj del segundo sólo lo ha hecho una vez. El prototipo de un generador en cascada es el generador de Gollmann (1988). Los esquemas en cascada generalmente utilizan un mecanismo de control de reloj, pero su ventaja está en el hecho de que su diseño es modular y repetitivo, permitiendo la concatenación de un número indefinido de generadores, obteniendo de esta manera enormes periodos y altas complejidades lineales. Son vulnerables al ataque de "lock-in" y se recomienda utilizar no menos de quince generadores en cascada. Se han identificado debilidades/anomalías en los generadores LFSR, Geffe, Umbral, Parada y Arranque básico, Parada y Arranque alternado y Parada y Arranque Bilateral, Producto Interno y la Cascada de Gollmann; mientras que el Sumador real y los generadores autodecimados presentan buenas estadísticas. Los esquemas de combinación sin memoria no pasan los tests de aleatoriedad. Cuando el combinador posee memoria (como es el caso del sumador real) se aprecia una marcada mejora, pero permanecen todavía algunas regularidades. Ls generadores controlados por reloj suelen malgastar periodo. Dentro de estos, los mejores son los autodecimados. Por último las cascadas tampoco suelen conseguir generar secuencias cuasi-aleatorias.

Generadores: basado en iteración de Mandelbrot, BBS, RSA, PLESS, congruencia lineal

Los generadores de "secuencias pseudoaleatorias caóticas" están basados en el empleo de funciones caóticas. El análisis matemático de las orbitas caóticas que rigen su comportamiento no lineal es muy complejo. Dentro de lo que constituye la teoría de fractales, el conjunto de Mandelbrot se define como un conjunto de puntos C=Creal+i.Cimag del plano complejo, de forma que al iterarse según la expresión Zn+1=Zn^2+K (n=0,1,2,.... y Z0=0+0.i) permanecen acotados. Si K es real (es decir, puntos del eje del conjunto), un método para generar una secuencia de números pseudoaleatorios basado en esta iteración de Mandelbrot es: Xn+1=Xn^2+K para n=0,1,2,.... donde X0=0 y la "semilla" K es un valor comprendido entre -2 y 0,25 (por ejemplo: K=-1,999999899 o K=-1,9898999999). Los números que se obtienen están acotados en el intervalo cerrado [-2,2] para valores de la "semilla" K en el intervalo -2_K_0,25. Cuando la "semilla" K es muy próxima a "-2" las series que se obtienen son casi caóticas. El "generador BBS (Blum-Blum-Shub)" está basado en restos cuadráticos en aritmética modular. Sean "p" y "q" dos números primos de (k/2) bits tales que p=q=3 mod 4 y definimos n=p.q. Sea QR(n) el conjunto de los restos (o residuos) cuadráticos módulo "n". Sea "S0" una "semilla", es decir, un elemento cualquiera del conjunto QR(n). Para i_0 se define: Si+1=Si^2 (mod n) y entonces se define el generador BBS como: f(S0)=(Z1,Z2,...,ZL) donde Zi=Si mod 2, con 1_i_L. Por tanto, de forma resumida un generador BBS verifica: Zi=[S0^(2^i) mod n] mod 2, donde 1_i_L. Si n=192649=(383).(503) y la "semilla" S0=101355^2 mod n=20749. Los primeros veinte bits del generador BBS son: 1100 1110 0001 0011 1010, ya que para: i=0 _ Si=20749 _ Zi=?; para i=1 _ Si=143135 _Zi=1; para i=2 _ Si=177671 _ Zi=1; para i=3 _ Si=97048 _ Zi=0; para i=4 _ Si=89992 _ Zi=0,.... etc.. El "generador RSA" opera tomando "p" y "q" dos números primos de k/2 bits y definiendo n=p.q. Se elige "b" tal que el mcd(b,FI(n))=1. Sean "n" y "b" públicos y"p" y "q" secretos. Una "semila" "S0" tiene "k" bits. Para i_1 se define: Si+1=Si^b mod n y se define el generador RSA como: f(S0)=(Z1,Z2,..,ZL) donde Zi=Si mod 2 con 1_i_L. Por ejemplo, si n=91261=(263).(347) y b=1547 y S0=75364, entonces los veinte primeros bits del generador RSA son: 1000 0111 0111 1001 1000, es decir para: i=0 _ Si=75634 _ Zi=?; para i=1 _ Si=31483 _ Zi=1, para i=2 _ Si=31238 _ Zi=0, para i=3 _ Si= 51968 _ Zi=0, etc.. Un "generador de secuencias pseudoaleatorias de V.S. Pless" (de 1977) se construye conectando las dos salidas de dos LFSRs a las entradas J y K de un flip-flop JK (como función de combinación no lineal con memoria) y tomando como salida del generador la salida Q del flip-flop JK. Este esquema de generador preserva las buenas propiedades de aleatoriedad de las secuencias producidas por los dos LFSRs y además soluciona el problema de la linealidad inherente en estos dispositivos. Se puede mejorar el generador colocando en serie a la salida Q del flip-flop JK un dispositivo que elimine bits de forma alternada. Si P1y P2 son los periodos de los dos LFSRs y son números impares, el periodo de la salida del generador Pless será P=P1*P2. Un generador de congruencia lineal se obtiene de la siguiente forma: sea M_2 un número entero y sean: 1_a,b_(M-1); se define k=|log2 M| y sea (k+1)_L_(M-1). Para una "semilla" S0, donde 0_S0_(M-1), se define Si=(a.Si-1 +b) mod M para 1_i_L, por tanto se define un "generador de congruencia lineal" como: f(S0)=(Z1,Z2,...,ZL) donde Zi=Si mod 2 con 1_i_L. Por ejemplo, si M=31, a=3, b=5, con semilla S0=0 la secuencia de salida Zi es: "1010 0011 01". Si la semilla S0=1 la secuencia binaria Zi será: "0100 1101 01". Si la semilla S0=13, la secuencia binaria de salida Zi es: "1111 1111 11". Si la semilla S0=30, la secuencia Zi de salida es: "0110 1010 00". Si la semilla es distinta de 13, entonces especifica un punto de arranque para un ciclo de longitud 30 y los siguientes 10 bits reducidos módulo 2 forman la secuencia pseudoaleatora Zi. Este generador producirá 31 posibles cadenas Z de 10 bits pseudoaleatorias. Los treinta distintos valores Si generados serán para S0=0: 0,5,20,3,14,16,22,9,1,8,29,30,2,11,7,26,21,6,23,12,10,4,17,25,18,28,27,24,15,19 y comienza a repetirse el ciclo empezando por "0".

Generadores: de Günther, de combinación lineal/no lineal basados en múltiples LFSRS interconectados

La figura 7 muestra un generador propuesto por C.G. Günther en 1988 denominado de "pasos alternados": los LFSRs 1 y 2 están basados en polinomios primitivos de grados n1 y n2 y periodos T1=(2^n1 -1) y T2=(2^n2 -1) (mayores que uno y primos entre sí; mcd(T1,T2)=1) y el LFSR-3 es del tipo De-Bruijn con un periodo de 2^k, comparte las ventajas de los generadores de "marcha y espera" pero evita algunas de sus debilidades. Si la salida De Bruijn del LFSR-3 es de periodo 2^k, entonces el periodo de salida del generador de "pasos alternados" es: T=(2^k).(T1).(T2) y su complejidad lineal: CL está acotada entre: (n1+n2).2^(k-1)<CL_(n1+n2).(2^k). Los generadores de secuencias pseudoaleatorias de combinación basados en varios LFSRs con polinomios primitivos de realimentación interconectados a través de una función booleana no lineal, sin memoria presentan las siguientes características: Sean tres LFSRs realimentados con polinomios primitivos de grados 4, 5 y 3. El periodo de la secuencia de salida resultante es T=mcm[(2^4 -1), (2^5 -1), (2^3 -1)]=mcm[15,31,7]=15.31.7=3255. Si la secuencia resultante se hubiese generado sin efectuar operaciones no lineales entre las tres secuencias componentes, entonces su complejidad lineal hubiese sido CL=4+5+3=12; es decir, podría haberse generado con un único LFSR de esta longitud, siendo necesarios (2.12=24) bits de la secuencia para obtener el polinomio de realimentación. Sin embargo, mediante la operación no lineal de combinación de las secuencias producidas por los tres LFSRs y teniendo en cuenta que todos los polinomios son primitivos, la complejidad lineal de dicha secuencia global es CL=4+4.5+4.5.3=84, es decir, podría generarse con un único LFSR de longitud 84, por lo que en este caso serían necesarios (2.84=168) bits de la secuencia para obtener el polinomio de realimentación. Por otra parte, un generador de combinación formado por dos LFSRs de longitudes L1 y L2 conectados a través de una puerta lógica "xor" (operador lineal) tendrá de periodo T=mcm[(2^L1 -1),(2^L2 -1)](^L1 -1).(2^L2 -1), siendo los periodos de cada LFSR: T1=(2^L1 -1) y T2=(2^L2 -1), y la complejidad lineal resultante: CL=L1+L2. Por último un generador de combinación formado por dos LFSRs de longitudes L1 y L2 conectados a través de una puerta lógica "and" (operador no lineal) tendrá de periodo resultante T=mcm[(2^L1 -1),(2^L2 -1)]=(2^L1 -1).(2^L2 -1) y complejidad lineal CL=L1.L2.

Criptoanálisis de generadores de secuencias pseudoaleatorias basados en un único LFSR

Dado un generador de secuencias binarias pseudoaleatorias basado en un solo LFSR es posible criptoanalizarlo con vistas a obtener el polinomio de realimentación/conexión a partir de una porción de su salida binaria. Consideremos un generador de secuencias pseudoaleatorias basado en un único LFSR cuya salida es: Zm+i=SUMATORIO-de-(j=0)-a-(m-1)-de:[cj.Zi+j] mod 2, donde c0,...,cm-1 pertenecen al conjunto {0,1} y c0=1. Puesto que todas las operaciones de este sistema criptográfico son lineales (es decir, el "sumatorio" es módulo 2, utilizandose el operador "xor"), se puede sospechar que el criptosistema es vulnerable al ataque de "texto en claro conocido". Si el adversario/oponente obtiene un conjunto contiguo de bits de la salida Zi con (1_i_n) y sabe "m" la longitud del LFSR, entonces puede determinar los coeficientes c0,c1,...,cm-1 y puede reconstruir el polinomio de realimentación del LFSR. Para cualquier i_1 se tiene: Zm+i=SUMATORIO-de-(j=0)-a-(m-1)-de: [cj.Zi+j] mod 2, que es una ecuación lineal en "m" incógnitas. Si (n_2.m), entonces existen "m" ecuaciones lineales en "m" incógnitas que se puede resolver. El sistema de "m" ecuaciones lineales se puede escribir en forma de matriz como se representa en la figura 6(a). Si la matriz de coeficientes tiene un inverso (módulo 2) se obtendrá la solución de la figura 6(b). De hecho, la matriz tendrá una inversa si "m" es el grado de "recurrencia" utilizado para generar la salida del generador. Supongamos que un adversario obtiene quince bits consecutivos de la salida de un generador de secuencias pseudoaleatorias basado en un solo LFSR de longitud "m=5", siendo estos bits: Z1,Z2,....,Z15=1101 0010 0001 010. Dicho adversario plantea una ecuación matricial utilizando tan sólo los diez primeros bits de la salida obtenida, obteniendose la expresión de la figura 6(c). Por tanto al final obtiene el polinomio de realimentación buscado del LFSR, que es: Zi+5=Zi + Zi+3 (mod 2), es decir el LFSR de longitud 5 queda representado por la figura 6(d). Por último, si se desea criptonalizar un generador basado de un sólo LFSR de longitud (m=4), cuya secuencia de salida es: "1000 1001 1010 111...." aplicaríamos el mismo procedimiento matricial utilizando sólo los ocho primeros bits de la secuencia (2.m=2.4=8): (c0,c1,c2,c3)=(Z5,Z6,Z7,Z8).[1000, 0001, 0010, 0100]^(-1)=(1,1,0,0) lo que significa que el polinomio de realimentación/conexión buscado es: Zi+4=Zi + Zi+1 (ó bien f(x)=1+x^3+x^4), la figura 8 muestra el esquema de dicho generador.

Métodos de evaluación
Baterías de test

Los generadores de secuencias pseudoaleatorios pueden utilizarse para construir cifradores de flujo en criptografía, o como secuencias para otras aplicaciones tales como CDMA, generación de números aleatorios, etc.. Antes de utilizarlos, es necesario evaluar sus prestaciones. Sin embargo, se diseñan heurísticamente, lo que implica un análisis detallado uno por uno. No existe ninguna herramienta matemática aplicable a todos los tipos de cifradores. Siempre sería posible inventar un cifrador para el cual no se hubiera descubierto todavía un análisis matemático. Por lo tanto, ¿cómo se puede demostrar entonces que un generador en general es bueno? De hecho, no se puede demostrar que es bueno, y éste es un concepto aplicable a cualquier método criptográfico. Lo que se debe demostrar es que con los conocimientos actuales, no se conoce ninguna pauta o método que permita romper el sistema fácilmente, al menos, comparativamente, con menos esfuerzo que un ataque por fuerza bruta. La única parte común a todos los generadores es la salida, la secuencia de símbolos. El análisis general forzosamente ha de tratar a cada generador como una caja negra y debe analizar las propiedades de la secuencia. La solución consiste en obtener algunos valores cuantitativos aplicando algoritmos llamados "tests" a las secuencias de salida de dichos generadores. Estos tests tienen que ser independientes del generador en particular empleado y se deben poder aplicar siempre. Estos tests miden la distancia entre la secuencia actual y una secuencia verdaderamente aleatoria. Los resultados de los tests a menudo son números, que pueden variar dentro de un rango continuo de valores. No siempre está claro cuándo una secuencia tiene que ser rechazada. Algunas veces, los parámetros obtenidos no ofrecen ninguna información en valor absoluto, aunque permiten comparar diferentes generadores entre sí para decidir cuál de ellos es mejor. Existen diversos tipos de tests: estadísticos, empíricos, teóricos, complejidades,... Se debe utilizar como mínimo uno de caa tipo para realizar una buena evaluación de un generador de secuencias pseudoaleatorias. Entre los principales test podemos destacar: (1) Test Equidistribuido. Cuenta el número de unos y de ceros de la secuencia binaria y comprueba que no haya grandes diferencias. Estas desviaciones se miden con una chi-cuadrado (c2). Definimos que la secuencia pasa el test si la c2 estimada cae dentro del intervalo de confianza al 95%. (2) Test Serie. Agrupa los bits de la secuencia formando símbolos de t bits no solapados, sobre los cuales evalúa su distribución contrastándola con la equidistribuida. Como en el test anterior, se aplica una c2 (95%). (3) Postulados de Golomb; el tercer Postulado de Golomb. Permite realizar la autocorrelación de la secuencia y compara el valor del pico máximo con el valor en el origen, la relación lóbulo principal - lóbulo secundario. El peor resultado de este test es cuando hay un pico elevado (aunque los demás valores puedan ser cero), entre otros razonamientos, debido al ataque por correlación. Es preferible tener muchos picos razonablemente moderados que unos pocos picos elevados. El resultado del test reflejará la relación lóbulo principal-secundario medido en dB. (4) Test Universal de Entropía: este test estima el valor de la entropía por bit de la secuencia de acuerdo con el algoritmo propuesto debido a Maurer en 1990. El método tiene tres parámetros: la memoria estimada de la secuencia original, la longitud del periodo de transición y el número de pasos del test. Dado que la entropía calculada es una estimación, se pueden originar valores mayores que la unidad. (5) Test Espectral, agrupando los bits en símbolos solapadamente, se calcula la distribución de apariciones de dichos símbolos. Sobre esta distribución, se aplica una transformada discreta de Fourier, obteniendo un espectro, lo que le confiere el nombre a este test. Si la secuencia es aleatoria, el espectro debería exhibir un valor máximo "1" en el origen y "0" en el resto de las componentes frecuenciales. La figura de mérites lo que se llama la "distorsión cuadrática", que mide la energía de las componentes frecuenciales no nulas y la compara con la energía de la componente constante.

Distorsión cuadrática = (E[F(k)]²) / [F(0)]²

A diferencia del tercer postulado de Golomb, aquí todos los picos son importantes, porque el aspecto principal es la diferencia entre el resultado y los valores ideales, la pérdida de energía, y no importa, en principio, si esta pérdida de energía está dispersada uniformemente, o concentrada únicamente en una componente particular. (6) Complejidad Lineal, calcula la longitud mínima del LFSR capaz de sintetizar la misma secuencia por medio del algoritmo de Massey-Berlekamp (de 1969). El resultado de la complejidad se compara con el periodo de la secuencia. Cuanto más cercanos sean los valores, mejor será el generador. (7) Complejidad de Ziv-Lempel, cuenta el número de patrones con diferentes estructuras en la secuencia. A partir de la medida de esta complejidad se puede estimar la entropía por bit de la secuencia como:

H=(C log(n))/n

donde C es la complejidad de Ziv-Lempel de la secuencia, y n su longitud. La aplicación de este test a la criptografía lo propuso Mund en 1992. Desde otro punto de vista, la compresión de Ziv-Lempel convierte cualquier secuencia en otra, normalmente más pequeña. Suponiendo que esta compresión es la mejor que se puede alcanzar, la secuencia no se puede reducir más allá, y por tanto, la razón entre la longitud de la secuencia comprimida y la longitud original puede servir como una estimación de la entropía. Los resultados de la entropía basada en la complejidad de Ziv-Lempel son irrelevantes porque todos los valores son muy similares y cercanos a la unidad. Por esta razón, no suele resultar útil para remarcar las diferencias entre los generadores. Los tests equidistribuido y serie se evalúan mediante un estimador chi-cuadrado. Fijando el intervalo de confianza al 95%, es fácil apreciar que ni el generador de Geffe ni el de Umbral pasan los tests. También hay una desviación en la cascada de Gollmann cuando se calcula el test serie con agrupaciones de tres bits. Esta pequeña variación es suficiente para eliminar el generador. Sin embargo, cualquiera podría discutir la razón de esta metodología. ¿Qué curre si todos los demás parámetros de los tests son perfectos y éste es el único valor que muestra una pequeña desviación? Es importante remarcar que cada test analiza y comprueba una característica específica de la secuencia, características que son diferentes aunque no necesariamente independientes, y tan pronto como se detecta una regularidad, hay evidencia de no-aleatoriedad y debe ser evitado su uso. En términos de seguridad, esta regularidad puede ser aprovechada para atacar el esquema. Por consiguiente, la cascada de Gollmann también es descartada. El tercer postulado de Golomb utiliza la función de autocorrelación. Además, se han calculado las funciones de autocorrelación periódicas pares e impares. En ambos casos se ha medido la relación entre los lóbulos principal y secundario, expresado en dB. Cuanto mayor sa la diferencia, mejor. El valor máximo alcanzable es 2L = 48.164 dB, lo que únicamente ocurre con el LFSR sólo. El valor mínimo se ha fijado a los 10 dB, que representa un décimo linealmente. Sólo cuatro generadores pasan el test (dos más si se relajan las condiciones y se aceptan el Sumador Real y el Bilateral). Para evaluar el test espectral se ha empleado la distorsión cuadrática y no únicamente la relación lóbulo principal lóbulo secundario. Podría servir como un parámetro resumen, ya que se ha detectado una cierta influencia del resto de parámetros sobre éste. Normalmente, el generador con peores resultados origina mayores distorsiones cuadráticas. A causa del algoritmo de síntesis de Berlekamp-Massey, es importante comprobar la CL (Complejidad Lineal) de la secuencia. Pero el valor absoluto no tiene ningún sentido si no se compara con el periodo de la secuencia. Cuanto más cercanos están, el comportamiento del generador es mejor. Aquí es donde los problemas del LFSR se cobran mayor relevancia. Sólo cinco generadores tienen una complejidad mayor que 100 y entre estos, sólo cuatro tienen una CL/P (Complejidad Lineal/Periodo) cercana a la unidad: los dos generadores autodecimados, el sumador real y el bilateral. La sustitución de los subgeneradores LFSR por NLFSR tiene el principal objetivo de incrementar la CL, pero esto conlleva una pequeña disminución en la autocorrelación. Cuando se evalúa el test espectral (el espectro está normalizado a 1 en el origen, igual como en la autocorrelación), el sumador real de Rueppel excede el umbral de 0,025 en todos los casos. El test espectral no cambia sustancialmente en el sumador real. En los dos generadores autodecimados, la autocorrelación presenta un cambio significativo y recuerda de alguna manera al perfil de un ruido blanco gaussiano. Las características más importantes que han permitido diferenciar la bondad de los generadores han sido el test serie, el tercer postulado de Golomb y el parámetro CL/P. Además, la entropía por bit difícilmente proporciona algun información y no permite distinguir las desviaciones respecto el comportamiento ideal. En algunos esquemas combinadores, la relación CL/P sigue siendo baja a pesar de la mejora de complejidad lineal en valor absoluto.

Aspectos finales

Los tipos más comunes de ataques a los sistemas criptográficos (es decir, cifradores, generadores de secuencias pseudoaleatorias, etc.) son: (1) Sólo al Texto Cifrado; el oponente posee una cadena de texto cifrado. (2) Texto en Claro Conocido; el oponente posee una cadena de texto en claro (o sin cifrar) y el correspondiente texto cifrado. (3) Texto en Claro Elegido; el oponente ha obtenido acceso temporal a la máquina de cifrado y puede elegir una cadena de texto en claro y reconstruir la cadena correspondiente de texto cifrado. (4) Texto Cifrado Elegido; el oponente ha obtenido acceso temporal a la máquina de descifrado y puede elegir una cadena de texto cifrado y construir la correspondiente cadena de texto en claro. En cada caso, el objetivo es determinar la clave utilizada. El ataque más débil es el ataque sólo a texto cifrado. El ataque a texto cifrado elegido es relevante en criptosistemas de clave pública como RSA. Existe una gran variedad de esquemas de generadores de secuencias pseudoaleatorias que utilizan varios LFSR seguidos de una función combinadora no-lineal. Los generadores pseudoaleatorios comúnmente aplicados en criptografía hacen uso del LFSR, que puede ser considerado simplemente como una FSM (Finite State Machine - Máquina de Estados Finitos). Siegenthaler en 1984 introdujo el concepto de la inmunidad a la autocorrelación. Una función booleana z=f (xo, x1,...,xn) es inmune a la correlación de orden m-ésimo (1_m_n), si y sólo si su transformada de Walsh satisface S(f) (w)=0 "w / W(w) _m, siendo W(w) el peso de Hamming de la n-tupla binaria w.

• Areitio, J. "Síntesis de Generadores de Secuencias Pseudoaeatorias basados en LFSRs". Conectrónica. Noviembre 1999.

• Deavours and Kruth, L. "Machine Cryptography and Modern Cryptanalysis". Artech House. 1985.

• Newton, D.E. "Encyclopedia of Cryptology". Abo-Clio. 1997.

• Golomb, S.W. "Shift Register Sequences". Holden Day. San Francisco. 1967.

Para ampliar información sobre este y otros artículos, así como para obtener un detalle más amplio de gráficos a consejamos solicitar un el ejemplar correspondiente a este artículo de la revista CONEtrónica. En ella encontrará con más detalle todos lo editado en Internet.


Figura 1



Figura 2



Figura 3



Figura 4



Figura 5



Figura 7



Figura 8



Copyright © 2003 por Aero ENDOR Webmasters. Reservados todos los derechos.
Q S O Radios no se hace responsable por el contenido publicado de fuentes externas.