Proyecto  ForMate

SESIÓN 13-03-2007

  UN POCO DE CRIPTOGRAFÍA

Inmaculada Illán/ Carlos Martínez

Curso 2006/07

  ARITMÉTICA MODULAR (LA ARITMÉTICA DEL RELOJ).

 En 1801 Gauss escribe su libro “Disquisiciones Arithmeticae”, uno de los libros más influyentes que jamás se hallan escrito. En este libro una de las cuestiones que se trataban era la idea de aritmética finita.

Tenemos una aritmética finita cuando se utiliza un sistema de numeración que vuelve periódicamente sobre sí mismo. Por ejemplo contar las horas de un reloj o los minutos. En estos casos Gauss se dio cuenta de que debía empezar a contar desde cero; y con esta sencilla observación investigó este sistema de numeración. Los resultados suelen ser con frecuencia sencillos, y en ocasiones del todo sorprendentes.

Por ejemplo: En un reloj 2+3=5 pero 7+6=1 cuando hablamos de horas ó 48+12=0 cuando hablamos de minutos.

Se dio cuenta de que casi todas las reglas de la aritmética ordinaria se pueden trasladar a la aritmética finita. Para evitar confusiones usó el símbolo º y el número a partir del cuál se vuelve a comenzar le llamó módulo de la aritmética. En nuestro caso el módulo sería 12 ó 60.

Lo cierto es que para cualquier número natural n podemos construir la correspondiente aritmética modular de módulo n en la que los números son 0, 1, …, n-1 y donde al sumar y multiplicar números se descartan los múltiplos enteros de n.

Ejemplos:

• 2x3º 6 (mod 7)
• 3x5º 1 (mod 7)
• Si contamos 100 días a partir de hoy, ¿en qué día de la semana estaremos?

Como 100º 2 (mod7) será el mismo que dentro de 2 días.

EJERCICIO 1:

Calcula los siguientes valores:

• 30 (mod 7)
• 45 (mod 9)
• 375 (mod 30)

EJERCICIO 2:

 Hay una manera muy sencilla de calcular a (mod b) ¿puedes explicarla?

EJERCICIO 3:

 Explica como puedes obtener en tu calculadora el resto de la división de 1247 entre 25, o en general de a entre b.

EJERCICIO 4:

Calcula (recuerda que el resultado es siempre un número comprendido entre 0 y 4, ambos inclusive):

a)   239 + 421 (mod 5) =

b)   239 – 128 (mod 5) =

c)   237 – 129 (mod 5) =

d)   – 223 (mod5) =

e)   (239)·(128) (mod 5) =

EJERCICIO 5:

Escribe las tablas de sumar y de multiplicar con módulo 5. 

• ¿Se puede dividir con módulo 5? ¿Qué significa dividir con módulo 5?
• El inverso de un número a módulo 5 es otro número b tal que ab (mod 5) = 1. Mirando a la tabla de multiplicar del ejercicio contesta a las siguientes preguntas:

a)   El inverso de 1 módulo 5 es:

b)   El inverso de 2 módulo 5 es:

c)   El inverso de 3 módulo 5 es:

d)   El inverso de 4 módulo 5 es:

• Encuentra el inverso del 7 (mod 10) y 30^-1 (mod 7)
• Calcula

a)   239/128 (mod 5)

b)   128/3024 (mod 5)

EJERCICIO 6:

 Escribe las tablas de sumar y de multiplicar con módulo 7.

Con la tabla de multiplicar calcula los inversos modulo 7 de los números del 1 al 6.

EJERCICIO 7:

 Calcula (el resultado final tiene que ser un número entre 0 y 4, ambos inclusive): 

a)   83⁴²⁷ (mod 5)

b)   2002¹¹¹ (mod 5)

c)   324²⁰³ (mod 5)

d)   832⁴⁵ (mod 7)

e)   123²¹³ (mod 7)

f)    Inverso de 429 (mod 7)

g)   127² (mod 9)

h)   253⁴ (mod 7)

i)     756⁵ (mod 5)

CRIPTOGRAFÍA

CRIPTOLOGÍA: Ciencia que trata de 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.

Se divide en dos grandes ramas:

• Criptografía que se ocupa del cifrado de los mensajes.
• Criptoanálisis que se encarga de descifrar los mensajes en clave, rompiendo así el criptosistema.

El texto que queremos cifrar se llama texto plano y una vez codificado le llamaremos texto cifrado. Al proceso que transforma un texto plano en un texto cifrado le llamaremos encriptación o cifrado, y al proceso inverso a la encriptación, que nos recupera el texto original la llamaremos desencriptación o descifrado.

EL CIFRARIO DE CÉSAR.

 Es un algoritmo de sustitución (cada carácter o signo del texto original es sustituido en el texto cifrado por otro carácter durante el proceso de cifrado). Su cifrado consistía en sustituir una letra por la situada 3 lugares más allá en el alfabeto (ver tabla 1 del anexo). El procedimiento utilizado es de tipo monoalfabético, ya que a la hora de cifrar la sustitución se hace utilizando un único alfabeto de cifrado.

Así, por ejemplo la palabra “HOLA” se cifraría como “KROD”.

El procedimiento del cifrado de César se puede mejorar si hacemos lo siguiente:

Codificamos cada letra del alfabeto según la siguiente tabla:

Y luego los números los transformamos según la fórmula y=ax+b (donde a y b son dos números que escoge la persona que cifra y que conoce la que debe descifrar). Si al hacer la transformación algún valor de y fuera mayor que 26 lo reducimos módulo 26. Posteriormente estos números se vuelven a transformar en letras para enviar el mensaje codificado.

Fíjate en que César utilizaba A=1 y B=3

EJERCICIO 8:

Utiliza el cifrario de César para encriptar el mensaje “todos los perros de esta calle ladran por la noche”

EJERCICIO 9:

Descifra el mensaje: “VL SXHGHV OHHU HVWD IUDVH OR KDV FRPSUHQGLGR”

EJERCICIO 10:

En la página web eduteka, tienes tres applets distintos de cifrado de César:

El cifrado de César I. Permite codificar texto.

El cifrado de César II. Ejercicios sobre el tipo de codificación.

El cifrado de César III. Nos permite hacer ejercicios para decodificar frases.

CIFRADO UTILIZANDO LAS FRECUENCIAS.

“Una manera de resolver un mensaje cifrado, si sabemos en que lengua está escrito, es encontrar un texto llano en la misma lengua, suficientemente largo, y luego, contar cuantas veces aparece cada letra. A la letra que aparezca con más frecuencia la llamamos la primera, a la siguiente en frecuencia la llamaremos segunda... y así hasta que hayamos cubierto todas las letras que aparecen en nuestro texto.

Luego observamos el texto cifrado que queremos resolver, y clasificamos sus símbolos de la misma manera. Encontramos el símbolo que aparece con mayor frecuencia y lo sustituimos por la primera de nuestro texto, hacemos lo mismo con la segunda y así sucesivamente, hasta que hayamos cubierto todos los símbolos del criptograma que queremos resolver”

Al-Kindi.

Con el fin de facilitarte la tarea, la tabla 4 te muestra la frecuencia de las letras en castellano.

EJERCICIO 11:

 Como aplicación de todo lo anterior, trata de descifrar el siguiente texto:

DT EZOZD WZD LWFXYZD OPW ACZIPREZ QZCXLEP OP XLEPXLETNLD OPDNTQCLY PDEP XPYDLUP GLXZD L EPYPC BFP GPC FYL APWTNFWL AZOPTD PDNZRPC PYECP “PYTRXL” Z “FYL XPYEP XLCLGTWWZDL. WLD OZD PDELY XFI ÑTPY”.

Para ello trata de completar la tabla siguiente: 

Utiliza la tabla 4 para tratar de descifrarlo.

TABLA 4. FRECUENCIA DE LAS LETRAS EN CASTELLANO. 

PARA APRENDER MÁS.

Si quieres aprender más cosas sobre esto puedes descargarte este documento.