Inicio Discusiones Funciones y conceptos del álgebra Criptografía y cifrados
Estudiante: Entendí muy bien la explicación sobre aritmética modular .
Maestro: Bien. ¿Sabía que este tipo de matemáticas se utilizan durante las guerras y también cuando se necesita mantener información privada y confidencial?
Estudiante: ¿Cómo se podría utilizar la aritmética modular durante una guerra?
Maestro: Se utilizó durante la Guerra Civil de los Estados Unidos en 1.860 y mil años antes en el Imperio Romano durante el período de César. Las personas que se querían comunicar con sus aliados, pero no con sus enemigos, enviaban mensajes encriptados que iban y volvían.
Estudiante: ¿Qué es un mensaje encriptado?
Maestro: Los mensajes usan letras y números de un mensaje dado y los transforman en series diferentes de letras y números que no tienen ningún sentido, a no ser que se tenga el código adecuado para descifrarlo.
Estudiante: ¿Y si se conoce el código?
Maestro: Entonces se puede leer el mensaje secreto. Existen procedimientos de codificación sumamente complejos que pueden crear obstáculos a expertos muy bien entrenados y aún a los computadores. Ahora quiero hablar de unas codificaciones simples para que pueda practicar las ideas básicas.
Estudiante: ¿Qué es un código?
Maestro: Un código es un método para encriptar un mensaje. Lo que quiero enseñarle tiene que ver con las operaciones de suma, resta, multiplicación y división, así que tenemos que crear primero un alfabeto numérico asignando números a las letras, comenzando por cero.
Estudiante: A será 0, B será 1 ..... así:
A |
B |
C |
D |
... |
Z |
0 |
1 |
2 |
3 |
... |
25 |
Maestro: Bien. Casi todos los cifrados usan aritmética modular en algún paso de su encriptamiento o descifrado. Como hemos usado los números de 0 a 25 para representar las 26 letras del alfabeto, usaremos mod 26 en todos nuestros códigos del ejercicio.
Nota: Como esta discusión es traducida del inglés, no usa la Ñ, letra que no existe en ese idioma, y de ahí que se utilice mod 26
Comencemos con lo que se denomina un cifrado de desplazamiento. Primero debemos traducir nuestro mensaje al alfabeto numérico. Por ejemplo la codificación de 'JAMES' será así:
J |
A |
M |
E |
S |
9 |
0 |
12 |
4 |
18 |
Ahora escoja en número para hacer el desplazamiento
Estudiante: Escojamos el 7
Maestro: Necesitamos recordar este número , que llamaremos el valor "B-desplazamiento", tanto para cifrar como para *des*cifrar el mensaje. Ahora cambiamos el cifrado añadiendo B a cada uno de los números de nuestro código de palabras así:
J |
= |
9 |
+ |
7 |
= |
16 |
A |
= |
0 |
+ |
7 |
= |
7 |
M |
= |
12 |
+ |
7 |
= |
19 |
E |
= |
4 |
+ |
7 |
= |
11 |
S |
= |
18 |
+ |
7 |
= |
25 |
Entonces tenemos:
7 |
19 |
11 |
25 |
Podemos ahora cambiar estos números nuevamente a letras, utilizando nuestro alfabeto numérico. El nombre de JAMES en criptografía con un "B-desplazamiento" de 7 es:
Q |
H |
T |
L |
Z |
Ensayemos con otro ejemplo, encriptar la frase 'es un espía ' usando el mismo "B-desplazamiento"
Estudiante: Primero traducimos las palabras codificadas al alfabeto numérico así:
E |
S |
U |
N |
E |
S |
P |
I |
A |
||
4 |
18 |
20 |
13 |
4 |
18 |
15 |
8 |
0 |
Luego añadimos el "B-desplazamiento" a cada número:
E |
= |
4 |
+ |
7 |
= |
11 |
S |
= |
18 |
+ |
7 |
= |
25 |
U |
= |
20 |
+ |
7 |
= |
27 |
N |
= |
13 |
+ |
7 |
= |
20 |
E |
= |
4 |
+ |
7 |
= |
11 |
S |
= |
18 |
+ |
7 |
= |
25 |
P |
= |
15 |
+ |
7 |
= |
22 |
I |
= |
8 |
+ |
7 |
= |
15 |
A |
= |
0 |
+ |
7 |
= |
7 |
y lo traducimos nuevamente a letras.11 es L, 25 es Y, 20 es U, 22 es W, 15 es P, 7 es H, pero ¿qué pasa con 27?
Maestro: ¿Tal vez mod 26 sería útil?
Estudiante: ¡Correcto!, 27 mod 26 es 1, que corresponde a B, así que UN = BU.
Maestro: Si quiere mandar el mensaje ´James es un espía´ a alguien, pero no quiere que todo el mundo pueda leerlo, podrá enviar este mensaje: ´QHTLZ LY BU LYWPH´. Un buen criptógrafo podría utilizar el tamaño de las palabras y su puntuación para adivinar el cifrado y descifrar el mensaje. Por ejemplo ¿qué palabras tienen solo dos letras?
Estudiante: Entiendo, haría un listado de palabras con dos letras y con cinco, hasta que descifre algunas de las letras y así pueda llegar al mensaje final.
Maestro: ¡Sí! Así lo haría un buen criptógrafo. Para evitar que se descifre fácilmente el mensaje, lo hacemos más difícil y removemos la puntuación y agrupamos las letras en ´palabras´ de cinco letras, así que el mensaje seria:
QHTLZ LYBUL YWPH
Para que alguien traduzca el mensaje, tendrá que utilizar nuestro código al revés.
Estudiante: Primero tendrían que traducir las letras a números nuevamente, así que QHTLZ sería otra vez
16 7 19 11 25
Maestro: Pero para resolver el cifrado ellos tendrán que saber que usamos el "B-desplazamiento" de 7
Estudiante: ¡...que, como estamos trabajando hacia atrás tendríamos que restar! ¡Así que tenemos 16 - 7 = 9, que es 'J', 7 - 7 = 0, que es 'A', y así sucesivamente!
Maestro: ¿Qué sucede con la letra B?
Estudiante: ¡ Sucede que B es 1, y que 1 menos 7 es 6 negativo! ¿Qué pasó?
Maestro: Que se olvidó de reversar el cálculo de ´mod 26´. Recuerde que la operación de ´mod 26´ nos obligó a restar un múltiplo de 26. En este caso 26*1 = 26. Tenemos entonces que sumarlo nuevamente.
Estudiante: Menos 6 mas 26 es 20 que se traduce en U. ¡Qué bueno, tiene sentido!
Maestro: Los cifrados de desplazamiento también pueden trabajar en sentido opuesto, donde se resta el "B-desplazamiento" primero, cuando se está cifrando el mensaje, y luego lo suma nuevamente cuando se está descifrando.
Ensayemos otra clase de cifrado. Se llama un cifrado de multiplicación. Es muy similar al cifrado de desplazamiento, excepto que se multiplica y divide en vez de sumar y restar. Escoja una palabra fácil para usarla como ejemplo.
Estudiante: ¿Qué tal la palabra S I M P L E que en el alfabeto numérico es:
18 8 12 15 11 4?
Maestro: Bien. Utilizaremos de nuevo el número 7, pero esta vez lo llamaremos ´A´ para no confundirlo con el cifrado de desplazamiento. Ahora multiplique el valor de las letras del alfabeto numérico por un "A-multiplicador":
S |
= |
18 |
* |
7 |
= |
126 |
I |
= |
8 |
* |
7 |
= |
56 |
M |
= |
12 |
* |
7 |
= |
84 |
P |
= |
15 |
* |
7 |
= |
105 |
L |
= |
11 |
* |
7 |
= |
77 |
E |
= |
4 |
* |
7 |
= |
28 |
Como estos números son muy grandes para nuestro alfabeto numérico, tenemos que utilizar nuevamente el mod 26.
Estudiante: Muy bien,
126 mod 26: 126/26 = 4 con residuo 22, entonces 22
56 mod 26: 56/26 = 2 con residuo 4, entonces 4
84 mod 26: 3 con residuo 6, entonces 6
105 mod 26: 4 con residuo 1, entonces 1
77 mod 26: 2 con residuo 25, entonces 25
28 mod 26: 1 con residuo 2, entonces 2
Entonces el mensaje cifrado es W E G B Z C. ¡Eso fue muy sencillo!
Maestro: Tal vez, pero ¿sabe cómo decodificarlo?
Estudiante: Hmmm... Trabajando en reverso, W es 22. Dividido por nuestro multiplicador ´A´, es 22 sobre 7 que es 3 con un residuo de 1. ¿Qué hago con esto?
Maestro: ¡Esta es la parte difícil! Antes de dividir necesitamos reversar la operación del mod 26 nuevamente. Como lo hicimos antes, añada 26 y vea si la división funciona.
Estudiante: Bueno. 22 + 26 = 48, que no es completamente divisible por 7.
Maestro: Haga otros ensayos.
Estudiante:
48 + 26 = 74, no.
64 + 26 = 100, no.
90 + 26 = 126, dividido por 7 es 18, sí
Ese funciona, porque 18 es nuestra letra original ´S´, pero ya no es tan sencillo.
Maestro: Hay otro método. Ensaye a multiplicar cada código numérico de su alfabeto por 15 y tome luego mod 26.
Estudiante:
W |
es |
22, |
por |
15 |
es |
330, |
mod |
26 |
es |
18, |
que es |
'S' |
E |
es |
4, |
por |
15 |
es |
60, |
mod |
26 |
es |
8, |
que es |
'I' |
G |
es |
6, |
por |
15 |
es |
90, |
mod |
26 |
es |
12, |
que es |
'M' |
B |
es |
1, |
por |
15 |
es |
15, |
mod |
26 |
es |
15, |
que es |
'P' |
Z |
es |
25, |
por |
15 |
es |
375, |
mod |
26 |
es |
11, |
que es |
'L' |
C |
es |
2, |
por |
15 |
es |
30, |
mod |
26 |
es |
4, |
que es |
'E' |
Eso funcionó, pero ¿de donde salió el 15?
Maestro: La aritmética modular no es exactamente lo mismo que la aritmética normal. En la aritmética normal el inverso de un multiplicador A es 1/A, por ejemplo el inverso de 7 es la fracción 1/7. ¡En aritmética modular un multiplicador solo tendrá un inverso si el multiplicador (por ejemplo 7) y la base modular (en nuestro caso 26) no tienen factores comunes mayores a 1! El inverso modular - lo llamaremos A´ (A prima) -será un número entero que tampoco tiene factores comunes con la base modular. 7 y 15 son inversos modulares en mod 26.
Estudiante: ¿Existe alguna manera para encontrar el inverso modular de un número?
Maestro: Es lo mismo que en la aritmética normal. En la aritmética modular si un número y su inverso se multiplican entre sí, el resultado es 1; por lo tanto, (A*A´) mod 26 = 1. Comience por hacer una lista de múltiplos de 26, y luego añada 1 a cada uno.
Estudiante:
26 |
* |
1 |
= |
26, |
más uno es |
27 |
26 |
* |
2 |
= |
52, |
más uno es |
53 |
26 |
* |
3 |
= |
78, |
más uno es |
79 |
26 |
* |
4 |
= |
104, |
más uno es |
105 |
26 |
* |
5 |
= |
130, |
más uno es |
131 |
26 |
* |
6 |
= |
156, |
más uno es |
157 |
27 |
* |
7 |
= |
182, |
más uno es |
183 |
Maestro: Creo que esto debe ser suficiente. Ahora sabemos que todos esos números, mod 26, son iguales a 1. ¿Hay alguno que sea divisible exactamente por 7?
Estudiante: Si, ¡105 dividido por 7 es ... 15!
Maestro: ¿Qué pasaría si en cambio utilizáramos el multiplicador de 9? ¿Tiene 9 un inverso?
Estudiante: Hmmm. 27 dividido 9 es 3, así que 9 y 3 son inversos modulares, ¿correcto?
Maestro: En mod 26, sí. Si utilizamos módulos diferentes, números diferentes tendrán diferentes inversos, y algunos no tendrán ningún inverso.
Estudiante: Como cuando comparten un factor común con 26, ¿correcto? ¿Por qué es esto?
Maestro: Veamos qué pasa cuando usamos el número 6, que comparte el factor 2 con 26. Aquí mostramos algunas letras codificadas multiplicando por 6:
A |
0 |
por |
6 |
= |
0, |
mod |
26 |
= |
0 |
B |
1 |
por |
6 |
= |
6, |
mod |
26 |
= |
6 |
C |
2 |
por |
6 |
= |
12, |
mod |
26 |
= |
12 |
D |
3 |
por |
6 |
= |
18, |
mod |
26 |
= |
18 |
E |
4 |
por |
6 |
= |
24, |
mod |
26 |
= |
24 |
F |
5 |
por |
6 |
= |
30, |
mod |
26 |
= |
4... |
M |
12 |
por |
6 |
= |
72, |
mod |
26 |
= |
20 |
N |
13 |
por |
6 |
= |
78, |
mod |
26 |
= |
0 |
O |
14 |
por |
6 |
= |
84, |
mod |
26 |
= |
6 |
P |
15 |
por |
6 |
= |
90, |
mod |
26 |
= |
12 |
Estudiante: Pero A y N quedan codificadas iguales, como también lo son B y O, y C y P. ¿Este patrón continua?
Maestro: Sí. Porque como 26 y 6 tienen un factor común que es dos, cada número representará dos letras. No podemos reversar el proceso puesto que no sabríamos cuáles de las dos letras escoger. Esto sucede cuando el número que usamos como multiplicador comparte un factor con 26.
Estudiante: ¿Así que esto no pasaría con 5, pero sí con 13?
Maestro: Ensaye
Estudiante:
A |
0 |
0 |
B |
5 |
13 |
C |
10 |
0 |
D |
15 |
13 |
E |
20 |
0 |
F |
25 |
13 |
G |
4 |
0 |
H |
9 |
13 |
I |
14 |
0 |
J |
19 |
13 |
K |
24 |
0 |
L |
3 |
13 |
M |
8 |
0 |
N |
13 |
13 |
O |
18 |
0 |
P |
23 |
13 |
Q |
2 |
0 |
R |
7 |
13 |
S |
12 |
0 |
T |
17 |
13 |
U |
22 |
0 |
V |
1 |
13 |
X |
6 |
0 |
Y |
11 |
13 |
Z |
16 |
0 |
Estudiante: Para un factor común de 13 existen 13 posibilidades de letras para cada número, como usted lo dijo. Entonces 13 no tiene un inverso, pero 5 sí lo tiene.
Maestro: Mire nuevamente su lista de 'múltiplos de 26 más uno' y trate de encontrarlo.
Estudiante: ¡Bueno... 27... 53... 79... 105! 105 dividido por 5 es 21, así que 5 y 21 son inversos en mod 26. Entonces para mod 26 tenemos 7 con 15, 5 con 21, y 3 con 9, ¿hay algunos otros?
Maestro: Sí. Estos pares funcionan para mod 26, pero recuerde que no se aplica a otro sistema con un número diferente de letras.
1 es su propio inverso
3 y 9
5 y 21
7 y 15
11 y 19
17 y 23
25 es también su propio inverso
Estudiante: ¿ Qué tan difíciles se pueden volver los cifrados?
Maestro: Hay cifrados que se la ganan a los mejores programadores y a los computadores más nuevos. Así tiene que ser para estar más adelantados que la tecnología de la oposición. Estoy seguro de que en la medida que la tecnología se vuelve mejor y más rápida, también lo serán los cifrados. Los cifrados que hemos visto en esta discusión son algunos de los primeros, que datan de antes de la existencia de los computadores. En realidad, a César le gustaba cifrar con el código de desplazamiento 3.
Estudiante: Apuesto a que los códigos más nuevos contienen muchas matemáticas avanzadas.
Maestro: Si, así es. Veamos el último cifrado del cual vamos a hablar. Se llama el cifrado afín. Afín significa lineal , así que este cifrado toma la forma de una recta:
(A*x + B) mod 26
Con este se deben conocer tanto el multiplicador ´A ´ como el ´B-desplazamiento' para decodificar el mensaje. Note que si A = 1 se tiene cifrado normal de desplazamiento, y cuando B = 0 se tiene un cifrado de multiplicación. Nuevamente aquí el máximo común divisor entre A y 26 tiene que ser 1, para poder decodificar el mensaje.
Estudiante: ¿Podemos usar el 7 nuevamente?
Maestro: Claro, usemos el 7 para nuestra A y 5 para nuestra B.
Estudiante: Entonces si yo le permito a alguien conocer mi A y mi B y qué tipo de cifrado uso, esa persona puede decodificar mis mensajes.
Maestro: Correcto. Practiquemos con la palabra ´CHAIR´.
Estudiante: Déjeme ensayarlo, el primer paso es:
C H A I R ---- 2 7 0 8 17
Ahora tenemos (7*x +5) mod 26, entonces:
7*2 + 5 = 19, mod 26 = 19 que es T
7*7 + 5 = 54, mod 26 = 2 que es C
7*0 + 5 = 5, mod 26 = 5 que es F
7*8 +5 = 61, mod 26 = 9 que es J
7*17 +5 = 124, mod 26 = 20 que es U
El mensaje cifrado es T C F J U.
Maestro: Muy bien, ahora para trabajar en reverso, restamos 5 y multiplicamos por el inverso modular, que para 7 mod 26, sabemos que es 15.
Estudiante:
T = 19: 15*(19-5) mod 26 = 210 mod 26 = 2
C = 2: 15*( 2-5) mod 26 = -45 mod 26 = ??
F = 5: 15*( 5-5) mod 26 = 0 mod 26 = 0
J = 9: 15*( 9-5) mod 26 = 60 mod 26 = 8
U = 20: 15*(20-5) mod 26 = 225 mod 26 = 17
¡Espere! ¿Cómo hago mod para un número negativo como - 45?
Maestro: Lo mismo que con un número positivo, así que -45 mod 26 = -19, pero entonces usted le suma 26 para lograr un resultado positivo y obtiene -45 mod 26 = -19 + 26 = 7.
Estudiante: Así que la respuesta final es 2 7 0 8 17, que nos indica CHAIR, ¡qué bien!