.png/1280px-Playfair_Cipher_01_HI_to_BM_(cropped).png)
Шифр Плейфера или квадрат Плейфера или шифр Уитстона–Плейфера — это метод ручного симметричного шифрования , который был первым шифром замены литеральных диграмм . Схема была изобретена в 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]
Шифр Плейфера использует таблицу 5*5, содержащую ключевое слово или фразу . Запоминание ключевого слова и 4 простых правил — все, что требовалось для создания таблицы 5 на 5 и использования шифра.
Чтобы создать таблицу ключей, сначала нужно заполнить пробелы в таблице (модифицированный квадрат Полибия ) буквами ключевого слова (отбросив все повторяющиеся буквы), затем заполнить оставшиеся пробелы остальными буквами алфавита по порядку (обычно опуская «J» или «Q», чтобы уменьшить алфавит; другие версии помещают и «I», и «J» в одно и то же пространство). Ключ может быть записан в верхних строках таблицы слева направо или в каком-либо другом порядке, например, в виде спирали, начинающейся в верхнем левом углу и заканчивающейся в центре. Ключевое слово вместе с соглашениями по заполнению таблицы 5 на 5 составляют ключ шифра.
Чтобы зашифровать сообщение, нужно разбить его на диграммы (группы из 2 букв) так, чтобы, например, «HelloWorld» стало «HE LL OW OR LD». Эти диграммы будут заменены с использованием таблицы ключей. Поскольку для шифрования требуются пары букв, сообщения с нечетным количеством символов обычно добавляют необычную букву, например «X», чтобы завершить окончательную диграмму. Две буквы диграммы считаются противоположными углами прямоугольника в таблице ключей. Чтобы выполнить замену, примените следующие 4 правила по порядку к каждой паре букв в открытом тексте:
Для расшифровки используйте обратное (противоположное) из двух правил сдвига, выбирая букву слева или вверх по мере необходимости. Последнее правило остается неизменным, так как преобразование переключает выбранные буквы прямоугольника на противоположную диагональ, а повтор преобразования возвращает выбор в исходное состояние. Первое правило можно отменить, только отбросив любые дополнительные экземпляры выбранной вставной буквы — обычно «X» или «Q» — которые не имеют смысла в конечном сообщении после завершения.
Существует несколько незначительных вариаций [ какие? ] оригинального шифра Плейфера. [13]
Используя «пример Плейфэра» в качестве ключа (предполагая, что I и J взаимозаменяемы), таблица становится такой (пропущенные буквы выделены красным):
Первый шаг шифрования сообщения «спрячь золото в пне» — преобразовать его в пары букв «HI DE TH EG OL DI NT HE TR EX ES TU MP» (с нулевым «X», используемым для разделения повторяющихся «E»). Затем:
Таким образом, сообщение «спрячь золото в пне» становится «BM OD ZB XD NA BE KU DM UI XM MO UV IF», что можно переформулировать как «BMODZ BXDNA BEKUD MUIXM MOUVI F» для удобства чтения зашифрованного текста.
Предположим, что нужно зашифровать диграмму OR. Существует пять общих случаев:
Как и большинство классических шифров, шифр Плейфера может быть легко взломан, если имеется достаточно текста. Получение ключа относительно просто, если известны как открытый текст, так и шифротекст . Когда известен только шифротекст, криптоанализ шифра методом грубой силы включает поиск в ключевом пространстве совпадений между частотой появления диграмм (пар букв) и известной частотой появления диграмм в предполагаемом языке исходного сообщения. [14]
Криптоанализ Playfair похож на криптоанализ четырехквадратных и двухквадратных шифров, хотя относительная простота системы Playfair упрощает идентификацию возможных строк открытого текста. В частности, диграф Playfair и его обратный вариант (например, AB и BA) будут расшифровываться в тот же шаблон букв в открытом тексте (например, RE и ER). В английском языке есть много слов, которые содержат эти обратные диграфы, такие как REceivER и DEpartED. Идентификация близлежащих обратных диграфов в зашифрованном тексте и сопоставление шаблона со списком известных слов открытого текста, содержащих шаблон, является простым способом генерации возможных строк открытого текста, с которых можно начать построение ключа.
Другой подход к решению проблемы шифра Playfair — метод «взбирания на холм дробовиком» . Он начинается со случайного квадрата букв. Затем вносятся незначительные изменения (например, переключение букв, строк или отражение всего квадрата), чтобы увидеть, больше ли открытый текст-кандидат похож на стандартный открытый текст, чем до изменения (возможно, путем сравнения биграмм с известной диаграммой частот). Если новый квадрат считается улучшением, то он принимается и затем подвергается дальнейшей мутации, чтобы найти еще лучшего кандидата. В конце концов, обнаруживается, что открытый текст или что-то очень близкое к нему достигает максимального балла по любому выбранному методу оценки. Очевидно, что это выходит за рамки обычного человеческого терпения, но компьютеры могут использовать этот алгоритм для взлома шифров Playfair с относительно небольшим объемом текста.
Другим аспектом Playfair, который отделяет его от четырех- и двухквадратных шифров, является тот факт, что он никогда не будет содержать двухбуквенную диграмму, например EE. Если в шифртексте нет двухбуквенных диграмм, а длина сообщения достаточно велика, чтобы сделать это статистически значимым, весьма вероятно, что метод шифрования — Playfair.
Хороший учебник по восстановлению ключа для шифра Playfair можно найти в главе 7, "Решение систем полиграфической замены", Полевого руководства 34-40-2 , выпущенного армией США. Другой криптоанализ шифра Playfair можно найти в главе XXI книги Хелен Фуше Гейнс " Криптоанализ / исследование шифров и их решений ". [15]
Подробный криптоанализ Playfair проводится в главе 28 детективного романа Дороти Л. Сэйерс Have His Carcase . В этой истории показано, что сообщение Playfair является криптографически слабым, поскольку детектив способен разгадать весь ключ, сделав лишь несколько догадок относительно форматирования сообщения (в данном случае, что сообщение начинается с названия города, а затем даты). Книга Сэйерс включает в себя подробное описание механики шифрования Playfair, а также пошаговый отчет о ручном криптоанализе.
Немецкая армия, военно-воздушные силы и полиция использовали двойной шифр Плейфера в качестве шифра средней степени сложности во время Второй мировой войны, основанный на британском шифре Плейфера, который они взломали в начале Первой мировой войны. [16] Они адаптировали его, введя второй квадрат, из которого выбиралась вторая буква каждой биграммы, и отказались от ключевого слова, разместив буквы в случайном порядке. Но с немецкой любовью к формальным сообщениям они были взломаны в Блетчли-парке . Сообщениям предшествовал последовательный номер, а числа были написаны прописью. Поскольку немецкие числа от 1 (eins) до двенадцати (zwölf) содержат все буквы в двойных квадратах Плейфера, кроме восьми, формальный трафик было относительно легко взломать (Смит, стр. 74-75)
Расширенные тематические криптографические кроссворды, такие как « Кроссворд слушателя» (опубликованный в субботнем выпуске британской газеты The Times ), иногда включают шифры Плейфера. [17] Обычно в сетку необходимо ввести от четырех до шести ответов в коде, а ключевая фраза Плейфера тематически важна для окончательного решения.
Шифр хорошо подходит для кроссвордов, потому что открытый текст находится путем решения одного набора подсказок, в то время как шифртекст находится путем решения других. Затем решатели могут построить таблицу ключей, соединив биграммы (иногда можно угадать ключевое слово, но никогда не обязательно).
Использование шифра Плейфера обычно объясняется в преамбуле к кроссворду. Это уравнивает шансы тех решателей, которые ранее не сталкивались с этим шифром. Но способ использования шифра всегда один и тот же. Используемый 25-буквенный алфавит всегда содержит Q и имеет совпадающие I и J. Таблица ключей всегда заполняется строка за строкой.