Il Caesar Cipher in Java

1. Panoramica

In questo tutorial, esploreremo il codice Caesar, un metodo di crittografia che sposta le lettere di un messaggio per produrne un altro, meno leggibile.

Prima di tutto, esamineremo il metodo di cifratura e vedremo come implementarlo in Java.

Quindi, vedremo come decifrare un messaggio crittografato, a condizione che conosciamo l'offset utilizzato per crittografarlo.

E infine, impareremo come rompere un tale codice e quindi recuperare il messaggio originale da quello crittografato senza conoscere l'offset utilizzato.

2. Caesar Cipher

2.1. Spiegazione

Prima di tutto, definiamo cos'è un cifrario. Un cifrario è un metodo per crittografare un messaggio, con l'intento di renderlo meno leggibile. Per quanto riguarda il codice Caesar, è un codice di sostituzione che trasforma un messaggio spostando le sue lettere di un dato offset.

Supponiamo di voler spostare l'alfabeto di 3, quindi la lettera A verrebbe trasformata in D , B in E , C in F e così via.

Ecco la corrispondenza completa tra lettere originali e trasformate per un offset di 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

Come possiamo vedere, una volta che la trasformazione va oltre la lettera Z , si ritorna all'inizio dell'alfabeto, in modo che X , Y e Z vengono trasformati in A , B e C , rispettivamente.

Pertanto, se scegliamo un offset maggiore o uguale a 26, eseguiamo un ciclo, almeno una volta, sull'intero alfabeto. Immaginiamo di spostare un messaggio di 28, il che significa in realtà che lo stiamo spostando di 2. In effetti, dopo lo spostamento di 26, tutte le lettere corrispondono.

In realtà, possiamo trasformare qualsiasi offset in un offset più semplice eseguendo un'operazione modulo 26 su di esso :

offset = offset % 26

2.2. Algoritmo in Java

Vediamo ora come implementare il cifrario Caesar in Java.

Per prima cosa, creiamo una classe CaesarCipher che conterrà un metodo cipher () che accetta un messaggio e un offset come parametri:

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

Questo metodo crittograferà il messaggio utilizzando la cifratura Caesar.

Supponiamo qui che gli offset siano positivi e che i messaggi contengano solo lettere minuscole e spazi. Quindi, quello che vogliamo è spostare tutti i caratteri alfabetici per l'offset dato:

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;

Come possiamo vedere, ci affidiamo ai codici ASCII delle lettere dell'alfabeto per raggiungere il nostro obiettivo .

Per prima cosa, calcoliamo la posizione della lettera corrente nell'alfabeto, e per questo, prendiamo il suo codice ASCII e sottraiamo il codice ASCII della lettera a da esso. Quindi applichiamo l'offset a questa posizione, utilizzando attentamente il modulo per rimanere nell'intervallo alfabetico. E infine, recuperiamo il nuovo carattere aggiungendo la nuova posizione al codice ASCII della lettera a .

Ora, proviamo questa implementazione sul messaggio "mi ha detto che non avrei mai potuto insegnare a guidare a un lama" con un offset di 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");

Come possiamo vedere, il messaggio cifrato rispetta la corrispondenza definita in precedenza per un offset di 3.

Ora, questo particolare esempio ha la specificità di non superare la lettera z durante la trasformazione, non dovendo quindi tornare all'inizio dell'alfabeto. Quindi, riproviamo con un offset di 10 in modo che alcune lettere vengano mappate su lettere all'inizio dell'alfabeto, come t che verrà mappata su 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");

Funziona come previsto, grazie all'operazione modulo. Quell'operazione si occupa anche di offset maggiori. Supponiamo di voler utilizzare 36 come offset, che è equivalente a 10, l'operazione modulo garantisce che la trasformazione darà lo stesso risultato.

3. Decifrare

3.1. Spiegazione

Ora, vediamo come decifrare un messaggio del genere quando conosciamo l'offset utilizzato per crittografarlo.

As a matter of fact, deciphering a message encrypted with Caesar cipher can be seen as ciphering it with a negative offset, or also ciphering it with a complementary offset.

So, let's say we have a message encrypted with an offset of 3. Then, we can either encrypt it with an offset of -3 or encrypt it with an offset of 23. Either way, we retrieve the original message.

Unfortunately, our algorithm doesn't handle negative offset out of the box. We'll have problems converting letters looping back to the end of the alphabet (for example transforming the letter a into the letter z with an offset of -1). But, we can compute the complementary offset, which is positive, and then use our algorithm.

Allora, come ottenere questo offset complementare? Il modo ingenuo di farlo sarebbe quello di sottrarre l'offset originale da 26. Ovviamente, questo funzionerà per offset compresi tra 0 e 26, ma in caso contrario darà risultati negativi.

È qui che utilizzeremo nuovamente l'operatore modulo, direttamente sull'offset originale, prima di eseguire la sottrazione . In questo modo, ci assicuriamo di restituire sempre un offset positivo.

3.2. Algoritmo in Java

Ora implementiamolo in Java. Per prima cosa, aggiungeremo un metodo decipher () alla nostra classe:

String decipher(String message, int offset) {}

Quindi, chiamiamo il metodo cipher () con il nostro offset complementare calcolato:

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

Ecco fatto, il nostro algoritmo di decifrazione è impostato. Proviamolo nell'esempio 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");

Come possiamo vedere, recuperiamo il nostro messaggio originale.

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

Come possiamo vedere, il metodo recupera l'offset corretto, che può quindi essere utilizzato per decifrare il messaggio e recuperare quello originale.

Ecco i diversi Chi-quadrato calcolati per questa particolare interruzione:

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

Come possiamo vedere, quello per l'offset 10 è chiaramente più piccolo degli altri.

5. conclusione

In questo articolo, abbiamo trattato il codice di Cesare. Abbiamo imparato a cifrare e decifrare un messaggio spostando le sue lettere di un dato offset. Abbiamo anche imparato a rompere il codice. E abbiamo visto tutte le implementazioni Java che ci consentono di farlo.

Il codice di questo articolo può essere trovato su GitHub.