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

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:

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  X 13 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,

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:  

"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":

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

• La clave publica es : el modulo n. a, ÃY, y Y.

• La clave privada es: X

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

Capitulo 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. Algebra 60 (1979)

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.

Autor:

Eleuterio Romero Peña

Director Mma Alfonso Segundo Gómez Mulett

UNIVERSIDAD DE CARTAGENA

FACULTAD DE CIENCIAS EXACTAS y NATURALES

DEPARTAMENTO DE POSTGRADO

PROGRAMA DE MATEMÁTICA

ESPECIALIZACIÓN EN MATEMÁTICAS AVANZADA

CARTAGENA DE INDIAS D.T.y. C

2008