Шифр Плейфера

Шифр Плейфэра или квадрат Плейфэра или шифр Уитстона-Плейфэра представляет собой метод ручного симметричного шифрования и был первым шифром замены буквальных диграмм . Схема была изобретена в 1854 году Чарльзом Уитстоном носит имя лорда Плейфэра , но за пропаганду ее использования .

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

История

Шифр Плейфэра был первым шифром, который зашифровал пары букв в истории криптологии. ^[2] Уитстон изобрел шифр для секретности в телеграфии , но он носит имя его друга лорда Плейфэра , первого барона Плейфэра из Сент-Эндрюса, который пропагандировал его использование. ^[3]^[4]^[5] Первое зарегистрированное описание шифра Плейфэра было в документе, подписанном Уитстоном 26 марта 1854 года.

Первоначально он был отвергнут Министерством иностранных дел Великобритании , когда был разработан, из-за его предполагаемой сложности. Уитстон предложил продемонстрировать, что трое из четырех мальчиков в соседней школе могут научиться пользоваться им за 15 минут, но заместитель министра иностранных дел ответил: «Это вполне возможно, но вы никогда не сможете научить этому атташе». ^[6]

Однако позже он использовался в тактических целях британскими войсками во Второй англо-бурской войне и в Первой мировой войне, а также с той же целью британцами и австралийцами во время Второй мировой войны . ^[4]^[5] Это произошло потому, что Playfair достаточно быстр в использовании и не требует специального оборудования — только карандаш и немного бумаги. Типичным сценарием использования Playfair была защита важных, но некритических секретов во время реального боя, например, того факта, что артиллерийский обстрел дымовыми снарядами начнется в течение 30 минут для прикрытия продвижения солдат к следующей цели. К тому времени, когда вражеские криптоаналитики смогут расшифровать такие сообщения несколько часов спустя, такая информация станет для них бесполезной, поскольку она больше не будет актуальной. ^[7]

Во время Второй мировой войны правительство Новой Зеландии использовало его для связи между Новой Зеландией , островами Чатем и береговыми наблюдателями на островах Тихого океана. ^[8]^[9] Береговые наблюдатели, созданные разведкой Королевского военно-морского флота Австралии, также использовали этот шифр. ^[10]

Заменено

Playfair больше не используется военными из-за известных проблем с безопасностью и появления автоматических устройств шифрования. Этот шифр считается небезопасным еще до Первой мировой войны .

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

Описание

Шифр Playfair использует таблицу 5*5, содержащую ключевое слово или фразу . Запоминание ключевого слова и 4 простых правил — это все, что требовалось для создания таблицы 5 на 5 и использования шифра.

Чтобы создать таблицу ключей, нужно сначала заполнить пробелы в таблице (модифицированный квадрат Полибия ) буквами ключевого слова (отбрасывая все повторяющиеся буквы), а затем заполнить оставшиеся места остальными буквами алфавита в порядке (обычно опуская «J» или «Q», чтобы уменьшить алфавит до нужного размера; в других версиях «I» и «J» помещаются в одно и то же место). Ключ можно записать в верхних строках таблицы слева направо или в каком-либо другом образце, например в виде спирали, начинающейся в верхнем левом углу и заканчивающейся в центре. Ключевое слово вместе с правилами заполнения таблицы 5 на 5 составляют ключ шифрования.

Чтобы зашифровать сообщение, нужно разбить его на биграммы (группы из двух букв), так что, например, «HelloWorld» превратится в «HE LL OW OR LD». Эти биграммы будут заменены с использованием ключевой таблицы. Поскольку для шифрования требуются пары букв, к сообщениям с нечетным количеством символов обычно добавляется необычная буква, например «X», для завершения конечной биграммы. Две буквы диграммы считаются противоположными углами прямоугольника в ключевой таблице. Чтобы выполнить замену, примените следующие 4 правила по порядку к каждой паре букв в исходном тексте:

Если обе буквы одинаковые (или осталась только одна буква), добавьте «X» после первой буквы. Зашифруйте новую пару и продолжайте. В некоторых вариантах Playfair вместо «X» используется «Q», но подойдет любая буква, которая сама по себе является редкостью в виде повторяющейся пары.
Если буквы появляются в одной строке вашей таблицы, замените их буквами справа от них соответственно (переход на левую сторону строки, если буква в исходной паре находилась на правой стороне строки).
Если буквы появляются в одном и том же столбце вашей таблицы, замените их буквами, расположенными непосредственно ниже соответственно (переходя в верхнюю часть столбца, если буква в исходной паре находилась в нижней части столбца).
Если буквы находятся не в одной строке или столбце, замените их буквами в той же строке соответственно, но в другой паре углов прямоугольника, определенного исходной парой. Порядок важен: первая буква зашифрованной пары находится в той же строке, что и первая буква пары открытого текста.

Для расшифровки используйте инверсию (противоположность) двух правил сдвига, выбирая букву слева или вверх в зависимости от ситуации. Последнее правило остается неизменным, так как преобразование переключает выделенные буквы прямоугольника на противоположную диагональ, а повтор преобразования возвращает выделение в исходное состояние. Первое правило можно отменить, только удалив любые лишние экземпляры выбранной вставки буквы — обычно «X» или «Q» — которые не имеют смысла в конечном сообщении после завершения.

Есть несколько незначительных вариаций ^{[ который? ]} оригинального шифра Playfair. ^[13]

Пример

Используя «пример playfair» в качестве ключа (при условии, что I и J взаимозаменяемы), таблица принимает вид (пропущенные буквы красного цвета):

Первым шагом шифрования сообщения «спрячь золото в пне» является преобразование его в пары букв «HI DE TH EG OL DI NT HE TR EX ES TU MP» (с нулевым «X», используемым для разделения повторяющаяся буква «Е»). Затем:

1. Пара HI образует прямоугольник, замените ее на BM
2. Пара DE находится в столбце, замените ее на OD
3. Пара TH образует прямоугольник, замените ее на ZB
4. Пара EG образует прямоугольник, заменяем ее на XD
5. Пара ОЛ образует прямоугольник, замените ее на NA.
6. Пара DI образует прямоугольник, заменяем ее на BE
7. Пара NT образует прямоугольник, замените ее на КУ.
8. Пара ОН образует прямоугольник, заменяем ее на DM
9. Пара TR образует прямоугольник, замените его на UI
10. Пара EX (X вставлена в разделитель EE) стоит в ряд, замените ее на XM
11. Пара ES образует прямоугольник, замените ее на МО.
12. Пара ТУ стоит в ряду, замените ее на УФ.
13. Пара МП образует прямоугольник, замените ее на ЕСЛИ

Таким образом, сообщение «спрячь золото в пне» становится «BM OD ZB XD NA BE KU DM UI XM MO UV IF», которое для удобства чтения зашифрованного текста можно реструктурировать как «BMODZ BXDNA BEKUD MUIXM MOUVI F».

Уточнение с картинкой

Предположим, кто-то хочет зашифровать биграмму ИЛИ. Существует пять общих случаев:

1)

* * * * *
* O Y R Z
* * * * *
* * * * *
* * * * *

Следовательно, OR → YZ

2)

* * O * *
* * B * *
* * * * *
* * R * *
* * Y * *

Следовательно, ИЛИ → BY

3)

Z * * O *
* * * * *
* * * * *
R * * X *
* * * * *

Следовательно, OR → ZX

4)

* * * * *
* * * * *
* O R W *
* * * * *
* * * * *

Следовательно, OR → RW

5)

* * * * *
* * R * *
* * O * *
* * I * *
* * * * *

Следовательно, ИЛИ → IO

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

Как и большинство классических шифров, шифр Плейфэра можно легко взломать, если имеется достаточно текста. Получить ключ относительно просто, если как открытый текст , так и зашифрованный текст известны . Когда известен только зашифрованный текст, криптоанализ методом грубой силы включает поиск в ключевом пространстве совпадений между частотой появления биграмм (пар букв) и известной частотой появления биграмм на предполагаемом языке исходного сообщения. ^[14]

Криптоанализ Playfair аналогичен анализу шифров с четырьмя и двумя квадратами , хотя относительная простота системы Playfair упрощает идентификацию строк-кандидатов открытого текста. В частности, орграф Playfair и его обратная сторона (например, AB и BA) будут расшифровываться в один и тот же шаблон букв в открытом тексте (например, RE и ER). В английском языке есть много слов, содержащих эти перевернутые диграфы, например REceivER и DEpartED. Идентификация близлежащих перевернутых орграфов в зашифрованном тексте и сопоставление шаблона со списком известных слов открытого текста, содержащих этот шаблон, — это простой способ сгенерировать возможные строки открытого текста, с которых можно начать построение ключа.

Другой подход к решению шифра Плейфэра — это метод восхождения на холм с дробовиком . Все начинается со случайного квадрата букв. Затем вносятся незначительные изменения (т. е. переключение букв, строк или отражение всего квадрата), чтобы увидеть, похож ли открытый текст-кандидат на стандартный открытый текст больше, чем до изменения (возможно, путем сравнения биграмм с известной диаграммой частот). Если новый квадрат считается улучшением, его принимают, а затем мутируют, чтобы найти еще лучшего кандидата. В конце концов обнаруживается, что открытый текст или что-то очень близкое к нему дает максимальный балл независимо от выбранного метода оценки. Очевидно, что это выходит за рамки типичного человеческого терпения, но компьютеры могут использовать этот алгоритм для взлома шифров Playfair с помощью относительно небольшого объема текста.

Еще одним аспектом шифра Playfair, который отличает его от шифров с четырьмя и двумя квадратами, является тот факт, что он никогда не будет содержать двухбуквенную биграмму, например EE. Если в зашифрованном тексте нет двухбуквенных диграмм и длина сообщения достаточно велика, чтобы сделать это статистически значимым, весьма вероятно, что используется метод шифрования Playfair.

Хорошее руководство по восстановлению ключа для шифра Плейфэра можно найти в главе 7 «Решение систем полиграфической замены» Полевого руководства 34-40-2 , выпущенного армией США. Другой криптоанализ шифра Плейфэра можно найти в главе XXI книги Хелен Фуше Гейнс «Криптоанализ / исследование шифров и их решений» . ^[15]

Подробный криптоанализ Playfair проводится в главе 28 Дороти Л. Сэйерс детективного романа « Принеси его труп» . В этой истории показано, что сообщение Playfair является криптографически слабым, поскольку детектив может определить весь ключ, сделав лишь несколько предположений относительно форматирования сообщения (в данном случае сообщение начинается с имени город, а затем дату). Книга Сэйерса включает подробное описание механики шифрования Playfair, а также пошаговое описание ручного криптоанализа.

Немецкая армия, военно-воздушные силы и полиция использовали двойной шифр Плейфэра в качестве шифра средней степени сложности во время Второй мировой войны, основанный на британском шифре Плейфэра, который они взломали в начале Первой мировой войны. ^[16] Они адаптировали его, введя второй квадрат, из которого выбиралась вторая буква каждой биграммы, и отказались от ключевого слова, разместив буквы в случайном порядке. Но из-за любви немцев к формальным сообщениям они были нарушены в Блетчли-парке . Сообщениям предшествовал порядковый номер, а цифры прописывались. Поскольку немецкие цифры от 1 (eins) до двенадцати (zwölf) содержат все буквы, кроме восьми, в квадратах Double Playfair, пробочный трафик было относительно легко нарушить (Смит, стр. 74–75).

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

Сложные тематические загадочные кроссворды, такие как слушателя» « Кроссворд (опубликованный в субботнем выпуске британской газеты «Таймс» ), иногда включают шифры Playfair. ^[17] Обычно в сетку необходимо ввести от четырех до шести ответов в коде, а ключевая фраза Playfair тематически важна для окончательного решения.

Шифр хорошо подходит для разгадывания кроссвордов, поскольку открытый текст находится путем решения одного набора ключей, а зашифрованный текст — путем решения других. Затем решатели могут построить таблицу ключей, соединив биграммы в пары (иногда можно угадать ключевое слово, но это никогда не требуется).

Использование шифра Playfair обычно объясняется в преамбуле кроссворда. Это выравнивает правила игры для тех решателей, которые раньше не сталкивались с шифром. Но способ использования шифра всегда один и тот же. Используемый 25-буквенный алфавит всегда содержит Q и совпадает с I и J. Ключевая таблица всегда заполняется построчно.

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

В романе Have His Carcase» « Дороти Л. Сэйерс подробно описывается взлом шифра Playfair.
о Второй мировой войне «Троянский конь» Триллер Хаммонда Иннеса скрывает формулу нового высокопрочного металлического сплава с использованием шифра Playfair.
В фильме « Сокровище нации: Книга тайн» подсказка об охоте за сокровищами закодирована в виде шифра Playfair.
В аудиокниге Rogue Angel : God of Thunder подсказка шифра Playfair используется для отправки Ани Крид в Венецию.
В романе «Йорк: Карта звезд» (третья часть трилогии для детей) Лоры Руби ключ к разгадке шифра Морнингстарра зашифрован с помощью шифра Плейфэра.
Шифр Playfair служит сюжетным ходом в эпизоде 2 сезона сериала « Бэтвумен» 2019 года .
В романе С. (Роман Дорста) в сносках к рассказу обнаружен шифр Плейфера.

См. также

Темы криптографии

Примечания

^ Повторяющиеся буквы не допускаются, одна буква опущена (Q) или объединена (I/J), поэтому расчет равен 600 = 25×24.
^ Взломщики кодов (1996) Дэвид Кан, Scribner Books от Simon & Schuster
^ Кристенсен, Крис (2006). «Полиграфические шифры» (PDF) . Университет Северного Кентукки, Крис Кристенсен . Проверено 9 января 2018 г.
^ Перейти обратно: ^а ^б Кан, Дэвид (1996). Взломщики кодов: всеобъемлющая история секретной связи с древних времен до Интернета . Скрибнер. ISBN 978-0684831305 .
^ Перейти обратно: ^а ^б Клима, Рик (2018). «Секретные коды во время Второй мировой войны» (PDF) . Аппалачский государственный университет, доктор Рик Клима . Архивировано из оригинала (PDF) 13 октября 2017 г. Проверено 9 января 2018 г.
^ Рид, Томас Вемисс (1899). Мемуары и переписка Лиона Плейфэра: Первый лорд Плейфэр Сент-Эндрюса ... Харпер и братья. стр. 158–159.
^ Лорд, Уолтер (2012). Одинокое бдение: Береговые стражи Соломоновых островов . Открытые дорожные медиа. Киндл издание. п. 6.
^ «История безопасности связи в Новой Зеландии Эрика Могона» , глава 8
^ «История обеспечения информации (IA)» . Бюро безопасности правительственной связи . Правительство Новой Зеландии. Архивировано из оригинала 12 ноября 2011 г. Проверено 24 декабря 2011 г.
^ Лорд, Уолтер (2012). Одинокое бдение: Береговые стражи Соломоновых островов . Открытые дорожные медиа. Киндл издание. п. 6.
^ Моборн, Джозеф Освальд (1914). Сложная проблема криптографии и ее решение . Форт Ливенвот, Канзас: Издательство школ армейской службы.
^ Фридман, Уильям (июнь 1942 г.). Полевые кодексы американской армии в американских экспедиционных войсках во время Первой мировой войны (PDF) . Военное министерство США. п. 4.
^ Гейнс 1956 , с. 201
^ Гейнс 1956 , с. 201
^ Гейнс 1956 , стр. 198–207.
^ Каррер-Бриггс, Ноэль (1987). «Некоторые из плохих родственников ультрас в Алжире, Тунисе, Сицилии и Италии». Разведка и национальная безопасность . 2 (2): 274–290. дои : 10.1080/02684528708431890 .
^ База данных кроссвордов слушателей

Ссылки

Гейнс, Хелен Фуше (1956) [1939], Криптоанализ / исследование шифров и их решений , Дувр, ISBN 0-486-20097-3
Смит, Майкл Станция X: Взломщики кодов из Блетчли-парка (1998, Channel 4 Books/Macmillan, Лондон) ISBN 0-7522-2189-2
Кан, Дэвид (1996), Взломщики кодов: Всеобъемлющая история секретной связи с Интернетом с древних времен , Scribner, ISBN 978-0684831305

Внешние ссылки

[1] Повторяющиеся буквы не допускаются, одна буква опущена (Q) или объединена (I/J), поэтому расчет равен 600 = 25×24.

[2] Взломщики кодов (1996) Дэвид Кан, Scribner Books от Simon & Schuster

[:0-3] Кристенсен, Крис (2006). «Полиграфические шифры» (PDF) . Университет Северного Кентукки, Крис Кристенсен . Проверено 9 января 2018 г.

[:1-4] Перейти обратно: ^а ^б Кан, Дэвид (1996). Взломщики кодов: всеобъемлющая история секретной связи с древних времен до Интернета . Скрибнер. ISBN 978-0684831305 .

[:2-5] Перейти обратно: ^а ^б Клима, Рик (2018). «Секретные коды во время Второй мировой войны» (PDF) . Аппалачский государственный университет, доктор Рик Клима . Архивировано из оригинала (PDF) 13 октября 2017 г. Проверено 9 января 2018 г.

[6] Рид, Томас Вемисс (1899). Мемуары и переписка Лиона Плейфэра: Первый лорд Плейфэр Сент-Эндрюса ... Харпер и братья. стр. 158–159.

[7] Лорд, Уолтер (2012). Одинокое бдение: Береговые стражи Соломоновых островов . Открытые дорожные медиа. Киндл издание. п. 6.

[8] «История безопасности связи в Новой Зеландии Эрика Могона» , глава 8

[9] «История обеспечения информации (IA)» . Бюро безопасности правительственной связи . Правительство Новой Зеландии. Архивировано из оригинала 12 ноября 2011 г. Проверено 24 декабря 2011 г.

[10] Лорд, Уолтер (2012). Одинокое бдение: Береговые стражи Соломоновых островов . Открытые дорожные медиа. Киндл издание. п. 6.

[11] Моборн, Джозеф Освальд (1914). Сложная проблема криптографии и ее решение . Форт Ливенвот, Канзас: Издательство школ армейской службы.

[12] Фридман, Уильям (июнь 1942 г.). Полевые кодексы американской армии в американских экспедиционных войсках во время Первой мировой войны (PDF) . Военное министерство США. п. 4.

[13] Гейнс 1956 , с. 201

[14] Гейнс 1956 , с. 201

[15] Гейнс 1956 , стр. 198–207.

[NCB-16] Каррер-Бриггс, Ноэль (1987). «Некоторые из плохих родственников ультрас в Алжире, Тунисе, Сицилии и Италии». Разведка и национальная безопасность . 2 (2): 274–290. дои : 10.1080/02684528708431890 .

[17] База данных кроссвордов слушателей

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]