Шифр Плейфера: Ранний диграммный шифр подстановки

Введение

Шифр Плейфера, или квадрат Плейфера, или шифр Уитстоуна — Плейфера — это метод ручного симметричного шифрования и был первым шифром подстановки диграмм. Схема была изобретена в 1854 году Чарльзом Уитстоуном, но названа в честь лорда Плейфера за популяризацию его использования. Эта техника шифрует пары букв (биграммы или диграммы), а не отдельные буквы, как в простом шифре подстановки, и значительно сложнее, чем системы шифров Виженера, использовавшиеся в то время. Таким образом, шифр Плейфера значительно труднее взломать, поскольку частотный анализ, применяемый к простым шифрам подстановки, неэффективен против него. Частотный анализ биграмм возможен, но значительно сложнее. С 600 возможными биграммами, в отличие от 26 возможных монограмм (отдельных символов, обычно букв в данном контексте), для практического применения требуется значительно больший зашифрованный текст.

История

Шифр Плейфера был первым шифром в истории криптологии, шифровавшим пары букв. Уитстоун изобрел этот шифр для обеспечения секретности телеграфной связи, но он получил имя его друга, лорда Плейфера, первого барона Плейфера из Сент-Эндрюса, который активно продвигал его использование. В дальнейшем шифр применялся британскими войсками в тактических целях во Второй бурской войне и в Первой мировой войне, а также британцами и австралийцами во время Второй мировой войны. Это объяснялось тем, что шифр Плейфера достаточно прост и быстр в использовании и не требует специального оборудования – только карандаша и бумаги. Типичным сценарием использования шифра Плейфера была защита важной, но не критичной информации во время боевых действий, например, сведения о том, что артиллерийский обстрел дымовыми снарядами начнется в течение 30 минут для прикрытия продвижения солдат к следующей цели. К моменту расшифровки таких сообщений вражескими криптоаналитиками, спустя несколько часов, эта информация становилась бесполезной, поскольку теряла актуальность. Во время Второй мировой войны правительство Новой Зеландии использовало шифр для связи между Новой Зеландией, островами Чатем и наблюдательными постами в Тихом океане. Этот шифр также использовался наблюдательными постами, организованными военно-морской разведкой Австралии.

Заменен

Playfair больше не используется военными из-за известных уязвимостей и появления автоматических устройств шифрования. Этот шифр считается небезопасным еще со времен, предшествующих Первой мировой войне. Первое опубликованное решение шифра Плейфера было описано в 19-страничном памфлете лейтенанта Джозефа О. Моборна, опубликованном в 1914 году. Уильям Фридман в 1942 году характеризовал его как обеспечивающий крайне низкий уровень безопасности.

Описание

Шифр Playfair использует таблицу 5x5, содержащую ключевое слово или фразу. Запоминание ключевого слова и 4 простых правил было всем, что требовалось для создания таблицы 5x5 и использования шифра. Для генерации таблицы ключей сначала заполняют пробелы в таблице (модифицированный квадрат Полибия) буквами ключевого слова (исключая повторяющиеся буквы), затем заполняют оставшиеся пробелы остальными буквами алфавита по порядку (обычно опуская "J" или "Q", чтобы алфавит поместился; в других версиях "I" и "J" помещают в одну ячейку). Ключевое слово можно записывать в верхних строках таблицы слева направо или в другом порядке, например, по спирали, начинающейся в верхнем левом углу и заканчивающейся в центре. Ключевое слово вместе с правилами заполнения таблицы 5x5 составляют ключ шифра. Для шифрования сообщения его разбивают на диграммы (группы из 2 букв), например, "HelloWorld" становится "HE LL OW OR LD". Эти диграммы заменяются с использованием таблицы ключей. Поскольку для шифрования требуется пара букв, сообщения с нечетным количеством символов обычно дополняются редкой буквой, такой как "X", для завершения последней диграммы. Две буквы диграммы рассматриваются как противоположные углы прямоугольника в таблице ключей. Для выполнения замены применяют следующие 4 правила, по порядку, к каждой паре букв открытого текста:

Если обе буквы одинаковы (или осталась только одна буква), добавляют "X" после первой буквы. Шифруют новую пару и продолжают. Некоторые варианты Playfair используют "Q" вместо "X", но подойдет любая буква, сама по себе редко встречающаяся в качестве повторяющейся пары. Если буквы находятся в одной строке таблицы, заменяют их буквами, расположенными непосредственно справа (с переходом к левому краю строки, если буква в исходной паре была на правом краю). Если буквы находятся в одном столбце таблицы, заменяют их буквами, расположенными непосредственно ниже (с переходом к верхнему краю столбца, если буква в исходной паре была внизу столбца). Если буквы не находятся в одной строке или столбце, заменяют их буквами, расположенными в одной строке, но в других углах прямоугольника, определяемого исходной парой. Порядок важен – первая буква зашифрованной пары находится в той же строке, что и первая буква пары открытого текста. Для расшифровки используют обратное (противоположное) действие двух правил сдвига, выбирая букву слева или выше, в зависимости от ситуации. Последнее правило остается неизменным, так как преобразование меняет выбранные буквы прямоугольника местами по противоположной диагонали, а повторное преобразование возвращает выбор в исходное состояние. Первое правило можно обратить только путем удаления любых дополнительных экземпляров выбранной вставки – обычно "X" или "Q" – которые не имеют смысла в окончательном сообщении после завершения. Существует несколько незначительных вариаций оригинального шифра Playfair.

Криптоанализ

Как и большинство классических шифров, шифр Плейфера может быть легко взломан при наличии достаточного объема текста. Получение ключа относительно просто, если известны как открытый текст, так и шифротекст. Когда известен только шифротекст, криптоанализ шифра методом полного перебора включает поиск в пространстве ключей соответствий между частотой встречаемости диграмм (пар букв) и известной частотой встречаемости диграмм в предполагаемом языке исходного сообщения. Криптоанализ шифра Плейфера аналогичен криптоанализу шифров с четырьмя и двумя квадратными таблицами, однако относительная простота системы Плейфера облегчает идентификацию возможных вариантов открытого текста. Важно отметить, что диграмма Плейфера и ее обратная (например, AB и BA) будут расшифровываться в одну и ту же буквенную последовательность в открытом тексте (например, RE и ER). В английском языке существует множество слов, содержащих такие обратные диграммы, как RECEIVER и DEPARTED. Выявление близко расположенных обратных диграмм в шифротексте и сопоставление шаблона со списком известных слов открытого текста, содержащих этот шаблон, является простым способом генерации возможных строк открытого текста, с которых можно начать построение ключа. Другой подход к взлому шифра Плейфера – метод восхождения по холму с использованием случайного поиска. Он начинается со случайного квадрата букв. Затем вносятся незначительные изменения (например, перестановка букв, строк или отражение всего квадрата), чтобы проверить, является ли полученный кандидат в открытый текст более похожим на стандартный открытый текст, чем до изменения (например, путем сравнения диграмм с известной таблицей частот). Если новый квадрат признается улучшением, он принимается и подвергается дальнейшим изменениям для поиска еще более подходящего кандидата. В конечном итоге, открытый текст или что-то очень близкое к нему, достигают максимального балла, определяемого выбранным методом оценки. Это, очевидно, выходит за рамки обычного человеческого терпения, но компьютеры могут использовать этот алгоритм для взлома шифров Плейфера с относительно небольшим объемом текста. Еще одним отличием шифра Плейфера от шифров с четырьмя и двумя квадратными таблицами является то, что он никогда не содержит диграммы с повторяющимися буквами, например, EE. Если в шифротексте отсутствуют диграммы с повторяющимися буквами, а длина сообщения достаточно велика, чтобы это было статистически значимо, то весьма вероятно, что использовался шифр Плейфера. Хорошее руководство по восстановлению ключа для шифра Плейфера можно найти в главе 7 "Решение полиграфических систем подстановки" Полевого руководства 34-40-2, изданного Армией Соединенных Штатов. Другой криптоанализ шифра Плейфера можно найти в главе XXI книги Хелен Фуше Гейнс "Криптоанализ / исследование шифров и их решений". Подробный криптоанализ шифра Плейфера представлен в главе 28 детективного романа Дороти Л. Сэйерс "Имейте его труп". В этой истории показано, что сообщение, зашифрованное шифром Плейфера, криптографически слабо, поскольку детектив смог восстановить весь ключ, сделав лишь несколько предположений относительно форматирования сообщения (в данном случае, что сообщение начинается с названия города и затем даты). Книга Сэйерс содержит подробное описание механики шифрования Плейфера, а также пошаговое описание ручного криптоанализа. Немецкая армия, военно-воздушные силы и полиция использовали шифр Double Playfair в качестве шифра среднего уровня во время Второй мировой войны, основанный на британском шифре Плейфера, который они взломали в начале Первой мировой войны. Они адаптировали его, введя второй квадрат, из которого выбиралась вторая буква каждой биграммы, и отказались от ключевого слова, размещая буквы в случайном порядке. Однако из-за склонности немцев к формализованным сообщениям, они были взломаны в Блетчли-парке. Сообщениям предшествовал последовательный номер, а цифры записывались прописью. Поскольку немецкие числа от 1 (eins) до двенадцати (zwölf) содержат все, кроме восьми букв в квадратах Double Playfair, формализованный трафик было относительно легко взломать (Смит, стр. 74-75).

Like most classical ciphers, the Playfair cipher can be easily cracked if there is enough text. Obtaining the key is relatively straightforward if both plaintext and ciphertext are known. When only the ciphertext is known, brute force cryptanalysis of the cipher involves searching through the key space for matches between the frequency of occurrence of digrams (pairs of letters) and the known frequency of occurrence of digrams in the assumed language of the original message. Cryptanalysis of Playfair is similar to that of four square and two square ciphers, though the relative simplicity of the Playfair system makes identifying candidate plaintext strings easier. Most notably, a Playfair digraph and its reverse (e. g. AB and BA) will decrypt to the same letter pattern in the plaintext (e. g. RE and ER). In English, there are many words which contain these reversed digraphs such as REceivER and DEpartED. Identifying nearby reversed digraphs in the ciphertext and matching the pattern to a list of known plaintext words containing the pattern is an easy way to generate possible plaintext strings with which to begin constructing the key. A different approach to tackling a Playfair cipher is the shotgun hill climbing method. This starts with a random square of letters. Then minor changes are introduced (i. e. switching letters, rows, or reflecting the entire square) to see if the candidate plaintext is more like standard plaintext than before the change (perhaps by comparing the digrams to a known frequency chart). If the new square is deemed to be an improvement, then it is adopted and then further mutated to find an even better candidate. Eventually, the plaintext or something very close is found to achieve a maximal score by whatever grading method is chosen. This is obviously beyond the range of typical human patience, but computers can adopt this algorithm to crack Playfair ciphers with a relatively small amount of text. Another aspect of Playfair that separates it from four square and two square ciphers is the fact that it will never contain a double letter digram, e. g. EE. If there are no double letter digrams in the ciphertext and the length of the message is long enough to make this statistically significant, it is very likely that the method of encryption is Playfair. A good tutorial on reconstructing the key for a Playfair cipher can be found in chapter 7, "Solution to Polygraphic Substitution Systems," of Field Manual 34 40 2, produced by the United States Army. Another cryptanalysis of a Playfair cipher can be found in Chapter XXI of Helen Fouché Gaines' Cryptanalysis / a study of ciphers and their solutions. A detailed cryptanalysis of Playfair is undertaken in chapter 28 of Dorothy L. Sayers' mystery novel Have His Carcase. In this story, a Playfair message is demonstrated to be cryptographically weak, as the detective is able to solve for the entire key making only a few guesses as to the formatting of the message (in this case, that the message starts with the name of a city and then a date). Sayers' book includes a detailed description of the mechanics of Playfair encryption, as well as a step by step account of manual cryptanalysis. The German Army, Air Force and Police used the Double Playfair cipher as a medium grade cipher in WWII, based on the British Playfair cipher they had broken early in WWI. They adapted it by introducing a second square from which the second letter of each bigram was selected, and dispensed with the keyword, placing the letters in random order. But with the German fondness for pro forma messages, they were broken at Bletchley Park. Messages were preceded by a sequential number, and numbers were spelled out. As the German numbers 1 (eins) to twelve (zwölf) contain all but eight of the letters in the Double Playfair squares, pro forma traffic was relatively easy to break (Smith, page 74 75)

Использование в современных кроссвордах

Расширенные тематические криптографические кроссворды, такие как "Кроссворд слушателя" (публикуемый в субботнем выпуске британской газеты "Таймс"), иногда включают в себя шифры Плейфера. Обычно от четырех до шести ответов необходимо ввести в сетку в зашифрованном виде, а ключевая фраза Плейфера тематически связана с окончательным решением. Этот шифр хорошо подходит для кроссвордов, поскольку открытый текст находится путем решения одного набора подсказок, а зашифрованный текст – путем решения других. Решающие могут затем составить ключевую таблицу, объединяя диграммы (иногда возможно угадать ключевое слово, но это не обязательно). Использование шифра Плейфера обычно объясняется в преамбуле к кроссворду, что уравнивает шансы для тех, кто ранее не сталкивался с этим шифром. Однако принцип использования шифра всегда остается неизменным. Используемый алфавит из 25 букв всегда содержит Q, а буквы I и J объединяются в одну. Ключевая таблица всегда заполняется построчно.

В популярной культуре

В романе «Имейте его труп» Дороти Л. Сэйерс подробно описывается процесс взлома шифра Плейфэра. В триллере времен Второй мировой войны «Троянский конь» Хаммонда Иннеса формула нового высокопрочного металлического сплава зашифрована с использованием шифра Плейфэра. В фильме «Национальное сокровище: Книга тайн» подсказка для поиска сокровищ закодирована шифром Плейфэра. В аудиокниге «Непослушный ангел: Бог грома» подсказка, зашифрованная шифром Плейфэра, отправляет Анджу Крид в Венецию. В романе «Йорк: Карта звёзд» (третья часть трилогии для детей) Лауры Руби подсказка к разгадке шифра Морнингстарр зашифрована с помощью шифра Плейфэра. Шифр Плейфэра используется как сюжетный элемент в эпизоде второго сезона сериала «Бэтвумен» 2019 года. В романе «С. (Dorst novel)» шифр Плейфэра обнаружен в сносках к истории.