- Sistemas Lineales y No Lineales
Sistemas Lineales
En todas las ramas de la ciencia e ingeniería ha predominado el estudio de los sistemas lineales. Intuitivamente, es aquel en el que un cierto cambio en las señales de entrada provoca un cambio proporcional en las señales de salida. De manera formal, un sistema lineal se suele definir como aquel que cumple el principio de superposición:
Si: x1[n] => y1 [n] y x2[n] => y2 [n],
Entonces:
a1*x1 [n] + a2*x2 [n] => a1*y1[n] + a2*y2[n]
Para cualquier a1; a2
Sistemas No Lineales
La realidad es que no existe ningún sistema físico que sea estrictamente lineal, pero en determinadas ocasiones las no linealidades resultan despreciables y los sistemas lineales proporcionan una aproximación adecuada.
Un sistema dinámico se puede definir como un conjunto de reglas que describen cómo evoluciona un determinado fenómeno a partir de un cierto estado inicial a medida que cambia una variable independiente, generalmente el tiempo. Estos sistemas fueron fundamentales en el estudio físico del universo desde los tiempos de Newton y Leibniz, puesto que son el instrumento usado generalmente para describirlo.
Los sistemas dinámicos discretos generalmente se formulan mediante sistemas de ecuaciones en diferencias (EDs). Los sistemas dinámicos se pueden clasificar de acuerdo con numerosos criterios:
1. Discretos o continuos
2. Deterministas o aleatorios
3. Conservativos o disipativas
Mapas Caóticos o Atractores
Los sistemas dinámicos, discretos, deterministas y no lineales son conocidos como mapas caóticos o atractores, cuya definición usando las variables de un sistema caótico es: La región del espacio de fases hacia las que converge una órbita de un conjunto de condiciones iniciales.
Atractor de Lorenz
El sistema de ecuaciones diferenciales que gobierna este sistema se muestra en la fórmula (2):
... (2)
Atractor de Chua
El sistema de ecuaciones diferenciales que gobierna este sistema se muestra en la fórmula (3)
... (3)
Atractor de Roosler
El sistema de ecuaciones diferenciales que gobierna este sistema se muestra en la fórmula (4).
... (4)
.
La Criptografía se ocupa de dar solución a los problemas de identificación, autenticación y privacidad de la información en los sistemas informáticos. Sin embargo en los métodos tradicionales de cifrado de los datos, los ataques para poder acceder a la información de los textos cifrados se han hecho más factibles debido al gran avance tecnológico y el desarrollo de las computadoras con las cuales descubrir las claves de los textos cifrados se ha vuelto una tarea cada vez más fácil. Por eso es que en el presente trabajo se trata de mejorar el nivel de seguridad en la transmisión de datos, para lo cual aplicamos la teoría del caos para la generación de claves de las secuencias seudo aleatorias.
Se ha escogido la teoría del caos en la generación de números seudo aleatorios por sus propiedades que detallamos a continuación:
- Son sensibles a condiciones iniciales, produciendo diferentes resultados a pequeños cambios.
- Son sensibles a los parámetros que describen los sistemas dinámicos descritos por la teoría del caos.
- En el caso de la generación de secuencias seudo aleatorias puede aumentar o disminuir el periodo dependiendo de los parámetros que se apliquen en la ecuación de iteración que se emplee para la descripción del sistema dinámico.
Teniendo en cuenta que se requiere aumentar la seguridad en la transmisión de información, un cifrador debe ser robusto ante ataques, los cuales se basan en la obtención del mensaje original a partir del mensaje cifrado. Obtener la clave (los parámetros) a partir del texto cifrado u obtener la señal portadora caótica. Uno de los esquemas de un cifrador que brinda robustez es el esquema de Even y Mansour, debido a que cuenta con generadores de secuencias seudo aleatorias como llaves, y un bloque permutador con comportamiento aleatorio o seudo aleatorio, el cual se puede conseguir mediante una dependencia directa con una de las secuencias seudo aleatorias.
La secuencia seudo aleatoria que va a ser utilizada en el cifrador debe tener periodo largo, para garantizar una mayor seguridad, con este fin se eligió el sistema de Lorenz como generador de dicha secuencia, sin embargo este sistema al ser analógico es inseguro y poco robusto, además cuenta con valores negativos dentro de la secuencia que genera, haciendo complicada su implementación en hardware.
Frente a este problema se opta por discretizar el sistema, acotando la secuencia a valores enteros y positivos para facilitar el cálculo. La ventaja de contar con un criptosistema digital es su ergodicidad y la mayor seguridad que brinda comparado con un criptosistema analógico.
Los pasos a seguir para llevar a cabo este estudio fueron:
1.-) Investigación y selección del algoritmo para el cifrador
El Cifrador
Es el mecanismo encargado de alterar la información la cual se hace irreconocible a un intruso y reversible en el destino. Puede aplicarse extremo a extremo o individualmente a cada enlace. Soporta el servicio de confidencialidad y complementa otros mecanismos de seguridad. Existen varios esquemas cifradores, siendo el esquema seleccionado el siguiente:
Cifrador de Even y Mansour
Even y Mansour proponen la construcción de un cifrador de bloques usando únicamente una permutación seleccionada en forma aleatoria. Esta permutación es accesible de manera pública (como caja negra) y cualquiera que trate de atacar al cifrador tendrá acceso a él. La seguridad es demostrada bajo la hipótesis que la permutación es elegida aleatoria o al menos pseudo aleatoria.
La clave K, la cual consiste en dos bloques o subclaves K1 y K2 es usada de la siguiente manera: el mensaje original M y la subclave K1 se combinan mediante una operación XOR, luego la permutación F es aplicada y la salida es combinada con la otra subclave K2 usando otra operación XOR y producir de esta manera el criptograma o mensaje cifrado C. La clave K es una secuencia de números pseudo aleatorios que se originan por medio de un bloque PRNG (Pseudo Random Number Generator).
Lo interesante de este esquema es que la clave modifica la permutación de una manera simple y rápida de implementar, además si escogemos la permutación pseudo aleatoria cada ataque sobre el sistema tendrá probabilidades mínimas de éxito.
Esquema de Even y Mansour donde M = mensaje original, F = bloque de permutación,
= XOR (bit a bit), {K1, K2} = Clave, C = criptograma
Bloque PRNG
Un generador de números pseudo aleatorios (PRNG) es un mecanismo criptográfico utilizado para generar números pseudo aleatorios. Si se diseña, implementa y utiliza apropiadamente, cualquier adversario con enormes recursos computacionales no será capaz de predecir una secuencia de la salida del PRNG. En el presente trabajo se utiliza las características mencionadas del PRNG para generar las subclaves K1 y K2.
Esquema de Even y Mansour incluyendo los bloques PRNG
La generación de números aleatorios siempre ha atraído el interés debido a que juegan un rol importante en diversas áreas de conocimiento, son muy usados en criptografía y telecomunicaciones.
Propiedades deseadas de buenos generadores
Veamos como operan los generadores para poder entender porque uno puede ser considerado mejor que otro. El método más común es generar el siguiente número a partir de los últimos números generados:
... (5)
Si conocemos f y tenemos el valor inicial x0 podemos generar la secuencia en cualquier momento. El valor usado para comenzar la secuencia (x0) es llamado semilla. Nótese que f es determinística. Dada la semilla se puede predecir con probabilidad 1 los números de la secuencia. Sin embargo, los números son aleatorios en el sentido de que pasan pruebas estadísticas de aleatoriedad y por esto son llamados pseudo aleatorios. En muchos casos se prefieren estos números en vez de los completamente aleatorios ya que es necesario repetir las secuencias en distintos experimentos. Si deseamos otra secuencia simplemente cambiamos la semilla.
Las propiedades deseadas del generador son las siguientes:
Deben ser eficientes computacionalmente: dado que típicamente se requieren varios miles de números aleatorios por corrida, el tiempo de procesador requerido para generarlos debe se pequeño.
El periodo debe ser largo: periodos cortos limitan la longitud aprovechable de una corrida de simulación porque el reciclaje resulta en una repetición de secuencias de eventos.
Los valores sucesivos deben ser independientes y uniformemente distribuidos: la correlación entre números sucesivos debe ser pequeña de modo que la secuencia de números generada sea seudo aleatoria.
Generador de números seudo aleatorios basados en la Teoría del Caos
El desorden lleva consigo la variación y el cambio. A nuestro alrededor, la política, el clima, la economía... todo se encuentra en permanente evolución.
Para poder organizar y sistematizar todas estas formas de cambio con el objetivo de estudiarlas y predecirlas, sería deseable poder realizar representaciones de los cambios de manera comprensible, poder clasificar y entender los distintos tipos de cambio así como disponer de métodos para identificarlos.
Es aquí donde las matemáticas, y en particular la rama de los sistemas dinámicos, ofrecen vías eficaces que permiten realizar este tipo de análisis. Para trasladar el estudio de cualquier fenómeno al ámbito matemático es necesario realizar un proceso de modelado que consiste esencialmente en:
Detectar las variables que influyen en un fenómeno dado.
Analizar su comportamiento relativo, es decir, determinar cómo influyen unas sobre otras y cómo se comportan a lo largo del tiempo.
Como resultado, obtendremos un modelo matemático del fenómeno, que podrá ser una ecuación diferencial, si se logran estudiar variaciones instantáneas, o una transformación iterativa si las variaciones son discretas.
Una vez conseguido el modelo matemático, en particular, las fórmulas o ecuaciones que lo regulan, es posible estudiar su evolución en el tiempo e incluso hacer previsiones. Si además hemos conseguido aislar el fenómeno que nos interesa de los efectos del resto del universo entonces podremos prever su evolución con total seguridad. Este es el punto de vista determinista.
¿Qué lugar ocupa entonces el azar, el desorden, el caos? La respuesta es que a pesar de poder conocer perfectamente la evolución de cada elemento, el movimiento global puede ser muy desordenado, es decir, dos sujetos que en un determinado momento estén infinitamente próximos, pueden estar muy lejos en un instante posterior
Estas propiedades del caos proporcionan un potencial para aplicaciones en criptografía ya que las predicciones a largo plazo de los sistemas caóticos son muy difíciles. El caos en generación de números aleatorios permite repetir la misma cadena de números siempre que se utilice la misma función de correspondencia caótica (o atractor) y valor inicial o semilla. La apariencia aleatoria del sistema hace prácticamente imposible los ataques del tipo codebook (un codebook contiene todas las posibles transformaciones entre texto en claro y texto cifrado bajo cada clave). Puesto que las funciones caóticas son muy sensibles a las condiciones iniciales, cualquier ligera diferencia en el valor inicial empleado, significará que el texto cifrado producido utilizando caos será muy diferente. Esto significa que el sistema será robusto contra ataques por fuerza bruta, ya que el número de posibles claves es impresionantemente grande, dependiendo de la precisión de los valores iniciales que estarán en función del hardware utilizado, y que puede ser más o menos elevado según el dominio sea analógico o digital.
Puesto que las funciones caóticas son muy sensibles a las condiciones iniciales, cualquier ligera diferencia en el valor inicial empleado, significará que el texto cifrado producido utilizando caos será muy diferente.
Para poder lograr la generación de números pseudo aleatorios, requerimos de un sistema de ecuaciones que cumpla con los requerimientos mencionados anteriormente, es consecuencia, es conveniente utilizar uno que describa el comportamiento dinámico de un sistema caótico, y que a la vez sea relativamente sencillo de implementar en hardware.
Atractor de Lorenz
El atractor de Lorenz es un sistema de ecuaciones diferenciales autónomo, un sistema dinámico, que en principio su autor lo propuso para tratar de comprender los fenómenos meteorológicos. Se encontró con que a pesar de que los valores generados nunca se repiten y de que las condiciones iniciales pueden hacer variar completamente los valores generados, el atractor toma una forma única y parece conservar cierto orden, sus infinitas trayectorias nunca se cortan.
El modelo atmosférico que utilizó Lorenz consiste en una atmósfera bidimensional rectangular, cuyo extremo inferior está a una temperatura mayor que el superior. De esta manera el aire caliente subirá y el aire frío bajará creándose corrientes que harán un intercambio de calor por convección.
Conviene señalar que las condiciones necesarias para que exista caos en un sistema de ecuaciones diferenciales autónomo son: deben haber al menos tres ecuaciones diferenciales y al menos tres variables y al menos alguna no linealidad.
Las ecuaciones que describen este proceso simplificado de la convección atmosférica son:
... (6)
Las tres variables con las que describía el estado de la atmósfera son: (1) El flujo de convección x. (2) La distribución de la temperatura y. (3) La distribución de la temperatura z.
2.-) Investigación de algoritmo para el cifrado
De la primera parte se ha elegido como algoritmo para el cifrador, el algoritmo derivado del atractor de Lorenz, cuyas ecuaciones diferenciales con las que se muestran a continuación:
... (7)
Donde (Número de Prandti), (Número de Rayleigh) y (No tiene nombre) son los parámetros de control.
En base a estas ecuaciones, se explicará el procedimiento a seguir para el desarrollo del algoritmo de cifrado.
Se debe investigar la manera de seleccionar los parámetros característicos de las ecuaciones dinámicas del atractor de Lorenz, de tal manera que el algoritmo cumpla con los requisitos fundamentales y necesarios solicitados en el campo de la criptografía caótica.
Para realizar un algoritmo que nos sirva en el cifrado, debemos realizar un generador de números seudo aleatorios, lo cual se puede lograr con la obtención de una ecuación de recurrencia:
... (8)
Que según el sistema de ecuaciones (7) obtendremos un sistema de ecuaciones de recurrencia, para realizar dichas ecuaciones de recurrencia debemos realizar un proceso de discretización, ya que el siguiente valor de la secuencia () depende del valor anterior ().
En otras palabras el sistema continuo se convierte en un sistema discreto tridimensional (mapa 3D) utilizando la aproximación de Euler de primer orden:
... (9)
Que aplicado sobre la primera ecuación del sistema (7), obtenemos:
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
Como esta ecuación es independiente de la variable y por comodidades de cálculo, cambiaremos a por , por y por , resultando:
... (10)
Si se realiza el mismo procedimiento con las variables y obtenemos el siguiente sistema discreto:
... (11)
Donde es el parámetro de escala de tiempo. Para reducir el hardware necesario el sistema trabaja con aritmética entera binaria (Enteros y positivos), y para simplificar las divisiones necesarias (se harán desplazamientos de bits) se utilizan múltiplos del tipo . Para ello se efectúan las siguientes transformaciones de polarización y cambios de escala:
... (12)
Donde y son respectivamente los parámetros de polarización y cambio de escala. Con esta transformación garantizaremos trabajar con números positivos (Parámetro ) y debido a que hemos realizado una discretización de un sistema continuo, se añaden errores de discretización y para atenuar este error es que se introduce un factor de escala (Parámetro ).
Reemplazando la transformación (12) en el sistema discreto (11) obtenemos:
... (13)
Conforme variamos los parámetros , y del sistema (7) encontramos multitud de soluciones posibles: exóticos ciclos límites agrupados en nudos, pares de ciclos límites unidos, caos intermitente, periodicidad ruidosa, atractores extraños, etc.
El espacio de parámetros es grande, pero analizaremos ciertas propiedades de las ecuaciones de Lorenz que nos ayudará a acotar este espacio:
Puntos Fijos: (0, 0, 0) es un punto fijo para todos los valores de los parámetros. Si , también existen un par de puntos fijos simétricos, , . Lorenz los bautizó como y . Cuando se unen con el origen en una bifurcación de Pitchfork.
Estabilidad Lineal del Origen: Al linealizar las ecuaciones e están acopladas y la ecuación para representa un decaimiento exponencial a 0. Las otras dos direcciones están gobernadas por un sistema en el plano para es un punto de silla (En el sistema 3D tenemos dos ramas linealmente estables y una inestable). Si el origen es un sumidero (En particular un nodo estable).
Estabilidad Global del Origen: Podemos ver que para el origen es globalmente estable (Todas las trayectorias van a él y no hay ni ciclos límites ni caos).
Estabilidad de y : Ahora , puede verse que y son linealmente estables para , donde: . Fuera de este rango nada podemos decir sobre el comportamiento de las soluciones, aunque sabemos que no pueden ser expelidas al infinito y que a partir de una bifurcación de Hopf Subcrítica (Que desestabiliza a ) cualquier ciclo límite deberá ser inestable.
Lorenz integró las ecuaciones (7) para , y empezó a analizar la estabilidad del sistema según la variación de .
El comportamiento para valores pequeños de se resume en la siguiente figura:
Comportamiento de x con respecto a
La aparición de e ir aumentándola da lugar a una fenomenología muy rica llamada “Caos Transitorio”, el cuál no es caótico pero muestra sensibilidad respecto a condiciones iniciales. Que demuestra que un sistema determinista puede ser impredecible aun cuando el estado final sea muy simple.
Para coexisten los puntos fijos con “Atractores Extraños”, el cual exhibe sensibilidad respecto a las condiciones iniciales siendo además dicho atractor un objeto fractal. Así podemos tener histéresis entre caos y equilibrio al variar y que perturbaciones suficientemente grandes pueden inducir transiciones entre estos estados tan distintos.
Es justamente esto último el factor clave para la elección del parámetro , deseamos que nuestro sistema sea sensible a condiciones iniciales, así que si pensamos en el intervalo de Caos Transitorio tendríamos que escoger el mayor valor de que pertenece a dicho intervalo, así nos acercaríamos a la frontera con el intervalo de Atractor Extraño, el cuál también posee la cualidad de sensibilidad pero que además se convierte en un objeto fractal, y el comportamiento de ambos es totalmente diferente, por tanto nos convendría elegir un valor cercano a este límite. Teniendo en cuenta además la filosofía d simplicidad de hardware tendríamos que elegir un valor entero de , por tanto elegimos: .
Los intervalos obtenidos por Lorenz, los obtuvo tomando como valores fijos a y , por tanto tenemos que tomar los valores más cercanos a dichas cantidades pero que sean potencias de dos, por tanto elegimos: y .
Con ayuda de la herramienta Matlab, graficaremos la curva del atractor de Lorenz para los parámetros calculados por Lorenz y para los parámetros calculados por nosotros, los comandos utilizados se muestran en la sección anexo:
Curva del atractor de Lorenz para . A la izquierda para , y a la derecha para y .
Analizando el atractor para los parámetros hallados hasta el momento, calculamos los valores más negativos de la curva:
Valores más negativos del Atractor de Lorenz
Podemos notar que los valores más negativos de los puntos de la curva del atractor de Lorenz, son mayores a -20, por tanto el factor de polarización en la transformación (12), debe ser: , para garantizar que todos los puntos del atractor de Lorenz, para los valores de estos parámetros, sean cantidades positivas.
Tomando el último componente de la segunda ecuación del sistema (13) , podemos notar que debe ser una cantidad negativa debido a que y son cantidades mayores a uno, por tanto este componente es crucial en la segunda ecuación ya que si tomará un valor muy elevado podría causar una fluctuación hacia los números negativos, lo cual haría que nuestro algoritmo colapse ya que lo implementaremos en una lógica binaria positiva. Además que si deseamos reducir la cantidad de recursos a emplear, debemos hacer dicha cantidad lo más pequeña posible. Esto depende de los parámetros , como y (Factor de Escala >1) son mayores a uno entonces para que disminuya al producto .
El coeficiente de de la segunda ecuación del sistema (13) es: , en función a la simplicidad de hardware haremos: .
Por tanto: ... (14)
Asimismo, de la primera ecuación del sistema (13), tomamos el coeficiente de : , y hacemos que sea una cantidad potencia de dos: , como
Entonces:
... (15)
De (14) y (15) obtenemos:
... (16)
Los posibles valores de y se muestran en la Tabla 1.
Tabla 1
|
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
|
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
|
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
|
| 4 |
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
|
-8 |
| 5 |
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
|
8 |
| 6 |
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
|
40 |
| 7 |
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
|
104 |
| 8 |
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
|
232 |
| … |
… |
… |
posibles valores de n, k y B
Los valores que tomemos dependerán de la aplicación que deseemos darle, pero para fines del proyecto en la cual desarrollaremos un prototipo, basta con tomar el mínimo valor de que cumpla con las condiciones de polarización, es decir: .
Por tanto: .
Asimismo, las cantidades independientes del sistema de ecuaciones (13) deben ser cantidades enteras:
... (17)
Por tanto:
Influye únicamente en el truncamiento de cálculos mientras mayor sea el valor de más exacto serán mis cálculos. Tomaremos:
Reemplazando los valores de todos los parámetros hallados, el sistema (13) queda de la siguiente manera:
... (18)
Notar que en el sistema de ecuaciones (18), hemos separado algunas componentes en dos partes, esto debido para que los coeficientes de cada variable sean potencias positivas o negativas de dos y de ésta manera simplifiquemos cálculos.
[1] DISEÑO E IMPLEMENTACION DE UN CIFRADOR BASADO EN PRNGs CAOTICOS PARA UNA TRANSMISION DE DATOS
http://aniak.uni.edu.pe/Proyecto_Grupo_CriptoCaas.html
[1] José M. Albornoz y Antonio Parravano: Acoplados y sus aplicaciones en criptografía”. Universidad de los Andes, Mérida, Venezuela. Postgrado de Física Fundamental.
[2] María A. Molina Vilchis, Ramón Silva Ortigoza y Eduardo Vega Alvarado: “Aplicaciones de secuencias Pseudo Aleatorias en la Seguridad de Información”. CIDETEC-IPN, Departamento de Postgrado Unidad Profesional Adolfo López Mateos, México, D.F., México.
[3] C. M. Gonzáles, H. A. Larrondo, C. A. Ganoso, L. J. Arnone: “Generación de secuencias binarias pseudo aleatorias por medio de un mapa caótico 3D”. Universidad Nacional de Mar del Plata-Argentina
[4] A. Jiménez Triana, C. I. Camargo Bareño, J. A. Cortés Romero: “Síntesis de un circuito caótico empleando VHDL”.
[5] Hernando Castañeda Marín y Wladimir Rodríguez Graterol: “Construcción de un cifrador basado en una permutación pseudos-aleatoria”. Universidad de Pamplona, estudiante Doctorado Universidad de los Andes y Doctorado en Ciencias Aplicadas. Mérida, Venezuela.
[6] Doctor Jorge Ramió Aguirre, Libro Electrónico de seguridad Informática y Criptografía V 4.1, Universidad Politécnica de Madrid.
[7] José Manuel mendías Cuadros, Estructura y Tecnología de computadoras. Dpto de arquitectura de computadores e Informática Universidad Complutense de Madrid.
[8] A. Menezes, P. Van Oorschot, S. Venstone. “Handbook of Applied Cryptography”. CRC Press. 1997.
Sistema Criptografico Caotico
