1. No category

Departamento de Matemática Aplicada
http://www.dma.fi.upm.es/
Faculta de Informática – Universidad Politécnica de Madrid
Aplicaciones de Aritmética Modular
Laboratorio de Matemática Discreta
Jesús Martínez Mateo [email protected]
Algunas de las aplicaciones más interesantes de la aritmética modular son aquellas en las que
se utilizan los conocimientos de esta disciplina para el cifrado y descifrado de mensajes. Es lo
que conocemos como criptografía, y que comúnmente utilizamos para el intercambio de
secretos entre dos interlocutores.
Sesión 1. Cifrado de clave privada: Método de Julio César
Antes de poder cifrar un mensaje, en primer lugar debemos codificar el mismo substituyendo
cada letra del mensaje por un valor numérico. Por ejemplo, podemos utilizar como valor
numérico la posición que ocupa cada letra en el alfabeto utilizado. Después de codificar, cifrar
y descifrar el mensaje, podremos decodificar el mismo y recuperar el texto original.
Esta codificación y decodificación la podemos implementar en Python utilizando las dos
siguientes funciones, char2num(c) y num2char(n). Asumimos que ‘a’ será la primera
letra del alfabeto y por lo tanto ocupará la posición cero, y ‘z’ –la última letra del alfabeto–
corresponderá con la posición 25 (asumiendo que no incluimos la letra ‘ñ’ dentro de nuestro
alfabeto).
La función char2num(c) devuelve el número asociado a la letra proporcionada. En este
ejemplo la función nos proporcionará el valor esperado siempre que proporcionemos una letra
en minúsculas correspondiente del alfabeto utilizado.
def char2num(c):
n = ord(c) - ord('a')
return n
Por ejemplo:
>>> char2num('d')
3
La función num2char(n) realiza el proceso inverso y devuelve la letra correspondiente a la
posición proporcionada.
Departamento de Matemática Aplicada
http://www.dma.fi.upm.es/
Faculta de Informática – Universidad Politécnica de Madrid
def num2char(n):
c = chr(ord('a') + n)
return c
Por ejemplo:
>>> num2char(13)
'n'
Utilizando ambas funciones podemos codificar y decodificar un mensaje. Durante la
codificación convertimos una cadena de caracteres (letras) en una lista de números. La
codificación de una cadena de texto la podemos implementarla con la siguiente función:
def text2list(T):
L = []
for c in T:
L.append(char2num(c))
return L
Una cadena de texto en Python la proporcionamos entrecomillando el texto de la siguiente
forma. Ejemplo:
>>> text2list('hola')
[7, 14, 11, 0]
Decodificamos un mensaje mediante la función:
def list2text(L):
T = ''
for n in L:
T = T + num2char(n)
return T
Ejemplo
>>> list2text([0, 3, 8, 14, 18])
'adios'
Asumiendo que queremos cifrar un mensaje utilizando una transformación afín de la forma x
→ a x + b (mod 26), con m.c.d.(a, 26) = 1 (donde 26 es el número de letras del alfabeto
utilizado). La función que implementa este cifrado es la siguiente:
Departamento de Matemática Aplicada
http://www.dma.fi.upm.es/
Faculta de Informática – Universidad Politécnica de Madrid
def cifra(M, a, b):
L = text2list(M)
U = []
n = char2num('z') + 1
for x in L:
y = (a * x + b) % n
U.append(y)
return list2text(U)
Ejercicio 1
a) Escribe la función descifra(M, a1, b) que implemente el procedimiento
inverso, esto es, el procedimiento de descifrado. La función recibirá como parámetros:
el mensaje cifrado (en texto), M, el inverso de a en aritmética Zn, a1, y b. Donde a y b
son los mismos parámetros que se utilizaron para cifrar el mensaje.
Recuerda que en las funciones proporcionadas n = 26.
b) Prueba ambas funciones con el cifrado y descifrado del mensaje “aritmetica”,
utilizando los valores a = 5, y b = 7. Calcula manualmente el inverso requerido para
llamar a la función descifra().
c) [OPCIONAL] Implementa la función inverso(a, m) que calcule de forma genérica
el inverso de a (mod n) e incluye esta función dentro de una función descifra(M,
a, b) que reciba como parámetro a en vez de su inverso.
Departamento de Matemática Aplicada
http://www.dma.fi.upm.es/
Faculta de Informática – Universidad Politécnica de Madrid
Sesión 2. Cifrado de clave pública: Método RSA
Para realizar el cifrado de clave pública mediante el método RSA necesitamos convertir un
texto en una secuencia de números. Cada uno de esos números se construirá a partir de un
número determinado de letras. Teniendo en cuenta que nuestro alfabeto requiere al menos
dos cifras decimales para identificar el mayor de los índices de una letra, utilizaremos una
asignación fija de dos cifras por letra de la siguiente forma: 'a' = 00, 'b' = 01, 'c' =
02, …, 'z' = 25 (teniendo en cuenta una vez más que no incluimos la letra ñ en nuestro
alfabeto, el espacio, así como ningún otro carácter especial).
La siguiente función en Python convierte una cadena de texto en un número:
def text2num(T):
L = text2list(T)
m = 0
i = (len(L) - 1) * 2
for n in L:
m = m + (n + 1) * 10**i
i = i - 2
return m
Ejemplo 1
>>> text2num('hola')
8151201
La función inversa es la siguiente:
def num2text(m):
L = []
while m > 0:
n = m % 100
m = m / 100
L.insert(0, n - 1)
return list2text(L)
Ejemplo 2
>>> num2text(8151201)
'hola'
Departamento de Matemática Aplicada
http://www.dma.fi.upm.es/
Faculta de Informática – Universidad Politécnica de Madrid
Se escogen dos números primos p y q que se mantienen en secreto en todo momento. A partir
de ambos números primos calculamos n = p * q, y escogemos otro número primo e que será
nuestro exponente. Hacemos públicos los números n y e, que se utilizarán para cifrar y
descifrar un mensaje de la siguiente forma.
Asumiendo que el número correspondiente a nuestro mensaje es M. Calculamos el mensaje
cifrado, C, como:
C = Me (mod n)
Para descifrar el mensaje original calculamos:
M = Cd (mod n)
donde d es el inverso de e (mod (p-1)(q-1)).
Ejercicio 2
a) Implementa las funciones cifraRSA(M, n, e) y descifraRSA(M, n, d)
que implementen los procedimientos de cifrado y descifrado de un mensaje descritos
anteriormente. Utiliza los siguiente valores: p = 89, q = 97, e = 71, y d = 119.
b) Prueba ambas funciones con el cifrado y descifrado de los textos “ca”, “qt”, y “zp”.
c) [OPCIONAL] Implementa una función que permita el cifrado de un mensaje
independientemente de su longitud (como punto de partida se puede asumir que el
mensaje contiene un número para de letras).
d) [OPCIONAL] ¿Podría mejorarse la codificación de los mensajes de texto? Implementa
dicha mejora.