Proyecto de investigación sobre la utilidad de la aritmética modular en los sistemas criptográficos y en los grupos lineales modulares especiales (página 2)

Se habla de Componentes de una matriz Modular para referirse a los elementos de la misma; esto es, a los aij ? A, si A= [ aij ] es una matriz de Se hacen claras diferencias entre los símbolos Zn y el primer símbolo es el anillo de enteros modulares y el segundo símbolo es el anillo de matrices modulares de tamaño m.

El término de Orden aquí se utiliza solo cuando se refiere al número de elementos de cualquier Grupo, es decir a la cardinalidad del Grupo. Algo semejante ocurre con la expresión Rango del Grupo General Lineal, o de cualquier grupo especial, con el que se hace alusión al Tamaño de las matrices que pertenecen a los grupos especiales.

En el presente Trabajo se denota el Grupo General Lineal de rango m >1

sobre el anillo Zn de los enteros modulares con modulo n, a través de la siguiente expresión: GL (m, Zn). Este Grupo Lineal Modular surge frecuentemente de ciertas aplicaciones de la teoría de enteros modulares en el estudio o creación de sistemas criptográficos tanto simétrico como de clave pública. En consecuencia de lo anterior, es que el objetivo general de este trabajo es conocer el Orden de uno de sus subgrupos, del Grupo Lineal Modular Especial, que pueda emplearse en futuros sistemas Criptográficos que usen algebra matricial modular.

1. Profesor del departamento de física y matemática de la Universidad de los Andes de Trujillo, Venezuela

CAPÍTULO.1

Identificación

1.1. TITULO.

Utilidad de la Aritmética Modular en los Sistemas Criptográficos y en los Grupos Lineales Modulares Especiales

1.2. LUGAR DONDE SE DESARROLLARA EL PROYECTO.

El proyecto se desarrollará, en la Universidad de Cartagena de Indias.

1.3. RESPONSABLE.

Eleuterio Romero Peña.

1.4. PRESENTADO

A la Facultad de Ciencias Exactas y Naturales

Especialidad Matemáticas Avanzada de la Universidad de Cartagena

CAPITULO.2

Descripción del proyecto

2.1 Problema de Investigación.

El proyecto se centra en la necesidad de identificar la Utilidad de la Aritmética Modular en los Sistemas Criptográficos que usen algebra matricial modular o ecuaciones de congruencia lineal. Del mismo modo en la aplicación en los Grupos Lineales Modulares Especiales de rango m con entrada en Zn. Con lo que se satisfaría el problema de algunos estudiantes de estructuras algebraicas del programa de matemáticas y de la especialidad de matemáticas avanzada de la universidad de Cartagena en ignorar la utilidad de la aritmética modular en los sistemas criptográficos y en los grupos lineales modulares especiales.

De acuerdo con el contexto anterior, se proponen las siguientes preguntas de investigación:

1. ¿Qué utilidad tiene la aritmética modular en los sistemas criptográficos que usan en sus algoritmos ecuaciones de congruencia lineal y el algebra matricial modular?

2. ¿Qué utilidad tiene la aritmética modular en los grupos lineales modulares especiales?

3. ¿Cómo viene expresado el orden del grupo lineal modular especial?

2.2. Justificación de la Investigación

Los resultados de esta investigación nos proporciona una útil herramienta de la utilidad de la aritmética modular, en la búsqueda del orden de un subgrupo del GL(m,Zn) y de un modelo matemático para la seguridad de la información en una sociedad que en el presente siglo se caracteriza por la accesibilidad a la información para todas las personas que dispongan de los medios para acceder a ella. En una sociedad donde la codificación y decodificación de la información esta al alcance de las mayorías de las personas contemporáneas.

2.3. Objetivos Específicos

• Conocer la utilidad de la aritmética modular en los sistemas criptográficos y en los grupos lineales modulares especiales

• Conocer el Orden del Grupo Lineal Modular Especial de rango m sobre Zn, a partir del Orden del Grupo General Lineal de rango m con entrada en Zn, que pudieran emplearse en futuras Sistemas Criptográficos que usen el Algebra Matricial Modular

2.4. Objetivo General

Conocer la utilidad de la aritmética modular en los sistemas criptográficos y en los grupos lineales modulares especiales

2.5. Metodología

Para comprobar los objetivos específicos de este trabajo, utilizaremos el Método Lógico Deductivo, en el siguiente orden:.

• Utilizaremos técnicas de reducción del problema al caso primo y empleando la descomposición prima de n

• Aplicaremos el Orden del Grupo General Lineal Modular.

• .Demostraremos el epimorfismo de una aplicación y consideraremos su Ker

• .Aplicaremos el primer teorema de isomorfismo de grupos, la función de Euler y algunos conceptos relacionados con la aritmética modular

CAPÍTULO 3

Fundamentación teórica

"Nada hay tan oculto que no acabe por saberse"

Pasaje Bíblico

3.1. Fundamentos Teóricos de Criptografía

3.1.1. Criptografía

Consultando en la Web (es.wikipedia.org/wiki/Criptografía – 45k) se encontró que Etimológicamente viene del griego "Kriptos" que significa ocultar y "Graphos", que significa escritura. En consecuencia, Criptografía es el arte de escribir con clave secreta o de un modo enigmático. Es la ciencia que estudia como mantener la seguridad en la información, a través de códigos y claves. Luego entonces el Objetivo de la criptografía no es ocultar la existencia de un mensaje, sino ocultar su significado a través de un proceso que se le llama Cifrado.

La ventaja de la criptografía es que si el enemigo intercepta el mensaje cifrado este le es ininteligible.

¿Cómo funciona la criptografía? "Esta se basa en que el emisor emite un texto plano, que con la ayuda de una clave, crea un texto cifrado o un criptograma", Harvey Triana (2008). Este texto cifrado, por medio del canal de comunicación establecido, llega al destinatario o descifrador que lo convierte, apoyándose en la misma clave del emisor o en otra clave, según sea el tipo de criptosistema que esté utilizando de llave Pública o privada, en el texto plano.

Conviene hacer notar que la Criptografía sólo hace referencia al uso de códigos, por lo que no engloba a las técnicas que se usan para romper dichos códigos, conocidas en su conjunto como Criptoanálisis y que definiremos más adelante. En cualquier caso ambas disciplinas están íntimamente ligadas; no olvidar que cuando se diseña un sistema para cifrar información, hay que tener muy presente su posible criptoanálisis, ya que en caso contrario podría llevarse desagradables sorpresas.

3.1.2. Esteganografia

A diferencia de la Criptografía, la Esteganografia, "Stéganos" (Encubrir) y "Grafos" (Escribir), es ocultar la información dentro de otra. La información contenida se le llama Etimógrafa2 (Del gr. etymon, sentido verdadero. Y del gr. grapho que significa escribir. Luego entonces Etimografia es parte de la Estenografía que se dedica de la información verdadera que se quiere ocultar) y la conteniente se le llama Hidégrafa3 (Del griego hide, que significa señuelo, camuflar, mimetizar y grapho que significa escribir. Luego entonces, La hidegrafia es la parte de la Esteganografia que se encarga en mimetizar la información verdadera de modo que esta pase desapercibida).

La diferencia entre Criptografía y Esteganografia, es que la primera no esconde la información sino el mensaje de la misma, mientras la Esteganografia esconde la información y no el contenido de esta

____________________________________________

2 y 3. Teorías construidas como extensión semántica, por Eleuterio Romero Peña

3.1.3. Texto plano o Claro

En la terminología de la criptografía, la información original que debe protegerse se denomina texto plano o Claro.

3.1.4. Cifrado y Descifrado

El cifrado es el proceso de convertir el texto plano en un galimatías, denominado texto cifrado o criptograma. En otras palabras, Cifrar es escribir en clave una información original. O es el proceso de de convertir un texto legible en uno ilegible a través de códigos o claves. Las dos técnicas más sencillas de cifrado, en la criptografía clásica, son la sustitución (que supone el cambio de significado de los elementos básicos del mensaje – las letras, los dígitos o los símbolos-) y la transposición (que supone una reordenación de los mismos).

El Descifrado es el proceso inverso que recupera el texto plano a partir del criptograma y la clave. En palabras castizas, es revelar lo que está escrito en clave. O es el proceso de convertir un texto ilegible en uno legible a través de códigos o claves.

3.1.5. Texto cifrado o codificado

Es el texto que resulta de cifrar o codificar la información original o el texto plano, no siempre con el fin de ser remitido

3.1.6. Criptograma

Es el texto cifrado para ser remitido

3.1.7. Criptologia

"La Criptologia (del griego krypto y logos, estudio de lo oculto, lo escondido) es la ciencia que trata los problemas teóricos relacionados con la seguridad en el intercambio de mensajes en clave entre un emisor y un receptor a través de un canal de comunicaciones", afirma Inés Otilia Fernández (2007), diccionario de investigación Holística 8a Edición, Fundación Sypal, Caracas pp 204. "Es la ciencia que estudia la forma de Cifrar mensajes de forma que solamente puedan ser leídos por las personas a las que van dirigidos", según definición de Manuel José Lucena López (Criptografía y Seguridad en Computadores. Dpto. de Informática Universidad de Jaén. Edición virtual. España. 2001. http://www.kriptopolis.org. Capítulo 2-Página 24. ). Este autor para su mejor estudio divide la criptología en dos grandes ramas. Así:

• La criptografía: Ocupada del cifrado de mensajes en clave y del diseño de criptosistemas (Un criptosistema es el conjunto de procedimientos que garantizan la seguridad de la información y utilizan técnicas criptográficas. El término en inglés es cipher. El elemento fundamental de un Criptosistema es la "llave" o clave. Más adelante se profundiza este concepto (* )).

• El criptoanálisis o anales criptográficos: Se dijo arriba que trata de descifrar los mensajes en clave, rompiendo así el criptosistema. Se encarga de "romper" con las técnicas de cifrado (descifrar el mensaje sin ser el verdadero destinatario). Como área de la matemática, son los métodos para romper los criptogramas por análisis y deducción sin tener conocimiento previo de la clave.

De forma un poco genérica se dice que la labor de la criptografía es convertir un texto Plano en uno cifrado, mientras que la labor del criptoanálisis es conseguir el texto original a partir del criptograma sin poseer las claves necesarias para ello. En resumen, Criptologia es el estudio de la criptografía y el criptoanálisis

3.1.8. Fuerza Bruta

Es el criptoanálisis que se hace probando todas las claves posibles

3.1.9. Criptosistema o Sistemas Criptográficos

Son los sistemas para Cifrar y Descifrar informaciones a través de algoritmos criptográficos y claves

3.1.10. Definición Matemática de Criptosistema

Asumiendo el compromiso hecho en (* ( sobre Criptosistemas o sistemas de cifrado, matemáticamente puede definirse como una quíntupla formada por (M, C, K, D, E), donde:

• M = {m1, m2, m3, ,,,,,, mn }

Es el conjunto de todos los mensajes sin cifrar. Es el espacio de mensajes construidos con los textos en claro que se pueden formar con el alfabeto. Es el conjunto finito de posibles textos planos u originales.

Cada texto mi e M (i variando desde 1 hasta n) se representa por un formato numérico en el que se transforma el texto plano o sin cifrar mi por un medio previamente definido. Por ejemplo: asignándole a cada letra de nuestro alfabeto el número de su posición. A = 1, B = 2, C = 3, D=4, E=5, F=6…

2. C= {c1, c2, c3….cn }

Representa el conjunto de todos los posibles mensajes cifrados, o criptogramas. Es el conjunto finito de posibles textos cifrados

3. K = {k1, k2, k3,…,kn }

Representa el conjunto de claves o llaves que se pueden emplear en el criptosistema. Es el conjunto finito de posibles claves

4. E= {e1, e2, e3…ek ..en }

Es el conjunto de aplicaciones de Cifrado, que para cada k e K, aplica a cada elemento m e M para obtener un elemento c e C. Esto es: Para cada clave ki i=1,2,.., n ek envían cada mensaje sin cifrar en el mensaje cifrado

La última definición de E nos dice que la propiedad básica de toda aplicación de Cifrado es que sea biyectiva en razón de:

a) No pueden haber dos letras distintas que se conviertan en la misma. La

traslación de Cesar tiene claramente esa propiedad. Sin embargo la

función f(x)(x2 en Z27, por ejemplo, sería muy mala función de encofrar

porque f (6)(62(9(mod27) y f (21)(212(9(mod27). Entonces las letras "F" y "T" de nuestro alfabeto se encifrarian ambas como "I" creando ambigüedad.

b) Porque siendo f una aplicación biyectiva, al aplicar f a m puede enviar c = f (m) al destinatario y este para poderlo leer debe aplicarle la función inversa de f a c obteniendo m, f-1 (c) = m, donde se puede recuperar el texto original.

5. D = {d1, d, d3…dk ..dn }

Es el conjunto de aplicaciones de Descifrado, análogo a E. Es decir,

Las aplicaciones dk envían cada mensaje cifrado en el mensaje sin cifrar correspondiente según la clave k e K. Transforma un elemento c e C en un elemento m e M. Esto es,

dk (ek (m)) (m

El objetivo del Cifrado y del posterior Descifrado de un mensaje es obtener el texto original: dk (ek (m)) (m condición matemática que debe cumplir todo criptosistema.

De la definición de criptosistema podemos inferir algunas consecuencias que aun siendo obvias, conviene tratar:

1. Para cada mensaje m e M y para cada k e K existe un único mensaje cifrado c e C tal que ek (m) (c

2. El mismo resultado para dk

3. La aplicación ek es biyectiva para cada k e K

3.1.11. Clasificación de los Criptosistemas

Es importante aclarar que no existe un solo criptosistema o un solo sistema para cifrar y Descifrar una información. "La clasificación de los Criptosistemas se hace en función de la disponibilidad de la clase de Cifrado o Descifrado que se tengan", afirman (Fletes & Reyes, 2004) y así lo explican en el siguiente mapa conceptual que reproducimos sin ninguna modificación.

Este trabajo solo habla de los sistemas modernos.

En Los criptosistemas Simétricos o de clave Privada, su simetría se refiere a que el emisor y el receptor utilizan la misma clave para cifrar y descifrar. Mientras que en Los criptosistemas Asimétricos o de clave Pública, se utilizan dos claves una publica para cifrar y otra privada para descifrar

3.1.11.1. Criptosistemas simétricos o de clave privada.

Son aquellos que emplean una misma clave K tanto para cifrar como para descifrar. Presentan el inconveniente de que para ser empleados en comunicaciones la clave k debe estar en posesión tanto en el emisor como en el receptor, lo cual genera la siguiente inquietud: ¿Cómo transmitirles a los participantes en la comunicación esa clave de forma segura?

Los-esquemas-del-documento-"criptografía" (www.matem.unam.mx/~rajsbaum/…/presentacion_seguridad_1.pdf) que a continuación se reproducen sin ninguna modificación, nos aclaran esas dudas:

Esquema de Criptosistema Simétrico

3.1.11.2. Criptosistemas asimétricos o de clave pública,

Uno de los pilares que cimienta la Criptografía de Clave Publica se sustenta en el problema de Factorización de Enteros que consiste en encontrar para un n(N, el conjunto de números primos p1,p2,.,pk tales que n( p1p2….pk. Emplea una doble clave (kp, KP). Donde kp se la conoce como clave privada y KP se la conoce como clave pública. Una de ellas sirve para la aplicación o función f de cifrado y la otra para la aplicación g de descifrado. En muchos casos son intercambiables, esto es, si emplea una para cifrar la otra sirve para descifrar y viceversa. Estos criptosistemas deben garantizar además que el conocimiento de la clave pública KP no permita calcular la clave privada kp. Ofrecen un abanico superior de posibilidades, pudiendo emplearse para establecer comunicaciones seguras por canales inseguros puesto que únicamente viaja por el canal la clave pública, que sólo sirve para cifrar, o para llevar a cabo autenticaciones. Sin la clave privada (que no es deducible a partir de la clave pública) un observador no autorizado del canal de comunicación será incapaz de descifrar el mensaje cifrado.

Esquema de Criptosistema Asimétrico o de llave pública

3.1.12. Algoritmos Criptográficos

Son métodos matemáticos para cifrar y descifrar una información. En razón de esto, se dice que la criptografía es un área de la matemática

3.1.13. Algunos Algoritmos Criptográficos de Criptosistemas Simétricos

El esquema básico de los algoritmos de clave simétrica es:

MENSAJE + CLAVE = CÓDIGO (encriptación)

CÓDIGO + CLAVE = MENSAJE (desencriptación)

Explicamos la teoría de algunos de los principales algoritmos criptográficos simétricos:

a).Algoritmo Cesar

El algoritmo César es uno de los más antiguos de los cifrados de clave

Privada. Matemáticamente para trabajar con este cifrado se toma el alfabeto como el módulo. Es una de las técnicas de codificación más simples y más usadas. Es un tipo de cifrado por sustitución en el que una letra en el texto original es reemplazada por otra letra que se encuentra en una posición que está un número determinado de espacios más adelante en el alfabeto. El caracter cifrado se obtiene avanzando 'k' pasos en el alfabeto a partir del caracter original. Obviamente 'k' es la clave.

Ejemplo

Con k=2, si el texto original es "ABCDE" se codifica como "CDEFG"

Ejemplo.

Para K(3 una B en el texto original se convierte en una E en el texto

Codificado. Según se puede apreciar en el siguiente esquema publicado

en la Web (es.wikipedia.org/wiki/Cifrado_César -)

El algoritmo César mueve cada letra un determinado número de espacios en el alfabeto.

b).Algoritmo Hill

En 1929, Lester S. Hill, un joven matemático, publica en Nueva York un artículo en el que propone la utilización del álgebra y, en particular de las Matrices, en la operación de cifrado. La importancia del método de Cifrado propuesto por Hill descansa en la utilización de Transformaciones Lineales representadas por Matrices operando en módulo 26 -las letras del alfabeto inglés.

c).Algoritmo Vigenère

El cifrado Vigenère se asemeja mucho al Cifrado de Cesar, pero su diferencia radica en que el primero utiliza una clave más larga. El algoritmo Vigenére se ha tratado de mejorar en muchas ocasiones, una mejora sobre el cifrado de Vigenère fue introducida por el sistema de Vernam, utilizando una clave aleatoria de longitud igual a la del mensaje; la confianza en este nuevo criptosistema hizo que se utilizase en las comunicaciones confidenciales entre la Casa Blanca y el Kremlin, hasta, por lo menos, el año 1987.

d).Algoritmo DES

Finalmente se analiza el sistema de Cifrado por clave privada más difundida y ampliamente utilizada en el mundo conocido como 'DES' (Data Encription standard). Cuando fue creado el algoritmo se suponía tan fuerte que inmediatamente se propuso como el Estándar Federal para cifrar datos. DES fue durante mucho tiempo un buen algoritmo de encriptación para la mayoría de las aplicaciones comerciales. El gobierno de Estados Unidos de América, sin embargo nunca confió en el DES para proteger sus datos clasificados debido a que la longitud de la clave del DES era de solamente de 50 bits suficientemente cortas para ser vulnerable a un ataque por fuerza bruta.

3.1.14. Algunos algoritmos Criptográficos Asimétricos

Explicamos la teoría de algunos de los principales algoritmos criptográficos Asimétricos:

a).Algoritmo RSA

Debe su nombre a sus tres inventores: Los matemáticos, Ronald Rivest, Adi Shamir y Leonard Adleman, que publicaron por primera vez el método en 1977. Se basa en la dificultad que presenta la factorización de números enteros de gran tamaño. Este sistema emplea la doble clave (kp, KP). Las claves pública y privada se calculan a partir de un número que se obtiene como producto de dos primos grandes. Un atacante que quiera recuperar un texto claro a partir del criptograma y de la clave pública, tiene que enfrentarse a dicho problema de factorización.

b).Algoritmo Diffie-Hellman

Primer algoritmo de clave pública, enunciado por W. Diffie y M. Hellman (1976), basa su seguridad en la dificultad de Calcular logaritmos discretos en un campo finito. Se emplea para distribución de claves pero no para cifrar y descifrar.

c).Algoritmo de Curva Elíptica (CCE)

El cual es una variante de la criptografía asimétrica o de clave pública basada en las matemáticas de las curvas elípticas. Sus autores argumentan que la CCE puede ser más rápida y usar claves más cortas que los métodos antiguos — como RSA— al tiempo que proporcionan un nivel de seguridad equivalente.

d).Algoritmo de Cayley-Purser

Algoritmo ideado por Sarah Flannery (1998) se basa en la no conmutatividad del producto de dos matrices de 2×2 que se toman al azar del GL (2, Zn). En el caso particular de este algoritmo, la autora requirió conocer el orden de GL (2, Zn).

En el algoritmo, Sarah utiliza la matriz de multiplicación modular en lugar de exponenciación modular, y es mucho más rápido que otros algoritmos de clave pública. Por ejemplo, alrededor de 20 veces más rápido que el cifrado RSA de 200 dígitos módulo.

3.1.15. Algoritmos Criptográficos Híbridos.

Es el sistema de cifrado que usa tanto los sistemas de clave simétrica como el de clave asimétrica. Funciona mediante el cifrado de clave pública para compartir una clave para el cifrado simétrico. En cada mensaje, la clave simétrica utilizada es diferente por lo que si un atacante pudiera descubrir la clave simétrica, solo le valdría para ese mensaje y no para los restantes. Como GnuPG y PGP (GnuPG y PGP son programas, para cifrar mensajes y documentos) usan sistemas de cifrado híbridos. La clave simétrica es cifrada con la clave pública, y el mensaje saliente es cifrado con la clave simétrica, todo combinado automáticamente en un sólo paquete. El destinatario usa su clave privada para descifrar la clave simétrica y acto seguido usa la clave simétrica para descifrar el mensaje.

3.2. Fundamentación Teórica de Aritmética Modular

"La fuga4, es lógica pura al utilizar

la Aritmética Modular"

Friderich Chopin

3.2.1. Definición de Aritmética Modular

En matemática, la aritmética modular es un sistema aritmético para clases de equivalencia de números enteros llamadas clases de congruencia. Algunas veces se le llama, sugerentemente, 'aritmética del reloj', ya que los números 'dan la vuelta' tras alcanzar cierto valor (el módulo). Por ejemplo, cuando el módulo es 12, entonces cualesquiera dos números que divididos por doce den el mismo resto son equivalentes (o "congruentes") uno con otro. Los números

…, -34, -22, -10, 2, 14, 26,…

son todos "congruentes módulo 12" unos con otros, ya que cada uno deja el mismo resto (2) cuando los dividimos por 12. La colección de todos esos números es una clase de congruencia.

La Aritmética Modular Comprende el estudio de las clases de restos (residuos) de los enteros al dividirse por un entero positivo n llamado modulo n.

4. Fuga es una forma de construcción musical, con un procedimiento de creación y estructura muy determinadas

3.2.2. Criterio de congruencia

Dado a, b (Z y un n(Z, n(0 fijo. Diremos que a es congruente con b modulo n, o que están en la relación de congruencia modulo n, y se indica por a ( b (mod n) si y solo si n / (a-b). Las tres definiciones siguientes son equivalentes:

a ( b (mod n) si y solo si

• n / (a-b)

• a y b dejan el mismo residuo al dividirse entre n.

• a= nq (b o

A n se le llama modulo de la congruencia, que no es más que el número entero positivo que tiene el papel de divisor en la definición de congruencia .

3.2.3. Definición de Enteros Modulares

Bien se sabe que la relación de congruencia modulo n es una relación de equivalencia para toda n(0. En consecuencia de ello, genera o induce una partición en Z en clases de equivalencias: Los subconjuntos de Z o la clase de equivalencia cuyos elementos dan el mismo residuo 0 al dividirlos entre n, los subconjuntos de Z o la clase de equivalencia cuyos elementos dan el mismo residuo 1 al dividirlos entre n, hasta los subconjuntos de Z o la clase de equivalencia cuyos elementos dan el mismo residuo n-1 al dividirlos entre n. A cada uno de estos enteros que están en la misma clase de equivalencia o que dejan el mismo residuo al dividirse entre el modulo n se les llaman Enteros Modulares o Residuales y a los subconjuntos de Z o a las clases de equivalencia se

Les llaman Clases residuales modulo n o de Equivalencia modulo n

Y se designa por [c]n o simplemente, [c] cuando no hay duda sobre el

modulo. Luego entonces a los conjuntos de la forma

Al c ( Z se le llama representante de la clase [c]n. Por antonomasia al símbolo [c]n se le llama clase residual de c modulo n.

Como c mod (n) es el residuo r al dividir c entre n, entonces sin pérdida de generalidad se toma a r como el elemento representativo de la clase residual modulo n. Por lo tanto, para todo c ( Z, [c]n( [r]n, de lo que se infiere que el conjunto de todas las clases residuales modulo n es finito, tiene n elementos; se denota como Zn y viene dado por:

Entonces Zn es un conjunto cociente de Z respecto a la relación de congruencia modulo n. En términos generales se afirma que

a ( b (mod n) si y solo si [a]n ([b]n

Por comodidad tipográfica en este trabajo se escriben los elementos de Zn con un segmento arriba del entero y no entre los brackets o paréntesis cuadrados.

3.2.4.Aritmetica en Zn

La congruencia modulo n es compatible con la suma y el producto de Z, es decir, si a = b (mod n) y x = y (mod n) entonces se tiene que

a(x = b(y (modn) y ax = by (modn).

Con base en la compatibilidad de la congruencia con la suma y el producto de Z, son definibles en Zn dos operaciones binarias internas:

llamadas suma y producto respectivamente, y están definidas de la siguiente manera, para cualesquiera a, b( Z:

El primer mas y el primer punto son operaciones binarias en Zn y el segundo mas como el segundo punto son operaciones binarias en Z

Propiedades de la suma y la multiplicación en Zn

1. Son operaciones cerradas, conmutativas y asociativas

2. Cumplen la propiedad distributiva

3. Tienen elemento neutro: [0] es el elemento neutro para

(Zn, +) y [1] es el elemento neutro para (Zn,.)

4. Elemento inverso

En el caso de (Zn,+) existe el elemento opuesto o inverso aditivo: -[a] = [-a].

Para el caso de (Zn,.) en general no todos los elementos en Zn tienen inverso multiplicativo. Para que en (Zn,.) exista el elemento inverso de un elemento [a]n se requiere que el (n,a)=1. Esto es, que a y n sean primos relativos o coprimos.

El inverso multiplicativo de [a] en Zn, se denota como [a]-1.

5. Propiedad cancelativa

3.2.5. Elementos Invertibles o unidades de Zn.

Se dice que [a] es invertible en Zn respecto a la operación producto si y solo si existe un [b] en Zn tal que [a] [b]= [1]. Ese elemento [b] es el inverso de [a] en Zn, y se dijo que se denota como [a]-1.

La condición necesaria y suficiente para que [a]n sea invertible en Zn es que el ( a, n( ( 1. Es decir, la clase residual [a]n es in vertible en Zn si todos sus elementos son coprimos con n. Lo que se sintetiza en el siguiente teorema que se enuncia sin demostración:

Teorema 1.2.3. Dado a, n ( N, tales que el (a, n) ( 1 entonces a tiene inverso modular n

¿Qué pasa si n es primo?. La respuesta nos las da el siguiente corolario que se enuncia solo con el fin de conocer la respuesta a la pregunta formulada:

Corolario. Si n es primo, el grupo finito que esta n genera tiene estructura de Grupo.

Pues todos sus elementos tienen inverso excepto el cero.

Continuando con el concepto del inverso modular, se denota por

En la ec 2 se aprecia que la función f de Euler produce el número de clase de congruencia [a](Zn que tienen inverso para la multiplicación.

Que es el número de elementos inversibles del anillo Zn y asocia a cada n(N el número de unidades de Zn.

Propiedades y cálculo de la función

Se sigue de la definición

3.2.6. Matrices con entradas en Zn

Son matrices cuyos componentes son los enteros modulares. Pero antes de desarrollar esta teoría veamos un concepto importante de matriz en un campo cualquiera.

3.2.7. Matrices Cuadradas

Una matriz A es cuadrada, si tiene igual número de filas que de columnas. Es decir, si es de tamaño m x m. Y para este caso, se dice simplemente que es de tamaño m.

3.2.8. Matrices Regulares

Una matriz A de tamaño m se dice que es Invertible o Regular si existe una matriz B también de tamaño m tal que AB = BA = In donde In es la matriz identidad de tamaño m. Una matriz cuadrada que posee inversa se dice que es inversibles o regular y su determinante es distinto de cero.

3.2.9. Matrices de Tamaño m con entrada en Zn

En Zn pueden definirse matrices de tamaño m x q o en su defecto de tamaño m; pero para efecto de cumplir con la finalidad de este trabajo se habla únicamente de matrices de tamaño m con entrada o con componentes en Zn: De manera que una matriz A de tamaño m con entrada en Zn, o lo que es lo mismo una matriz modular de tamaño m, es aquella cuyos componentes son representaciones de las clases residuales modulo n:

En el álgebra de este tipo de matrices, la suma y la multiplicación son las usuales y la suma y multiplicación de sus componentes son las modulares o las definidas en Zn. Para estar en contexto con los objetivos de este trabajo, las matrices de las que se hace alusión en son matrices modulares cuadradas de tamaño m, además regulares.

Ejemplos de este tipo de Matrices en Z2

Ejemplos de Operaciones Matriciales con componentes en Z2

Entonces

Se observa que la suma y la multiplicación de matrices modulares son Cerradas.

En razón que el conjunto de Matrices Regulares de tamaño m con entrada en Zn forman un Grupo con las operaciones de grupo dada por la multiplicación usual de matrices, entonces a este grupo de matrices se le suele llamar Grupo Lineal General de rango m con entrada en Zn, que se denota así: GL (m, Z n).

3.2.10. Definición Formal de GL (m, Z n)

Como se recuerda, el Grupo Lineal General de rango m sobre Z n, es el Grupo de matrices invertibles o regulares de tamaño m con entradas en Zn y con la operación de Grupo, obviamente, por la multiplicación usual de matrices. Es el grupo multiplicativo de las matrices mxm con entradas en los Enteros modulares y determinante distinto de [0]. Esta misma definición en forma de conjunto es:

La anterior definición es equivalente a las siguientes:

3.2.11. Orden del GL (m, Zn)

Sea Zn un campo finito de orden n, entonces el GL (m; Zn) es un grupo finito, con el siguiente orden:

El orden de GL (m; Zn) puede ser demostrado, pero aquí simplemente se da la idea que su demostración se hace teniendo en cuenta que las columnas de las matrices de GL (m; Zn) es una base para Contando las columnas de la matriz, la primera columna puede ser todo menos la columna cero; la segunda columna puede ser todo menos los múltiplos de la primera columna, etc. De ahí que el orden de GL (m; Zn) sea el que se enuncia arriba.

Algunos subgrupos de GL(m; Zn ), son: el grupo lineal modular especial

SL(m; Zn), el grupo modular ortogonal O(m; Zn ), el grupo modular

Ortogonal especial SO(m; Zn ) y el grupo modular simpléctico

Sp(2m; Zn ). Que para efecto de los objetivos de este trabajo solo calcularemos el orden de grupo lineal especial, SL (m; Zn ),

3.2.12. Grupo Lineal Modular Especial

El Grupo Lineal Modular Especial de rango m sobre Zn, se denota como SL (m. Zn), y es el Grupo de todas las matrices del GL (m, Zn), cuyo determinante es igual a 1. Es decir:

La anterior definición es equivalente a decir lo siguiente:

3.2.13. Primer Teorema de Isomorfismo de Grupos

El primer Teorema de Isomorfismo de Grupos, dice:

3.2.14. Aplicación Grupo Determinante

La siguiente aplicación se le llama aplicación de Grupos determinante:

Si ? es un epimorfismo, se le llama epimorfismo determinante.

El Ker de ?, por definición viene expresado de la siguiente manera:

3.2.15. Producto Semidirecto Interno

Por otra parte consideramos importante definir en este trabajo, por su aplicación en el desarrollo del mismo, el concepto de producto directo interno, tomado sin ninguna modificación del artículo publicado por la Universidad de Buenos Aires – Facultad de Ciencias Exactas y Naturales – Departamento de Matemática (ALGEBRA II – Práctica N_2 – Primer cuatrimestre de 2003 Pp4): Sea G un grupo y sean H y K subgrupos de G. Se dice que G es el producto Semidirecto interno de H y K si H G,

H n K = {1}. 1, es el elemento idéntico de G respecto al producto y

G = HK

CAPITULO 4

Determinación del orden del grupo lineal modular especial de rango m y con entrada en Zn

El teorema que aparece a continuación, responde una de las intencionalidades de este trabajo, el cual proporciona el Orden del Grupo Lineal Modular Especial de rango m en Zn.

4.1. Consideraciones Preliminares

Para calcular el orden de este sub grupo, además de tener en cuenta la fundamentación teórica expuesta arriba, son necesarias las siguientes consideraciones preliminares:

1. En primer lugar se considera el Orden del Grupo General Lineal Modular que arriba se dijo que viene dado por la expresión:

2. Se utiliza el resultado del primer Teorema de Isomorfismo de Grupos.

3. Se aplica la función de Euler y

4. Se hace uso del siguiente epimorfismo de Grupo determinante:

4.2. Teorema del Orden del Grupo Lineal Especial:

El orden del Grupo Lineal Modular Especial de orden m sobre Zn es:

Demostración

Se sabe perfectamente bien que

Esto es:

GL (m; Zn ) / Ker (?) Im ?. Esto es equivalente a:

GL (m; Zn) / SL (m; Zn) U (Zn). Ver (11) y (12)

Se enfatiza que SL (m; Zn) GL (m; Zn) por ser el núcleo del epimorfismo de Grupo determinante. De manera que, GL (m; Zn) se puede escribir como producto Semidirecto interno de SL (m; Zn) por el U ( Zn).

CAPITULO 5

Utilidad de la aritmética modular en los cifrados y descifrados de criptosistemas

Una de las principales aplicaciones de la aritmética modular en la criptografía es la Codificación (o Cifrar) y Decodificación (Descifrar) de mensajes. Siendo consecuente con los objetivos propuestos en este trabajo y en razón que existen muchos algoritmos de Cifrados, en este aparte solo se ve la aplicación o utilidad de la aritmética modular y del Grupo General Lineal Modular en algunos de ellos. Para tal efecto se ha dividido la utilidad de la aritmética modular en los algoritmos que hacen uso de la aritmética modular y en los algoritmos que hacen uso de matrices modulares.

5.1. Algoritmos que hacen uso de la Aritmética Modular

a). Algoritmo de Cesar

Consistía en escribir el mensaje con un alfabeto que estaba formado por las letras del alfabeto latino normal desplazadas 3 posiciones a la derecha. Con nuestro alfabeto el sistema quedaría así:

Por ejemplo, si se quiere enviar el mensaje ATACARALAMANECER, lo que se escribirá realmente es DWDFDUDÑDODPHFHU.

El receptor del mensaje conocía la clave secreta de éste (es decir, que estaba escrito con un alfabeto desplazado 3 posiciones a la derecha), y podía descifrarlo fácilmente haciendo el desplazamiento inverso con cada letra del mensaje. Pero para el resto de la gente que pudiese accidentalmente llegar a ver el mensaje, el texto carecía de ningún sentido. Aparentemente es un cifrado muy débil y poco seguro, pero en la época de Julio César no era de conocimiento general la idea de ocultar el significado de un texto mediante cifrado. De hecho, que un mensaje estuviese por escrito ya era un modo de asegurar la confidencialidad frente a la mayoría de la población analfabeta de la época.

Lo que interesa del cifrado César es que es un claro ejemplo de utilización de la aritmética modular para garantizar la confidencialidad de la información mediante el cifrado o encriptación.

Matemáticamente, para cifrar o codificar podemos describir el método usado por Julio César como una función de congruencia lineal del tipo,

f3(x) ( x(3(mod27) (13)

Para un alfabeto con 27 caracteres como el español. La x indica la posición que la letra "en claro" ocupa en alfabeto. f3(x) indica la posición de la letra cifrada correspondiente a x en el alfabeto. Según esto, f3 (0)=3, y f3 (26)=2. Esto es, la A se cifra como D, y la Z como C.

Para descifrar o decodificar se emplea la función g3(x) ( x-3 (mod 27).

Para cifrar y descifrar el mensaje los comunicantes han de conocer y usar una misma clave secreta, que en este caso es el desplazamiento aplicado sobre el alfabeto (Desplazamiento=3).

En general, La codificación se puede representar usando aritmética modular, transformando las letras en números, de acuerdo al esquema

A = 0, B = 1,…, Z = 27. La codificación de la letra x con un desplazamiento n puede ser descrita matemáticamente como,

fn(x) ( x(n (mod27)

La decodificación se hace de manera similar,

gn(x) ( x-n (mod 27).

Una sustitución mono alfabeto como la del cifrado César también puede interpretarse como una transformación congruente lineal conocida criptográficamente como transformación afín: Esta no es más que una transformación, definida por T(u) =Au(v donde A es una matriz y v es un vector fijo.

Puede extenderse la transformación afín a un caso mucho más general

con la siguiente congruencia lineal:

Siendo M el valor numérico de un caracter del alfabeto original, a y b dos números enteros menores que el cardinal n del alfabeto, y cumpliendo que a y n sean primos entre sí, ya que de no se r así diferentes letras del alfabeto original darían lugar a una misma letra en el alfabeto cifrado equivalente. La clave de cifrado k viene entonces dada por el par (a, b),

donde a es una constante que determina el intervalo de separación entre dos letras del alfabeto cifrado cuando estas son consecutivas en el alfabeto original. Esta constante se denomina coeficiente o factor de decimación. b es una constante que determina el desplazamiento entre las letras del mensaje claro y las correspondientes en el cifrado.

b). Algoritmo Vigenére

El cifrado de Vigenère (1586) es una generalización del Cifrado Cesar, con la particularidad de que la clave toma sucesivamente diferente valores:

Mensaje: P A R I S V A U T B I E N U N E M E S S E

Clave: L O U P L O U P L O U P L O U P L O U P L

Criptograma: A O L X D J U J E P C T Y I H T X S M H P

En términos matemáticos emplea la siguiente transformación de congruente lineal de cifrado:

Yi ( Xi + Zi(mod27) (15)

Con Zi = L, O, U, P, alternativamente, siendo el 27 el número de letras del alfabeto.

Se observa que a una misma letra en el texto claro le pueden corresponder diferentes letras en el texto cifrado.

c). Algoritmo RSA

Suponemos que A quiere enviar un mensaje confidencialmente a B a través de un medio de transmisión inseguro. El mensaje o el texto en claro que quiere transmitir lo representa como un entero positivo m < n, n es un natural. n(p.q. Con p y q primos distintos con más de 200 dígitos. Y estos son los TRES pasos que tiene que seguir:

1. Generación de las claves:

Recordemos que en una comunicación entre dos partes A y B, cada una de ellas generará antes de empezar su propio par de claves (Pública, privada). Así A tendrá el par (KPA, kpA) y B su par (KPB, kpB),

donde KPA y KPB son las claves públicas que son conocidas por las dos partes, y kpA y kpB las privadas, que cada parte guarda la suya en secreto y no será conocida por la otra parte. Lo mismo para el par de claves de B.

a). Cada usuario del sistema elige una pareja de números primos p y q de 200 dígitos aproximadamente, que deben permanecer en secreto

b). Calcula n = pq y se considera como conjunto de mensajes a utilizar

el grupo multiplicativo U (Zn) cuyo orden es ?(n), donde ?(n) es la función de Euler definida por ?(n) = (p-1) (q-1)

c). Elige arbitrariamente e, 0 < e < ?(n) , tal que el mcd [e, ?(n)] = 1

d).Mediante el algoritmo de Euclides extendidos se calcula el inverso modular de e, en U (Z((n(). E s decir se calcula un d en Z((n( de

modo que d(e-1mod ?(n). Con 0(d ( ?(n).

e). Toma como clave pública (n, e) y como su clave privada d.

Los números p, q y ?(n( también deben permanecer en secretos

f). El remitente ahora tiene m, conoce n y e, mientras el destinatario

es avisado. Transmite el mensaje cifrado c al destinatario. Los números e y d se les llaman exponente de cifrado y exponente descifrado respectivamente. El entero n se le llama modulo del criptosistema RSA

2. Cifrado de Mensajes

Si un usuario A le va a enviar un mensaje a otro usuario B, realiza las operaciones siguientes:

a). Obtiene la clave publica de B, (nB, eB)

b). Representa al mensaje m, como un entero de U (Z nB). 0(m( nB a través de una tabla: A B C D E F G H I J K L M N O P Q R S T U VW X Y Z asignándole a cada letra un numero de Zn a partir del cero. Una vez más recordamos que los números del 0 a n-1 son de Zn. Entonces, A(0 HASTA Z(25

c). A envía a B el siguiente criptograma:

En RSA los mensajes que se transmiten son elementos de

U (Zn) y si se desea transmitir un mensaje más largo, se debe dividir en

Bloques de tal manera que cada bloque sea un elemento de U (Zn)

3. Descifrado de mensaje

Para recuperar el mensaje m, el usuario B utiliza su clave privada dB mediante,

eB dB ( 1 mod? (nB)

Calcula m a través de la siguiente aplicación.

Hay que hacer notar que con este algoritmo los mensajes que se cifran y descifran son números enteros modulares de tamaño menor que n, no son letras sueltas como en el caso de los cifrados César o Vigenére.

Ejemplo del algoritmo RSA

Utilicemos los primos p = 281 y q = 167 para ejemplificar el método RSA

1. Determinación de la Clave.

a). El usuario B, que es el receptor, elige de forma secreta dos primos

p = 281 y q = 167.

Encuentra n = 281 ( 167 = 46.927 y el orden del grupo U (Zn), esto es:

((n) = (280 ( 1). (167 ( 1) = 46.480

b). B, elige arbitrariamente el exponente de cifrado e, comprendido entre 0 y el orden del grupo U (Zn): 0 < e < 46.480.

Por ejemplo e = 39.423 y comprueba que el (e, 46.4 80) ( 1

c). Mediante el algoritmo de Euclides extendido se calcula el inverso de e en Z((n), esto es d. Y se tiene:

d ( e-1 mod ( (46.927)

d = 26.767

Las claves serán:

Clave Pública del receptor B: (e, n) ( (39.423; 46.927).

Clave Privada del receptor B: (d, n) ( (26.767; 46.927).

Por supuesto que el receptor B debe mantener en secreto los números:

p = 281, q = 167 y ((n) = 46.480

d).Finalmente el usuario B da a conocer su clave pública manteniendo en secreto la privada y los restantes valores como p, q y ((n)

2. Cifrado del mensaje m

Como el usuario A le va a enviar a B el mensaje m "HOLA" utilizando un alfabeto de 36 símbolos, en primer lugar debe determinar la longitud del mensaje y tener en cuenta que va codificar las letras del alfabeto en base 36 y que la longitud del mensaje no puede exceder el valor de

n= 46.927. Como Entonces el procedimiento es el siguiente:

a. El remitente A Asigna a cada letra del mensaje m un número de Z36 según el alfabeto, que por comodidad en la escritura lo hacemos sin los bracked o sin el segmento arriba:

HOLA = (17, 24, 21, 10)

b. Reagrupa el texto a cifrar en bloques de igual longitud, esto es en grupo de r letras cada uno. Entonces el texto HOLA queda así: (H, O) y (L, A). Y el bloque a cifrar es: (17, 24) y (21, 10).

c. Expresa ambos bloques como un número en base 36:

(17, 24) = 17. 360 +24. 361 = 881

(21, 10) = 21. 3600+10. 361 = 381

d. Eleva estos números a e modulo (46.927):

88139423 ( 45.840 mod (46.927)

38139423 ( 26.074 mod (46.927)

e. Expresa estos números en base 36, teniendo en cuenta que va a tener tres componentes:

45.840 = 12. 360 +13. 36+35. 362 = (12, 13, 35)

26.074 = 10. 360 +4. 36+20. 362 = (10, 4, 20)

f. Según el alfabeto considerado a cada número le asignamos una letra:

(12, 13, 35) =) CDZ

(10, 4 20) =) A4K

Luego el mensaje cifrado es "CDZA4K".

3. Descifrado del mensaje

Para descifrar habría que hacer el mismo proceso, pero partiendo de bloques de tres letras y terminando en bloques de dos letras y elevando a e en lugar de d.

5.2. Algoritmos que hacen uso del Algebra Matricial Modular

a). Algoritmo de Hill

Este algoritmo tiene un interés didáctico importante debido al uso de matrices que en él se hace. Para cifrar usa como clave secreta una matriz cuadrada A invertible de tamaño n y con coeficiente eny su inversa para descifrar. Es decir con la condición de que su determinante sea una unidad del anillo Luego entonces el algoritmo de Hill se obtiene al transformar bloques de n caracteres en un texto cifrado a través de la relación:

C = (A · P + B) (mod 28) donde, el m.c.d (det(A), 28) ( 1

Nota: No está de más recordar que las matrices están en y que todas las operaciones aritméticas se realizan obviamente en la forma modulo 28. Y que los enteros modulares, por comodidad en su escritura y en las operaciones, los escribimos sin las denotaciones clásicas que convenimos e n la teoría modular que se escribió arriba.

• A es la clave secreta

• P es un bloque de n caracteres. Es el texto claro. El texto que se va a Cifrar, P (

• B es una matriz nx1. Una matriz columna

• C es la matriz columna resultante del cifrado de P. Es el texto cifrado, C (

• 28 es el número de símbolos del alfabeto: _ A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z _ que se corresponden con los números del 0 al 27 (el 0 corresponde al espacio en blanco separador de dos palabras)

Un ejemplo para un cifrado digráfico (bloques de 2 caracteres) sería.

Para el texto original siguiente: ESTACION CENTRAL X

Disponemos el texto de la forma siguiente y aplicamos la transformación indicada:

Donde P1 y P2 son dos caracteres del mensaje sin cifrar,

C1 y C2 los correspondientes cifrados

Continuando con el ejemplo y codificando

Y así sucesivamente para cada bloque de 2 caracteres, resultando:

Texto cifrado: NDTCVZCNYISNCAQHDR

La consecuencia es que el mismo caracter se codifica de distintas formas (la primera E se ha codificado como una N, y la segunda E del texto original se ha codificado como una S).

El Descifrado del sistema de Hill es simétrico (la clave de Descifrado se calcula a partir de la clave de encriptación y viceversa) y será aplicar la transformación:

P = A-1 · (C – B) (mod 28), donde A-1 es la matriz inversa de A mod 28.

Si A es una matriz tal que m.c.d (det(A), n)=1 y d = det(A) entonces la inversa módulo n de una matriz cualquiera es:

A-1= d-1.B donde d-1 es el inverso de d módulo n y B es la transpuesta de la matriz adjunta de A.

Ejemplo

Vamos a cifrar la palabra MAX utilizando un cifrado poligráfico de tamaño 3. Tomemos sus equivalentes numéricos:

M  A  X13 1 25

 Si las matrices de cifrado A y B son:

det (A) = d = 3 entonces tendremos que d-1 = 19 pues 3.19 = 57 = 1(mod 28); por otro lado,

Adj(A)

Adj (A)t =

El resultado es [62 64 -11] es decir [18 8 17] tomándolo módulo 26. Así que el bloque que corresponde a MAX es QHP.

Probemos con el descifrado:

El resultado es como era de prever [13 1 25], es decir el bloque MAX original.

  Otro enfoque para este importante algoritmo de HILL, es:  

 a). PARA EL CIFRADO DE HILL

"Para un cifrado digráfico (bloques de 2 caracteres) sería para el texto original siguiente"

E S T A C I O N C E N T R A L X

05 20 21 01 03 09 16 14 00 03 05 14 21 19 01 12 00 25

Disponemos el texto de la forma siguiente y aplicamos la transformación indicada:

Si el número de letras es impar debemos añadir letras al final de mensaje, por ejemplo "blancos".

"E 05 y S 20":

C1= 1*5 + 27*20 = 545 = 13 (mod 28) (letra M)

C2= 0*5 + 3*20 = 60 = 4 (mod 28) (letra D)  

Y así sucesivamente para cada bloque de 2 caracteres, resultando:

MDSCUZBNXIRNBAPHCR

La consecuencia es que el mismo carácter se codifica de distintas formas

 b). PARA EL DESCIFRADO DE HILL

Es simétrico (la clave de desencriptación se calcula a partir de la clave de encriptación y viceversa) y será aplicar la transformación:

INCONVENIENTES 

1. Distribución de clave  en secreto.

2. La longitud del texto cifrado es el mismo que la del texto original.

3. Si faltan caracteres para formar los bloques de n-caracteres, se le añaden espacios en blanco.

4.  El sistema se convierte débilmente ante el conocimiento de una cadena de texto original y su correspondiente texto codificado.

5.   El tamaño del espacio de claves es pequeño.

VENTAJAS

1. Los algoritmos simétricos son generalmente, al menos, 1.000 veces más rápidos que los sistemas de clave-pública.

2. El método es inmune al análisis de frecuencia de letras, a diferencia de los sistemas monoalfabéticos.

3. El IC (índice de coincidencia) del texto codificado va a ser muy distinto al del texto original, ya que la conversión es tal que rompe la frecuencia del texto original.

4.  Para un tamaño de clave grande y sin método para conseguir el texto original y codificado se vuelve SEGURO.

b). Algoritmo Cayley-Purser

Este algoritmo utiliza matrices 2 x 2 entre el grupo multiplicativo GL (2, Zn). El módulo n = pq, donde p y q son dos primos de 100 dígitos o más, hace que el orden del grupo sea demasiado grande e igual a:

|GL (2, Zn)| = n f (n) 2 (p + 1) (q + 1), donde f es la función de Euler.

Esto denota que el orden de GL (2, Zn) no depende de n únicamente.

Debido a que este algoritmo utiliza nada más que la matriz de multiplicación (modulo n) y no exponenciación modular como en RSA, es de esperar que cifrar y descifrar sea considerablemente más rápido que el RSA. Esta cuestión fue comprobada, mediante la aplicación de ambos algoritmos para grandes masas de texto y se constató que el algoritmo de Cayley- Purser fue aproximadamente veinte y dos veces más rápido que el algoritmo RSA

El algoritmo de CP

1. Generación de la Clave

El algoritmo Cayley-Purser o simplemente CP funciona del siguiente modo:

a. Tómese dos primos p y q inmensamente grande y calcular el modulo

n = pq

b. Elegir al azar dos matrices χ y a de GL (2, Zn), elegidas de tal forma que χ    χ. Esto es, χ y  no son conmutativas.

c. Tómese al azar un r en N y calcula

• β = χ – 1a – 1χ y

• γ = χr

• La clave publica es : el modulo n. a, β, y γ.

• La clave privada es: χ

2. Cifrado

El procedimiento a seguir por el remitente A:

a. Representar el mensaje como una matriz µ de 2X2 con entradas en Zn.

b. El remitente elige aleatoriamente un natural s y calcula:

c. Con el fin de cifrar la matriz &µ, correspondiente a una unidad de texto para enviarlo a B, la persona A debe consultar los parámetros hecho público por B.

d. Cuando estos parámetros se consultan, la matriz &µ se cifra mediante el siguiente procedimiento:

&µ' = k &µ k

e. Luego &µ' y e se envía al receptor

3. Descifrado

El receptor recupera el texto original. Esto es, cuando recibe la matriz &µ' y e .Cuando esto ocurre, descifra la matriz &µ' de la siguiente manera:

Calcula

a. λ = χ – 1 e

b. Comprueba que µ = λ µ' λ

Veámoslo.

A fin de que,

Capítulo 6

Introducción histórica

La historicidad de este trabajo se inscribe en el estudio o creación de los Sistemas Criptográficos tanto Simétricos como de Clave Publica, tales como los sistemas "VIGENÉRE CIPHER" y como los sistemas de "HILL CIPHER", los cuales se basan en las teorías desarrolladas por el Criptòlogo Blaise de Vigenére y por la poligráfica LESTER HILL. De igual manera esta investigación, tuvo en cuenta el estudio de la joven Irlandesa SARA FLANNERY quien creó en el año 1999 el Sistema de Clave Publica denominado "CAYLEY-PURSER ALGORITHMO" o simplemente "CP", para lo cual requirió conocer el Orden del Grupo General Lineal, GL(2,Zpq), para p y q primos.

Es imprescindible en la lista de mención de antecedentes de este trabajo, el artículo de Roy Quintero Órdenes de Algunos Grupos Lineales Modulares (2006), pues sobre este artículo como ya se dijo es que, se fundamenta esta propuesta. Así mismo se han tenido en cuenta las obras del matemático Emil Artin, tales como: The Orders of Linear Groups (1955), donde desarrolla la teoría sobre el Orden de los Grupos Lineales Modulares y The Ordes of the Classical Simple Groups (1971), donde explica metódicamente el Orden de los Grupos Clásicos Simples; de igual manera se consideró los aportes del trabajo del Cubano Pedro Domínguez Wade, "Representaciones Modulares de Grupos Finitos" (2003). En este trabajo el autor expone algunos resultados referentes a las Representaciones de un Grupo Finito sobre Anillos Unitarios Conmutativos de rango m. En este mismo sentido, se apropió de algunos conceptos significativos y generativos del artículo Matrices Modulares y Criptografía (1993) de Elif Ozcara Cantel, quien trata con tanta profundidad la Aritmética de las matrices modulares, como el Orden de algunos Subgrupos de Matrices Modulares y su utilidad en la criptografía. Por último se utilizó la tesis doctoral de José Francisco Vicente Francés, (4 de febrero, de 2008), "Propuesta y análisis de Criptosistemas de Clave Publica Basados en Matrices Triangulares Superior por Bloque". El taller digital.com, Pp16-35

CAPITULO 7

Conclusiones y futuras líneas de trabajo

"No hay rama de la matemática,

por abstracta que sea, que no pueda

aplicarse algún día a los fenómenos del mundo real."

Nikolai Lobachevski

7.1. Conclusión

En este aparte se presentan, de forma general, las conclusiones de este trabajo de grado. Asimismo, se describen las actividades que se pueden realizar para mejorar el mismo.

Las investigaciones hechas en este trabajo tuvieron sus dificultades en la exigüidad, escasez o en la falta de antecedentes, y en las limitaciones que suscitan la protección de los textos en los que existen restringidas informaciones y que algunos de ellos nos fueron accesibles. Cada autor, texto, artículo y fuente consultada se le ha respetado el derecho de autor cuyas informaciones no serán utilizadas por el autor de este trabajo con fines distintos al soporte teórico del presente trabajo.

La criptografía es una ciencia no solo interdisciplinaria si no también multidisciplinaria, entre las cuales están las ciencias matemáticas, la computación y la tecnología de punta (Cualquier tecnología que fue recientemente inventada y es de avanzada).

Los algoritmos de Cifrados de clave pública que resisten la Fuerza Bruta ("En criptografía, se denomina ataque de fuerza bruta a la forma de recuperar una clave probando todas las combinaciones posibles hasta encontrar aquella que permite el acceso":wikipedia página modificada por última vez el 03:08, 21 sep 2008) le dan a la tecnología de punta altos porcentajes de seguridad y precisión en las acciones de las Fuerzas Militares en su lucha contra insurgentes.

Las técnicas Criptográficas aparecen ligadas a su objeto de estudio, mantener secretas ciertas informaciones; hoy muy utilizadas por particulares, organizaciones políticas, los gremios económicos, los gobiernos y las fuerzas militares entre otros. De modo que la Criptografía tiene una función NO solo social, sino también político-militar, en cuya tendencia hacia la infalibilidad es neurálgica la aritmética modular. En la actualidad los Sistemas Criptográficos con estructuras de grupo, son de gran utilidad en la construcción de sistemas de seguridad tanto en las entidades públicas como privadas.

Se dice con tendencia hacia la infalibilidad porque en la elaboración de este trabajo se encontraron casos en los que no existe hoy en día, ni exista muy probablemente en un futuro, ningún sistema de cifrado eficaz que garantice el secreto perfecto ni la resistencia al ataque de una Fuerza Bruta. Los criptosistemas únicamente pueden garantizar la seguridad de la información durante un periodo de tiempo. Todos ellos, tarde o temprano, van a ser vencidos por los criptoanalistas. Si esto no sucediera la criptografía como ciencia habría muerto, ya que no existiría razón alguna para continuar las investigaciones.

Por otra parte, siempre se ha considerado que los mensajes se suponen escritos en un lenguaje y por lo tanto mediante signos de un alfabeto (p.ej. el alfabeto latino). Sin embargo para su tratamiento es conveniente escribirlos numéricamente. Para ello, basta definir una función inyectiva del conjunto A de signos del alfabeto en Zn. Y es aquí donde las distintas partes de las matemáticas entran a reflejar su esencial papel en el desarrollo de algunos sistemas criptográficos, especialmente el de clave pública. Puede afirmarse con toda certeza de la utilidad de la aritmética modular en los distintos algoritmos de los Sistemas Criptográficos, tanto los que hacen uso de las ecuaciones de congruencia lineal (los cifrados de Cesar, de Vigenére) como los que utilizan el algebra matricial modular (cifrado de Hill, de Cayley-Purser). Una de las principales aplicaciones de la Aritmética Modular en la Criptografía es la Codificación y Decodificación de mensajes.

Se pudo observar a través de los ejemplos propuestos que la codificación de mensajes utilizando el algebra matricial modular hace más complejo el algoritmo de Cifrado y por lo tanto consigue una mayor seguridad. De ahí la utilidad del Grupo Lineal General y de su subgrupo, el grupo Lineal Especial, en los algoritmos de Cifrado y de Descifrado de mensajes. La característica esencial que debe tener la matriz de codificación es que debe ser invertible para garantizar el Descifrado del mensaje a través de la matriz inversa. Así mismo se comprobó que los números grandes son usados en los sistemas de clave pública para hacer difícil que pueda determinarse una clave privada a partir de la pública. Particularmente en el algoritmo RSA se trata de factorizar un número primo grande, y hasta el momento no se conocen medios prácticos para hacerlo.

En síntesis, la Aritmética Modular tiene una gran utilidad en los Grupos Lineales Especiales en el proceso del cálculo de su orden. De igual manera, la aritmética modular se usa en las operaciones de cifrado y descifrado por la particularidad de tener algoritmos perfectamente reversibles, es decir que tienen su correspondiente función inversa lo que es ideal para codificar y decodificar. Este hecho evidencia la utilidad de la aritmética modular en la criptografía. A lo que Neal Koblitz5 (1985), afirma: "La aritmética Modular deben seguir jugando el importante papel que históricamente han jugado en la seguridad de la información. Y al mismo tiempo, seguir siendo el puente de relación de las matemáticas con las ciencias de la computación. relación que debe ser cuidada, mantenida y estimulada".

5. profesor de Matemáticas en la Universidad de Washington, USA

7.2. Futuras Líneas de Trabajo

Durante la realización de este trabajo, surgieron varios temas que ameritan ser investigados. Algunas de las extensiones o trabajos futuros que podrían realizarse sobre esta investigación son las siguientes:

1. Órdenes de los subgrupos modulares como:

Ortogonal de rango m sobre Zn: O (m;Zn)

Ortogonal espacial de rango m sobre Zn: SO (m; Zn) y

Simplético de rango 2m sobre Zn: Sp (2m; Zn),

2. Aplicación de la criptografía en las curvas elípticas

3. Los criptosistemas asimétricos basados en matrices triangulares superiores por bloque

4. Para esta otra propuesta permítannos contextualizarla:

Un retículo es el conjunto de combinaciones lineales enteras de un conjunto de vectores linealmente independientes. Su estructura en dimensión 2 ó 3 se parece a una red. Estas estructuras tienen aplicaciones en otras partes de las matemáticas, como álgebras de Lie; o en otras ciencias, como la Criptografía.

Con base en lo anterior, la propuesta es:

Investigar la utilidad de los retículos en los sistemas criptográficos de clave pública.

Referencias bibliográficas

[1] B. McDonald. Linear Algebra over Conmutative Rings, Marcel Dekker,

New York, 1984.

[2] Buchmann, J., Introduction to Cryptography, Springer-Verlag,NewYork,

2000.

[3] B. N. Cooperstein, Minimal degree for a permutation representation of a classical group, Israel J. Math. 30 (1978), 213–235.

[4] Cameron, P., Notes on Classical Groups, 2000, Disponible en:

http://www.maths.qmul.ac.uk/ »pjc/class gps/

[5] D. E. Taylor, The Geometry of the Classical Groups, Heldermann Verlag, Berlin, 1992.

[6] Domínguez W, Pedro, Articulo Representaciones Modulares de Grupos finitos (2003), Habana-Cuba

[7] E. Artin, The orders of the classical simple groups, Comm. Pure Appl. Math. (1955), 455–472.

[8] E. Artin, Geometric Algebra, Interscience, New York, 1957.

[9] Flannery, S. y Flannery, D., In Code, Workman Publishing, New York,

2001.

[10] G. Malle, J. Saxl and T.Weigel, Generation of classical groups, Geom. Dedicata 49 (1994), 85–116.

[11] J. Dieudonn´e, La G´eometrie des Groupes Classiques, Springer, Berlin, 1955.

[12] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson, An ATLAS of Finite Groups, Oxford University Press, Oxford, 1985.

[13] J. Tits, Buildings of Spherical Type and Finite BN-Pairs, Lecture Notes in Math. 382, Springer–Verlag, Berlin, 1974.

[14] L. E. Dickson, Linear Groups, with an Exposition of the Galois Field Theory, Dover Publ. (reprint), New York, 1958.

[15] M. Aschbacher, on the maximal subgroups of the finite classical groups, Invent. Math. 76 (1984), 469-514.

[16] MacWilliams, J., Orthogonal matrices over ¯nite ¯elds, Amer. Math.

Monthly, 76(1969), 152-164.

[17] M. W. Liebeck, On the orders of maximal subgroups of the finite classical Groups, Proc. London Math. Soc. (3) 50 (1985), 426–446.

[18] P. B. Kleidman and M. W. Liebeck, The Subgroup Structure of the Finite Classical Groups, London Math. Soc. Lecture Notes 129, Cambridge Univ. Press, Cambridge, 1990.

[19] P. J. Cameron and W. M. Kantor, 2- collineation groups of finite projective spaces, J. Algebra 60 (1979), 384–422.

[20] Roby, N., Sur le cardinal du groupe Gl(n; A) ou A est un anneau, An. Acad. Brasil. Ci., 49(1977), No1, 15-18.

[21] R. W. Carter, Simple Groups of Lie Type, Wiley, New York, 1972.

[22] W. M. Kantor, Permutation representations of the finite classical groups of small degree or rank, J. Algeb

DEDICATORIA

Dedico este trabajo a mis padres (Q.E.P.D), porque tenían las dos mejores profesiones del mundo, en razón a la pedagogía que ellas encierran:

1. Mi papá fue campesino o Agricultor, quien con la paciencia solo peculiar en ellos, esperaba la cosecha no solo para paliar la "variedad Diferenciable" de necesidades que padecíamos, sino también para pagarme la matricula cuando hacia secundaria. De él aprendí a sembrar semillas de esperanza, a quitar la cizaña y la hierba mala de esta sociedad ascética.

2. Mi mamá era lavandera en el pueblo, lavaba "manduquíao" o "aporreao" para alimentar a mis hermanos mayores mientras se producían las cosechas del sembrío de mi papá. Continuó con esta digna profesión al venirse a Cartagena a parirme. Aquí se especializó en la Universidad de la Vida en Planchado de ropa con plancha de hierro y a carbón. En esta ciudad se quedó hasta su fallecimiento, quince años después del fallecimiento de papá. De ella aprendí a lavar la mugre de esta sociedad.

3. A todos quienes hagan uso de la pedagogía del campesino y de la lavandera de pueblo para formar a los jóvenes de los sectores populares en la concepción de una patria con equidad y con justicia social.

4. A todos quienes utilicen la función social de las matemáticas para generarle a los estudiantes un pensamiento analítico y crítico de la realidad social de este país.

AGRADECIMIENTO

Esta es una de las páginas que me son más difíciles en mis producciones escritas. Porque tratar de compendiar en una página todas las personas que hicieron desde modestos hasta esenciales aportes no es nada fácil.

No obstante a lo anterior, mis sinceros agradecimientos al Profesor Alfonso Segundo Gómez Mulett, mi tutor y mí maestro. Porque jamás escatimó esfuerzos en la orientación de este trabajo. Para el no habían Sábados ni Domingos, siempre estuvo dispuesto e interesado en que este trabajo, en su contenido pedagógico y académico fuera mejor.

También quiero agradecer con especial afecto, al profesor William Caballero Guardo, pues no solo sus orientaciones académicas fueron fundamentales para la calidad de este trabajo, sino también sus palabras de estímulos.

Llevo en el alma y en el recuerdo las palabras de confianza de todos los maestros de la Especialidad, como las que solía decirme el maestro NESTOR RODRIGUERZ en los salones, en los pasillos o en la calle cuando la casualidad así lo ameritaba.

CARTAGENA DE INDIAS D.T.y. C

2008

PROYECTO DE INVESTIGACIÓN SOBRE LA UTILIDAD DE LA ARITMETICA MODULAR EN LOS SISTEMAS CRIPTOGRAFICOS Y EN LOS GRUPOS LINEALES MODULARES ESPECIALES

ELEUTERIO ROMERO PEÑA

Director

Mma ALFONSO SEGUNDO GÓMEZ MULETT

UNIVERSIDAD DE CARTAGENA

FACULTAD DE CIENCIAS EXACTAS

DEPARTAMENTO DE POSTGRADO

PROGRAMA DE MATEMÁTICA

ESPECIALIZACIÓN EN MATEMÁTICAS AVANZADA

CARTAGENA DE INDIAS D.T. y C.

2008

Proyecto de Investigación presentado a la Facultad de Ciencias Exactas y Naturales de la Universidad de Cartagena- Coordinación de Postgrados de Matemática Avanzada para Optar el Titulo de Especialista en Matemática Avanzada

Proyecto de Investigación Aprobado

DECLARACIÓN DE AUTOR

La responsabilidad del contenido de este Proyecto de Investigación, me

corresponde exclusivamente.

Se permiten citas breves sin permiso especial del autor, siempre y cuando se otorgue el crédito correspondiente. Se podrá solicitar permiso al autor Kra 83B #22B26 o al celular 3114231035 Cartagena-Bolívar.

______________________________

Eleuterio Romero Peña

Autor:

Eleuterio Romero Peña