Javaのシーザー暗号

1。概要

このチュートリアルでは、メッセージの文字をシフトして別の読みにくい暗号を生成する暗号化方式であるシーザー暗号について説明します。

まず、暗号化メソッドを実行し、Javaで実装する方法を確認します。

次に、暗号化に使用されるオフセットがわかっている場合に、暗号化されたメッセージを解読する方法を説明します。

そして最後に、そのような暗号を破り、使用されるオフセットを知らなくても、暗号化されたメッセージから元のメッセージを取得する方法を学びます。

2.シーザー暗号

2.1。説明

まず、暗号とは何かを定義しましょう。暗号は、メッセージを読みにくくすることを目的として、メッセージを暗号化する方法です。シーザー暗号に関しては、指定されたオフセットだけ文字をシフトすることによってメッセージを変換する換字式暗号です。

アルファベットを3シフトすると、文字Aは文字DにBEにCFに変換されます。

これは、オフセット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

ご覧のとおり、変換が文字Zを超えると、アルファベットの先頭に戻り、XYZがそれぞれABCに変換されます。

したがって、26以上のオフセットを選択すると、アルファベット全体で少なくとも1回ループします。メッセージを28シフトするとします。つまり、メッセージを2シフトしているということです。実際、26シフトした後、すべての文字が一致しています。

実際、モジュロ26演算を実行することで、任意のオフセットをより単純なオフセットに変換できます。

offset = offset % 26

2.2。Javaのアルゴリズム

それでは、Javaでシーザー暗号を実装する方法を見てみましょう。

まず、メッセージとオフセットをパラメーターとして受け取るcipher()メソッドを保持するクラスCaesarCipherを作成しましょう。

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

この方法では、シーザー暗号を使用してメッセージを暗号化します。

ここでは、オフセットが正であり、メッセージには小文字とスペースのみが含まれていると想定します。次に、必要なのは、指定されたオフセットだけすべてのアルファベット文字をシフトすることです。

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;

ご覧のとおり、目標を達成するためにアルファベットのASCIIコードに依存しています

まず、アルファベットの現在の文字の位置を計算し、そのために、そのASCIIコードを取得してそこから文字aのASCIIコードを減算します。次に、この位置にオフセットを適用し、モジュロを慎重に使用してアルファベットの範囲を維持します。最後に、文字aのASCIIコードに新しい位置を追加して、新しい文字を取得します。

それでは、「ラマに運転を教えることは絶対にできないと彼は言った」というメッセージに対して、オフセット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");

ご覧のとおり、暗号化されたメッセージは、オフセット3に対して以前に定義されたマッチングを尊重します。

さて、この特定の例は、変換中に文字zを超えないという特異性を持っているため、アルファベットの先頭に戻る必要はありません。したがって、オフセット10で再試行して、一部の文字がアルファベットの先頭の文字にマップされるようにします。たとえば、tdにマップされます。

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

モジュロ演算のおかげで、期待どおりに機能します。この操作では、より大きなオフセットも処理されます。オフセットとして36を使用するとします。これは10に相当します。モジュロ演算により、変換で同じ結果が得られます。

3.解読

3.1。説明

それでは、暗号化に使用されるオフセットがわかっているときに、そのようなメッセージを解読する方法を見てみましょう。

実際のところ、シーザー暗号で暗号化されたメッセージを解読することは、負のオフセットで暗号化すること、または相補的なオフセットでメッセージを暗号化することと見なすことができます

したがって、オフセット3で暗号化されたメッセージがあるとします。次に、オフセット-3で暗号化するか、オフセット23で暗号化できます。どちらの方法でも、元のメッセージを取得します。

残念ながら、私たちのアルゴリズムは、箱から出して負のオフセットを処理しません。アルファベットの末尾にループバックする文字の変換で問題が発生します(たとえば、文字aをオフセット-1の文字zに変換します)。ただし、正の相補オフセットを計算してから、アルゴリズムを使用することはできます。

では、この補完的なオフセットを取得する方法は?これを行うための単純な方法は、26から元のオフセットを減算することです。もちろん、これは0から26までのオフセットで機能しますが、それ以外の場合は負の結果になります。

ここで、減算を実行する前に、元のオフセットで直接モジュロ演算子を再度使用します。そうすることで、常に正のオフセットを返すようにします。

3.2。Javaのアルゴリズム

それをJavaで実装しましょう。まず、クラスにdecipher()メソッドを追加します。

String decipher(String message, int offset) {}

次に、計算された相補オフセットを使用してcipher()メソッドを呼び出します。

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

これで、解読アルゴリズムが設定されました。オフセット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");

ご覧のとおり、元のメッセージを取得しています。

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

ご覧のとおり、このメソッドは正しいオフセットを取得します。これを使用して、メッセージを解読し、元のオフセットを取得できます。

この特定の休憩に対して計算されたさまざまなカイ2乗は次のとおりです。

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

ご覧のとおり、オフセット10のものは他のものより明らかに小さいです。

5。結論

この記事では、シーザー暗号について説明しました。メッセージの文字を特定のオフセットだけシフトすることにより、メッセージを暗号化および解読する方法を学びました。また、暗号を破る方法も学びました。そして、それを可能にするすべてのJava実装を見ました。

この記事のコードはGitHubにあります。