Caesar Cipher di Jawa

1. Ikhtisar

Dalam tutorial ini, kita akan menjelajahi sandi Caesar, metode enkripsi yang menggeser huruf dari sebuah pesan untuk menghasilkan pesan lain yang kurang dapat dibaca.

Pertama-tama, kita akan membahas metode penyandian dan melihat bagaimana menerapkannya di Java.

Kemudian, kita akan melihat cara menguraikan pesan terenkripsi, asalkan kita tahu offset yang digunakan untuk mengenkripsinya.

Dan akhirnya, kita akan belajar bagaimana memecahkan sandi semacam itu dan dengan demikian mengambil pesan asli dari yang terenkripsi tanpa mengetahui offset yang digunakan.

2. Caesar Cipher

2.1. Penjelasan

Pertama-tama, mari kita definisikan apa itu sandi. Penyandian adalah metode untuk mengenkripsi pesan, dengan maksud membuatnya kurang dapat dibaca. Sedangkan untuk sandi Caesar, ini adalah sandi pengganti yang mengubah pesan dengan menggeser hurufnya dengan offset yang diberikan.

Misalkan kita ingin menggeser alfabet sebanyak 3, maka huruf A akan berubah menjadi huruf D , B ke E , C ke F , dan seterusnya.

Berikut adalah pencocokan lengkap antara huruf asli dan huruf yang diubah untuk offset 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

Seperti yang kita lihat, sekali transformasi melampaui huruf Z , kita kembali ke awal alfabet, sehingga X , Y dan Z berubah menjadi A , B dan C , masing-masing.

Oleh karena itu, jika kita memilih offset yang lebih besar atau sama dengan 26, kita mengulang, setidaknya satu kali, di seluruh alfabet. Bayangkan kita menggeser pesan menjadi 28, itu berarti kita menggesernya menjadi 2. Memang, setelah menggeser 26, semua huruf cocok dengan sendirinya.

Sungguh, kita dapat mengubah offset apa pun menjadi offset yang lebih sederhana dengan melakukan operasi modulo 26 di atasnya :

offset = offset % 26

2.2. Algoritma di Jawa

Sekarang, mari kita lihat bagaimana mengimplementasikan sandi Caesar di Java.

Pertama, mari buat kelas CaesarCipher yang akan menampung metode cipher () yang mengambil pesan dan offset sebagai parameter:

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

Metode itu akan mengenkripsi pesan menggunakan sandi Caesar.

Kami akan menganggap di sini bahwa offset positif dan pesan hanya berisi huruf kecil dan spasi. Kemudian, yang kami inginkan adalah menggeser semua karakter alfabet dengan offset yang diberikan:

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;

Seperti yang bisa kita lihat, kita mengandalkan kode ASCII dari huruf alfabet untuk mencapai tujuan kita .

Pertama, kami menghitung posisi huruf saat ini dalam alfabet, dan untuk itu, kami mengambil kode ASCII-nya dan mengurangi kode ASCII huruf a darinya. Kemudian kami menerapkan offset ke posisi ini, dengan hati-hati menggunakan modulo agar tetap dalam rentang alfabet. Dan akhirnya, kita mengambil karakter baru dengan menambahkan posisi baru ke kode ASCII huruf a .

Sekarang, mari kita coba implementasi ini pada pesan "dia mengatakan kepada saya bahwa saya tidak pernah bisa mengajari llama mengemudi" dengan offset 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");

Seperti yang bisa kita lihat, pesan tersandi menghormati pencocokan yang didefinisikan sebelumnya untuk offset 3.

Sekarang, contoh khusus ini memiliki kekhususan untuk tidak melebihi huruf z selama transformasi, oleh karena itu tidak harus kembali ke awal alfabet. Jadi, mari kita coba lagi dengan offset 10 sehingga beberapa huruf akan dipetakan ke huruf di awal alfabet, seperti t yang akan dipetakan ke 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");

Ini berfungsi seperti yang diharapkan, berkat operasi modulo. Operasi itu juga menangani offset yang lebih besar. Katakanlah kita ingin menggunakan 36 sebagai offset, yang setara dengan 10, operasi modulo memastikan bahwa transformasi akan memberikan hasil yang sama.

3. Menguraikan

3.1. Penjelasan

Sekarang, mari kita lihat bagaimana menguraikan pesan seperti itu ketika kita mengetahui offset yang digunakan untuk mengenkripsinya.

Faktanya, mengartikan pesan yang dienkripsi dengan sandi Caesar dapat dilihat sebagai sandi dengan offset negatif, atau juga mengartikannya dengan offset komplementer .

Jadi, katakanlah kita memiliki pesan yang dienkripsi dengan offset 3. Kemudian, kita bisa mengenkripsinya dengan offset -3 atau mengenkripsinya dengan offset 23. Bagaimanapun juga, kita mengambil pesan asli.

Sayangnya, algoritme kami tidak menangani offset negatif di luar kotak. Kita akan mengalami masalah dalam mengonversi huruf yang berulang kembali ke akhir alfabet (misalnya mengubah huruf a menjadi huruf z dengan offset -1). Tapi, kita bisa menghitung offset pelengkap, yang bernilai positif, dan kemudian menggunakan algoritma kita.

Jadi, bagaimana cara mendapatkan offset pelengkap ini? Cara naif untuk melakukan ini adalah dengan mengurangi offset asli dari 26. Tentu saja, ini akan bekerja untuk offset antara 0 dan 26 tetapi sebaliknya akan memberikan hasil negatif.

Di situlah kita akan menggunakan operator modulo lagi, langsung pada offset asli, sebelum melakukan pengurangan . Dengan begitu, kami memastikan selalu mengembalikan offset positif.

3.2. Algoritma di Jawa

Sekarang mari kita terapkan di Java. Pertama, kami akan menambahkan metode decipher () ke kelas kami:

String decipher(String message, int offset) {}

Kemudian, panggil metode cipher () dengan offset komplementer yang dihitung:

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

Itu saja, algoritme penguraian kami sudah disiapkan. Mari kita coba pada contoh dengan 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");

Seperti yang bisa kita lihat, kita mendapatkan kembali pesan asli kita.

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

Seperti yang bisa kita lihat, metode mengambil offset yang benar, yang kemudian dapat digunakan untuk menguraikan pesan dan mengambil yang asli.

Berikut adalah Chi-kuadrat berbeda yang dihitung untuk jeda khusus ini:

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

Seperti yang bisa kita lihat, yang satu untuk offset 10 jelas lebih kecil dari yang lain.

5. Kesimpulan

Pada artikel ini, kami membahas sandi Caesar. Kami belajar cara menyandikan dan menguraikan pesan dengan menggeser huruf-hurufnya dengan offset tertentu. Kami juga belajar cara memecahkan sandi. Dan kami melihat semua implementasi Java yang memungkinkan kami melakukan itu.

Kode artikel ini dapat ditemukan di GitHub.