[PDF] Avances en el estudio de la complejidad lineal del filtrado no lineal

1 Curso 1994/95 CIENCIAS Y TECNOLOGÍAS PINO CABALLERO GIL Avances en el estudio de la complejidad lineal del filt...

Curso 1994/95 CIENCIAS Y TECNOLOGÍAS

PINO CABALLERO GIL

Avances en el estudio de la complejidad lineal del filtrado no lineal

Directora AMPARO FÚSTER SABATER

SOPORTES AUDIOVISUALES E INFORMÁTICOS Serie Tesis Doctorales

¿Qu´e es m´ as grande-el mar o la palabra con que lo nombramos? Emilio Adolfo Westphalen

El presente trabajo ha sido realizado bajo la direcci´on de la Doctora D˜ na Amparo F´ uster Sabater, a quien deseo expresar mi m´as profundo agradecimiento por su inestimable ayuda y permanente dedicaci´on. Tambi´en quiero hacer constar mi gratitud a los miembros del Laboratorio de Criptograf´ıa del Consejo Superior de Investigaciones Cient´ıﬁcas de Madrid, a los compa˜ neros del Departamento de Estad´ıstica, Investigaci´on Operativa y Computaci´on de la Universidad de La Laguna y a todas aquellas personas que de una u otra forma me han ayudado, especialmente a Carlos Bruno Casta˜ neda, a Antonio Sede˜ no Noda, y a mi tutor el doctor D. Joaqu´ın Sicilia Rodr´ıguez. La Laguna, a uno de Junio de 1995. Pino Caballero Gil

´Indice general Pr´ ologo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1. Conceptos B´ asicos y Antecedentes 1.1. Teor´ıa Lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1. Registros de Desplazamiento Realimentados . . . . . . 1.1.2. Polinomio Caracter´ıstico y Polinomio Minimal . . . . . 1.1.3. Propiedades de las PN-secuencias . . . . . . . . . . . . 1.1.4. Complejidad Lineal . . . . . . . . . . . . . . . . . . . . 1.1.5. Perﬁl de Complejidad Lineal . . . . . . . . . . . . . . . 1.2. Teor´ıa no Lineal . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1. Principios de Dise˜ no para el Filtrado no Lineal . . . . . 1.2.2. Aproximaciones a las Secuencias Filtradas no Linealmente . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Recorrido Bibliogr´aﬁco . . . . . . . . . . . . . . . . . . . . . . 1.3.1. Estudio de Groth sobre las Funciones de Segundo Orden 1.3.2. Caracterizaci´on de las Secuencias Seg´ un Key . . . . . . 1.3.3. Cotas de Kumar y Scholtz para Algunas Secuencias . . 1.3.4. Test de Presencia de Ra´ıces de Rueppel . . . . . . . . . 1.3.5. Recapitulaci´on de Resultados . . . . . . . . . . . . . .

15 15 17 21 27 28 30 31 34

2. Cotas de la Complejidad Lineal 2.1. Representaciones de los Cosets . . 2.2. Cosets de Distancia Fija . . . . . 2.3. Orden de la Funci´on . . . . . . . 2.4. Cota Inferior General . . . . . . . 2.5. Producto de Fases 2((d)) -distantes 2.6. Quasicosets de Distancia Fija . . 2.7. Cosets Sim´etricos . . . . . . . . . 2.8. Cotas Superiores . . . . . . . . .

55 56 57 58 59 62 67 69 75

. . . . . . . .

37 41 41 44 47 49 52

2.9. Sugerencias para la Elecci´on del Filtrado . . . . . . . . . . . . 79 3. Algoritmos de C´ alculo de Cotas Inferiores 3.1. Paso de Determinante a Cadena Binaria . 3.2. Interpretaci´on de las Operaciones L´ogicas . 3.2.1. Operaci´on AND . . . . . . . . . . . 3.2.2. Operaci´on XOR . . . . . . . . . . . 3.2.3. Operaci´on OR . . . . . . . . . . . . 3.3. Fundamento Te´orico del Algoritmo 1 . . . 3.3.1. Sistemas de Ecuaciones . . . . . . . 3.3.2. Operaciones Binarias . . . . . . . . 3.4. Algoritmo 1 . . . . . . . . . . . . . . . . . 3.4.1. Notaci´on . . . . . . . . . . . . . . . 3.4.2. Algoritmo . . . . . . . . . . . . . . 3.4.3. Ejemplo Num´erico . . . . . . . . . 3.5. Fundamento Te´orico del Algoritmo 2 . . . 3.5.1. Sistemas de Ecuaciones . . . . . . . 3.5.2. Operaciones Binarias . . . . . . . . 3.6. Algoritmo 2 . . . . . . . . . . . . . . . . . 3.6.1. Notaci´on . . . . . . . . . . . . . . . 3.6.2. Algoritmo . . . . . . . . . . . . . . 3.6.3. Ejemplo Num´erico . . . . . . . . . 3.7. Comparaci´on Entre Ambos Algoritmos . . 3.7.1. Similitudes . . . . . . . . . . . . . 3.7.2. Diferencias . . . . . . . . . . . . . . 3.8. Observaciones y Conclusiones . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

83 84 85 85 86 87 88 88 88 89 89 90 90 92 93 93 93 93 94 95 102 103 103 105

4. Procedimientos Alternativos 109 4.1. Equivalente Lineal Descompuesto . . . . . . . . . . . . . . . . 109 4.1.1. Producto de Orden Dos . . . . . . . . . . . . . . . . . 110 ´ 4.1.2. Funci´on de Orden Dos con un Unico T´ermino Producto 114 4.1.3. Suma de Dos Productos de Orden Dos . . . . . . . . . 115 4.1.4. Producto de Orden Tres . . . . . . . . . . . . . . . . . 116 4.1.5. Generalizaci´on y Conclusiones . . . . . . . . . . . . . . 117 4.2. Generalizaci´on del M´etodo de Kumar y Scholtz . . . . . . . . 117 4.2.1. Degeneraci´on de Todos los Cosets Sim´etricos . . . . . . 118 4.2.2. Degeneraci´on de Algunos Cosets Sim´etricos . . . . . . 120 4.2.3. No Degeneraci´on de Algunos Cosets . . . . . . . . . . . 121

5. Principales Aportaciones y Conclusiones

123

6. Ap´ endice 127 6.1. Algoritmo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.2. Algoritmo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Referencias

151

Pr´ ologo La importancia de la Informaci´on y por tanto de su Protecci´on es un hecho ampliamente reconocido y manifestado. Actualmente, en lo que se ha dado en llamar la Era Inform´atica toma a´ un mayor sentido la conocida frase de Bacon (1561-1626) Nam et ipsa scientia potestas est (La informaci´ on es poder). Las formas de llevar a cabo esa protecci´on han variado mucho a lo largo de los a˜ nos. De hecho, dada la actual exigencia de preservar la informaci´on mediante procesos inmediatos, los viejos procedimientos de la Criptograf´ıa Cl´asica se han visto relegados a meras curiosidades precient´ıﬁcas. A pesar de que otros conceptos criptogr´aﬁcos gozan de mayor popularidad, no cabe duda de que es el Cifrado en Flujo la u ´ nica soluci´on factible para optimizar el recurso tiempo. Su origen es pr´actica y tecnol´ogicamente la plasmaci´on del u ´ nico cifrado matem´aticamente perfecto: el Cifrado de Vernam. Las secuencias aleatorias propuestas por Vernam [169] son sustituidas en este caso por secuencias seudoaleatorias, nacidas de la tecnolog´ıa inform´atica. Sus m´etodos de generaci´on han sido analizados en profundidad durante casi dos d´ecadas debido a su maniﬁesta utilidad en una amplia variedad de situaciones tecnol´ogicas que incluyen la Seguridad y Eﬁciencia de las Comunicaciones, la Simulaci´on de Procesos Aleatorios o la Generaci´on de C´odigos entre otras. Entre las caracter´ısticas que se le exigen a una secuencia seudoaleatoria para ser de utilidad criptogr´aﬁca destaca la de una alta complejidad lineal (cantidad de secuencia necesaria para describir el resto de la secuencia). Por eso se hace necesario que a las secuencias generadas con un simple Registro de Desplazamiento con Realimentaci´on Lineal (RDRL) se les aplique una transformaci´on no lineal conocida con el nombre de Filtrado no Lineal. Dicho generador resulta o´ptimo en casi todos los aspectos, sin embargo parad´ojicamente se han llevado a cabo pocos esfuerzos en la investigaci´on sobre la complejidad lineal resultante debido fundamentalmente a la diﬁcultad que su an´alisis plantea. Por tanto el prop´osito fundamental de la presente memoria es el estudio de la complejidad lineal de varios casos de ﬁltrados no lineales. En particular se hace hincapi´e en aqu´ellos con un u ´nico t´ermino de orden m´aximo. Esto se debe a que gran parte de este trabajo puede considerarse como una continuaci´on del trabajo realizado por Rueppel con su ‘test de presencia de ra´ıces’ [152]. Por estar las t´ecnicas que se exponen en sus comienzos, no se pretende

dar ninguna soluci´on cerrada, sino que m´as bien se abre la posibilidad de continuar la investigaci´on en el futuro seg´ un las directrices que aqu´ı se inician. Para su desarrollo se ha dividido la presente memoria en cuatro cap´ıtulos organizados de la siguiente forma: En el cap´ıtulo 1, con el prop´osito de que la memoria sea autocontenida, se efect´ ua en primer lugar una revisi´on de los conceptos fundamentales que se manejan. En segundo lugar se lleva a cabo un recorrido bibliogr´aﬁco por los trabajos que conforman el punto de partida para las nuevas teor´ıas que se plantean y desarrollan en los cap´ıtulos posteriores. Adem´as se a˜ naden algunas rectiﬁcaciones y ampliaciones a las teor´ıas de cada autor. El cap´ıtulo 2 se dedica ´ıntegramente a la deducci´on te´orica de cotas de la complejidad lineal del ﬁltrado. Para ello se explotan dos maneras duales de enfocar el problema. Por un lado se obtienen para un amplio grupo de funciones no lineales cotas del valor de complejidad lineal muy generales. Por otro lado se determina un grupo de funciones no lineales para las que se tiene garantizado un alto valor de complejidad lineal. Los resultados obtenidos de ambas maneras se presentan al ﬁnal del cap´ıtulo en forma de pr´acticas sugerencias para la elecci´on del ﬁltrado. En el cap´ıtulo 3 se desarrolla una t´ecnica para el c´alculo de cotas inferiores a la complejidad lineal de los ﬁltrados no lineales. A diferencia de los esquemas existentes en los que se requiere el c´alculo de determinantes en cuerpos ﬁnitos, este m´etodo se basa u ´ nicamente en operaciones l´ogicas sobre cadenas binarias. Esta t´ecnica queda plasmada en dos algoritmos. Ambos resultan ser de gran aplicabilidad ya que s´ olo requieren que el ﬁltrado tenga un u ´ nico t´ermino de orden m´aximo. Adem´as, los resultados obtenidos permiten acotar inferiormente la complejidad lineal mediante una curva polin´ omica, lo que queda reﬂejado en estimaciones de complejidades lineales muy altas, v´alidas para muchos casos pr´acticos. En el cap´ıtulo 4 se plantean dos procedimientos alternativos cuyas bases se sit´ uan en los trabajos de Key [85] y Kumar y Scholtz [90]. Con ambos an´alisis se pone de maniﬁesto al mismo tiempo la posibilidad de enfocar el problema utilizando herramientas muy diversas, y la gran diﬁcultad que entra˜ na el estudio exhaustivo del valor concreto de la complejidad lineal. Por u ´ ltimo y a modo de ap´endice ﬁguran los diagramas de ﬂujo de los algoritmos y los listados de los programas realizados para el c´alculo num´erico.

Cap´ıtulo 1 Conceptos B´ asicos y Antecedentes Este cap´ıtulo aporta las herramientas necesarias para la investigaci´ on realizada. En las dos primeras secciones se establecen los conceptos y resultados b´asicos correspondientes respectivamente a las estructuras lineales y no lineales que se manejan. Obs´ervese que muchas deﬁniciones sencillas se exponen de forma abreviada entre par´entesis. En la u ´ ltima secci´on se hace un recorrido bibliogr´aﬁco donde se destacan aquellos resultados que constituyen el punto de partida de las nuevas teor´ıas que se desarrollan en cap´ıtulos posteriores. En esta parte se incluyen adem´as para cada autor referenciado, una serie de observaciones tales como rectiﬁcaciones y ampliaciones.

1.1.

Teor´ıa Lineal

El u ´ nico cifrado incondicionalmente seguro conocido hasta el momento es el cifrado de Vernam o de cinta aleatoria. Ahora bien, dada la longitud de la clave necesaria, este tipo de cifrado resulta poco pr´actico. De ah´ı la tendencia a usar su esquema de cifrado y descifrado para dise˜ nar nuevos sistemas que eviten el problema de la longitud de la clave. Esa es la idea de los cifrados en flujo cuyo esquema de funcionamiento se muestra en la ﬁgura 1. La situaci´on ideal para la seguridad de estos esquemas ser´ıa que la secuencia de clave o secuencia cifrante fuera aleatoria, tal y como ocurre 17

´ CONCEPTOS BASICOS Y ANTECEDENTES

Figura 1.1: Cifrado en Flujo en el cifrado de Vernam. Pero dada la necesidad pr´actica de usar un algoritmo determin´ıstico para generar la secuencia, se tiene que ´esta es siempre una secuencia ﬁnita y por tanto nunca puede ser considerada verdaderamente aleatoria. Para garantizar su seguridad criptogr´ aﬁca, a estas secuencias se les exigen una serie de caracter´ısticas que las hacen parecer aleatorias. Las secuencias que las veriﬁcan se conocen con el nombre de seudoaleatorias. Las propiedades que deben cumplir est´an contenidas en los llamados postulados de aleatoriedad que Golomb formula en [68] y que se pueden describir en el caso binario de la forma siguiente: G1. En cualquier secuencia de periodo p, el n´ umero de unos debe ser casi p igual al n´ umero de ceros, es decir, 2 si p es par y p±1 si p es impar. 2 G2. En cualquier secuencia peri´odica, aproximadamente la mitad de las rachas debe tener longitud uno, la cuarta parte de las rachas longitud dos, la octava parte longitud tres y as´ı sucesivamente. Adem´as, para cada una de estas longitudes deben existir tantas rachas de ceros como de unos. G3. La funci´on de autocorrelaci´on debe tomar los valores siguientes: Si p|t,AC(t) = 1. −1/(p − 1) si p es par = , Si p |t, AC(t)= A−D p −1/p si p es impar siendo A y D respectivamente el n´ umero de coincidencias y diferencias entre {sn } y {sn+t } Dada una secuencia {sn }, la secuencia {sn+t }=st , st+1 , st+2 , ... se llama desplazamiento de fase o fase t-´esima de {sn }, y la secuencia {sn·d }=s0 , sd , s2d , ... se llama decimaci´ on d de la secuencia {sn }.

1.1. TEOR´IA LINEAL

El u ´ ltimo postulado G3 implica que el recuento de coincidencias entre una secuencia {sn } y su desplazamiento de fase {sn+t } no debe proporcionar ninguna informaci´on sobre el periodo de la secuencia salvo cuando t es m´ ultiplo del periodo. Para comprobar la seudoaleatoriedad de las secuencias se utilizan contrastes de hip´otesis tales como el test de frecuencias (para comprobar G1), el test de las rachas y el test serial (para G2) y el test de correlaci´on (para G3). Dado que el objetivo de este trabajo no es el estudio de estos tests, para mayor informaci´on sobre los mismos pueden consultarse diversas fuentes como [102] y [88]. Por otra parte, adem´as de la aleatoriedad, existen otras propiedades que una secuencia debe cumplir para ser de utilidad criptogr´aﬁca [112], tales como: C1. El periodo p de la secuencia debe ser muy grande (aproximadamente del orden de 1050 ). C2. La secuencia ha de ser f´acil de generar. C3. El conocimiento de una parte de la secuencia cifrante no debe permitir a un criptoanalista generar la secuencia completa. Despu´es de haber dejado claras las propiedades que debe cumplir una secuencia cifrante, se estudiar´a en el pr´oximo apartado el m´as extendido de todos los m´etodos de generaci´on de dichas secuencias, los llamados registros de desplazamiento realimentados.

1.1.1.

Registros de Desplazamiento Realimentados

Existen muchas y variadas aplicaciones de las secuencias en cuerpos ﬁnitos cuyos t´erminos dependen de una forma sencilla de sus predecesores. Una ventaja computacional de estas secuencias reside en su facilidad para ser generadas mediante procedimientos recursivos. Adem´as, tal y como veremos, estas secuencias presentan algunas propiedades estructurales muy u ´tiles. En particular dichas secuencias resultan de gran inter´es tanto en Criptograf´ıa como en Teor´ıa de la Codiﬁcaci´on y algunas ramas de la Ingenier´ıa El´ectrica. Los cuerpos ﬁnitos a los que se hace referencia en este trabajo son los cuerpos de Galois GF(q), formados por los enteros {0,1,...,q-1} siendo q un n´ umero primo (cuerpo con la suma y el producto m´odulo q), y los cuerpos extensi´on ﬁnita de ´este, GF(qn ). En concreto este trabajo se dedica exclusivamente al caso binario (q=2).

´ CONCEPTOS BASICOS Y ANTECEDENTES

Figura 1.2: RDR Los generadores de las secuencias mencionadas responden todos a la forma general g(x1 , x2 , ..., xn ) = (x2 , x3 , ..., xn+1 ), donde g es una aplicaci´on de (GF(2))n en (GF(2))n . En particular resultan de mayor utilidad pr´actica aqu´ellos tales que g(x1 , x2 , ..., xn ) = (x2 , x3 , ..., h(x1 , x2 , ..., xn )), siendo h una aplicaci´on de (GF(2))n en GF(2). Dichos generadores se denominan registros de desplazamiento realimentados (RDR ´o FSR del ingl´es Feedback Shift Register) y pueden implementarse f´acilmente mediante circuitos electr´onicos. La ﬁgura 2 muestra el esquema general de un generador de este tipo. A intervalos peri´odicos determinados por un reloj, los contenidos de xi son transferidos a xi−1 . Para obtener cada nuevo valor de xn+1 se calcula una funci´on h(x1 , x2 , ..., xn ) de todos los t´erminos presentes en el registro. De esta forma la salida del generador resulta ser una secuencia de elementos recibidos en cada intervalo de una unidad de tiempo. Entre estos generadores, los m´as estudiados y utilizados son los lineales. Se habla de registro de desplazamiento con realimentaci´ on lineal (RDRL ´o LFSR del ingl´es Linear Feedback Shift Register) cuando la funci´on de realimentaci´on h se puede expresar de una forma lineal mediante h(x1 , x2 , ..., xn ) = c1 xn + c2 xn−1 + · · · + cn x1 . La notaci´on de la ﬁgura 3 ser´a la utilizada a lo largo de todo el trabajo. Tanto los coeﬁcientes ci como los d´ıgitos de salida sj son elementos del cuerpo de Galois GF(2). El n´ umero L de celdas se llama longitud del RDRL,

1.1. TEOR´IA LINEAL

Figura 1.3: RDRL y cada celda se llama etapa del RDRL. A cada vector formado por los contenidos de las L etapas sj , ..., sj+L−1 se le denomina estado del RDRL y se le denota mediante sˆj . El vector sˆ0 formado por los L d´ıgitos s0 , ..., sL−1 inicialmente cargados en las L etapas se llama estado inicial del RDRL. Si se representan como nodos cada uno de los posibles estados y se unen mediante arcos aquellos estados que van uno a continuaci´ on de otro, al digrafo resultante se le llama diagrama de transici´ on de estados. Los coeﬁcientes ci se caracterizan mediante el llamado polinomio de realimentaci´ on o de conexi´on, C(x)= 1 + c1 x + c2 x2 + · · · + cL xL que tiene como grado m´aximo L. Se denota mediante s={sn }n∈N a la secuencia producida por el RDRL. Los d´ıgitos sj (j > L − 1) se determinan a partir del RDRL y de su estado inicial seg´ un la expresi´on sj+L =

i=1

ci sj+L−i, ∀j ≥ 0,

on de o´ tambi´en sj+L + c1 sj+L−1 + · · · + cL sj = 0, conocida como relaci´ recurrencia lineal de orden L. Asociada a dicha relaci´on se tiene la matriz cuadrada de orden L y elementos binarios,      A=    

0 1 0 .. 0 0

0 0 1 . 0 0

... ... ... ... ... ...

0 c1 0 c2 0 c3 . . 0 cL−1 1 cL

     .    

Mediante esta matriz se puede describir cada estado del RDRL en funci´on

´ CONCEPTOS BASICOS Y ANTECEDENTES

del estado inicial seg´ un la expresi´on s j = s 0 Aj . Si cL = 0 se dice que el RDRL es no singular. En ese caso, cualquiera de los posibles estados del RDRL tiene un predecesor u ´ nico, por lo que su diagrama de transici´on de estados est´a formado por varias componentes conexas que son circuitos. Obs´ervese que en ese caso cualquier secuencia {sn } producida por un RDRL con un determinado estado inicial tambi´en puede obtenerse mediante un desplazamiento de fase {sn+t } generado por el mismo RDRL pero con distinto estado inicial. El n´ umero de tales desplazamientos de fase coincide con el n´ umero de nodos de la componente conexa a la que pertenece el estado inicial de partida. Se deﬁne la D-transformada o funci´ on generatriz S(x) de la secuencia {sn } como la serie S(x) =

∞

j=0

sj xj = s0 + s1 x + s2 x2 + · · ·. La idea subya-

cente en esta expresi´on consiste en que en ella quedan almacenados de forma ordenada todos los t´erminos de la secuencia, luego de alguna forma reﬂeja sus propiedades. Mediante esta funci´on y el polinomio de realimentaci´on se puede construir el polinomio, P(x)=C(x)S(x), llamado polinomio de estado inicial. Gracias a la relaci´on de recurrencia lineal se puede demostrar que este polinomio es siempre de grado menor que L. La expresi´on que lo describe se conoce como identidad fundamental. Seg´ un [71], si mcd(P(x),C(x))=1, entonces el RDRL de polinomio de realimentaci´on C(x) es el de menor longitud que puede usarse para generar la secuencia {sn } que determina la funci´on S(x). Esta propiedad jugar´a un papel fundamental en el an´alisis de Fourier que se presentar´a en el apartado 1.2.2. Una de las caracter´ısticas m´as destacables de las secuencias recurrentes lineales en un cuerpo ﬁnito es que, despu´es de un posible comportamiento irregular, siempre terminan manifestando su naturaleza peri´odica. Se denomina periodo de la secuencia {sn } al menor entero p tal que odico de {sn } a la {sn+p }= {sn } ∀n > n0 y se llama comienzo no peri´ subsecuencia s0 ,s1 , ..., sn0 . Teorema 1.1.1 Toda secuencia producida por un RDRL de longitud L es peri´ odica y su L periodo p cumple que p ≤ 2 − 1. Demostraci´ on Dado un estado inicial, si uno de los estados del RDRL es el estado nulo, entonces el periodo es exactamente p=1≤2L -1 ya que la

1.1. TEOR´IA LINEAL

secuencia se convierte en la secuencia nula despu´es de pasar por el estado nulo. Sup´ongase ahora que el RDRL no pasa por el estado nulo. Excluyendo el vector nulo existen exactamente 2L − 1 cadenas binarias distintas de longitud L. Por tanto, si se consideran los 2L primeros estados s j del RDRL, un par de valores i y j tales que se tiene forzosamente que s j = s i para alg´ L 0≤ i < j ≤ 2 −1. A partir de esa igualdad, usando la relaci´on de recurrencia lineal y un procedimiento de inducci´on se llega a que s n+j−i = s n ∀n ≥ i, lo que demuestra la periodicidad de la secuencia y que el menor periodo es p≤ j − i ≤ 2L − 1. Concretamente, si el RDRL es no singular se tiene que la secuencia producida es peri´odica desde el principio, es decir, no contiene un comienzo no peri´odico. Por eso en este trabajo s´olo se consideran RDRLs no singulares. Ejemplo 1.1.1 Dados L=4, c1 = c2 = 0, c3 = c4 = 1 y el estado inicial (1,0,0,0) se tiene el siguiente RDRL de polinomio de realimentaci´ on C(x)=1+x3+x4 . A continuaci´ on se muestran los sucesivos estados del RDRL a cada golpe de reloj. reloj 0 1 2 3 4

s0 1 0 0 0 1

s1 0 0 0 1 0

s2 0 0 1 0 0

s3 0 1 0 0 1

reloj s0 5 0 6 0 7 1 8 1 9 0

s1 0 1 1 0 1

s2 1 1 0 1 0

s3 1 0 1 0 1

reloj s0 10 1 11 0 12 1 13 1 14 1

s1 0 1 1 1 1

s2 1 1 1 1 0

s3 1 1 1 0 0

Su diagrama de transici´ on de estados est´ a formado por el nodo que representa el estado nulo y el circuito con los 15 estados distintos. La D-transformada queda de la forma S(x)=1+x4+x7 +x8 +· · ·, luego el polinomio de estado inicial es P(x)=(1+ x4 + x7 + x8 + · · ·)+ (x3 + x7 + x10 + · · · )+ (x4 + x8 + x12 + · · ·)= 1+ x3 .

1.1.2.

Polinomio Caracter´ıstico y Polinomio Minimal

Con el ﬁn de analizar la periodicidad de las secuencias generadas, a continuaci´on se deﬁne un polinomio asociado a cada RDRL mediante el cual se pueden describir los t´erminos de las secuencias. En esta secci´on tambi´en se

´ CONCEPTOS BASICOS Y ANTECEDENTES

describen las secuencias de m´aximo periodo que, seg´ un el requerimiento C1, son las que se utilizan en criptograf´ıa. Al polinomio m´onico asociado al RDRL deﬁnido en GF(2)[x] mediante c(x) = xL + c1 xL−1 + · · · + cL−1 x + cL se le conoce como polinomio caracter´ıstico del RDRL. Este polinomio s´olo depende de la relaci´on de recurrencia lineal, por lo que puede ser expresado en funci´on de la matriz A seg´ un c(x)=det(x·IL +A). Por otra parte, la relaci´on que le une con el polinomio de realimentaci´on viene dada por C(x)=xL c(x−1 ), es decir, son polinomios rec´ıprocos. Como primera aplicaci´on de este polinomio se presenta la siguiente representaci´on de los t´erminos de la secuencia. Teorema 1.1.2 Dada una secuencia binaria {sn } producida por un RDRL de longitud L y polinomio caracter´ıstico c(x), si las L ra´ıces de c(x) α1 , ..., αL son distintas, entonces sn =

j=1

βj αjn , ∀n = 0, 1, ... siendo β1 , ..., βL elementos de GF(2L )

un´ıvocamente determinados por el estado inicial. Demostraci´ on El estado inicial se puede expresar seg´ un las ecuaciones sn =

j=1

βj αjn , n=0,1,...,L-1 ya que el determinante asociado a este sistema

es un determinante de Vandermonde no nulo por ser las ra´ıces αj todas distintas. Los restantes elementos deﬁnidos seg´ un esa relaci´on veriﬁcan la relaci´on de recurrencia lineal sn+L + c1 sn+L−1 + · · · + cL sn = c1

L j=1

βj αjn+L−1 + · · · + cL

L j=1

βj αjn =

L j=1

j=1

βj αjn+L +

βj αjn c(αj ) = 0, ∀n. Por tanto, ya que

cada relaci´on de recurrencia lineal y estado inicial determinan un´ıvocamente una secuencia, se tiene que la secuencia deﬁnida mediante esa expresi´on coincide con la secuencia {sn } generada por el RDRL. En adelante se usar´a la notaci´on TrL1 para representar a la funci´on traza TrGF (2L )/GF (2) que aplica cada elemento β ∈ GF (2L) en el cuerpo GF(2) de 2 L−1 la forma TrGF (2L )/GF (2) (β) = β+ β 2 + β 2 + · · ·+ β 2 . Esta funci´on traza no es s´olo una transformaci´on lineal de GF(2L) sobre GF(2), sino que adem´as sirve como descripci´on de cualquier otra transformaci´on lineal entre ambos cuerpos [101].

1.1. TEOR´IA LINEAL

A continuaci´on se muestra un resultado an´alogo al teorema 1.2 para el caso en el que el polinomio caracter´ıstico sea irreducible. En este caso todas las ra´ıces de c(x) corresponden a distintas potencias de una de ellas y los elementos de la secuencia se expresan en t´erminos de una funci´on traza. Teorema 1.1.3 Dadas una secuencia binaria {sn } producida por un RDRL de longitud L y polinomio caracter´ıstico c(x) irreducible sobre GF(2) y α ∈GF(2L ) una ra´ız de c(x), entonces existe un u ´nico elemento A ∈GF(2L ) tal que sn = T r1L (Aαn ) =

L−1 i=0

(Aαn )2 , ∀n = 0, 1, ... i

Demostraci´ on Dado que {1,α,α2,...,αL−1 } es una base de GF(2L) sobre GF(2) por ser c(x) irreducible, se puede deﬁnir una aplicaci´on lineal f de un lo GF(2L) sobre GF(2) de la forma f(αn ) = sn (∀n = 0, 1, ..., L − 1). Seg´ ya comentado [101], toda transformaci´on lineal de GF(2L) sobre GF(2) se puede describir mediante una funci´on traza. En particular, la transformaci´on deﬁnida se puede expresar de la forma f(αn ) = sn = T r1L(Aαn ) para un u ´ nico L A∈ GF (2 ), [101]. La secuencia as´ı deﬁnida coincide con la secuencia generada por el RDRL de polinomio caracter´ıstico c(x) ya que veriﬁca la relaci´on de recurrencia lineal T r1L(Aαn+L ) + c1 T r1L (Aαn+L−1 ) + · · · + cL T r1L(Aαn )= T r1L (Aαn+L + c1 Aαn+L−1 + · · · + cLAαn )= T r1L (c(α)Aαn )= 0 ∀n ≥ 0, y posee el mismo estado inicial. Seg´ un la expresi´on de la secuencia dada en el teorema anterior, cada uno de los 2L posibles valores del coeﬁciente A determina una secuencia diferente que puede ser generada mediante el RDRL. Dado que existen exactamente 2L posibles estados iniciales del RDRL, se puede establecer una biyecci´on entre los coeﬁcientes A ∈GF(2L) y los posibles estados iniciales del RDRL. Concretamente, para cada estado inicial, mediante la expresi´on del teorema 1.3 se deﬁne un sistema de ecuaciones lineales que permite calcular el coeﬁciente A correspondiente. Por tanto siempre se puede escoger como estado inicial aqu´el que produzca el coeﬁciente A=1, quedando en ese caso la expresi´on ´ anterior de la forma sn = T r1L (αn ). Esta ser´a ampliamente utilizada en el u ´ ltimo cap´ıtulo de este trabajo. En este punto hacemos un inciso en el desarrollo normal de la memoria para introducir varios conceptos de Teor´ıa de Galois [125].

´ CONCEPTOS BASICOS Y ANTECEDENTES 2

Sea β ∈GF(2L ) entonces los elementos β, β 2, β 2 , ..., β 2 se llaman L ra´ıces conjugadas de β respecto a GF(2). Si α ∈GF(2 ) es un elemento primitivo de GF(2L) (su orden, 2L -1, coincide con el orden de GF(2L)), entonces los elementos no nulos de GF(2L) se pueden expresar como potencias de α. Siempre se puede deﬁnir una partici´on del conjunto de elementos β no nulos de GF(2L) en conjuntos disjuntos de ra´ıces conjugadas. Los conjuntos disjuntos de exponentes de esas ra´ıces conjugadas expresadas como potencias de un elemento primitivo jugar´an un papel fundamental en el desarrollo de esta memoria. Se deﬁne ahora la siguiente relaci´on de equivalencia sobre Z∗2L −1 : E1 ∼ E2 , E1 ,E2 ∈Z∗2L −1 si y s´olo si ∃i, 0≤ i ≤ L − 1 tal que E1 2i ≡ E2 mod(2L 1). Las clases de equivalencia resultantes de esta partici´on coinciden con los conjuntos disjuntos de exponentes de las ra´ıces conjugadas anteriormente mencionadas. L−1

Definici´ on 1.1.1 Se denomina coset al conjunto de todos los enteros de la forma E·2i mod(2L-1) siendo 0≤ i ≤ L − 1 y E∈ Z∗2L −1 . Observaci´ on 1.1.1 En este trabajo usamos la terminolog´ıa coset por razones de conveniencia y simplicidad en lugar de una traducci´ on como podr´ıa ser clase de equivalencia. Por extensi´on a veces tambi´en se asigna este nombre a los conjuntos de ra´ıces conjugadas. Dado que los cosets son disjuntos, siempre podemos referirnos al coset que contiene un elemento E como coset E. Al menor de sus elementos se le conoce como l´ıder del coset. Seg´ un la deﬁnici´on de coset se deduce que, si se expresan dichos enteros en base 2, todos los elementos de un mismo coset tienen exactamente el mismo peso de Hamming (n´ umero de unos en su representaci´on binaria). A este valor se le llama peso del coset. Obs´ervese que en la expresi´on de sn dada en el teorema 1.3 est´an incluidos todos los elementos del coset {1, 2, 22 , ..., 2L−1} de peso 1. Se llama cardinal del coset al n´ umero de elementos del coset. Golomb en [68] distingue los cosets E tales que mcd(E,2L − 1) = 1 del resto. A los primeros los llama cosets propios y a los dem´as, cosets impropios.

1.1. TEOR´IA LINEAL

Ejemplo 1.1.2 Para L = 4, 2L − 1 = 15 = 3 · 5, GF(24 ) = {0, 1, α, α2, ..., α14 }, GF(24 }{0}= {{1}, {α, α2, α4 , α8 }, {α3 , α6, α12 , α9}, {α5 , α10 }, {α7, α14 , α13 , α11 }} Coset E1 : 1, 2, 4, 8 : 0001, 0010, 0100, 1000 coset propio de peso 1 Coset E2 : 3, 6, 12, 9 : 0011, 0110, 1100, 1001 coset impropio de peso 2 Coset E3 : 5, 10 : 0101, 1010 coset impropio de peso 2 Coset E4 : 7, 14, 13, 11 : 0111, 1110, 1101, 1011 coset propio de peso 3 Tanto la caracterizaci´on dada en el teorema 1.3 como los cosets recien deﬁnidos juegan un papel fundamental en el tema que se analiza ya que constituyen la base de los an´alisis de algunos autores y de gran parte del presente trabajo. Tal y como ya se ha mencionado, el periodo es una de las caracter´ısticas m´as relevantes de las secuencias cifrantes. Dado que el periodo de las secuencias producidas por cualquier RDRL de longitud L est´a acotado por 2L -1, a continuaci´on se describen las secuencias cuyo periodo coincide exactamente con ese valor. Si el periodo de una secuencia producida por un RDRL de longitud L es L 2 -1, se dice que es una secuencia de longitud m´ axima, m-secuencia o PN-secuencia, y tambi´en que el RDRL que la genera es un RDRL de longitud m´ axima. Un RDRL no singular de longitud L genera una msecuencia si y s´olo si su polinomio caracter´ıstico es primitivo (polinomio de menor grado tal que una de sus ra´ıces es un elemento primitivo de GF(2L)) y el estado inicial es no nulo. Toda secuencia producida por un RDRL satisface varias relaciones de recurrencia lineal aparte de la usada para generarla. Por ejemplo, dado el periodo p de una secuencia, siempre se tiene la relaci´on v´alida sn+p =sn , ∀n = 0, 1, .... En el caso extremo de la secuencia nula se tiene que satisface cualquier relaci´on de recurrencia. Dada una secuencia binaria producida por un RDRL cualquiera, al polinomio caracter´ıstico de menor orden posible que permita describir una relaci´on de recurrencia lineal v´alida para dicha secuencia se le conoce como polinomio minimal de la secuencia. Este polinomio puede ser de menor o igual grado que el polinomio caracter´ıstico del RDRL usado para generar la secuencia, y siempre divide a los polinomios caracter´ısticos de todos los RDRLs que sirvan para generarla.

´ CONCEPTOS BASICOS Y ANTECEDENTES

El polinomio minimal es de importancia crucial para las secuencias producidas por un RDRL dado que su orden (menor entero positivo t tal que el polinomio divide a (xt − 1)) coincide con el periodo de la secuencia. Teorema 1.1.4 Dada una secuencia {sn }de polinomio minimal m(x)∈GF(2)[x], entonces el periodo de {sn } es igual a ord(m(x)). Demostraci´ on Si p es el periodo de la secuencia {sn } y n0 es la longitud de su comienzo no peri´odico, entonces sn+p = sn , ∀n ≥ n0 y en particular sn+n0 +p = sn+n0 , ∀n ≥ 0. Entonces, por su condici´on de polinomio minimal de la secuencia, m(x) divide a xn0 +p -xn0 , luego m(x)=xh g(x) con h≤ n0 y g(x)∈GF(2)[x] que divide a xp − 1. Por tanto ord(m(x))= ord(g(x))≤ p. Por otro lado, dado que el periodo p siempre divide a ord(m(x)) [101], se tiene la igualdad. A continuaci´on se da un criterio para descubrir si un polinomio caracter´ıstico de un RDRL corresponde o no al polinomio minimal de la secuencia generada. Teorema 1.1.5 Dada una secuencia binaria {sn } no nula generada por un RDRL de longitud L y polinomio caracter´ıstico c(x)∈GF(2)[x], entonces c(x) es el polinomio minimal de la secuencia si y s´olo si los estados s 0 ,s 1 ,...,s L−1 del RDRL son linealmente independientes sobre GF(2). Demostraci´ on ‘=⇒’ Se procede por reducci´on al absurdo. Si s 0 ,s 1 ,...,s L−1 fueran linealmente dependientes sobre GF(2), se tendr´ıa que b0 s 0 + b1 s 1 + · · · + bL−1 s L−1 = 0, b0 , b1 , ...bL−1 ∈GF(2). Multiplicando dicha ecuaci´on por la matriz An se tiene que b0 s n + b1 s n+1 + · · · + bL−1s n+L−1 = 0, ∀n ≥ 0. Si bj =0 ∀j = 0, se obtendr´ıa la secuencia nula sn = 0 ∀n ≥ 0, cosa que es contradictoria con las hip´otesis. Si j≥ 1 es el mayor valor tal que bj = 0, entonces la secuencia satisface una relaci´on de recurrencia lineal de orden j < L, lo que entra en contradicci´on con que c(x) sea el polinomio minimal de la secuencia. Luego s 0 ,s 1 ,...,s L−1 son linealmente independientes sobre GF(2). ‘⇐=’ Se supone por reducci´on al absurdo que c(x) no es el polinomio minimal de la secuencia. En ese caso la secuencia satisface una relaci´on lineal de orden m con 1≤ m < L, lo que contradice la independencia lineal de los L estados.

1.1. TEOR´IA LINEAL

A lo largo de esta memoria se trabajar´a siempre con PN-secuencias, es decir, con secuencias tales que su polinomio minimal es primitivo. Adem´as se considerar´a siempre el RDRL cuyo polinomio caracter´ıstico es el polinomio minimal de la secuencia.

1.1.3.

Propiedades de las PN-secuencias

En este apartado se analiza si las PN-secuencias binarias (generadas mediante un RDRL no singular de polinomio primitivo y estado inicial no nulo) cumplen o no los postulados de Golomb y los requerimientos criptogr´aﬁcos comentados en el apartado 1.1. Estas secuencias pasan con cierto margen los contrastes de hip´otesis mencionados all´ı, tal y como se deduce de las siguientes observaciones hechas para cada uno de los postulados. G1. Dado que el RDRL genera c´ıclicamente los 2L -1 estados no nulos, cada estado no nulo ocurre exactamente una vez por periodo. Luego el n´ umero de L−1 L−1 unos por periodo es 2 mientras que el de ceros es 2 -1. G2. Hay 2L−k−2 estados cuyos k+2 bits m´as signiﬁcativos son 011...10 (k unos) y otros 2L−k−2 estados para el caso 100...01 (k ceros). Luego de longitud k≤L-2 existen 2L−k−2 rachas, tanto de ceros como de unos. El estado 011...11 aparece exactamente una vez y su sucesor 111...11 va seguido a su vez por el estado 111...10, mientras que al estado 100...00 le sigue forzosamente 000...01. De todo esto se deduce que existe una racha de ceros y ninguna racha de unos de longitud L-1 y s´olo hay una racha de unos y ninguna de ceros de longitud L. G3. El n´ umero de coincidencias por periodo entre {sn } y {sn+t } viene dado por el n´ umero de ceros por periodo de {sn +sn+t }, considerando la suma m´odulo 2. Este n´ umero es 2L−1 -1 y en consecuencia el n´ umero de diferencias −1 L−1 es 2 . Por tanto la autocorrelaci´on es AC(t)= 2L −1 , cuando 1≤ t < 2L − 1. De lo anterior se concluye que las PN-secuencias cumplen satisfactoriamente los tres postulados de Golomb. Sin embargo, con respecto a las propiedades de naturaleza criptogr´aﬁca a continuaci´on se ve que, debido a la propiedad C3 del apartado 1.1, dichas secuencias no resultan suﬁcientemente seguras como claves de un cifrado en ﬂujo. C1. Dado que el periodo de una PN-secuencia generada por un RDRL de longitud L es 2L -1, se pueden conseguir f´acilmente grandes periodos. Por ejemplo para L=166 el periodo 2166 -1 ronda el valor 1050 . Adem´as ni siquiera resulta dif´ıcil encontrar, para cualquier valor de L, suﬁcientes polinomios primitivos entre los que elegir el polinomio caracter´ıstico del RDRL. En par-

´ CONCEPTOS BASICOS Y ANTECEDENTES

ticular, existen exactamente φ(2 L−1) polinomios primitivos de grado L. Por tanto, si se consideran iguales aquellas secuencias que diﬁeran s´olo en su L estado inicial, se tienen φ(2 L−1) PN-secuencias distintas. Este n´ umero crece exponencialemente a medida que L crece, de manera que, mientras para L=11 hay 176, para L=24 hay 276480. C2. Los RDRLs son muy f´aciles de implementar en hardware ya que su estructura est´a basada en puertas simples. C3. Las PN-secuencias resultan muy inseguras dado que el conocimiento de 2L d´ıgitos consecutivos sk , sk+1 , ..., sk+2L−1 permite al criptoanalista determinar exactamente los coeﬁcientes de realimentaci´on ci y de ah´ı la secuencia completa. Esto es posible mediante la ecuaci´on matricial L

    

sj+L−1 sj+L−2 sj+L sj+L−1 .. . sj+2L−2 sj+2L−3

. sj . sj+1 . . . sj+L−1

    

c1 c2 .. cL





   

=

  

sj+L sj+L+1 .. sj+2L−1

    

Por el teorema 1.5 se tiene que cualesquiera L estados consecutivos son siempre linealmente independientes. Por tanto, la ecuaci´on matricial anterior representa un sistema compatible de L ecuaciones cuyas soluciones son los coeﬁcientes ci . De lo anterior se concluye que el u ´nico de estos requerimientos que no cumplen las PN-secuencias es el requerimiento C3, por tanto en lo que resta de cap´ıtulo se proceder´a de la siguiente manera: 1. Se presentar´an herramientas que permitan analizar el requerimiento C3. 2. Se estudiar´an con ellas otros tipos de generador de secuencia cifrante. Con respecto a este u ´ltimo paso, dado que las PN-secuencias cumplen el resto de propiedades, resulta bastante natural aprovechar esas buenas cualidades de los RDRLs que las generan. Para ello lo l´ogico es utilizar estos RDRLs de una forma no lineal de manera que no se modiﬁquen dichas propiedades, pero s´ı se veriﬁque el requerimiento C3. Esto se har´a en la secci´on 1.2. Por otro lado, el primer paso mencionado se desarrollar´a a lo largo de los dos siguientes apartados.

1.1. TEOR´IA LINEAL

1.1.4.

Complejidad Lineal

La complejidad lineal de una secuencia peri´odica es el concepto central de este trabajo. Toda secuencia binaria de periodo p puede generarse siempre mediante un RDRL. Al menos siempre se puede considerar como estado inicial el primer periodo y como polinomio caracter´ıstico 1+xp . En general se deﬁne la complejidad lineal de una secuencia peri´odica {sn } como la longitud del menor RDRL que puede utilizarse para generarla. A este RDRL se le conoce como equivalente lineal de la secuencia. El polinomio caracter´ıstico del equivalente lineal es el polinomio minimal de la secuencia {sn }. En el caso de secuencias inﬁnitas se habla de complejidad lineal global y se denota como Λ({sn }) mientras que en el caso de secuencias ﬁnitas sn = s0 , s1 , ..., sn−1 se habla de complejidad lineal local y se denota mediante Λ(sn ) (´o tambi´en Ln ). Evidentemente una secuencia ﬁnita sn , realizaci´on concreta de una secuencia inﬁnita {sn }, tiene su complejidad lineal local acotada inferiormente por la complejidad lineal global de ´esta, Λ(sn ) ≤ Λ({sn }). Dado que se trata de determinar la secuencia entera a partir del conocimiento de una parte, resulta evidente la importancia del estudio de la complejidad lineal como medida de impredecibilidad de la secuencia. Seg´ un lo comentado en el apartado anterior, siempre se puede obtener la secuencia completa {sn } a partir de 2 · Λ({sn }) d´ıgitos conocidos. Existe un algoritmo bien conocido para calcular la complejidad lineal local de una secuencia conocida a partir de sus d´ıgitos. El prop´osito inicial del algoritmo dise˜ nado por Berlekamp [4] era la decodiﬁcaci´on de c´odigos BCH, pero posteriormente Massey [111] demostr´o su utilidad para el c´alculo de la complejidad lineal local. A partir de entonces el algoritmo se conoce como algoritmo de Berlekamp-Massey. El algoritmo de Berlekamp-Massey relaciona las complejidades lineales locales asociadas respectivamente a los primeros n y n-1 d´ıgitos de una misma secuencia binaria Λ(sn ) y Λ(sn−1 ). Se llama discrepancia y se denota como δn−1 a la diferencia entre el n-´esimo d´ıgito de la secuencia analizada sn−1 y el n-´esimo d´ıgito generado por el equivalente lineal de la secuencia sn−1 . Obviamente si el equivalente lineal de sn−1 tambi´en genera la secuencia sn , entonces δn−1 =0 y ambas complejidades lineales locales coinciden Λ(sn )=Λ(sn−1). Si, por el contrario dicho RDRL no sirve para generar sn , entonces δn−1 =1 y la complejidad lineal local de sn es mayor que la de sn−1 cuando la de ´esta es

´ CONCEPTOS BASICOS Y ANTECEDENTES

menor que n2 . Por tanto, el proceso de actualizaci´on de la complejidad lineal local que se lleva a cabo en el algoritmo de Berlekamp-Massey, cuya completa descripci´on se puede encontrar en [112], se resume como sigue. n n−1 * Si δn−1 = 0 entonces Λ(s ) ) = Λ(s n Λ(s ) = Λ(sn−1 ) si Λ(sn−1 ) ≥ n2 * Si δn−1 = 1 entonces Λ(sn ) = n + 1 − Λ(sn−1 ) si Λ(sn−1 ) < n2 Por u ´ ltimo hay que destacar que el algoritmo de Berlekamp-Massey es aplicable a todo tipo de secuencias binarias, tanto las generadas linealmente como las no lineales.

1.1.5.

Perfil de Complejidad Lineal

La complejidad lineal de una secuencia es una medida de su impredecibilidad, mientras que el llamado perﬁl de complejidad lineal reﬂeja su aleatoriedad. Ya se ha mencionado que si una secuencia tiene periodo p entonces puede ser generada con un RDRL de longitud p, polinomio caracter´ıstico 1+xp y estado inicial correspondiente al primer periodo de la secuencia. A este generador se le conoce como RDRL c´ıclico puro. De lo anterior se tiene que la complejidad lineal de una secuencia nunca puede superar el valor de su periodo. Como se ha dicho en el apartado anterior, el algoritmo de BerlekampMassey sirve para calcular la complejidad lineal local Ln . Adem´as, para calcular Ln este algoritmo necesita previamente calcular todas las complejidades lineales L1 , L2 ,..., Ln−1 de las subsecuencias s0 , s0 s1 ,..., s0 s1 ...sn−2 . Se llama perfil de complejidad lineal (PCL) de la secuencia sn al vector de complejidades lineales locales (L1 , L2 , .., Ln ). El PCL representa el comportamiento din´amico de la complejidad lineal local frente al n´ umero n de d´ıgitos considerados. Se dice que el PCL tiene un salto en sk−1 si Lk − Lk−1 > 0 y esta diferencia se llama peso del salto. A partir del algoritmo de Berlekamp-Massey se sabe que s´olo puede haber salto en sk−1 si 2Lk−1 < k y que si lo hay entonces Lk = k + 1 − Lk−1 . La secuencia 1000111101000011011110100010100 obtenida lanzando una moneda 31 veces puede ser utilizada para ilustrar el concepto de perﬁl de complejidad lineal como medida de aleatoriedad. Se considera la secuencia s obtenida repitiendo sucesivamente la secuencia anterior. Si se representa su PCL frente al n´ umero de d´ıgitos n se observa que se aproxima a la recta n2

1.2. TEOR´IA NO LINEAL

desde n=1 hasta n=62. A partir de n=62 las sucesivas complejidades lineales locales permanecen constantes e iguales a 31 (periodo de la secuencia). De ah´ı se puede deducir que el polinomio caracter´ıstico de menor orden que se puede usar para generar la secuencia es 1+x31 y por tanto que la complejidad lineal global de esta secuencia toma su valor m´aximo, el periodo. Por otro lado, para mostrar que la exigencia de un alto valor de complejidad lineal no es condici´on suﬁciente para garantizar aleatoriedad, consid´erese ahora la secuencia formada por treinta ceros y un uno. Esta secuencia puede ser generada, igual que en el caso anterior, por el RDRL c´ıclico puro de longitud 31. Sin embargo, al contrario que en el caso anterior, esta secuencia no cumple ninguna de las propiedades de aleatoriedad. Esto puede asociarse a su PCL, pues en ´el las complejidades lineales locales se mantienen iguales a 0 hasta el caso n=31 en que pasa a valer 31, donde se mantiene para valores mayores de n. Seg´ un estos sencillos ejemplos es f´acil asociar la idea de aleatoriedad de una secuencia a la cercan´ıa de su PCL a la recta n2 , cuesti´on demostrada te´oricamente en [91]. Adem´as hay que mencionar que la no aleatoriedad reﬂejada en el PCL ha demostrado ser de gran utilidad pr´actica ya que en muchos casos pasa desapercibida para los tests estad´ısticos. No obstante como u ´ ltima indicaci´on sobre el PCL hay que aclarar que aunque la cercan´ıa a la recta n2 es una cualidad necesaria para la aleatoriedad de la secuencia, esta condici´on no es suﬁciente ya que una regularidad excesiva en el PCL es incompatible con los postulados de Golomb. Sirva como muestra de ello la secuencia 11010001071015 1031 ..., donde 0x representa una secuencia de x ceros consecutivos. Tal y como primero conjetur´o Rueppel [152] y luego o Dai [27], esa secuencia tiene complejidad lineal

demostr´ n+1 local de valor 2 . Esta funci´on ciertamente est´a muy cercana a n2 pero su regularidad maniﬁesta claramente la no aleatoriedad de la secuencia, que queda por otra parte demostrada mediante contrastes de hip´otesis.

1.2.

Teor´ıa no Lineal

Para intentar conseguir una alta impredecibilidad de las secuencias producidas, los generadores de secuencia cifrante normalmente incorporan uno o varios RDRLs y alguna transformaci´on no lineal. Tal y como se vi´o en la secci´on anterior, la complejidad lineal proporciona una medida de dicha impredecibilidad. Por tanto resulta bastante conveniente poder analizar las

´ CONCEPTOS BASICOS Y ANTECEDENTES

secuencias cifrantes en t´erminos de su complejidad lineal. De ah´ı que un factor a tener en cuenta a la hora de dise˜ nar un generador es la posibilidad de an´alisis de esta propiedad. En esta secci´on se presentan algunas herramientas te´oricas que permiten calcular o acotar inferiormente la complejidad lineal global de algunas secuencias cifrantes. La transformaci´on no lineal m´as sencilla de todas es sin duda el producto ´ de dos d´ıgitos binarios (operaci´on AND). Esta encuentra su generalizaci´on natural en el caso de las funciones booleanas. De hecho existe una expresi´on can´onica para las funciones booleanas llamada forma algebraica normal (FAN) que representa dichas funciones como sumas de productos. Dado x= (x1 , x2 , ..., xL ) ∈ {0, 1}L, la FAN de una funci´on booleana no lineal f se puede escribir como f (x) = a0 + a1 x1 + · · · + aL xL + a1,2 x1 x2 + · · · + aL−1,L xL−1 xL + · · · + a1,2,...,L x1 x2 ...xL . Se llama producto de orden n a un producto de n variables y se llama orden de una funci´ on booleana al mayor de los o´rdenes de todos los t´erminos de su FAN. La FAN representa un sistema de referencia v´alido para toda la teor´ıa no lineal de las secuencias que, adem´as resultar´a de gran utilidad ya que existe cierta relaci´on entre el orden de la funci´on no lineal y la complejidad lineal de la secuencia resultante. Seg´ un el tipo de transformaci´on no lineal utilizada se distinguen dos m´etodos de generaci´on de secuencia cifrante. El llamado filtrado no lineal de un RDRL consiste en una funci´on booleana no lineal que se aplica a las etapas de un RDRL tal y como se muestra en la ﬁgura 4. En adelante se denota mediante z = {zn }n∈N a la secuencia resultante a la salida de un ﬁltrado no lineal f, llamada en muchos casos secuencia filtrada. Se tiene que z0 = f (s 0 ), z1 = f (s 1 ),..., z2L −2 = f (s 2L −2 ). En este caso la tendencia de la mayor´ıa de autores, seg´ un se ver´a en la secci´on 1.3, ha sido centrarse en la b´ usqueda de conjuntos de funciones no lineales que produzcan secuencias de complejidad lineal global predecible. Se suele seguir esta v´ıa porque en general, tal y como se menciona en [152], ‘es extremadamente dif´ıcil acotar inferiormente (o garantizar) la complejidad lineal de las secuencias producidas por un ﬁltrado no lineal de un RDRL’. Nosotros en este trabajo abordaremos este problema.

1.2. TEOR´IA NO LINEAL

Figura 1.4: Filtrado no Lineal El segundo m´etodo de generaci´on de secuencias cifrantes utiliza la combinaci´on no lineal de RDRLs. Las secuencias producidas por varios RDRLs se combinan mediante una funci´on no lineal F obteni´endose un generador conocido como combinador no lineal, cuyo funcionamiento se muestra en la ﬁgura 5. En el estudio de la complejidad lineal global del combinador no lineal el problema consiste generalmente en, dada una funci´on no lineal F, encontrar tipos de RDRLs para los que el generador resultante tenga una complejidad lineal global predecible. Este problema es bastante m´as f´acil que el anterior y prueba de ello es que ya se han encontrado ([85], [180], [153], [56]) reglas sencillas para la elecci´on de los RDRLs que permiten un completo an´alisis de la complejidad lineal global del combinador no lineal resultante. En ambos casos, ﬁltrado y combinador no lineales: a) Los RDRLs proporcionan a la secuencia de salida una buena distribuci´on estad´ıstica y un gran periodo. b) La funci´on no lineal proporciona ‘confusi´on’ (no existe una relaci´on sencilla entre el texto original y el texto cifrado) [158] y una gran complejidad lineal. c) La clave secreta determina el estado inicial del RDRL(s) y puede tambi´en determinar la elecci´on de la funci´on no lineal concreta.

´ CONCEPTOS BASICOS Y ANTECEDENTES

Figura 1.5: Combinador no Lineal Dada la estructura del ﬁltrado no lineal, la mejor complejidad lineal global que se puede obtener es 2L − 1. El inter´es de este trabajo consiste en intentar demostrar que muchas secuencias ﬁltradas no linealmente tienen una complejidad lineal global muy grande. Tal y como se menciona en la secci´on anterior, si un RDRL no singular tiene polinomio de conexi´on primitivo y estado inicial no nulo, entonces los 2L − 1 estados siguientes son todos distintos y no nulos. Dado que para deﬁnir un´ıvocamente una funci´on hay que asignar una salida a cada una de las posibles entradas, tal y como se aﬁrma en [152], para cada RDRL de m´axima longitud y estado inicial no nulo existe una u ´nica correspondencia entre cada una de las posibles secuencias no nulas de longitud 2L -1 y alguna funci´on f de GF(2L) en GF(2). Esto implica que, para cualquiera de las posibles secuencias binarias de longitud 2L -1 siempre se puede encontrar una funci´on no lineal que aplicada a un RDRL de m´axima longitud genere esa secuencia. En particular existe dicha funci´on para todas las secuencias peri´odicas cuya complejidad lineal global est´a cercana al valor del periodo. El problema consiste en encontrar la relaci´on existente entre cada funci´on y la complejidad lineal global de la secuencia generada. El principal objetivo de este trabajo es intentar descubrir dicha relaci´on para una clase amplia de funciones. En el pr´oximo apartado se ven una serie de condiciones m´ınimas que debe cumplir un ﬁltrado no lineal para poder ser utilizado como generador de secuencia cifrante.

1.2. TEOR´IA NO LINEAL

1.2.1.

Principios de Dise˜ no para el Filtrado no Lineal

Los principios de dise˜ no [112] est´an se˜ nalados con P1, P2,.... En primer lugar, tal y como se mostr´o en la secci´on anterior, para partir de una buena base es necesario utilizar un RDRL de longitud m´axima y estado inicial no nulo. De esta forma se consiguen un periodo grande (C1) y buenas propiedades estad´ısticas (postulados de Golomb). En particular, si se parte de un RDRL de estas caracter´ısticas y longitud L, se obtiene a la salida una secuencia ﬁltrada cuyo periodo es 2L -1 ´o un divisor suyo. Por tanto el primer principio se puede escribir como sigue. P1. Utilizar un RDRL de longitud m´axima y estado inicial no nulo para obtener un gran periodo y buenas caracter´ısticas estad´ısticas. Tal y como ya se ha mencionado, la secuencia generada por un RDRL c´ıclico puro con estado inicial 00...001 tiene complejidad lineal global m´axima pero a cambio no cumple los postulados de Golomb. En relaci´ on con esto se tiene el siguiente resultado. Lema 1.2.1 El producto de todas las etapas de un RDRL no singular de longitud L, polinomio caracter´ıstico primitivo y estado inicial no nulo siempre produce una secuencia de m´ axima complejidad lineal global 2L -1. Demostraci´ on La secuencia generada por un RDRL no singular con polinomio caracter´ıstico primitivo es una PN-secuencia, por lo que en el diagrama de transici´on de estados el circuito contiene exactamente una vez ´ el estado formado por L unos. Este es el u ´ nico estado que produce para el ﬁltrado no lineal de la hip´otesis una salida de valor 1, por lo que la secuencia de salida de dicho ﬁltrado es la secuencia formada por 2L − 2 ceros y un uno, que ya sabemos tiene complejidad lineal 2L − 1. Seg´ un el comentario anterior al lema, se puede concluir la inutilidad de dicho producto como ﬁltrado no lineal por producir una secuencia que, a pesar de tener m´axima complejidad lineal global, no tiene las propiedades de aleatoriedad requeridas. Esto mismo se puede hacer extensivo a todas las transformaciones no lineales que incluyan s´olo productos de un orden alto, ya que las secuencias resultantes pueden aproximarse mediante la secuencia nula cometiendo s´olo errores en unos pocos bits. Esta predecibilidad queda de maniﬁesto en su PCL ya que no se aproxima a la recta n/2. Todo este razonamiento conduce a la

´ CONCEPTOS BASICOS Y ANTECEDENTES

recomendaci´on de utilizar transformaciones no lineales que incluyan varios productos de todos los o´rdenes, y que tengan un orden m´aximo no muy alto. La primera parte est´a contenida en el siguiente principio. P2. Incluir en la funci´on no lineal varios t´erminos de cada orden para conseguir una buena confusi´on. Por otro lado, seg´ un se ver´a m´as adelante, el orden k de la funci´on no lineal juega un papel fundamental en la determinaci´on de la complejidad lineal global de la secuencia producida, hasta el punto de que ´esta siempre L est´a acotada superiormente por ki=1 ( ). Esta propiedad sugiere el uso de i un orden k alto. Luego para llegar a un compromiso entre este razonamiento y el anterior al P2 se recomienda utilizar una funci´on de orden de valor aproximado a L/2, lo que queda recogido como sigue. P3. Escoger una funci´on no lineal de orden k que permita obtener una complejidad lineal global cercana al valor m´aximo k ∼ L/2. Las buenas caracter´ısticas estad´ısticas de la PN-secuencia pueden verse perjudicadas por una mala elecci´on de la funci´on booleana. Para intentar evitarlo, al menos se puede garantizar el cumplimiento del primer postulado de Golomb mediante el uso de un t´ermino lineal ya que la funci´on de la forma x1 + fs (x2 , ..., xn ) produce una secuencia binaria que contiene aproximadamente la mitad de unos, cuesti´on que se resume en el siguiente principio. P4. Incluir en la funci´on no lineal un t´ermino lineal para garantizar algunas propiedades estad´ısticas. Por u ´ ltimo, dado que la clave es secreta resulta bastante apropiado extender la inﬂuencia de este secreto no s´olo al estado inicial del RDRL sino tambi´en a la funci´on no lineal. De esa manera se podr´ıa hacer que cada clave estuviera formada por un estado inicial y una funci´on no lineal, tal y como se indica en el siguiente principio. P5. Hacer que la clave determine el estado inicial del RDRL y algunos t´erminos de la funci´on no lineal. Estos cinco principios pueden ser complementados en casos particulares con otros principios adicionales. De hecho, al ﬁnal del pr´oximo cap´ıtulo se aportar´an nuevas sugerencias que se sumar´an a ´estos. No obstante, aunque se sigan todos estos criterios en la elecci´on del ﬁltrado no lineal, la diﬁcultad principal en el manejo de estas transformaciones no lineales reside en su diﬁcultad de an´alisis. Este hecho se maniﬁesta claramente en el pr´oximo apartado donde se plantean varias formas diferentes de abordar este problema.

1.2. TEOR´IA NO LINEAL

1.2.2.

Aproximaciones a las Secuencias Filtradas no Linealmente

Aproximaci´ on Matricial Forma Algebraica Normal La primera aproximaci´on viene dada por la FAN de la funci´on no lineal ya que, como veremos, cualquier secuencia ﬁltrada puede expresarse como combinaci´on lineal de una serie de vectores linealmente independientes que quedan determinados a partir de la FAN del ﬁltrado no lineal. En particular, dada una PN-secuencia s={sn }, si se denota como s n+t ∈ L {0, 1}2 −1 al vector formado por el primer periodo del desplazamiento de fase L {sn+t } y como z n ∈ {0, 1}2 −1 al vector formado por el primer periodo de la secuencia ﬁltrada, seg´ un la FAN se tiene que z n = a1 s n+1 + · · · + aL s n+L + a1,2 s n+1 s n+2 + · · · + a1,2,...,L s n+1 · · · s n+L , donde los productos entre vectores son productos vectoriales. L Por tanto, dado que cualquier vector z n ∈ {0, 1}2 −1 puede expresarse como la combinaci´on lineal anterior, los 2L -1 vectores s n+1 , ..., s n+L , s n+1 s n+2 , ..., s n+1 s n+2 · · · s n+L son linealmente independientes tal y como indica el siguiente resultado. Lema 1.2.2 Si una funci´on no lineal f se aplica sobre las etapas de un RDRL de m´ axiL ma longitud, entonces las 2 -1 secuencias correspondientes a los t´erminos de la FAN son linealmente independientes y constituyen una base del espacio vectorial de las secuencias de periodo 2L -1. Dado que cada coeﬁciente de la FAN de f indica la participaci´on o no de cada secuencia de la base anterior, la FAN de f proporciona una descripci´on natural de la secuencia ﬁltrada. El problema de esta representaci´on surge cuando hay que obtener el primer periodo de la secuencia {zn } a partir de la expresi´on matricial z n = P t · A, donde P es una matriz cuadrada de orden 2L -1 cuyas ﬁlas est´an formadas respectivamente por s n+1 , ..., s n+1 ...s n+L y A aqu´ı denota el vector de coeﬁcientes de la FAN. Dada la dimensi´on de la matriz P, incluso para valores de L peque˜ nos, esta aproximaci´on implica un c´alculo matricial irrealizable.

´ CONCEPTOS BASICOS Y ANTECEDENTES

Equivalente Lineal Descompuesto Cualquier secuencia de periodo 2 − 1 se puede generar mediante un RDRL c´ıclico puro de longitud 2L − 1 tomando simplemente como estado inicial el primer periodo de la secuencia. De este hecho se obtiene una segunda representaci´on [152] de la secuencia ﬁltrada como suma de secuencias tal y como se ve a continuaci´on. El polinomio de conexi´on del RDRL c´ıclico puro de longitud 2L − 1 es 2L −1 +1, por lo que puede expresarse como producto de todos los polinomios x L irreducibles Ci (x) de grados divisores de L (salvo el polinomio x): x2 −1 +1 = Ci (x). L

Si esta propiedad se aplica a la identidad fundamental se tiene que S(x) = = CPii(x) , siendo el grado de Pi (x) menor que el de Ci (x). Por tanto (x)

P (x) x2L −1 +1

se ha logrado expresar la D-transformada de la secuencia ﬁltrada como suma de D-transformadas de secuencias generadas por varios RDRLs de polinomios de conexi´on Ci (x) cuya suma de longitudes coincide con 2L -1. De ah´ı que las 2L -1 secuencias correspondientes a las etapas de cada uno de estos RDRLs, tomando como estados iniciales vectores con un u ´nico uno, puedan considerarse como una segunda base para el espacio vectorial de las secuencias de periodo 2L -1. Esta segunda representaci´on implica la descomposici´on del RDRL de longitud L ﬁltrado no linealmente en un generador formado por varios RDRLs cuyos polinomios de conexi´on son polinomios irreducibles de grados divisores de L. A este generador se le conoce como equivalente lineal descompuesto y un ejemplo de su estructura se muestra en la ﬁgura 6. Cada polinomio de estado inicial Pi (x) nulo implica un estado inicial nulo para el RDRL correspondiente al polinomio de conexi´on Ci (x), es decir, implica la ausencia de dicho componente en el equivalente. La desventaja de este m´etodo viene dada, al igual que en el primer caso, por la necesidad de manejo de matrices de orden 2L -1. Los estados iniciales de los RDRLs componentes del equivalente han de obtenerse mediante la expresi´on matricial z n = D t · R, donde D es una matriz cuadrada de orden 2L -1 cuyas ﬁlas est´an formadas por las 2L -1 subsecuencias de longitud 2L -1 (correspondientes a las etapas de cada uno de los componentes y generadas a partir de estados iniciales con un u ´nico 1), y R es un vector de dimensi´on 2L -1 formado por los estados iniciales de todas las componentes del equivalente. El equivalente lineal descompuesto planteado es el antecedente de un nuevo equivalente que se presentar´a en el u ´ ltimo cap´ıtulo.

1.2. TEOR´IA NO LINEAL

Figura 1.6: Equivalente Lineal Descompuesto Estas dos aproximaciones proporcionan las herramientas necesarias para generar una funci´on no lineal que produzca una secuencia de complejidad lineal global garantizada, tal y como se ve en el siguiente apartado. C´ omo Garantizar la Complejidad Lineal Dado un valor de complejidad lineal, para un dise˜ nador de generadores de secuencia cifrante ser´ıa muy conveniente poder encontrar una funci´on no lineal que produzca una secuencia ﬁltrada con ese valor de complejidad lineal. Combinando las dos expresiones matriciales dadas en los apartados anteriores se obtiene A = (P t )−1 D t R = (D · P −1 )t R. Seg´ un esta expresi´on, siempre pueden escogerse los estados iniciales para cada una de las componentes del equivalente lineal descompuesto (R) y deducir mediante A qu´e funci´on no lineal concreta produce la secuencia ﬁltrada. Esto implica la elecci´on previa de la complejidad lineal global del generador mediante la adjudicaci´on de estados iniciales no nulos a aquellas componentes cuya suma de longitudes proporciona la complejidad lineal deseada. De nuevo, lo que inutiliza este m´etodo es la enorme dimensi´on de las matrices que hay que manejar ( 2L -1). En el siguiente apartado se plantea un acercamiento muy distinto al problema del an´alisis del ﬁltrado no lineal, mediante transformadas discretas de

´ CONCEPTOS BASICOS Y ANTECEDENTES

42 Fourier.

Aproximaci´ on Mediante el An´ alisis de Fourier Las transformadas de Fourier en un cuerpo de Galois juegan un papel muy importante en el estudio y procesamiento de las se˜ nales. En este apartado se extiende su aplicaci´on al an´alisis del ﬁltrado no lineal. Se dan aqu´ı sin demostraci´on algunos resultados fundamentales obtenidos mediante esta aproximaci´on por varios autores, Blahut [7], Massey y Serconek [116] y Paterson [143]. Dada una secuencia {sn }, se deﬁne la transformada discreta de Fourier (TDF) de sp = s0 , ..., sp−1 como el vector Sp = (S0 , ..., Sp−1 ) donde Si =

p−1

k=0

sk w ik con i=0,...,p-1 y w un elemento primitivo de orden p.

La secuencia puede obtenerse mediante la inversa de la TDF deﬁnida como sj =

1 p

p−1 i=0

Si w −ij con j=0,...,p-1.

Las componentes de las p-uplas sp y Sp pueden utilizarse respectivamente como coeﬁcientes de dos polinomios s(x) y S(x) de grados menores o iguales que p-1, s(x) = s0 + s1 x + · · · + sp−1 xp−1 y S(x) = S0 + S1 x + · · · + Sp−1 xp−1 . Seg´ un estas representaciones las deﬁniciones de TDF e inversa de TDF se pueden escribir como Si = s(w i) y sj = 1p S(w −j ) con i,j∈ {0,1,...,p-1}. El siguiente resultado debido a Blahut [7] conﬁrma la utilidad de la TDF para el c´alculo de la complejidad lineal global de una secuencia peri´odica. Teorema 1.2.1 Si {sn } tiene periodo p y Sp es la TDF de sp , entonces Λ({sn }) = WH (S p ). La TDF constituye una herramienta u ´ til para el an´alisis de las transformaciones no lineales de RDRLs, seg´ un se observa en las siguientes aplicaciones a los casos de un ﬁltrado no lineal de orden 2 [116] y un producto de fases equidistantes [143]. En 1994 [116] Massey y Serconek demuestran el siguiente resultado utilizando la herramienta propuesta. Proposici´ on 1.2.1 Dadas una secuencia {sn } de polinomio minimal c(x)∈ GF (2)[x] primitivo y de grado L primo, y la secuencia {zn } definida mediante zn = sn sn+δ , entonces la complejidad lineal de la secuencia resultante viene dada por Λ({zn }) = L L+( ). 2

´ 1.3. RECORRIDO BIBLIOGRAFICO

Este mismo resultado ser´a demostrado en el u ´ ltimo cap´ıtulo sin necesidad de utilizar transformadas discretas de Fourier. Tambi´en en 1994 [143] Paterson ampl´ıa este resultado a los casos de un producto de fases equidistantes y de una suma de productos de fases equidistantes. En el primer caso demuestra el siguiente resultado. Teorema 1.2.2 Dadas una secuencia {sn } de polinomio minimal c(x)∈ GF (2)[x] primitivo y de grado L primo, y la secuencia {zn } definida mediante zn = sn sn+δ sn+2δ · · · sn+(k−1)δ , si t es el menor entero positivo tal que 2L − 1|δ(2t − 1), t entonces Λ({zn }) ( )( Lt )k . k Al generalizar el resultado anterior se obtiene el siguiente. Teorema 1.2.3 Dadas una secuencia {sn } de polinomio minimal c(x)∈ GF (2)[x] primitivo y de grado L primo, y la secuencia {zn } definida mediante zn =

N −1 i=0

bi sn+i

sn+i+δ · · · sn+i+(k−1)δ , si t es el menor entero positivo tal que 2L − 1|δ(2t − 1), t entonces Λ({zn }) ≥ ( )( Lt )k − (N − 1). k Obs´ervese que la mejor cota que se puede obtener seg´ un este u ´ ltimo resultado viene dada para el caso t=L. La cota alcanzada para este caso tambi´en se demostrar´a en un apartado posterior sin necesidad de utilizar transformadas discretas de Fourier. En la pr´oxima secci´on se ver´an por orden cronol´ogico las diferentes aproximaciones al estudio de la complejidad lineal del ﬁltrado no lineal llevadas a cabo por algunos de los autores m´as representativos en este campo.

1.3.

Recorrido Bibliogr´ afico

1.3.1.

Estudio de Groth sobre las Funciones de Segundo Orden

En 1971 Groth [71] estudia el caso de sumas de productos de segundo orden de etapas de un RDRL con polinomio caracter´ıstico primitivo. Presenta la complejidad lineal como un par´ametro controlable y directamente

´ CONCEPTOS BASICOS Y ANTECEDENTES

proporcional al orden de la funci´on y no admite la existencia de posibles irregularidades. Para realizar su an´alisis impone las siguientes restricciones. El RDRL debe ser de longitud m´axima y la funci´on no lineal una suma de productos de orden dos tales que las fases consideradas no sobrepasen la longitud del RDRL. Adem´as como u ´ ltima restricci´on considera en todo caso el estado inicial s0 = s1 = · · · = sL−2 = 0, sL−1 = 1. Bajo estas condiciones la funci´on generatriz de la secuencia ﬁltrada {bn } se puede escribir como B(x) = y bin =

L−1 l=1

∞

n=0

bn xn =

L−1

∞ bi xn

B i (x) donde B i (x) =

n=0

i=1

eil,l+isL+n−l sL+n−(l+i) .

La expresi´on de B1 (x) se simpliﬁca de la siguiente forma B 1 (x) =

L−1

e1l,l+1 xl ([sL−l sL−(l+1) x−l + · · · + sL−1 sL−2 x−1 ]+

l=1 ∞

sL+n sL+n−1 xn )

n=0

Debido a la u ´ ltima restricci´on considerada la expresi´on entre corchetes se anula. Adem´as, utilizando la relaci´on de recurrencia lineal y esa misma restricci´on se tiene que B i (x)=

L−i l=1

eil,l+ixl Si , donde Si =

k=1

ck xi Sk−i.

De todo esto se obtiene la siguiente expresi´on de la funci´on generatriz de la secuencia B(x) =

L−1 L−i i=1 l=1

eil,l+ixl Si . De la deﬁnici´on recursiva de Si resultan

tambi´en expresiones con sub´ındices negativos, de manera que utilizando de nuevo la u ´ ltima restricci´on se obtiene que S−i = x−i Si . Esta igualdad se aplica al siguiente sistema de L-1 ecuaciones con L-1 inc´ognitas,        

1 + C2 x C3 x · CL−1 x 1 + C4 x2 · x2 C1 x + C3 x2 · · · · L−3 L−2 L−4 L−2 CL−3 x + CL−1 x CL−4 x +x · 1 L−3 CL−2 xL−2 + xL−1 C x · C 1x L−3  C1 x    C2 x2     · S0     L−2   CL−2 x  L−1 CL−1 x

x 0 · 0 1

       

S1 S2 · SL−2 SL−1

       

´ 1.3. RECORRIDO BIBLIOGRAFICO

Debido a la presencia de L-1 potencias de x en la diagonal menor se tiene que, seg´ un la regla de Cramer, en el denominador de las soluciones aparece un polinomio de grado L(L-1)/2. El determinante del numerador corresponde a un polinomio del mismo grado. Al desarrollar este determinante por los elementos de la matriz t´ermino independiente siempre se puede sacar como factor com´ un una potencia de x. Denotando i0 = m´ın i, pi0 = i0 y ∀i = i0 : ci =0

pi ≥ i0 , se tiene que

Si =

xpi a0 + a1 x + · · · + a L(L−1) −pi x

L(L−1) −pi 2

a0 + a1 x + · · · + a L(L−1) x

L(L−1) 2

S0 .

´ ltima restricci´on De la expresi´on de S0 que resulta despu´es de aplicar la u se llega a que pi

x Si =

a0 + a1 x + · · · + a L(L−1) −pi x

L(L−1) −pi 2

a0 + a1 x + · · · + a L(L+1) x

L(L+1) 2

En Si numerador y denominador son primos entre s´ı, y B(x) no es sino una combinaci´on de los Si multiplicados por xl , que a su vez es primo tambi´en con el denominador de Si . De todo esto Groth deduce que el numerador y el denominador de B(x) tienen que ser primos entre s´ı. De esta forma garantiza una complejidad lineal de valor el grado del polinomio del denominador que es L(L+1)/2. Ahora bien, a pesar de que el resto del an´alisis realizado es correcto, esta u ´ltima conclusi´on es err´onea y por tanto ese valor de complejidad lineal no est´a en modo alguno garantizado. Rectificaciones y Ampliaciones Como demostraci´on del u ´ ltimo comentario damos un contraejemplo. Se considera el RDRL de polinomio de realimentaci´on x6 + x5 + 1 y la funci´on no lineal sn sn+7 + sn+2 sn+5 . Siguiendo los pasos dados por Groth se llega a que S1 = x6 (1 + x3 + x6 + x5 + x9 )S0 , S4 = x10 (1 + x3 + x5 )S0 , S0 = 1 , y para esta funci´on particular se tiene que 1+x6 +x5 B(x) =

x6 (1 + x3 + x8 + x10 + x12 + x14 + x15 ) (1 + x + x3 )(1 + x5 + x6 )(1 + x + x4 + x5 + x6 )(1 + x2 + x4 + x5 + x6 )

´ CONCEPTOS BASICOS Y ANTECEDENTES

En este ejemplo, numerador y denominador no son primos entre s´ı, al contrario de lo que asegur´o Groth. Luego al simpliﬁcar queda de la forma B(x) =

x6 (1 + x3 + x5 + x6 + x9 ) (1 + x + x3 )(1 + x + x4 + x5 + x6 )(1 + x2 + x4 + x5 + x6 )

Por tanto, la complejidad lineal no es m´axima ya que como en este cociente numerador y denominador s´ı son primos entre s´ı se puede deducir que la complejidad lineal global del generador es 15. De hecho se observa con este ejemplo que el error proviene de asegurar que el numerador y el denominador de B(x) son primos entre s´ı siempre. Por otro lado, lo que s´ı podemos asegurar, dada la forma de B(x), es que siempre se puede sacar xi0 +m´ın l como factor com´ un en el numerador, luego siempre queda asegurada una complejidad lineal de valor L + i0 − (m´ax l − m´ın l) (denotando maxl y minl respectivamente al mayor y menor valor l tal que el,l+i = 0 para alg´ un i∈ {1, 2, ..., L − 1}). El mayor valor que se puede obtener para esta expresi´on es 2L, que resulta de tomar aquellos productos cuyos t´erminos menores sean muy cercanos (m´ax l ≈ m´ın l) y considerar aquellos RDRLs cuyos polinomios caracter´ısticos tengan s´olo potencias altas de x (i0 ≈ L). Por otro lado, si se consideran las sumas de productos de orden 2 de fases equidistantes sn sn+δ + sn+δ1 sn+δ1 +δ + · · · + sn+δk sn+δk +δ , se tiene que el numerador de B(x) queda de la forma Sδ xL−(δk +δ) [xδk +xδk −δ1 +xδk −δ2 +···+1]. Si el polinomio entre corchetes es primo con el denominador de B(x), entonces se obtiene una complejidad lineal m´axima. Por u ´ ltimo, el an´alisis planteado se puede generalizar al caso de funciones no lineales que incluyan tambi´en t´erminos lineales. Eso se consigue mediante la simple adici´on de un t´ermino B0 (x) = L−1

manera que B(x)=

∞ b0 xn ,

n=0

b0n =

L e0

l=1

l,l an−l an−l ,

B i (x). De esta forma ampl´ıa el an´alisis a una clase

i=0

mayor de funciones.

1.3.2.

Caracterizaci´ on de las Secuencias Seg´ un Key

En 1976 Key [85] investiga tanto el ﬁltrado no lineal de un RDRL como el combinador no lineal de varios RDRLs. Su aportaci´on fundamental consiste en que establece una relaci´on entre la complejidad lineal de la secuencia generada y las ra´ıces de su polinomio minimal.

´ 1.3. RECORRIDO BIBLIOGRAFICO

Al igual que Groth, Key comete un error en sus conclusiones. Por un lado asegura que un producto de segundo orden siempre tiene complejidad lineal m´axima y por otro, al generalizar esta propiedad a un producto de varios t´erminos, deduce que ‘sin diﬁcultad te´orica ni limitaci´on pr´actica, la complejidad lineal puede ser escogida de forma determin´ıstica’. No obstante hay que mencionar que ´el, al contrario que Groth, s´ı admite que pueden presentarse excepciones. Key parte del teorema 1.3 seg´ un el cual la secuencia producida por un RDRL se puede representar en funci´on de las ra´ıces de su polinomio caracter´ıstico. En su trabajo demuestra que las operaciones no lineales inyectan en dicha representaci´on ra´ıces del polinomio minimal de la secuencia resultante. Adem´as concluye que el n´ umero de tales ra´ıces que no desaparecen de la expresi´on de la secuencia resultante sirve como medida de su complejidad lineal global ya que coincide con la longitud del equivalente lineal. Ejemplo 1.3.1 Dado un RDRL de longitud L=4 y una funci´on de la forma sn sn+1 , se tiene que: sn = Aαn + A2 α2n + A4 α4n + A8 α8n y sn+1 = Aαn+1 + A2 α2n+2 + A4 α4n+4 + 8 8n+8 . Luego la funci´on producto se puede expresar como sn sn+1 ≡ Aα8 αn + A α A2 αα2n + A4 α2 α4n + A8 α4 α8n + A3 (α2 + α)α3n + A6 (α4 +α2 )α6n + A12 (α8 + α4 )α12n + A9 (α8 +α)α9n + A5 (α4 + α)α5n + A10 (α8 +α2 )α10n . En la expresi´on anterior, adem´ as del conjunto de ra´ıces conjugadas {α, 2 4 8 α , α , α } presentes en las expresiones de sn y sn+1 , aparecen dos nuevos conjuntos de ra´ıces conjugadas {α3 , α6 , α12 , α9 } y {α5 , α10 }. De las diez potencias de α anteriores, aqu´ellas cuyos coeficientes no se anulan son las ra´ıces del polinomio minimal de la secuencia filtrada. Por tanto, el n´ umero de estas ra´ıces determina el grado del polinomio caracter´ıstico del equivalente lineal, que es la complejidad lineal. A la vista del ejemplo anterior se observa que: Los u ´ nicos cosets que pueden aparecer en la expresi´on de una secuencia ﬁltrada son aqu´ellos que tienen peso menor o igual que el orden de la funci´on. Dada la forma de los coeﬁcientes que acompa˜ nan a las ra´ıces se deduce que dichas ra´ıces se presentan siempre en conjuntos de conjugadas.

´ CONCEPTOS BASICOS Y ANTECEDENTES

Dados un RDRL de longitud L y polinomio caracter´ıstico c(x) primitivo sobre GF(2) y α ∈ GF (2L ) una ra´ız de c(x), entonces la secuencia producida viene dada por sn = apartado 1.1.2.

L−1 i=0

Ai (α2 )n , Ai = A2 ∈ GF (2L ) seg´ un lo visto en el i

Key considera la secuencia producto sn s∗n =

L−1 L−1 i=0 j=0

Ai A∗j (α2 +2 )n . Utii

lizando la notaci´on referente a cosets, se tiene que el coset 2i + 2j tiene diferente peso seg´ un sea i=j o´ i= j. El caso i=j deﬁne el coset de peso uno y cardinal L, mientras que cuando i=j se tienen los cosets de peso dos cuya suma de cardinales es L(L-1)/2. Por tanto hay L(L+1)/2 potencias distintas de α presentes en la secuencia producto y, si ninguno de los coeﬁcientes se anula, el generador tiene complejidad lineal global de valor L(L+1)/2. Key en este punto trata de demostrar que esos coeﬁcientes nunca se anulan. Para ello parte de que la secuencia {s∗n } es simplemente un desplazamiento de fase de la secuenj cia {sn }, s∗n = sn+δ 0 < δ < L luego A∗j = Aj (α2 )δ . De esa manera tiene que la expresi´on anterior queda de la forma sn sn+δ =

L−1 L−1 i=0 j=0

Ai Aj (α2 )δ (α2 +2 )n . j

Si i=j el coeﬁciente Ai A∗i = A2i α2 δ nunca se anula. Si i=j, debido a la simetr´ıa de los exponentes 2i +2j , se concluye que los coeﬁcientes Ai A∗j y Aj A∗i acompa˜ nan siempre a la misma potencia. Por consiguiente, esta potencia desaparece siempre que la suma de ambos coeﬁcientes se anula. Es decir, considerando el l´ıder del coset (i=0), esta potencia desaparece siempre que j 0 A0 Aj (α2 )δ + Aj A0 (α2 )δ = 0 en GF(2L). Ahora bien, seg´ un Key esto no puede ocurrir porque 2j δ ≡ δ(mod(2L − 1)). i

El an´alisis llevado a cabo por Key es correcto pero la u ´ltima conclusi´on s´olo se veriﬁca para δ tal que 0< δ

[PDF] Avances en el estudio de la complejidad lineal del filtrado no lineal - Free Download PDF (2024)