Estructuras de repetición - Cifrado Vigenere

Una de las ventajas de utilizar programas de computadoras es que podemos realizar tareas repetitivas fácilmente. Los ciclos como for, while, y do-while son estructuras de control que nos permiten repetir un conjunto de instrucciones. A estas estructuras también se les llama estructuras de repetición. En la experiencia de laboratorio de hoy utilizarás ciclos for para completar una aplicación de cifrado.

Objetivos:

1. Aplicar estructuras de repetición para cifrar un mensaje.
2. Practicar operaciones aritméticas con caracteres.

Pre-Lab:

Antes de llegar al laboratorio debes haber:

1. Repasado los conceptos básicos relacionados a estructuras de repetición.

2. Repasado conceptos básicos de la clase string de C++, las funciones length, toupper y push_back, isalpha y las operaciones aritméticas con caracteres.

3. Visto el video sobre el "Ceasar Cypher" del Khan Academy, colocado en https://www.youtube.com/watch?v=sMOZf4GN3oc.

4. Visto el video sobre el "Vigenere Cypher", colocado en https://www.youtube.com/watch?v=9zASwVoshiM.

5. Estudiado los conceptos e instrucciones para la sesión de laboratorio.

6. Tomado el quiz Pre-Lab, disponible en Moodle.

Criptografía

La criptografía es un área que estudia la teoría y los métodos utilizados para proteger información de modo que personas que no estén autorizadas no puedan tener acceso a ella. Un sistema criptográfico es un sistema en el que la información (mensaje entendible por humanos) es transformada a un texto cifrado inentendible para las personas no autorizadas a verlo. Las personas autorizadas a ver el mensaje usan un descifrador para revertir el texto cifrado al mensaje original.

El Cifrado César (Ceasar Cypher)

El Cifrado César es una técnica muy simple de cifrado por sustitución. Se dice que el sistema se basa en el sistema utilizado por Julio César, líder militar y político de Roma en años antes de Cristo, para comunicarse con sus generales. La técnica cifra un mensaje de texto sustituyendo cada letra del mensaje por la letra que se encuentra a un número dado de posiciones más adelante en el alfabeto. Esto puede pensarse como un desplazamiento ("shift") del alfabeto. El diagrama de la Figura 1 representa un desplazamiento de 3 espacios. La letra ‘B’ es sustituida por la letra ‘E’.

Figura 1. Cifrado César con desplazamiento de 3 espacios.

Ejemplo 1: Con un desplazamiento de 3 espacios, la palabra "ARROZ" quedaría cifrada como "DUURC". Nota que, con este desplazamiento de 3 espacios, la letra ‘Z’ es sustituida por la letra ‘C’. Cuando el desplazamiento se pasa de la letra ‘Z’ comenzamos nuevamente en la letra ‘A’. Esto se llama un desplazamiento cíclico. La Figura 2 muestra un desplazamiento cíclico de 8 espacios.

Figura 2. Disco para cifrado César que muestra un desplazamiento de 8 espacios.

Utilizando el operador módulo

La operación de suma modular es esencial para implementar sistemas de cifrado en programación. En la aplicación de cifrado César de arriba podemos pensar que a cada letra del alfabeto (en inglés) le asignamos un número entre 0 y 25 (La A es 0, laB es 1, …, la Z es 25). El cifrado César convierte cada letra al número correspondiente en el intervalo [0, 25] y luego suma el desplazamiento. Para hacer el desplazamiento cíclico, cada vez que nuestro desplazamiento nos dé una letra que corresponda a un número mayor que 25, tomamos el residuo al dividir por 26 y usamos la letra que corresponda a ese residuo. Nota que tomar el residuo al dividir por 26 los resultados estarán entre 0 y 25, que son los valores asociados al alfabeto.

El residuo al dividir dos números enteros se puede obtener utilizando el operador de módulo: %.

Volviendo al Ejemplo 1, en la palabra "ARROZ", a la letra ‘Z’ le corresponde el número 25; al hacer un desplazamiento de 3 espacios, sumamos 3 a 25 y esto nos resulta en 28 que es un número mayor que 25. Si tomamos el residuo al dividir $25 + 3$ por 26, (25 + 3) % 26, obtenemos 2, que corresponde a la letra ‘C’.

El proceso de arriba funciona si podemos asociar las letras de la ‘A’ a la ‘Z’ con los números del 0 al 25. Esto se logra utilizando el valor numérico de los caracteres. Como en el código ASCII el valor de las letras ‘A’ a la ‘Z’ va desde 65 hasta 90, necesitamos hacer un ajuste en el cómputo de modo que a la A se le asigne 0. Para convertir una letra mayúscula a un número en el intervalo [0, 25] solo tenemos que restar 65 (’A’ - 65 = 0, ’Z’ - 65 = 25). Para cambiar un valor en el intervalo [0, 25] a la letra mayúscula que corresponde en el código ASCII solo tenemos que sumar 65 al número. Por ejemplo, el número 3 corresponde a la letra cuyo código ASCII es $3 + 65 = 68$, la letra ‘D’.

La Figura 3 muestra el pseudocódigo para una algoritmo para el cifrado César. Cada letra ‘c’ en el mensaje se convierte a un número en el intervalo [0, 25] (restándole ‘A’), luego se hace el desplazamiento de d unidades al número (sumando d módulo 26). Finalmente se convierte el resultado al carácter correspondiente sumando el código ASCII de ‘A’.

    Datos de entrada: un "string" de mensaje, la cantidad de desplazamiento `d` 
    Datos de salida: el mensaje cifrado usando cifrado César 

    1. cypheredText = ""
    2. para ("for") cada caracter c en ("in") el mensaje:
           c = ascii(c) - ascii('A')  # mueve c del intervalo [A,Z] al [0,25]
           c = ( c + d ) % 26         # desplaza (cíclicamente) c por d unidades
           c = ascii(c) + ascii('A')  # mueve c del intervalo [0,25] al [A,Z]
           cypheredText.append(c) 
    3. devuelve ("return") cypheredText 

Figura 3. Pseudo-código para cifrar utilizando un cifrado César.

El cifrado César no es muy seguro ya que puede descifrarse fácilmente con un análisis de frecuencia. Por ejemplo, se sabe que en el idioma inglés la letra ‘e’ es la letra más frecuente en un texto. Si buscamos la letra que más se repite en un texto cifrado con un cifrado César, lo más probable es que esa fue la letra que se sustituyó por la ‘e’; con esto podemos deducir cuál fue el desplazamiento utilizado y así descifrar el mensaje.

El Cifrado Vigenere

La debilidad principal del cifrado César es que cada letra en el mensaje se desplaza por el mismo número de posiciones. El cifrado Vigenere es un método de cifrado un poco más fuerte porque el desplazamiento en cada letra no es constante. El cifrado César recibe como datos de entrada el mensaje y un desplazamiento, mientras que el cifrado Vigenere recibe como dato de entrada el mensaje y una clave que determina el desplazamiento que se le hará a cada letra del mensaje.

Ejemplo 2. Supongamos por el momento que tanto el mensaje como la clave tienen el mismo largo. Por ejemplo, suponga que el mensaje es "COSAS" y la palabra clave es "MENOR". La letra ‘C’ se parea con la letra ‘M’, la letra ‘O’ se parea con la letra ‘E’, la ‘S’ con la ‘N’, etcétera, como en la figura de abajo. Como la letra ‘A’ corresponde a un desplazamiento de 0 espacios, entonces la letra ‘M’ corresponde a un desplazamiento de 12 espacios, la ‘E’ a un desplazamiento de 4 espacios, etc. Utilizando la palabra clave "MENOR", el cifrado Vigenere hará un desplazamiento de 12 espacios a la letra ‘C’, un desplazamiento de 4 espacios a la letra ‘O’, etc., hasta obtener la palabra cifrada "OSFOJ" como se muestra en la Figura 4.

Figura 4. Alineamiento del mensaje con la palabra clave y cifrado.

Podemos visualizar un cifrado Vigenere utilizando una tabla como la de la Figura 5. Nota que lo que se hace es usar un cifrado César con un desplazamiento diferente para cada letra del mensaje.

Figura 5. Tabla para el cifrado Vigenere.

Si la palabra clave es más corta que el mensaje, entonces repetimos la palabra clave tantas veces como haga falta, pareando letras del mensaje con letras de la palabra clave como se hace en la Figura 6.

Figura 6. Alineamiento del mensaje con la palabra clave y cifrado.

Funciones que se utilizarán en esta experiencia de laboratorio:

El programa que estarás modificando en la sesión de hoy utiliza los siguientes métodos de la clase string:

• length: Devuelve el largo de un objeto de la clase string; esto es, length devuelve el número de caracteres que tiene el "string". Se utiliza escribiendo .length() después del nombre del objeto.

• push_back: Este método recibe un carácter como argumento y lo añade al final del “string”. Se utiliza escribiendo .push_back(elCaracter) después del nombre del “string”. Por ejemplo, para añadir el carácter 'a' a un objeto de la clase string llamado cadena, escribimos cadena.push_back('a').

También utilizaremos las funciones:

• toupper: Esta función recibe como argumento un carácter y devuelve el caracter en mayúscula. Por ejemplo, para cambiar el carácter 'a' a mayúscula se utiliza toupper('a').

• isalpha: Esta función recibe como argumento un carácter y devuelve un valor distinto de cero (true) si el carácter es una letra y cero (false) si el carácter no es una letra. Por ejemplo, isalpha(3) devuelve false pero isalpha(‘F’) devuelve true.

Supón que tenemos dos objetos de clase string, stOne y stTwo con todos sus caracteres en minúscula. ¿Cuál de los siguientes códigos verifica que ambos strings tienen el mismo largo, y luego los cambia a mayúscula? La primera opción es incorrecta pues compara el contenido de los strings en vez de sus largos.

La segunda opción es la correcta, ya que compara el largo de stOne y stTwo, y entra al for loop. Nota que la condición de repetición del for loop es i < stOne.length(), genera los enteros desde 0 hasta el largo de los strings menos uno. Ya que nos aseguramos que stOne y stTwo tienen el mismo largo, no importa cual de los dos largos se utiliza en la condición. Al recorrer el string, accesamos cada caracter individual usando [i], y lo guardamos nuevamente en la misma posición del string utilizando [i] nuevamente, alterando el string original.

La tercera opción es incorrecta pues compara el contenido de los strings en vez de sus largos Además, el código dentro del if no funciona ya que se utiliza toupper() incorrectamente. La función toupper debe recibir como argumento un caracter, no un string.

La cuarta opción es incorrecta ya que no realiza el cambio a mayúscula correctamente dentro del for loop. Nota que toupper() es invocado con cada caracter, lo cual está correcto, pero no se guarda el cambio asignándoselo a la posición correspondiente de cada string. Si imprimimos stOne y stTwo luego, estarán iguales.

¿Cuál es la frase cifrada en Vigenere de la palabra SEASALTFELT usando la clave XANFNVJRWYJ? PENXNGCWAJC QZNANLVOWLC JMJAELQITLA AQDHDKSUDSX La primera opción es la correcta. Si la A representa un desplazamiento de 0 espacios, podemos obtener el desplazamiento de todos los demás. La X representa un desplazamiento de 23 espacios y por lo tanto (S + 23) % 26 es P (recuerda que el rango es de 0-25 ya que es módulo 26), la A representa 0 espacios y por lo tanto (E + 0) % 26 es E, la N desplaza la A 13 espacios, etc. Cuando se realizan las calculaciones, se encuentra que el mensaje cifrado es PENXNGCWAJC.

¿Qué resulta al ejecutar el siguiente código?
Despliega pizzapizza Nada, no corre porque hay un error. Despliega pizzaAZZIP Despliega pizzaPIZZA La respuesta correcta es la tercera (pizzaAZZIP). En el código, la variable length representa el largo del string stUp, que es 5. El for loop recorre el string al revés. La i comienza con el valor de length - 1 ya que queremos comenzar en la última posición del string. Recuerda que las posiciones de un string, al igual que las de un arreglo, comienzan en 0 y van hasta length - 1. La i va decreciendo en cada iteración, comenzando en 4, luego 3, luego 2, etc. La instrucción stUp.push_back(toupper(stUp[i])); logra añadir al final del string stUp los caracteres del string en mayúscula, pero al revés. Por esto, con cada iteración se añade una letra adicional y se termina con pizzaAZZIP.

Sesión de laboratorio:

En esta experiencia de laboratorio, completarás una aplicación para cifrar un mensaje de texto utilizando el cifrado Vigenere. Para simplificar el código, la clave y el mensaje deben consistir sólo de letras y tu programa debe cambiar todas las letras del mensaje y la clave a mayúsculas.

Ejercicio 1 - Cifrado con clave y mensaje del mismo largo (solo letras)

En este ejercicio completarás la aplicación para cifrar un mensaje de texto, que solo contiene letras, utilizando una palabra clave que también consiste solo de letras y que tiene el mismo largo del mensaje.

Instrucciones:

1. Carga a QtCreator el proyecto VigenereCypher. Hay dos maneras de hacer esto:

   • Utilizando la máquina virtual: Haz doble “click” en el archivo VigenereCypher.pro que se encuentra en el directorio /home/eip/labs/repetitions-vigenerecypher de la máquina virtual.
   • Descargando la carpeta del proyecto de Bitbucket: Utiliza un terminal y escribe el commando git clone http:/bitbucket.org/eip-uprrp/repetitions-vigenerecypher para descargar la carpeta repetitions-vigenerecypher de Bitbucket. En esa carpeta, haz doble “click” en el archivo VigenereCypher.pro.

2. Estarás añadiendo código en el archivo cypher.cpp. En este archivo, la función cypher recibe un mensaje y una clave del mismo largo que consisten sólo de letras, y devuelve el mensaje cifrado por el cifrado Vigenere. Tu tarea es completar la función de cifrado.

   El código debe verificar si el mensaje y la clave consisten solo de letras y tienen el mismo largo; si esto no ocurre, el mensaje cifrado será (literalmente) "MENSAJE O CLAVE INVÁLIDA". El programa debe implementar el cifrado Vigenere para ir cifrando cada letra del mensaje utilizando la clave. Solo debes utilizar las funciones mencionadas en la sección anterior. Para simplificar el código tu programa debe cambiar todas las letras del mensaje y la clave a mayúsculas.

3. Al terminar tu código, ve a la función main y descomenta la invocación a la función de prueba unitaria test_cypher1. Esta función realiza varias invocaciones a la función cypher para validar si sus resultados son correctos. Tu función cypher debe pasar todas las pruebas antes de continuar con la próxima parte de este laboratorio.

Ejercicio 2 - Cifrado con clave y mensaje de largos arbitrarios

En este ejercicio modificarás el código de la función cypher que creaste para el Ejercicio 1 de modo que la aplicación ahora puede cifrar cualquier mensaje utilizando una palabra clave que consista sólo de letras pero que tenga cualquier largo.

Instrucciones:

1. Escribe el código de la función cypher para que reciba un mensaje y una clave y devuelva el mensaje cifrado por el cifrado Vigenere. En esta ocasión, el mensaje y la clave pueden tener cualquier largo y el mensaje puede tener cualquier carácter (la clave solo puede tener letras).

   El programa debe implementar el cifrado Vigenere para ir cifrando cada carácter del mensaje utilizando las letras de la clave. Para simplificar el código, tu programa debe cambiar todas las letras a mayúsculas. Si alguno de los caracteres del mensaje no es una letra, el cifrador no lo cambia, como se muestra en la Figura 7. Si alguno de los caracteres de la clave no es una letra, el mensaje cifrado será "CLAVE INVALIDA". Solo debes utilizar las funciones mencionadas en la sección anterior.

   ---

   mensaje	A	L	&	U	N	A	$		C	O	S	A	S
   clave	M	E	N	O	R	M	E	N	O	R	M	E	N
   mensaje cifrado	M	P	&	I	E	M	$		Q	F	E	E	F

 **Figura 7.** Ejemplo de mensaje y clave con largo distinto y símbolos en el mensaje.

 ---

1. Al terminar tu código, ve a la función main, comenta la invocación a la función de prueba unitaria test_cypher1 y descomenta la invocación a la función de prueba unitaria test_cypher2 para que verifiques tu programa.

Entrega

Utiliza "Entrega" en Moodle para entregar el archivo cypher.cpp que contiene la función cypher que creaste en el Ejercicio 2. Recuerda utilizar buenas prácticas de programación, incluye el nombre de los programadores y documenta tu programa.

Referencias

http://www.nctm.org/uploadedImages/Classroom_Resources/Lesson_Plans/