Le chiffre César en Java

1. Vue d'ensemble

Dans ce tutoriel, nous allons explorer le chiffrement César, une méthode de chiffrement qui décale les lettres d'un message pour en produire un autre, moins lisible.

Tout d'abord, nous allons passer en revue la méthode de chiffrement et voir comment l'implémenter en Java.

Ensuite, nous verrons comment déchiffrer un message chiffré, à condition de connaître le décalage utilisé pour le chiffrer.

Et enfin, nous apprendrons comment casser un tel chiffrement et ainsi récupérer le message d'origine du message chiffré sans connaître le décalage utilisé.

2. Chiffre César

2.1. Explication

Tout d'abord, définissons ce qu'est un chiffre. Un chiffrement est une méthode de chiffrement d'un message, visant à le rendre moins lisible. Quant au chiffre César, c'est un chiffre de substitution qui transforme un message en décalant ses lettres d'un décalage donné.

Disons que nous voulons décaler l'alphabet de 3, puis la lettre A serait transformée en lettre D , B en E , C en F , et ainsi de suite.

Voici la correspondance complète entre les lettres originales et transformées pour un décalage 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

Comme on peut le voir, une fois que la transformation dépasse la lettre Z , on retourne au début de l'alphabet, de sorte que X , Y et Z se transforment en A , B et C , respectivement.

Par conséquent, si nous choisissons un décalage supérieur ou égal à 26, nous bouclons, au moins une fois, sur tout l'alphabet. Imaginons que nous décalions un message de 28, cela signifie vraiment que nous le décalons de 2. En effet, après avoir décalé de 26, toutes les lettres se correspondent.

Vraiment, nous pouvons transformer n'importe quel offset en un offset plus simple en effectuant une opération modulo 26 dessus :

offset = offset % 26

2.2. Algorithme en Java

Voyons maintenant comment implémenter le chiffrement Caesar en Java.

Tout d'abord, créons une classe CaesarCipher qui contiendra une méthode cipher () prenant un message et un offset comme paramètres:

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

Cette méthode cryptera le message en utilisant le chiffrement César.

Nous supposerons ici que les décalages sont positifs et que les messages ne contiennent que des lettres minuscules et des espaces. Ensuite, ce que nous voulons, c'est décaler tous les caractères alphabétiques par le décalage donné:

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;

Comme nous pouvons le voir, nous nous appuyons sur les codes ASCII des lettres de l'alphabet pour atteindre notre objectif .

Tout d'abord, nous calculons la position de la lettre courante dans l'alphabet, et pour cela, nous prenons son code ASCII et en soustrayons le code ASCII de la lettre a . Ensuite, nous appliquons le décalage à cette position, en utilisant soigneusement le modulo pour rester dans la plage de l'alphabet. Et enfin, on récupère le nouveau caractère en ajoutant la nouvelle position au code ASCII de la lettre a .

Maintenant, essayons cette implémentation sur le message "il m'a dit que je ne pourrais jamais apprendre à conduire à un lama" avec un décalage 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");

Comme on peut le voir, le message chiffré respecte la correspondance définie précédemment pour un décalage de 3.

Or, cet exemple particulier a la particularité de ne pas dépasser la lettre z lors de la transformation, donc de ne pas avoir à remonter au début de l'alphabet. Donc, essayons à nouveau avec un décalage de 10 pour que certaines lettres soient mappées sur des lettres au début de l'alphabet, comme t qui sera mappé sur 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");

Il fonctionne comme prévu, grâce à l'opération modulo. Cette opération prend également en charge les décalages plus importants. Disons que nous voulons utiliser 36 comme offset, ce qui équivaut à 10, l'opération modulo garantit que la transformation donnera le même résultat.

3. Déchiffrer

3.1. Explication

Voyons maintenant comment déchiffrer un tel message quand on connaît le décalage utilisé pour le chiffrer.

En effet, déchiffrer un message chiffré avec le chiffrement César peut être vu comme le chiffrer avec un offset négatif, ou aussi le chiffrer avec un offset complémentaire .

Donc, disons que nous avons un message chiffré avec un offset de 3. Ensuite, nous pouvons soit le chiffrer avec un offset de -3, soit le chiffrer avec un offset de 23. Dans tous les cas, nous récupérons le message d'origine.

Malheureusement, notre algorithme ne gère pas immédiatement le décalage négatif. Nous aurons des problèmes pour convertir les lettres en boucle vers la fin de l'alphabet (par exemple, transformer la lettre a en lettre z avec un décalage de -1). Mais, nous pouvons calculer le décalage complémentaire, qui est positif, puis utiliser notre algorithme.

Alors, comment obtenir cet offset complémentaire? La façon naïve de faire cela serait de soustraire le décalage d'origine de 26. Bien sûr, cela fonctionnera pour les décalages entre 0 et 26 mais donnera des résultats négatifs dans le cas contraire.

C'est là que nous utiliserons à nouveau l'opérateur modulo, directement sur le décalage d'origine, avant de faire la soustraction . De cette façon, nous nous assurons de toujours renvoyer un offset positif.

3.2. Algorithme en Java

Implémentons-le maintenant en Java. Tout d'abord, nous allons ajouter une méthode decipher () à notre classe:

String decipher(String message, int offset) {}

Ensuite, appelons la méthode cipher () avec notre offset complémentaire calculé:

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

Voilà, notre algorithme de déchiffrement est mis en place. Essayons-le sur l'exemple avec l'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");

Comme nous pouvons le voir, nous récupérons notre message d'origine.

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");

Comme nous pouvons le voir, la méthode récupère le décalage correct, qui peut ensuite être utilisé pour déchiffrer le message et récupérer l'original.

Voici les différents Chi-carrés calculés pour cette cassure particulière:

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

Comme on peut le voir, celui du décalage 10 est nettement plus petit que les autres.

5. Conclusion

Dans cet article, nous avons couvert le chiffre de César. Nous avons appris à chiffrer et déchiffrer un message en décalant ses lettres d'un décalage donné. Nous avons également appris à casser le chiffre. Et nous avons vu toutes les implémentations Java qui nous permettent de le faire.

Le code de cet article se trouve à l'adresse over sur GitHub.