1. 概要

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

まず、暗号化方式を確認し、Javaで実装する方法を確認します。

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

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

2. シーザー暗号

2.1. 説明

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

アルファベットを3シフトすると、文字Aは文字DBからECからFなど。

これは、オフセット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を超えると、アルファベットの先頭に戻り、X、Y、ZがそれぞれA、B、Cに変換されます。

したがって、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 を超えないという特異性を持っているため、アルファベットの先頭に戻る必要はありません。 したがって、dにマップされるtのように、一部の文字がアルファベットの先頭の文字にマップされるように、オフセット10で再試行してみましょう。

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に実装してみましょう。 まず、 decode()メソッドをクラスに追加します。

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. シーザー暗号を破る

4.1. 説明

シーザー暗号を使用したメッセージの暗号化と解読について説明したので、それを解読する方法を詳しく見ていきましょう。 つまり、最初は使用されたオフセットを知らなくても、暗号化されたメッセージを解読します。

そのために、テキスト内の英語の文字を見つける確率を利用します。 アイデアは、オフセット0〜25を使用してメッセージを解読し、どのシフトが英語のテキストと同様の文字分布を示すかを確認することです。

2つの分布の類似性を判断するために、カイ2乗統計を使用します。

カイ二乗統計は、2つの分布が類似しているかどうかを示す数値を提供します。 数字が小さいほど、類似しています。

したがって、すべてのオフセットのカイ2乗を計算してから、カイ2乗が最小のオフセットを返します。 これにより、メッセージの暗号化に使用されるオフセットが得られます。

ただし、この手法は防弾ではないことを覚えておく必要があります。メッセージが短すぎるか、残念ながら標準英語のテキストを表していない単語を使用すると、間違ったオフセットが返される可能性があります。

4.2. 基本文字の分布を定義する

Javaで破壊アルゴリズムを実装する方法を見てみましょう。

まず、 CaesarCipherクラスにbreakCipher()メソッドを作成します。これにより、メッセージの暗号化に使用されるオフセットが返されます。

int breakCipher(String message) {}

次に、英語のテキストで特定の文字を見つける確率を含む配列を定義しましょう。

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};

この配列から、確率にメッセージの長さを掛けることにより、特定のメッセージ内の文字の予想される頻度を計算できます。

double[] expectedLettersFrequencies = Arrays.stream(englishLettersProbabilities)
  .map(probability -> probability * message.getLength())
  .toArray();

たとえば、長さが100のメッセージでは、文字 a が7.3回出現し、文字eが13回出現することを期待する必要があります。

4.3. カイ二乗を計算します

次に、解読されたメッセージ文字の分布と標準的な英語の文字の分布のカイ2乗を計算します。

これを実現するには、カイ二乗を計算するためのユーティリティクラスを含む ApacheCommonsMath3ライブラリをインポートする必要があります。

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version>
</dependency>

ここで行う必要があるのは、0から25までの各オフセットに対して計算されたカイ2乗を含む配列を作成することです。

したがって、各オフセットを使用して暗号化されたメッセージを解読し、そのメッセージ内の文字をカウントします。

最後に、 ChiSquareTest#chiSquare メソッドを使用して、予想される文字分布と観測された文字分布の間のカイ2乗を計算します。

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;

observedLettersFrequencies()メソッドは、渡されたメッセージ内のaからzまでの文字数を単純に実現します。

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. 最も可能性の高いオフセットを見つける

すべてのカイ2乗が計算されると、最小のカイ2乗に一致するオフセットを返すことができます。

int probableOffset = 0;
for (int offset = 0; offset < chiSquares.length; offset++) {
    <span class="x x-first">log</span><span class="pl-k x">.</span><span class="x x-last">debug</span>(String.format("Chi-Square for offset %d: %.2f", offset, chiSquares[offset]));
    if (chiSquares[offset] < chiSquares[probableOffset]) {
        probableOffset = offset;
    }
}

return probableOffset;

ループを開始する前に最小であると見なすため、オフセット0でループに入る必要はありませんが、カイ2乗値を出力するために行います。

オフセット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");

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

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

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にあります。