El cifrado César en Java

1. Información general

En este tutorial, exploraremos el cifrado Caesar, un método de cifrado que cambia las letras de un mensaje para producir otro, menos legible.

En primer lugar, repasaremos el método de cifrado y veremos cómo implementarlo en Java.

Luego, veremos cómo descifrar un mensaje cifrado, siempre que sepamos el desplazamiento utilizado para cifrarlo.

Y finalmente, aprenderemos cómo romper dicho cifrado y así recuperar el mensaje original del cifrado sin conocer el desplazamiento utilizado.

2. Cifrado César

2.1. Explicación

En primer lugar, definamos qué es un cifrado. Un cifrado es un método para cifrar un mensaje, con la intención de hacerlo menos legible. En cuanto al cifrado César, es un cifrado de sustitución que transforma un mensaje cambiando sus letras por un desplazamiento determinado.

Digamos que queremos cambiar el alfabeto en 3, luego la letra A se transformaría en la letra D , la B en la E , la C en la F , y así sucesivamente.

Aquí está la coincidencia completa entre las letras originales y transformadas para un desplazamiento de 3:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Como vemos, una vez que la transformación va más allá de la letra Z , volvemos al inicio del alfabeto, de modo que X , Y y Z se transforman en A , B y C , respectivamente.

Por lo tanto, si elegimos un desplazamiento mayor o igual a 26, recorreremos, al menos una vez, todo el alfabeto. Imaginemos que cambiamos un mensaje en 28, eso realmente significa que lo estamos cambiando en 2. De hecho, después de cambiar en 26, todas las letras coinciden.

Realmente, podemos transformar cualquier desplazamiento en un desplazamiento más simple realizando una operación módulo 26 en él :

offset = offset % 26

2.2. Algoritmo en Java

Ahora, veamos cómo implementar el cifrado Caesar en Java.

Primero, creemos una clase CaesarCipher que contendrá un método cipher () tomando un mensaje y un desplazamiento como parámetros:

public class CaesarCipher { String cipher(String message, int offset) {} }

Ese método cifrará el mensaje utilizando el cifrado Caesar.

Supondremos aquí que las compensaciones son positivas y los mensajes solo contienen letras minúsculas y espacios. Entonces, lo que queremos es cambiar todos los caracteres alfabéticos por el desplazamiento dado:

StringBuilder result = new StringBuilder(); for (char character : message.toCharArray()) { if (character != ' ') { int originalAlphabetPosition = character - 'a'; int newAlphabetPosition = (originalAlphabetPosition + offset) % 26; char newCharacter = (char) ('a' + newAlphabetPosition); result.append(newCharacter); } else { result.append(character); } } return result;

Como podemos ver, nos basamos en los códigos ASCII de las letras del alfabeto para lograr nuestro objetivo .

En primer lugar, se calcula la posición de la letra en el alfabeto actual, y para ello, tomamos su código ASCII y restamos el código ASCII de la letra de una de ella. Luego aplicamos el desplazamiento a esta posición, usando cuidadosamente el módulo para permanecer en el rango del alfabeto. Y finalmente, recuperamos el nuevo carácter agregando la nueva posición al código ASCII de la letra a .

Ahora, probemos esta implementación en el mensaje "me dijo que nunca podría enseñar a conducir a una llama" con un desplazamiento de 3:

CaesarCipher cipher = new CaesarCipher(); String cipheredMessage = cipher.cipher("he told me i could never teach a llama to drive", 3); assertThat(cipheredMessage) .isEqualTo("kh wrog ph l frxog qhyhu whdfk d oodpd wr gulyh");

Como podemos ver, el mensaje cifrado respeta la coincidencia definida anteriormente para un desplazamiento de 3.

Ahora bien, este ejemplo en particular tiene la especificidad de no exceder la letra z durante la transformación, por lo tanto no tener que volver al inicio del alfabeto. Por lo tanto, intentemos de nuevo con un desplazamiento de 10 para que algunas letras se asignen a letras al comienzo del alfabeto, como t, que se asignará a d :

String cipheredMessage = cipher.cipher("he told me i could never teach a llama to drive", 10); assertThat(cipheredMessage) .isEqualTo("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo");

Funciona como se esperaba, gracias al funcionamiento del módulo. Esa operación también se encarga de compensaciones más grandes. Digamos que queremos usar 36 como compensación, que es equivalente a 10, la operación de módulo asegura que la transformación dará el mismo resultado.

3. Descifrar

3.1. Explicación

Ahora, veamos cómo descifrar un mensaje de este tipo cuando conocemos el desplazamiento utilizado para cifrarlo.

De hecho, descifrar un mensaje cifrado con cifrado César puede verse como cifrarlo con un desplazamiento negativo, o también cifrarlo con un desplazamiento complementario .

Entonces, digamos que tenemos un mensaje cifrado con un desplazamiento de 3. Luego, podemos cifrarlo con un desplazamiento de -3 o cifrarlo con un desplazamiento de 23. De cualquier manera, recuperamos el mensaje original.

Desafortunadamente, nuestro algoritmo no maneja el desplazamiento negativo de fábrica. Tendremos problemas para convertir letras en bucle hasta el final del alfabeto (por ejemplo, transformar la letra a en la letra z con un desplazamiento de -1). Pero podemos calcular el desplazamiento complementario, que es positivo, y luego usar nuestro algoritmo.

Entonces, ¿cómo obtener esta compensación complementaria? La forma ingenua de hacer esto sería restar la compensación original de 26. Por supuesto, esto funcionará para compensaciones entre 0 y 26, pero de lo contrario dará resultados negativos.

Ahí es donde haremos uso del operador de módulo nuevamente, directamente en el desplazamiento original, antes de hacer la resta . De esa forma, nos aseguramos de devolver siempre una compensación positiva.

3.2. Algoritmo en Java

Implementémoslo ahora en Java. Primero, agregaremos un método decipher () a nuestra clase:

String decipher(String message, int offset) {}

Luego, llamemos al método cipher () con nuestro desplazamiento complementario calculado:

return cipher(message, 26 - (offset % 26));

Eso es todo, nuestro algoritmo de descifrado está configurado. Probémoslo en el ejemplo con offset 36:

String decipheredSentence = cipher.decipher("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", 36); assertThat(decipheredSentence) .isEqualTo("he told me i could never teach a llama to drive");

Como podemos ver, recuperamos nuestro mensaje original.

4. Breaking the Ceasar Cipher

4.1. Explanation

Now that we've covered ciphering and deciphering messages using the Caesar cipher, we can dive into how to break it. That is, decipher a ciphered message without knowing the used offset at first.

To do that, we'll make use of the probabilities to find English letters in a text. The idea will be to decipher the message using offsets 0 to 25 and check what shift presents a letter distribution similar to that of English texts.

In order to determine the similarity of two distributions, we'll use the Chi-squared statistic.

The Chi-squared statistic will provide a number telling us whether two distributions are similar or not. The smaller the number, the more similar they are.

So, we'll compute the Chi-square for every offset and then return the one with the smallest Chi-square. This should give us the offset used to cipher the message.

However, we must keep in mind that this technique is not bulletproof and should the message be too short or using words unfortunately non-representative of a standard English text, it could return a wrong offset.

4.2. Define the Base Letters Distribution

Let's now see how to implement the breaking algorithm in Java.

First of all, let's create a breakCipher() method in our CaesarCipher class, which will return the offset used to encrypt a message:

int breakCipher(String message) {}

Then, let's define an array containing the probabilities to find a certain letter in an English text:

double[] englishLettersProbabilities = {0.073, 0.009, 0.030, 0.044, 0.130, 0.028, 0.016, 0.035, 0.074, 0.002, 0.003, 0.035, 0.025, 0.078, 0.074, 0.027, 0.003, 0.077, 0.063, 0.093, 0.027, 0.013, 0.016, 0.005, 0.019, 0.001};

From this array, we'll be able to calculate the expected frequencies of the letters in a given message, by multiplying the probabilities by the length of the message:

double[] expectedLettersFrequencies = Arrays.stream(englishLettersProbabilities) .map(probability -> probability * message.getLength()) .toArray();

For example, in a message of length 100, we should expect the letter a to appear 7.3 times, and the letter e to appear 13 times.

4.3. Calculate the Chi-squares

Now, we're going to calculate the Chi-squares of deciphered message letters distribution and standard English letters distribution.

To achieve that, we'll need to import the Apache Commons Math3 library that contains a utility class to compute Chi-squares:

 org.apache.commons commons-math3 3.6.1 

What we need to do now is to create an array that'll contain the calculated Chi-squares for each offset between 0 and 25.

Thus, we'll decipher the encrypted message using each offset, and then count the letters in that message.

Finally, we'll use the ChiSquareTest#chiSquare method to calculate the Chi-square between the expected and observed letters distribution:

double[] chiSquares = new double[26]; for (int offset = 0; offset < chiSquares.length; offset++) { String decipheredMessage = decipher(message, offset); long[] lettersFrequencies = observedLettersFrequencies(decipheredMessage); double chiSquare = new ChiSquareTest().chiSquare(expectedLettersFrequencies, lettersFrequencies); chiSquares[offset] = chiSquare; } return chiSquares;

The observedLettersFrequencies() method simply realizes a count of letters a to z in the passed message:

long[] observedLettersFrequencies(String message) { return IntStream.rangeClosed('a', 'z') .mapToLong(letter -> countLetter((char) letter, message)) .toArray(); } long countLetter(char letter, String message) { return message.chars() .filter(character -> character == letter) .count(); }

4.4. Find the Most Probable Offset

Once all the Chi-squares calculated, we can return the offset matching the smallest Chi-square:

int probableOffset = 0; for (int offset = 0; offset < chiSquares.length; offset++) { System.out.println(String.format("Chi-Square for offset %d: %.2f", offset, chiSquares[offset])); if (chiSquares[offset] < chiSquares[probableOffset]) { probableOffset = offset; } } return probableOffset;

Although it's not necessary to enter the loop with offset 0 as we consider it to be the minimum before starting the loop, we do it to print its Chi-square value.

Let's try this algorithm on the message encrypted using offset 10:

int offset = algorithm.breakCipher("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo"); assertThat(offset).isEqualTo(10); assertThat(algorithm.decipher("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", offset)) .isEqualTo("he told me i could never teach a llama to drive");

Como podemos ver, el método recupera el desplazamiento correcto, que luego se puede usar para descifrar el mensaje y recuperar el original.

Aquí están los diferentes Chi-cuadrados calculados para esta ruptura en particular:

Chi-Square for offset 0: 210.69 Chi-Square for offset 1: 327.65 Chi-Square for offset 2: 255.22 Chi-Square for offset 3: 187.12 Chi-Square for offset 4: 734.16 Chi-Square for offset 5: 673.68 Chi-Square for offset 6: 223.35 Chi-Square for offset 7: 111.13 Chi-Square for offset 8: 270.11 Chi-Square for offset 9: 153.26 Chi-Square for offset 10: 23.74 Chi-Square for offset 11: 643.14 Chi-Square for offset 12: 328.83 Chi-Square for offset 13: 434.19 Chi-Square for offset 14: 384.80 Chi-Square for offset 15: 1206.47 Chi-Square for offset 16: 138.08 Chi-Square for offset 17: 262.66 Chi-Square for offset 18: 253.28 Chi-Square for offset 19: 280.83 Chi-Square for offset 20: 365.77 Chi-Square for offset 21: 107.08 Chi-Square for offset 22: 548.81 Chi-Square for offset 23: 255.12 Chi-Square for offset 24: 458.72 Chi-Square for offset 25: 325.45

Como podemos ver, el del desplazamiento 10 es claramente más pequeño que los demás.

5. Conclusión

En este artículo, cubrimos el cifrado César. Aprendimos a cifrar y descifrar un mensaje cambiando sus letras por un desplazamiento determinado. También aprendimos cómo descifrar el cifrado. Y vimos todas las implementaciones de Java que nos permiten hacer eso.

El código de este artículo se puede encontrar en GitHub.