La utilidad de la aritmética modular en los sistemas criptográficos y en los grupos lineales modulares especiales (página 2)

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

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.

CAPITULO 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

CAPITULO 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 criptología (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 Holistica 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.

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

3.

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

4.

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,

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 comunciaciones 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

Para (Zn.), si [a]. [c] = [b]. [c] en Zn, entonces [a] = [b] en Z(n/mcd (n,c))

• Un caso especial es cuando (n,c)=1 , ya que entonces se cumple la propiedad cancelativa para el producto en Zn: si [a][c] = [b][c] en Zn ? [a] = [b] en Zn

• Si n es primo, (Zn, .) tendrá la propiedad cancelativa del producto para todo c

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

U (Zn) al conjunto de todos los elementos invertibles o unidades de Zn. En consecuencia, U (Zn) = {[a]( Zn: ( a, n(=1}. (1)

Vale la pena señalar que cuando n es primo, todos los enteros modulares

U (Zn) ( Zn ( {[0]n}( ([1]n, [2]n,…, [n-1]n ( son invertibles en Zn.

Al conjunto ([1]n, [2]n,…, [n-1]n ( se le llama Conjunto Reducido de Residuos Modulo n. Su orden viene dado por la siguiente expresión:

Voy a exponer en qué consiste la función ( de Euler, por tener mucha importancia en la aritmética modular:

Se define la función f de Euler con la función f: N ? N que a cada n le hace corresponder el número de enteros x (1

Propiedades y cálculo de la función

Se sigue de la definición

1. Que (( 1 (= 1, y que (( 0 ( no se define

• (( p (= (p –1). Si p es primo

• Si n se puede descomponer como n(pk, p primo y k natural. Entonces (( pk (= n (1 –p-1). si p es primo y k es un número natural.

• ( es una función multiplicativa condicional: si m y n son primos entre sí, entonces (( m.n (= ((m)((n) .

U (Zn) es un grupo multiplicativo de los enteros modulares distintos de [0]n, en otras palabras es el grupo de unidades de Zn.

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:

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

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,

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 T:Rn Rn, 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,

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