Introducción a la seguridad informática y criptografía clásica

TEMA III: FUNDAMENTOS BÁSICOS DE MATEMÁTICAS DISCRETAS


LECCIÓN 5: FUNDAMENTOS DE MATEMÁTICAS DISCRETAS PARA LA CRIPTOGRAFÍA

Autor: Dr. Jorge Ramió Aguirre.
Fecha de publicación: 28 de marzo de 2016.
Colaboración diseño Web: D. Jaime Sánchez Pedrós, becario Talentum Startups.

Esta única lección de matemáticas en el MOOC, tiene como objetivo realizar una breve introducción a aquellos conceptos y principios de las matemáticas discretas, que nos serán necesarios para comprender el funcionamiento de la criptografía clásica y, posteriormente, ser utilizadas en las operaciones de cifrado, descifrado y criptoanálisis que realizaremos en el curso. No pretende en absoluto ser un tratado de matemáticas; es más, en muchos apartados y para hacer más sencillo el aprendizaje, se huirá de explicaciones canónicas, fórmulas y nomenclatura propias de las matemáticas. Algo por lo que presento por adelantado mis disculpas a los matemáticos que lean este MOOC. Tras más de dos décadas enseñando criptografía, opino que este enfoque docente es más fácil de entender por parte del alumno. Básicamente nos centraremos en el concepto del módulo de cifra en el capítulo primero y en los inversos en el segundo, que es lo único que nos hace falta conocer de matemáticas discretas para trabajar con la cifra clásica. La lección tiene como elementos multimedia las píldoras formativas Thot número 11 ¿Cifrando dentro de un cuerpo?, número 23 ¿Qué son los inversos aditivos en un cuerpo?, número 12 ¿Qué son los inversos multiplicativos en un cuerpo?, número 24 ¿Por qué usamos el algoritmo de Euclides para calcular inversos? y número 25 ¿Cómo calculamos inversos con el Algoritmo Extendido de Euclides?

Temario


APARTADO 1. CIFRANDO DENTRO DE UN CUERPO

1.1. El concepto de módulo

En criptografía las operaciones de cifra se realizan dentro de un cuerpo de cifra o módulo. Dependiendo de que estemos hablando de criptografía clásica o bien de criptografía moderna, existirán ciertos matices que es menester aclarar y que en este capítulo vamos a abordar. Básicamente, la idea es que será distinto el sentido que le damos a cifrar dentro de un cuerpo o módulo en sistemas de cifra clásica y en sistemas de cifra moderna.

¿Qué es la aritmética modular? De la misma manera que la manecilla del segundero de un reloj al llegar a los 60 segundos se posiciona en el valor inicial 0 y en el minutero se apunta que ha transcurrido otro minuto, lo que obviamente puede aplicarse también al minutero y al horario, en matemática discreta decimos que un cuerpo finito n está conformado por n números enteros, que van desde el valor 0 hasta el valor n-1. Decimos entonces que trabajamos en un módulo n, cuando los elementos son todos los números enteros que van desde 0 hasta n-1.


Figura 1.1. Ejemplo de operación módulo 60 para el segundero y el minutero y módulo 12 para el horario.

Dichos números se conocen como restos. Esto es, los restos del número n igual a 7 serán {0, 1, 2, 3, 4, 5, 6} y los restos del número n igual a 10 serán {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Observa que si el número n es primo (el caso del 7), todos sus restos {1, 2, 3, 4, 5, 6} (el cero no se tiene en cuenta) son primos relativos con él, y si el número n es compuesto, como es el caso del 10, sólo algunos restos serán primos relativos con él {1, 3, 7, 9}. Esto que parece no tener aquí ninguna importancia por ser algo obvio, sí tendrá trascendencia en la cifra cuando hablemos de los inversos, es decir aquellos números que nos permitirán deshacer una operación de cifra, o lo que es lo mismo, descifrar.

Como en el ejemplo del reloj, si tras una operación el número resultante es igual o superior a n, o bien inferior a n, entraremos en lo que se conoce como grados de equivalencia. Por ejemplo, son equivalentes al resto 5 en mod 27 entre una infinidad de valores los números 32, 140, -22 y -76, pues 32 = 27x1 + 5; 140 = 27x5 + 5; -22 = 27x(-1) + 5 y -76 = 27x(-3) + 5. De la misma forma, 189 mod 27 = 0 porque 189 = 27x7 + 0.

Ejercicio 1.1
Resuelve mentalmente las siguiente equivalencias y expresa el resto en su forma canónica, es decir en un número comprendido entre 0 y n-1: 27 mod 15; 100 mod 53; -1 mod 23; -52 mod 13.

Nos vemos en el laboratorio...
Nuestra primera visita al laboratorio de prácticas será usar una calculadora común y básica para realizar operaciones modulares algo más difíciles que las del ejercicio anterior. Si no tienes a mano una calculadora, puedes usar la calculadora de Windows en modo científico, pero sin utilizar la función mod.
Práctica: encontrar el resultado de 23.595 mod 2.007 sin usar función módulo.
Solución: con una calculadora elemental dividimos 23.595/2.007 y obtenemos 11,756352. Restamos ahora la parte entera y nos queda la parte decimal 0,756352 que al multiplicarla por el módulo 2.007 nos da 1.517,9984. Redondeando este valor, obtenemos que 23.595 mod 2.007 = 1.518. Si se trabaja con más dígitos, como sería el caso de usar la calculadora de Windows, la división entrega 11,756352765321375186846038863976, por lo que 0,756352765321375186846038863976 x 2.007 = 1.518. Con el mismo método comprueba ahora que 1.143.962 mod 65.537 = 29.833. ¿Sabías que podías realizar operaciones modulares de esta forma cuando cuentas solamente con una calculadora simple sin la función mod?

 
Figura 1.2. Función mod en calculadoras de Windows.

Vamos a pensar un poco:
¿En qué módulo operaría un reloj tradicional? ¿Y un reloj digital? ¿Crees que un calendario podría ser otro sistema que trabaje en forma modular?

Es necesario aclarar que en teoría de números estas operaciones en un cuerpo se les denomina congruencias y se representan por el signo ≡. Así, la expresión a ≡ b mod n significa que a es congruente con b módulo n. Aún conscientes de que matemáticamente es más propio esto último, para simplificar usaremos el signo igual tal y como se indica a continuación.

19 ≡ 4 mod 5    (porque 19 = 5x3 + 4)

19 mod 5 = 4    (notación usada en este MOOC)

Recuerda que la operación mod se aplicará a toda la expresión que queda a la izquierda de la misma. De esta manera, 50 + 8*12 mod 27 es lo mismo que (50 mod 27 + 8*12 mod 27) mod 27. En la primera expresión no hace falta poner paréntesis, realizamos toda la operación y al final reducimos el resultado al módulo correspondiente. Es decir:

50 + 8*12 mod 27 = 146 mod 27 = 11

(50 mod 27 + 8*12 mod 27) mod 27 = (23 + 15) mod 27 = 38 mod 27 = 11

Nos vemos en el laboratorio...
Práctica: Con la calculadora científica de Windows y usando ahora la función mod, resuelve las siguientes congruencias:
a) 15*7-21 mod 27; b) 10-18*9 mod 26; c) 40*12 mod 60.
Solución: a) 3; b) 4; c) 0.

¿Va todo bien? Sí, pero a medias. ¿Qué sucedería si como ocurre en la criptografía moderna, se trabaja con números de cientos o miles de bits? Es muy duro hacer lo anterior, es decir reducir módulo al final, en operaciones del tipo (2160)1.024 mod 1.024, que es la expresión de algo tan simple como la firma RSA de un hash de 160 bits del mensaje a firmar, cifrado con la clave privada de 1.024 bits de su autor. No hay de qué preocuparse, esto se solucionará de una manera muy sencilla mediante algoritmos especiales de exponenciación rápida que se verán en cursos posteriores.

Nos vemos en el laboratorio...
Un ejercicio para comenzar a entender la magnitud de los números que se usarán en criptografía moderna. Usando el software de libre descarga "Fortaleza de cifrados" que puedes descargarlo desde la dirección que se indica, calcula estas operaciones modulares con números grandes. URL: http://www.criptored.upm.es/software/sw_m001e.htm.
Práctica: 7624524539977389266545798727262987285629 mod 8251934662886296118729013. No ponemos puntos de miles porque este programa los considera caracteres; así podrás copiar y pegar los números desde esta página web.
Solución:


Realiza otras operaciones modulares con diferentes números y observa que esta aplicación te deja introducir hasta 300 dígitos. El mensaje de error que verás si introduces un carácter en vez de un número, no es un error del programa en tanto en programación es muy fácil validar los datos de entrada. Se hizo para a propósito introducir números "especiales" de la forma "1270.09 de 40 dígitos" en los enunciados de prácticas y no tener que escribir 1270000000000000000000000000000000000009, con tantos ceros en el documento.

Vamos a pensar un poco:
¿Por qué se dice que entre dígitos y bits hay una relación aproximada de 3,3? Esto es, un número de 10 dígitos tendrá unos 33 bits, o bien un número de 64 bits tendrá unos 19 dígitos. Evidentemente esto es una aproximación, dependerá del número en cuestión, pero la aproximación es muy buena como ya lo comprobarás. Ayuda: los dígitos van del 0 a 9 y con 3 bits somos capaces de codificar hasta 8 valores, del 0 al 7.
Comprendido lo anterior, ¿qué valor en bits serían esos 300 dígitos que acepta como máxima entrada el programa Fortaleza de cifrados? ¿Es un valor cercano a algunos números usados habitualmente en la criptografía de clave pública actual?

Ahora lo vas a comprobar.

Nos vemos en el laboratorio...
Práctica: Comprueba esa relación de 3,3 con la calculadora de Windows. Introduce en binario 64 unos (lo máximo que soporta esa calculadora), cambia ahora a formato decimal y observa cuántos dígitos tiene ese número. Hecho esto, repite esta operación introduciendo ahora en binario un 1 seguido de 63 ceros (valor más pequeño de 64 bits) y observa cuántos dígitos se obtienen al verlo en formato decimal. ¿Cuántos dígitos decimales has obtenido para el número binario más grande de 64 bits y cuántos dígitos decimales para el número más pequeño? ¿Coincide con lo indicado más arriba?
Solución:
Número más grande de 64 bits:
1111111111111111111111111111111111111111111111111111111111111111 = 18.446.744.073.709.551.615 (20 dígitos)
Número más pequeño de 64 bits:
1000000000000000000000000000000000000000000000000000000000000000 = 9.223.372.036.854.775.808 (19 dígitos)
Valor medio = 19,5. Relación: 64/19,5 = 3,28. Sí coincide.

Vamos a pensar un poco:
Aunque es bastante obvio si conocemos cómo funciona la arimética binaria, observa que el primer número (18 trillones) es exactamente igual al doble de segundo menos una unidad. ¿Por qué?


1.2. El cuerpo de cifra en la criptografía clásica

A diferencia de la criptografía moderna, en criptografía clásica el cuerpo de cifra será el número de elementos que conforman el alfabeto del texto en claro. Aunque como ya hemos visto este alfabeto puede ser cualquier conjunto de letras y/o signos, en esta criptografía antigua o clásica es habitual para los hispanohablantes trabajar en módulo 27, ya que es el número de letras mayúsculas del alfabeto español, es decir de la A hasta la Z incluyendo la Ñ, codificando por lo general la letra A con el valor 0, la B con el 1, etc., y terminando con la Z y el valor 26, como se muestra en la figura 1.3.


Figura 1.3. Codificación estándar de las 27 letras del alfabeto español.

Sobre esos números se realizarán operaciones de suma, resta y producto para cifrar cada letra o bien un conjunto de letras del texto en claro.

Vamos a pensar un poco:
¿Por qué crees que en la cifra clásica se usaba preferentemente las letras mayúsculas y no las minúsculas, ni el espacio en blanco, ni los signos de puntuación?

En la criptografía clásica la cifra se realiza en un cuerpo cuyo tamaño es exactamente igual que la del alfabeto utilizado. De esta de manera, si ciframos usando solamente las letras mayúsculasde del alfabeto español de 27 letras, el módulo de trabajo será 27. Por ejemplo si la operación de cifra consistiese en multiplicar cada una de las letras del texto en claro por el número 5, entonces la ecuación de cifra para cada letra Mi de dicho texto será: Ci = 5 * Mi mod 27.

Ejercicio 1.2
Multiplica cada letra del mensaje HOLA por 5 en el módulo 27. ¿Cuál será el resultado de la cifra?
Solución:
Según la tabla de la figura 1.3, H=7, O=15, L=11, A=0. Por lo tanto C1 = 5*7 mod 27 = 8, C2 = 5*15 mod 27 = 21, C3 = 5*11 mod 27 = 1 y C4 = 5*0 mod 27 = 0. El criptograma será C = IUBA.


1.3. El alfabeto de cifrado en la cifra clásica

El alfabeto de cifrado consiste en un conjunto de letras y/o elementos gráficos que representan únicamente a un carácter, lógicamente todos distintos. Además de ese alfabeto estándar en español de letras mayúsculas, y por tanto módulo 27, ejemplos de otros alfabetos y módulos de trabajo pueden ser: mod 26 (mayúsculas inglés), mod 36 (mayúsculas inglés más los 10 dígitos), mod 37 (mayúsculas español más los 10 dígitos), mod 191 (subconjunto imprimible de los caracteres ASCII), etc.

En realidad, la codificación de esos caracteres o letras puede ser cualquiera. La razón de usar números correlativos según el alfabeto desde el 0 al 26 en español con mayúsculas, es sólo por simplicidad, dado que codificar las letras de otra manera más aleatoria (e.g. A=13, B=5, C=8, ... X=23, Y=3, Z=16) no añadirá complejidad a estos sistemas, en tanto la gran mayoría de sus algoritmos se atacarán por estadísticas del lenguaje y el código numérico que usemos en este caso para las letras no influirá en el resultado final. Es menester indicar, no obstante, que habrá algunos sistemas poligrámicos, como por ejemplo las matrices de Hill, que no se atacarán con estadísticas del lenguaje sino mediante otras técnicas.

La figura 1.4 muestra en color azul un alfabeto de cifra con los mismos elementos del lenguaje pero no ordenados correlativamente y en color rojo con elementos o signos diferentes.


Figura 1.4. Alfabeto en claro de 27 caracteres en español y dos posibles alfabetos de cifrado.

Ejercicio 1.3
¿A qué texto en claro corresponde el criptograma KQLKVC cifrado con el alfabeto en azul? ¿Si ahora cifras ese texto en claro encontrado con el alfabeto en rojo, qué criptograma se obtiene?
Solución:
La solucion es obvia, debes encontrarla tú mismo.

Vamos a pensar un poco:
En el ejercicio anterior has observado dos criptogramas con dos alfabetos de cifra distintos. Recordando lo que decíamos en una lección anterior sobre la definición que la RAE nos daba de criptografía, ¿te parece el segundo de ellos más enigmático que el primero? ¿Crees que es más seguro el segundo criptograma que el primero?


1.4. El cuerpo de cifra en la criptografía moderna

Al contrario de lo que ocurría con la criptografía clásica en que la cifra está orientada de manera preferente a las letras, además casi siempre en mayúsculas, y el valor de ese alfabeto coincidía con el módulo de cifra, en la criptografía moderna el cuerpo en el que se realizarán las operaciones no tiene relación alguna con el alfabeto utilizado en el texto en claro. Por ejemplo, si hablamos de un texto en un documento actual escrito en Word, se usarán los 256 caracteres del código ASCII-ANSI extendido, pero el cuerpo de cifra será distinto.

Es más, por lo general ese cuerpo de cifra o módulo en la criptografía actual suele ser un número mucho mayor, como por ejemplo 65.536 y 65.537 que se usan en el algoritmo de clave secreta IDEA, International Data Encryption Algorithm, o bien un número de unos 300 dígitos decimales o 1.024 bits, que se utiliza como valor mínimo del módulo en el popular algoritmo de clave pública RSA. Hoy en día, año 2016, es ya más común y aconsejable usar en este caso claves de 2.048 bits.

En la píldora formativa Thoth 11 de la figura 1.5, se repasan de una manera animada y amena estos conceptos. Refuerza estos principios viendo el vídeo. ¿Eres capaz de encontrar el gazapo que aparece en ella?


Figura 1.5. Píldora formativa Thot 11: ¿Cifrando dentro de un cuerpo?


APARTADO 2. INVERSOS EN UN CUERPO

2.1. Concepto de inverso aditivo

¿Qué son los inversos en un cuerpo? Como en la cifra realizaremos en emisión operaciones de suma y multiplicación módulo n de los elementos del texto en claro con números o alguna clave, o también suma or exclusivo módulo 2 en el caso de la cifra moderna, debemos asegurarnos de que en el extremo receptor se pueda deshacer dicha operación y recuperar así el texto en claro. Para ello usaremos los inversos, de manera que en el extremo receptor el destinatario de la cifra, conociendo generalmente una clave, realizará la misma operación que en el extremo emisor, pero aplicando estos valores inversos a los usados en emisión.

El inverso aditivo de un número en una operación suma dentro de un cuerpo n será el complemento de ese número dentro del cuerpo. Por ejemplo, en el cuerpo 27 el inverso aditivo de 12 será 15, puesto que 15+12 mod 27 = 0, que es la identidad de la suma. Esto significa que si para cifrar se aplica en emsión un desplazamiento de 12 espacios a la derecha (sumar) en el alfabeto, es decir la letra F=5 se convierte en la letra Q=17, para descifrar se puede desplazar el criptograma 12 espacios a la izquierda (restar), obteniendo lógicamente la letra F inicial, o bien usar este inverso y sumar (no restar) 15 al criptograma, de forma que Q + 15 = 17 + 15 = 32 mod 27 = 5 que es la letra F.

Como se puede observar, el inverso aditivo siempre existirá pues es simplemente el complemento de cuerpo.

Ejercicio 2.1
Si la expresión inv+ (a, n) denota inverso aditivo del número a en el cuerpo n, encuentra los siguientes inversos aditivos:
inv+ (9, 27), inv+ (37, 64) , inv+ (-5, 31).
Solución:
Los dos primero debes resolverlos tú mismo pues son muy sencillos. En el tercero, lo primero que debes hacer es poner el número -5 en su forma canónica dentro del cuerpo 31, es decir su equivalencia entre 0 y 30, simplemente sumando -5 + 31 mod 31 = 26 y resolver ahora inv+ (26, 31) = 5. Observa que en este caso al ser el número a negativo, obviamente el inverso será siempre el mismo número pero positivo; es decir inv+ (-18, 121) = 18, etc.

XOR o suma módulo 2

Un caso especial de inversos aditivos lo tenemos en la operación XOR y que se usará solamente en la cifra moderna. Aunque no será una operación de la cifra clásica, y por tanto no lo usaremos en los ejercicios y prácticas de este MOOC, se incluye en este apartado por consistencia del capítulo.

La operación XOR equivale a una suma módulo 2, es decir usando como restos el 0 y el 1, por lo tanto aplicable al entorno de operaciones digitales.

Ejercicio 2.2
Resuelve las operaciones modulares que se indican: 7 mod 2; 4 mod 2, -3 mod 2, 3*9 mod 2.
Solución:
En módulo 2 las operaciones son muy simples: números impares dan como resultado un 1 y números pares dan como resultado un 0. Esto es lo mismo que aplicar la tabla de verdad de esta operación, que indica que el XOR entre bits de igual valor entrega un 0 y el XOR entre bits de valores distintos entrega un 1. Así, 1 XOR 1 XOR 1 = 1, porque 1 XOR 1 = 0 y 0 XOR 1 = 1.

Observa que dado que los restos del módulo 2 son el 0 y el 1, este número no tiene inversos en el sentido que lo tienen los demás números. El inverso del or exclusivo es o XOR el mismo valor, dado que la operación XOR es involutiva, es decir aplicado dos veces se obtiene la identidad.

Recuerda que la operación se hace bit a bit y los números no tienen por qué ser el 0 y el 1; de hecho, por lo general serán números mucho mayores. Por ejemplo si hacemos un XOR entre los números decimales 19 y 30 tendremos: 19 XOR 30 = 13. ¿Por qué? Ahora lo veremos. El número 19 en binario es 10011 y 30 en binario es 11110; si realizamos la suma XOR bit a bit, se obtiene: 01101 que es igual a 13. Otro ejemplo con tamaños distintos de bits: 27 XOR 50 = 41, porque 27 = 11011 (de cinco bits) y 50 = 110010 (de seis bits) y 011011 XOR 110010 = 101001 = 41.

¿Y cuáles son los inversos? Si 27 XOR 50 = 41, entonces el inverso de 27 es 50 y el inverso de 50 es 21. Vamos a comprobarlo, suponiendo que el mensaje es 27 y la clave 50. Si realizamos la cifra, 27 XOR 50 = 41 como ya hemos visto. Para descifrar este criptograma numérico 41 y recuperar el secreto, haremos 41 XOR 50 = 101001 XOR 110010 = 011011 = 27, y hemos recuperado el secreto.

Nos vemos en el laboratorio...
Práctica: Usando la calculadora de Windows y siguiendo el ejemplo de los párrafos anteriores, cifra el mensaje LUZ con la clave abc, primero con sus valores decimales ASCII y después bit a bit. Hecho esto, descifra el criptograma y comprueba que se recupera el mensaje en claro LUZ. Ayuda. ASCII decimal: L = 76, U = 85, Z = 90, a = 97, b = 98, c = 99.
Solución:
L XOR a = 76 XOR 97 = 45 = - (carácter ASCII)
U XOR b = 85 XOR 98 = 55 = 7 (carácter ASCII)
Z XOR c = 90 XOR 99 = 57 = 9 (carácter ASCII)
Para descifrar el criptograma en ASCII -79 aplicamos la clave abc y obtenemos el texto en claro LUZ. Te lo dejo como ejercicio, así como demostrar que las operaciones pueden hacerse con los valores binarios de esos caracteres ASCII, realizando la suma XOR bit a bit.

En la píldora formativa Thoth 23 de la figura 2.1, encontrarás todos estos conceptos. Repásalos antes de continuar con la lección.


Figura 2.1. Píldora formativa Thot 23: ¿Qué son los inversos aditivos en un cuerpo?


2.2. Concepto de inverso multiplicativo

Se dice que un número a, elemento o resto del cuerpo n, tiene inverso multiplicativo en dicho cuerpo, o simplemente inverso, si existe otro número x que haga cumplir la condición de que:

a * x mod n = 1

Es decir, que al multiplicar el valor de a por el valor de x y reducirlo módulo n, se obtenga como resultado el valor 1, que es la identidad de la multiplicación.

Viendo la ecuación anterior y aunque matemáticamente no sea correcto decirlo, por simplicidad y para que podamos recordarlo de forma nmotécnica, podríamos asociar el concepto del inverso a que a = 1/x o bien que x = 1/a en ese cuerpo n. Observa que en aritmética modular no es lo mismo decir que x = 1/a mod n (lo cual no está permitido) a que x = a-1 mod n o bien que x = inv (a, n), que sí son expresiones correctas.

Vamos a pensar un poco:
Responde estas preguntas sin usar calculadora alguna. ¿Será el número 11 el inverso de 5 en módulo 27? ¿Es correcto que inv (7, 21) = 3? ¿O bien que 3 sea el inverso de 27 en módulo 81?

La píldora formativa Thoth 12 de la figura 2.2, ¿Qué son los inversos multiplicativos en un cuerpo? te presenta todos estos conceptos. Refuérzalos viendo el vídeo antes de continiar con el siguiente capítulo


Figura 2.2. Píldora formativa Thot 12 ¿Qué son los inversos multiplicativos en un cuerpo?


2.3. Condición necesaria para la existencia del inverso

Para que se cumpla la relación a * x mod n = 1, es imprescindible que el máximo común divisor entre a y n sea la unidad, esto es que mcd (a, n) = 1.

Ejercicio 2.3
Calcula el mcd (6, 27), el mcd (12, 27) y el mcd (10, 27). Si no eres capaz de resolverlo de forma mental, puedes usar la página de WolframAlpha: http://www.wolframalpha.com/input/?i=gcd+6,+27. Según el resultado obtenido, ¿qué valor usarías para multiplicar y cifrar así un mensaje en módulo 27, el 6, el 12 o el 10? La solucion a este ejercicio la debes encontrar tú.

Si esto no se tiene en cuenta, podríamos llegar al sinsentido de cifrar algo y que el receptor sea incapaz de descifrarlo. Por ejemplo, tal sería el caso si en un sistema elemental de cifra en módulo 27 multiplicamos el código de cada letra por 3; la cifra se produce pero no será posible descifrar el cripotgrama ya que no existe el inverso de 3 en ese módulo 27.

Nos vemos en el laboratorio...
Práctica: cifra el mensaje IMPOSIBLE en módulo 27 multiplicando cada letra por 3. Hecho esto intenta descifrar multiplicando el resultado por cualquier número dentro del cuerpo 27 y verás que es imposible recuperar el texto en claro. Nota: no hace falta que lo hagas con todo el mensaje; puedes comprobarlo sólo con el primer carácter I = 8 que al multiplicarlo por 3 se obtiene 24 = X. Multiplica ese valor 24 (la X) por todos los restos en mod 27 a ver si obtiene el 8 de la letra I. Puedes usar la calculadora de Windows en modo científicopara la operación mod.
Solución:
24*2 mod 27 = 21, 24*3 mod 27 = 18, 24*4 mod 27 = 15, 24*5 mod 27 = 12, 24*6 mod 27 = 9, 24*7 mod 27 = 6, 24*8 mod 27 = 3, 24*9 mod 27 = 0, 24*10 mod 27 = 24, 24*11 mod 27 = 21… y la cadena 21, 18, 15, 12, 9, 6, 3, 0 se repite, sin aparecer nunca el 8 que estamos buscando. No se ha calculado la operación con el resto 1 porque este valor nunca se usa para multiplicar el texto en la cifra clásica.

Vamos a pensar un poco:
¿Por qué crees que no se usa el valor 1 para cifrar un texto multiplicando el código de cada letra?


2.4. Visualización de inversos

Sea el cuerpo n = 10 con elementos o restos {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. A excepción del 0 y del 1 donde no tiene sentido hablar de estos inversos porque nunca multiplicaremos por 0 ni por 1 en una cifra, los únicos elementos en 10 que tendrán inversos son el 3, el 7 y el 9, pues el máximo común divisor de estos números y el módulo 10 es igual a 1.

Para comprobar que el número 3 tiene inverso en 10, podríamos multiplicar todos los elementos de n por 3 y reducir el resultado módulo 10. Veamos qué sucede.

  3*0 mod 10 = 0     3*1 mod 10 = 3     3*2 mod 10 = 6     3*3 mod 10 = 9     3*4 mod 10 = 2  
  3*5 mod 10 = 5     3*6 mod 10 = 8     3*7 mod 10 = 1     3*8 mod 10 = 4     3*9 mod 10 = 7  

Figura 2.3. Buscando el inverso de 3 en módulo 10.

Realizando esta operación con los 10 elementos del cuerpo, observamos que se obtienen todos los restos del número 10, del 0 al 9, y que solamente en el caso de x = 7 obtenemos el resultado 1 que estábamos esperando.

Por lo tanto, el inverso de 3 en el cuerpo 10 es 7, de la misma manera que el inverso de 7 en el cuerpo 10 es 3. Además, y esto será muy importante en criptografía, ese valor será único.

Ejercicio 2.4
Realiza la misma operación que has visto para encontrar el inverso de 3 en módulo 10, ahora para el número 4, esto es multiplicando 4 por todos los restos de 10 y reduciendo el resultado módulo 10, para comprobar que no existe el inverso del 4 en módulo 10.

Vamos a pensar un poco:
¿Por qué crees es muy importante en criptografía que el valor del inverso sea único? En realidad será vital.


2.5. Cálculo de inversos

El cálculo de inversos, en este caso multiplicativos, es una derivación del famoso teorema de Euclides con el que éramos capaces de encontrar el máximo común divisor entre dos números. La idea básica es que si entre dos números a y n no existen factores en común, entonces el máximo común divisor entre ellos será igual a 1. Y precisamente desde ese valor de la unidad podremos realizar un camino en sentido contrario en el algoritmo de Euclides, para llegar a ese inverso buscado que nos dice que si mcd (a, n) = 1 entonces existe el inverso de a en el cuerpo n, es decir inv (a, n). Este procedimiento se conoce como Algoritmo Extendido de Euclides AEE.

La píldora formativa Thoth 24 de la figura 2.4 ¿Por qué usamos el algoritmo de Euclides para calcular inversos?, muestra de una manera animada la razón de su uso. Observa cómo se va ordenando por restos y cómo se expresa la ecuación del máximo común divisor en función de los dos números en cuestión. No pases al siguiente apartado sin haber visto el vídeo.


Figura 2.4. Píldora formativa Thot 24: ¿Por qué usamos el algoritmo de Euclides para calcular inversos?

El ejercicio anterior es adecuado para explicar de una manera gráfica y bastante intuitiva qué significa un inverso dentro de un cuerpo, pero como te habrás dado cuenta no es ni mucho menos un algoritmo eficiente para encontrarlo. Para realizar este cálculo se utilizará el Algoritmo Extendido de Euclides que veremos a continuación.

Existen diversas formas de encontrar el inverso multiplicativo del número a en módulo n mediante este algoritmo. A continuación se describe una de ellas. Las ecuaciones que regirán para calcular x = inv (a, n) son las siguientes:

Hacer (g0, g1, u0, u1, v0, v1, i) = (n, a, 1, 0, 0, 1, 1)
Mientras gi distinto 0 hacer
   Hacer yi+1 = parte entera (gi-1/gi)
   Hacer gi+1 = gi-1 - yi+1 x gi
   Hacer ui+1 = ui-1 - yi+1 x ui
   Hacer vi+1 = vi-1 - yi+1 x vi
   Hacer i = i+1
Si (vi-1 < 0)
Hacer vi-1 = vi-1 + n
   Hacer x = vi-1

Vamos a encontrar el inverso de 9 en el cuerpo 275, esto es inv (9, 275). Sabemos que el inverso existe pues mcd (9, 275) = 1, dado que 9 = 32 y 275 = 52x11. En la figura 2.5 se recogen los pasos del algoritmo.


Figura 2.5. Cálculo del inv (9, 275) con el AEE.
Recuerdo de la operatividad del último cálculo:
  -9 = -1 - (4x2)
  275 = 31 - [4x(-61)]
Como vi-1 = -61, es decir ha salido un valor negativo, entonces X = - 61 + 275 = 214
Efectivamente, inv (9, 275) = 214 pues 214 x 9 = 1.926 mod 275 = 1, ya que 1.926 = 7 x 275 + 1

Ejercicio 2.5
Comprueba cada una de las operaciones que se muestran en la tabla de la figura 2.5. Hecho esto, usa el Algoritmo Extendido de Euclides haciendo una tabla similar y encuentra el inverso de 17 en módulo 315 es decir inv (17, 315) y el inverso de 123 en el cuerpo 1.000 es decir inv (123, 1.000). Verifica que los valores encontrados de los inversos son los correctos.

Para cálculos simples de inversos puedes usar esta calculadora de aritmética modular online: http://ptrow.com/perl/calculator.pl. Ten en cuenta que este software online calcula el inv (n, p), es decir el inverso del número n en el módulo p, y esto no quiere indicar que el módulo p deba ser un número primo. Observa además que indica el cálculo de inversos como 1/a.

Nos vemos en el laboratorio...
Vas a usar la calculadora Modular Arithmetic Calculator online antes indicada: http://ptrow.com/perl/calculator.pl.
Práctica: comprueba los inversos que has encontrado en el ejercicio 2.5: inv (17, 315) = 278 e inv (123, 1.000) = 187
Encuentra ahora el inverso de 2.001 en 101.000 y el inverso de 65.537 en módulo 123.451.234.512.345.
Solución: introduciendo los números sin puntos en los valores de a y del módulo m y pulsando en 1/a, se obtiene: inv (2001, 101000) = 32001 e inv (65537, 123451234512345) = 82767349638188.


Si además deseas ver qué operaciones se realizan con el Algoritmo Extendido der Euclides, siguiendo el código que has visto en este capítulo, puedes usar este software de la Universidad de Princeton http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php?.

Nos vemos en el laboratorio...
Vas a usar ahora el software online Modular inversion de la Universidad de Princeton antes indicado:
http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php?.
Práctica: encuentra nuevamente el inverso de 2.001 en 101.000. ¿Puedes encontrar en este caso el inverso de 65.537 en módulo 123.451.234.512.345? Si no es posible, encuentra ese inverso usando el software Fortaleza de cifrados que ya conoces: http://www.criptored.upm.es/software/sw_m001e.htm.
Solución: introduciendo los números sin puntos en los valores de a y del módulo p, se obtiene inv (2001, 101000) = 32001.

En este caso el inv (65.537, 123.451.234.512.345) no puede calcularse al haber un número mayor que 2.147.483.647 según nos indica el software. Vamos a calcularlo entonces usando el software Fortaleza de Cifrados pinchando en el icono herramientas, a continuación Inverso e introducimos número y módulo sin puntos, obteniendo el mismo resultado que el de la práctica anterior.

Seguramente te estarás haciendo la pregunta sobre cuán rápido es el Algoritmo Extendido de Euclides para calcular inversos. Se trata de un algoritmo muy rápido y además por lo general llega a la solución en muy pocos pasos. Por ejemplo, el cálculo de la clave la privada de RSA, inversa de la clave pública que típicamente es el valor 65.537 dentro de un cuerpo de 1.024 bits, puede decirse que es instantáneo. Lo vas comprobar ahora mismo.

La clave pública estándar en RSA es e = 65.357 y los primos p y q de 512 bits cada uno los que se indican. Esa clave pública tiene una clave privada o inversa cuya expresión es d = inv (e, ø(n)), siendo ø(n) = (p-1)(q-1).

Sea p = 66197543170843849840533774353620356391508998781699971424073172435615798297196826484495051057094750
26460901730886511842512944356873128784787527296733938141

Sea q = 19808826542405197030250728365018961587053374332415385696514927274019083385070715406366399204225513
389914729051422456448853473753204354080970072717103921891

Entonces el módulo n = pxq n = 1311295650204625541161348209180081873080775941823575867367190271619515603355507
150937967902354113951383621057864571465516040116715202043329101727218153906412626383648720913865909348865
849612918206096916109693874024530980045442517255141426561089003838872087939432951783881659618433694369737
48440508072489744631

p-1 = 6619754317084384984053377435362035639150899878169997142407317243561579829719682648449505105709475026
460901730886511842512944356873128784787527296733938140

q-1 = 1980882654240519703025072836501896158705337433241538569651492727401908338507071540636639920422551338
9914729051422456448853473753204354080970072717103921890

Entonces ø(n) = 1311295650204625541161348209180081873080775941823575867367190271619515603355507150937967902
354113951383621057864571465516040116715202043329101727218153906148340575053825093722868290862039640656163
354810255865484802085804238810369351160878402045904488987924183125128694198745954252593594908826829080586
51884600

Y por lo tanto d = inv (65537, ø(n)) = 32879932587412624193820948657180349146797062807249068813715973775918183484
048780095768232508941749794905236498296386610350011807041694276556950552170412346820392556661897500874154
483323767360273940536791331061097933497140632575185845593656683736436619830871265537390835357114708077682
141594444790395

Nos vemos en el laboratorio...
Práctica: calcula la clave privada del sistema RSA indicado usando el software Fortaleza de cifrados y comprueba que obtienes el mismo resultado que se indica más arriba: http://www.criptored.upm.es/software/sw_m001e.htm.
Nota: al copiar los números, recuerda que para mantener el formato de la lección éstos están recortados por la derecha; deberás concatenarlos.
Solución:

La píldora formativa Thoth 25 de la figura 2.6 ¿Cómo calculamos inversos con el algoritmo extendido de Euclides? te indica paso a paso cómo se usa este algoritmo para el cálculo de inversos. Repasa todos estos conceptos viendo este vídeo.


Figura 2.6. Píldora formativa Thot 25: ¿Cómo calculamos inversos con el algoritmo extendido de Euclides?

Ejercicio 2.6
Busca en Wikipedia la entrada Algoritmo de Euclides. Ahí verás también el Algoritmo Extendido de Euclides. A primera vista puede parecer algo complicado pero en absoluto lo será su cálculo, como has podido comprobar por los ejercicos hechos y por la píldora Thoth 25.


APARTADO 3. EVALUACIÓN DE LA LECCIÓN 5

3.1. Test de evaluación personal

En las siguientes 10 preguntas, elige la respuesta correcta. Sería muy recomendable que la primera vez que contestes este test lo hagas sin repasar la lección.

Para confirmar si tus respuestas son las correctas, accede y consulta las redes sociales de Crypt4you en twitter y en facebook. Las soluciones al test de esta quinta lección se publicarán en dichas redes sociales a partir del lunes 11 de abril de 2016.

1. Son ejemplos cotidianos de operación en forma modular:

a) Un reloj tradicional y un reproductor de DVD.
b) Un reloj digital y un horno microondas.
c) Un reloj tradicional y un termómetro.
d) Un reloj digital y un calendario.

2. ¿Cuál es el resultado correcto de esta operación?

a) 159 mod 99 = 59.
b) 159 mod 99 = 60.
c) 159 mod 99 = 69.
d) 159 mod 99 = 61.

3. ¿Cuál es el resultado correcto de esta operación?

a) – 8 mod 27 = 21.
b) – 8 mod 27 = 8.
c) – 8 mod 27 = 19.
d) – 8 mod 27 = 18.

4. ¿Cuál es el resultado de la congruencia 15-3*12 mod 27?

a) 15.
b) 21.
c) 26.
d) 6.

5. Multiplicamos el código de cada letra por 5, en la tabla del alfabeto se representa:

a) Por saltos modulares de 5 espacios multiplicado por el código de la letra.
b) Por desplazamientos modulares de 5 espacios y sumando el código de la letra.
c) Por desplazamientos modulares de 5 espacios.
d) Por saltos modulares de 5 espacios.

6. El cuerpo de cifra en la criptografía moderna:

a) Es el alfabeto ASCII de 256 caracteres.
b) No tiene relación alguna con el alfabeto que usemos.
c) Depende del alfabeto que usemos.
d) Debe ser siempre de 1.024 bits.

7. ¿Cuál puede ser el inverso de 5 en el cuerpo 12?

a) 10.
b) 7.
c) 5.
d) 3.

8. Para que exista el inverso multiplicativo de a en el cuerpo n es condición necesaria:

a) Que se cumpla mcm (a, n) = 1.
b) Que se cumpla mcd (a, n) = 1.
c) Que se cumpla mcd (a, n) = 0.
d) Que se cumpla mcm (a, n) = 0.

9. ¿Cuál de estas afirmaciones es falsa?

a) El inv (7, 26) = 15.
b) El inv (3, 26) = 9.
c) El inv (5, 26) = 21.
d) El inv (13, 26) = 14.

10. ¿Qué valor puede usarse para cifrar un mensaje en módulo 27 por multiplicación?

a) 3.
b) 6.
c) 7.
d) 15.


Ir a: [Portada c4y]    [Lección 4] [Índice] [Lección 6]