Die Caesar-Chiffre in Java

1. Übersicht

In diesem Tutorial werden wir die Caesar-Chiffre untersuchen, eine Verschlüsselungsmethode, mit der Buchstaben einer Nachricht verschoben werden, um eine andere, weniger lesbare zu erzeugen.

Zunächst werden wir die Verschlüsselungsmethode durchgehen und sehen, wie sie in Java implementiert wird.

Dann werden wir sehen, wie eine verschlüsselte Nachricht entschlüsselt wird, vorausgesetzt, wir kennen den Offset, der zum Verschlüsseln verwendet wird.

Und schließlich lernen wir, wie man eine solche Chiffre bricht und so die ursprüngliche Nachricht von der verschlüsselten abruft, ohne den verwendeten Offset zu kennen.

2. Caesar Chiffre

2.1. Erläuterung

Lassen Sie uns zunächst definieren, was eine Chiffre ist. Eine Verschlüsselung ist eine Methode zum Verschlüsseln einer Nachricht, um sie weniger lesbar zu machen. Die Caesar-Chiffre ist eine Substitutions-Chiffre, die eine Nachricht transformiert, indem ihre Buchstaben um einen bestimmten Versatz verschoben werden.

Angenommen, wir möchten das Alphabet um 3 verschieben, dann wird Buchstabe A in Buchstabe D , B nach E , C nach F usw. umgewandelt.

Hier ist die vollständige Übereinstimmung zwischen ursprünglichen und transformierten Buchstaben für einen Versatz von 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

Wie wir sehen können, kehren wir, sobald die Transformation über den Buchstaben Z hinausgeht , zum Anfang des Alphabets zurück, so dass X , Y und Z in A , B bzw. C transformiert werden .

Wenn wir also einen Versatz größer oder gleich 26 wählen, durchlaufen wir mindestens einmal eine Schleife über das gesamte Alphabet. Stellen wir uns vor, wir verschieben eine Nachricht um 28, das heißt wirklich, wir verschieben sie um 2. In der Tat stimmen nach der Verschiebung um 26 alle Buchstaben überein.

Wirklich, wir können jeden Versatz in einen einfacheren Versatz umwandeln, indem wir eine Modulo 26-Operation ausführen :

offset = offset % 26

2.2. Algorithmus in Java

Lassen Sie uns nun sehen, wie die Caesar-Verschlüsselung in Java implementiert wird.

Erstellen wir zunächst eine Klasse CaesarCipher , die eine cipher () -Methode enthält, die eine Nachricht und einen Offset als Parameter verwendet:

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

Diese Methode verschlüsselt die Nachricht mit der Caesar-Chiffre.

Wir nehmen hier an, dass Offsets positiv sind und Nachrichten nur Kleinbuchstaben und Leerzeichen enthalten. Dann wollen wir alle alphabetischen Zeichen um den angegebenen Versatz verschieben:

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;

Wie wir sehen können, verlassen wir uns auf die ASCII-Codes der Buchstaben, um unser Ziel zu erreichen .

Zuerst berechnen wir die Position des aktuellen Buchstabens im Alphabet und nehmen dafür den ASCII-Code und subtrahieren den ASCII-Code des Buchstabens a davon. Dann wenden wir den Versatz auf diese Position an und verwenden das Modulo vorsichtig, um im Alphabetbereich zu bleiben. Und schließlich rufen wir das neue Zeichen ab, indem wir die neue Position zum ASCII-Code von Buchstabe a hinzufügen .

Versuchen wir nun diese Implementierung mit der Meldung "Er sagte mir, ich könnte einem Lama niemals das Fahren beibringen" mit einem Versatz von 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");

Wie wir sehen können, berücksichtigt die verschlüsselte Nachricht die zuvor definierte Übereinstimmung für einen Versatz von 3.

Dieses spezielle Beispiel hat nun die Spezifität, den Buchstaben z während der Transformation nicht zu überschreiten , und muss daher nicht zum Anfang des Alphabets zurückkehren. Versuchen wir es also noch einmal mit einem Versatz von 10, damit einige Buchstaben den Buchstaben am Anfang des Alphabets zugeordnet werden, wie z. B. t, das d zugeordnet wird :

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

Dank der Modulo-Operation funktioniert es wie erwartet. Diese Operation kümmert sich auch um größere Offsets. Angenommen, wir möchten 36 als Offset verwenden, was 10 entspricht. Die Modulo-Operation stellt sicher, dass die Transformation das gleiche Ergebnis liefert.

3. Entschlüsseln

3.1. Erläuterung

Lassen Sie uns nun sehen, wie eine solche Nachricht entschlüsselt wird, wenn wir den Offset kennen, mit dem sie verschlüsselt wurde.

Tatsächlich kann das Entschlüsseln einer mit Caesar-Verschlüsselung verschlüsselten Nachricht als Verschlüsselung mit einem negativen Versatz oder auch als Verschlüsselung mit einem komplementären Versatz angesehen werden .

Nehmen wir also an, wir haben eine Nachricht mit einem Versatz von 3 verschlüsselt. Dann können wir sie entweder mit einem Versatz von -3 oder mit einem Versatz von 23 verschlüsseln. In beiden Fällen rufen wir die ursprüngliche Nachricht ab.

Leider verarbeitet unser Algorithmus den negativen Offset nicht sofort. Wir haben Probleme beim Konvertieren von Buchstaben, die bis zum Ende des Alphabets zurücklaufen (z. B. Umwandlung des Buchstabens a in den Buchstaben z mit einem Versatz von -1). Wir können jedoch den positiven Komplementärversatz berechnen und dann unseren Algorithmus verwenden.

Wie erhält man diesen komplementären Offset? Der naive Weg, dies zu tun, wäre, den ursprünglichen Versatz von 26 zu subtrahieren. Natürlich funktioniert dies für Versätze zwischen 0 und 26, führt aber ansonsten zu negativen Ergebnissen.

Dort verwenden wir den Modulo-Operator erneut direkt auf dem ursprünglichen Offset, bevor wir die Subtraktion durchführen . Auf diese Weise stellen wir sicher, dass immer ein positiver Offset zurückgegeben wird.

3.2. Algorithmus in Java

Lassen Sie es uns jetzt in Java implementieren. Zuerst fügen wir unserer Klasse eine decipher () -Methode hinzu:

String decipher(String message, int offset) {}

Rufen wir dann die cipher () -Methode mit unserem berechneten komplementären Offset auf:

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

Das war's, unser Entschlüsselungsalgorithmus ist eingerichtet. Versuchen wir es am Beispiel mit 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");

Wie wir sehen können, rufen wir unsere ursprüngliche Nachricht ab.

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

Wie wir sehen können, ruft die Methode den richtigen Versatz ab, der dann verwendet werden kann, um die Nachricht zu entschlüsseln und die ursprüngliche abzurufen.

Hier sind die verschiedenen Chi-Quadrate, die für diese bestimmte Pause berechnet wurden:

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

Wie wir sehen können, ist der für Offset 10 deutlich kleiner als der andere.

5. Schlussfolgerung

In diesem Artikel haben wir die Caesar-Chiffre behandelt. Wir haben gelernt, wie man eine Nachricht verschlüsselt und entschlüsselt, indem man ihre Buchstaben um einen bestimmten Versatz verschiebt. Wir haben auch gelernt, wie man die Chiffre bricht. Und wir haben alle Java-Implementierungen gesehen, die uns dies ermöglichen.

Der Code dieses Artikels ist auf GitHub zu finden.