Caesar Cipher di Jawa

1. Gambaran keseluruhan

Dalam tutorial ini, kita akan meneroka Caesar cipher, kaedah penyulitan yang mengalihkan huruf mesej untuk menghasilkan yang lain, yang kurang dapat dibaca.

Pertama sekali, kita akan melalui kaedah penyisipan dan melihat bagaimana melaksanakannya di Java.

Kemudian, kita akan melihat cara menguraikan mesej yang dienkripsi, dengan syarat kita mengetahui ofset yang digunakan untuk menyulitkannya.

Dan akhirnya, kita akan belajar cara memecahkan cipher seperti itu dan dengan itu mengambil semula mesej asal dari yang disulitkan tanpa mengetahui ofset yang digunakan.

2. Caesar Cipher

2.1. Penjelasan

Pertama sekali, mari kita tentukan apa itu cipher. Cipher adalah kaedah untuk mengenkripsi mesej, yang bermaksud menjadikannya tidak dapat dibaca. Bagi Caesar cipher, ini adalah pengganti pengganti yang mengubah mesej dengan mengalihkan hurufnya dengan ofset tertentu.

Katakan kita mahu menggeser abjad dengan 3, maka huruf A akan diubah menjadi huruf D , B ke E , C ke F , dan seterusnya.

Berikut adalah padanan lengkap antara huruf asli dan huruf berubah untuk mengimbangi 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, setelah transformasi melampaui huruf Z , kita kembali ke permulaan abjad, sehingga X , Y dan Z masing-masing berubah menjadi A , B dan C.

Oleh itu, jika kita memilih ofset lebih besar atau sama dengan 26, kita mengulangi, sekurang-kurangnya satu kali, pada keseluruhan abjad. Cuba bayangkan kita mengalihkan mesej dengan 28, itu benar-benar bermaksud kita mengalihkannya dengan 2. Sesungguhnya, setelah beralih dengan 26, semua huruf sesuai dengan mereka.

Sungguh, kita dapat mengubah sebarang ofset menjadi offset yang lebih sederhana dengan melakukan operasi modulo 26 padanya :

offset = offset % 26

2.2. Algoritma di Jawa

Sekarang, mari kita lihat bagaimana menerapkan Caesar cipher di Java.

Pertama, mari buat kelas CaesarCipher yang akan memegang kaedah cipher () dengan mengambil mesej dan mengimbangi sebagai parameter:

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

Kaedah itu akan menyulitkan mesej menggunakan Caesar cipher.

Kami anggap di sini bahawa ofset positif dan mesej hanya mengandungi huruf kecil dan spasi. Kemudian, apa yang kita mahukan adalah menggeser semua aksara abjad mengikut ofset 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 kita lihat, kita bergantung pada kod ASCII huruf abjad untuk mencapai tujuan kita .

Pertama, kita menghitung kedudukan huruf semasa dalam abjad, dan untuk itu, kita mengambil kod ASCII dan mengurangkan kod ASCII huruf a darinya. Kemudian kami menerapkan ofset ke kedudukan ini, dengan hati-hati menggunakan modulo untuk tetap berada dalam julat abjad. Dan akhirnya, kami mengambil watak baru dengan menambahkan kedudukan baru pada kod ASCII huruf a .

Sekarang, mari kita coba pelaksanaan ini pada pesan "dia mengatakan kepada saya bahawa saya tidak pernah dapat mengajar llama untuk memandu" dengan mengimbangi 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 kita lihat, mesej yang disisipkan menghormati padanan yang ditentukan sebelumnya untuk mengimbangi 3.

Sekarang, contoh khusus ini mempunyai kekhususan untuk tidak melebihi huruf z semasa transformasi, oleh itu tidak perlu kembali ke permulaan abjad. Oleh itu, mari kita cuba lagi dengan mengimbangi 10 sehingga beberapa huruf akan dipetakan ke huruf pada awal abjad, 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");

Ia berfungsi seperti yang diharapkan, berkat operasi modulo. Operasi itu juga menguruskan ofset yang lebih besar. Katakan kita mahu menggunakan 36 sebagai ofset, yang bersamaan dengan 10, operasi modulo memastikan bahawa transformasi akan memberikan hasil yang sama.

3. Penafsiran

3.1. Penjelasan

Sekarang, mari kita lihat cara menguraikan mesej sedemikian apabila kita mengetahui ofset yang digunakan untuk menyulitkannya.

Sebenarnya, menguraikan mesej yang dienkripsi dengan Caesar cipher dapat dilihat sebagai menyandarkannya dengan ofset negatif, atau juga menyandarkannya dengan pelengkap ofset .

Oleh itu, katakan kita mempunyai mesej yang disulitkan dengan ofset 3. Kemudian, kita boleh menyulitkannya dengan ofset -3 atau menyulitkannya dengan ofset 23. Walau bagaimanapun, kita akan mendapatkan semula mesej asal.

Malangnya, algoritma kami tidak menangani ofset negatif di luar kotak. Kita akan menghadapi masalah menukar huruf yang berulang ke hujung abjad (contohnya mengubah huruf a menjadi huruf z dengan mengimbangi -1). Tetapi, kita dapat mengira penggantian pelengkap, yang positif, dan kemudian menggunakan algoritma kita.

Jadi, bagaimana untuk mendapatkan pengimbangan pelengkap ini? Cara naif untuk melakukan ini adalah untuk mengurangkan pengimbangan awal dari 26. Sudah tentu, ini akan berfungsi untuk ofset antara 0 dan 26 tetapi akan memberikan hasil negatif sebaliknya.

Di situlah kita akan menggunakan pengendali modulo sekali lagi, secara langsung pada ofset asal, sebelum melakukan pengurangan . Dengan cara itu, kami memastikan sentiasa mengembalikan keseimbangan positif.

3.2. Algoritma di Jawa

Sekarang mari kita laksanakan di Java. Pertama, kami akan menambahkan kaedah dekipher () ke kelas kami:

String decipher(String message, int offset) {}

Kemudian, mari kita sebut kaedah cipher () dengan pengiraan pelengkap yang dikira:

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

Itu sahaja, algoritma penghuraian kami disiapkan. Mari mencubanya pada contoh dengan mengimbangi 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 dapat kita lihat, kita mengambil semula mesej asal 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 dapat kita lihat, kaedah mendapatkan kembali ofset yang betul, yang kemudian dapat digunakan untuk menguraikan pesan dan mengambil semula yang asli.

Berikut adalah petak Chi yang berbeza yang dikira untuk rehat 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 kita lihat, yang satu untuk ofset 10 jelas lebih kecil daripada yang lain.

5. Kesimpulan

Dalam artikel ini, kami membahas Caesar cipher. Kami belajar bagaimana menyusun dan menguraikan mesej dengan mengalihkan hurufnya dengan ofset tertentu. Kami juga belajar cara memecahkan cipher. Dan kami melihat semua pelaksanaan Java yang membolehkan kami melakukan itu.

Kod artikel ini boleh didapati di GitHub.