Автор оригинала: François Dupire.
1. Обзор
В этом уроке мы рассмотрим шифр Цезаря, метод шифрования, который сдвигает буквы сообщения, чтобы создать другое, менее читаемое.
Прежде всего, мы рассмотрим метод шифрования и посмотрим, как его реализовать в Java.
Затем мы посмотрим, как расшифровать зашифрованное сообщение, при условии, что мы знаем смещение, используемое для его шифрования.
И, наконец, мы узнаем, как взломать такой шифр и таким образом извлечь исходное сообщение из зашифрованного, не зная используемого смещения.
2. Шифр Цезаря
2.1. Объяснение
Прежде всего, давайте определим, что такое шифр. Шифр-это метод шифрования сообщения , предназначенный для того, чтобы сделать его менее читаемым. Что касается шифра Цезаря, то это шифр подстановки, который преобразует сообщение, сдвигая его буквы на заданное смещение.
Допустим, мы хотим сдвинуть алфавит на 3, тогда буква A будет преобразована в букву D , B в E , C в 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, мы делаем цикл, по крайней мере, один раз, по всему алфавиту. Давайте представим, что мы сдвигаем сообщение на 28, что на самом деле означает, что мы сдвигаем его на 2. Действительно, после сдвига на 26 все буквы совпадают сами по себе.
Действительно, мы можем преобразовать любое смещение в более простое смещение, выполнив над ним операцию по модулю 26 :
offset = offset % 26
2.2. Алгоритм в Java
Теперь давайте посмотрим, как реализовать шифр Цезаря на Java.
Во-первых, давайте создадим класс CaesarCipher , который будет содержать метод cipher () , принимающий сообщение и смещение в качестве параметров:
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-код и вычитаем из него ASCII-код буквы a . Затем мы применяем смещение к этой позиции, тщательно используя модуль, чтобы оставаться в диапазоне алфавита. И, наконец, мы извлекаем новый символ, добавляя новую позицию к коду ASCII буквы a .
Теперь давайте попробуем эту реализацию на сообщении “он сказал мне, что я никогда не смогу научить ламу водить машину” со смещением 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, чтобы некоторые буквы были сопоставлены с буквами в начале алфавита, например t , которые будут сопоставлены с 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");Он работает, как и ожидалось, благодаря операции по модулю. Эта операция также заботится о больших смещениях. Допустим, мы хотим использовать 36 в качестве смещения, что эквивалентно 10, операция по модулю гарантирует, что преобразование даст тот же результат.
3. Расшифруйте
3.1. Объяснение
Теперь давайте посмотрим, как расшифровать такое сообщение, когда мы знаем смещение, используемое для его шифрования.
На самом деле, расшифровку сообщения, зашифрованного шифром Цезаря, можно рассматривать как шифрование его с отрицательным смещением или также шифрование его с дополнительным смещением .
Итак, допустим, у нас есть сообщение, зашифрованное со смещением 3. Затем мы можем либо зашифровать его со смещением -3, либо зашифровать со смещением 23. В любом случае, мы получим исходное сообщение.
К сожалению, наш алгоритм не обрабатывает отрицательное смещение из коробки. У нас возникнут проблемы с преобразованием букв, возвращающихся в конец алфавита (например, преобразование буквы a в букву z со смещением -1). Но мы можем вычислить дополнительное смещение, которое является положительным, а затем использовать наш алгоритм.
Итак, как получить это дополнительное смещение? Наивный способ сделать это-вычесть исходное смещение из 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. Взлом шифра Цезаря
4.1. Объяснение
Теперь, когда мы рассмотрели шифрование и расшифровку сообщений с использованием шифра Цезаря, мы можем погрузиться в то, как его взломать. То есть расшифровать зашифрованное сообщение, не зная сначала используемого смещения.
Для этого мы воспользуемся вероятностями нахождения английских букв в тексте . Идея будет заключаться в том, чтобы расшифровать сообщение, используя смещения от 0 до 25, и проверить, какой сдвиг представляет распределение букв, аналогичное распределению английских текстов.
Чтобы определить сходство двух распределений, мы будем использовать статистика Хи-квадрат .
Статистика Хи-квадрат даст число, указывающее нам, похожи ли два распределения или нет. Чем меньше их число, тем больше они похожи.
Итак, мы вычислим Хи-квадрат для каждого смещения, а затем вернем тот, у которого наименьший Хи-квадрат. Это должно дать нам смещение, используемое для шифрования сообщения.
Однако мы должны иметь в виду, что этот метод не является пуленепробиваемым и если сообщение будет слишком коротким или с использованием слов, к сожалению, не представляющих стандартный английский текст, оно может вернуть неправильное смещение.
4.2. Определите распределение базовых букв
Теперь давайте посмотрим, как реализовать алгоритм взлома в Java.
Прежде всего, давайте создадим метод break Cipher() в нашем классе Caesar Cipher , который вернет смещение, используемое для шифрования сообщения:
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. Вычислите Хи-квадраты
Теперь мы рассчитаем Хи-квадраты распределения расшифрованных букв сообщений и стандартного распределения английских букв.
Для этого нам нужно будет импортировать библиотеку Apache Commons Math3 , содержащую служебный класс для вычисления Хи-квадратов:
org.apache.commons commons-math3 3.6.1
Теперь нам нужно создать массив, который будет содержать вычисленные Хи-квадраты для каждого смещения от 0 до 25 .
Таким образом, мы расшифруем зашифрованное сообщение, используя каждое смещение, а затем посчитаем буквы в этом сообщении.
Наконец, мы будем использовать метод Chi Square Test#chi Square для вычисления Хи-квадрата между ожидаемым и наблюдаемым распределением букв:
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;Метод observed Letters Frequencies() просто реализует количество букв a to 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. Найти наиболее вероятное Смещение
После вычисления всех Хи-квадратов мы можем вернуть смещение, соответствующее наименьшему Хи-квадрату:
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;Хотя нет необходимости вводить цикл со смещением 0, поскольку мы считаем его минимальным перед началом цикла, мы делаем это, чтобы вывести его значение Хи-квадрат.
Давайте попробуем этот алгоритм на сообщении, зашифрованном с использованием смещения 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 .