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

Шифр Плейфера или квадрат Плейфера — ручная симметричная техника шифрования, в которой впервые использована замена биграмм. Изобретена в 1854 году английским физиком Чарльзом Уитстоном, но названа именем лорда Лайона Плейфера^[англ.], который внёс большой вклад в продвижение использования данной системы шифрования в государственной службе. Шифр предусматривает шифрование пар символов (биграмм) вместо одиночных символов, как в шифре подстановки и в более сложных системах шифрования Виженера. Таким образом, шифр Плейфера более устойчив к взлому по сравнению с шифром простой замены, так как усложняется его частотный анализ. Он может быть проведён, но не для символов, а для биграмм. Так как возможных биграмм больше, чем символов, анализ значительно более трудоёмок и требует большего объёма зашифрованного текста.

История

Несмотря на то, что шифр был изобретением Уитстона, он стал известен как шифр Плейфера. Его первое описание было зарегистрировано в документе, подписанном Уитстоном 26 марта 1854 года^[1]. Друг Уитстона лорд Лайон Плейфер рекомендовал этот шифр для использования высшими государственными и военными деятелями. Однако Министерство иностранных дел Великобритании отклонило этот документ из-за сложности его восприятия. Когда Уитстон предложил продемонстрировать, что трое из четырёх мальчиков в соседней школе научатся использовать этот шифр за пятнадцать минут, заместитель министра иностранных дел ответил: «Это очень возможно, но вы никогда не научите этому атташе»^[2].

Шифр использовался в тактических целях британскими вооружёнными силами во Второй Англо-Бурской войне и в Первой мировой войне, а также австралийцами и немцами во время Второй мировой войны. Причиной использования шифра Плейфера была его достаточная простота в применении и отсутствие необходимости в дополнительном специальном оборудовании. Основной целью использования этой системы шифрования была защита важной, но несекретной информации во время ведения боя. К тому времени, когда вражеские криптоаналитики взламывали сообщение, информация уже была бесполезна для них^[1]^[3].

Использование шифра Плейфера в настоящее время является нецелесообразным, поскольку современные компьютеры могут легко взломать шифр в течение нескольких секунд. Первый изданный алгоритм взлома шифра Плейфера был описан в 1914 году в брошюре объёмом 19 страниц Джозефом О. Моуборном^[англ.]^[3]^[4]^[5].

Описание шифра Плейфера

Шифр Плейфера использует матрицу 5х5 (для латинского алфавита, для кириллического алфавита необходимо увеличить размер матрицы до 4х8), содержащую ключевое слово или фразу. Для создания матрицы и использования шифра достаточно запомнить ключевое слово и четыре простых правила. Чтобы составить ключевую матрицу, в первую очередь нужно заполнить пустые ячейки матрицы буквами ключевого слова (не записывая повторяющиеся символы), потом заполнить оставшиеся ячейки матрицы символами алфавита, не встречающимися в ключевом слове, по порядку (в английских текстах обычно опускается символ «Q», чтобы уменьшить алфавит, в других версиях «I» и «J» объединяются в одну ячейку). Ключевое слово может быть записано в верхней строке матрицы слева направо, либо по спирали из левого верхнего угла к центру. Ключевое слово, дополненное алфавитом, составляет матрицу 5х5 и является ключом шифра^[6]^[7].

Для того чтобы зашифровать сообщение, необходимо разбить его на биграммы (группы из двух символов), например «Hello World» становится «HE LL OW OR LD», и отыскать эти биграммы в таблице. Два символа биграммы соответствуют углам прямоугольника в ключевой матрице. Определяем положения углов этого прямоугольника относительно друг друга. Затем, руководствуясь следующими 4 правилами^[6], зашифровываем пары символов исходного текста:

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

Для расшифровки необходимо использовать инверсию этих четырёх правил, откидывая символы «Х» (или «Q»), если они не несут смысла в исходном сообщении.

Иллюстрация правил

Предположим, что необходимо зашифровать биграмму OR. Рассмотрим 4 случая:

1)

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

OR заменяется на YZ

2)

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

OR заменяется на BY

3)

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

OR заменяется на ZX

4)

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

OR заменяется на ZY

Пример

Рассмотрим следующий пример^[8]. Пусть ключевым словом является WHEATSON, тогда получаем матрицу:

W	H	E	A	T
S	O	N	B	C
D	F	G	I	K
L	M	P	Q	R
U	V	X	Y	Z

Зашифруем сообщение «IDIOCY OFTEN LOOKS LIKE INTELLIGENCE». Для этого разобьём сообщение на биграммы:

ID IO CY OF TE NL OO KS LI KE IN TE LL IG EN CE

Так как седьмая биграмма содержит повторяющиеся буквы, то необходимо вставить X между ними:

ID IO CY OF TE NL OX OK SL IK EI NT EL LI GE NC E

Для того чтобы последний элемент стал биграммой, нужно добавить в конец X:

ID IO CY OF TE NL OX OK SL IK EI NT EL LI GE NC EX

Теперь применяя описанные выше правила шифруем каждую биграмму по очереди.

Текст: ID IO CY OF TE NL OX OK SL IK EI NT EL LI GE NC EX

Закрытый текст: KF FB BZ FM WA SP NV CF DU KD AG CE WP QD PN BS NE

Таким образом сообщение «IDIOCY OFTEN LOOKS LIKE INTELLIGENCE» преобразуется в «KFFBBZFMWASPNVCFDUKDAGCEWPQDPNBSNE».

Криптоанализ шифра Плейфера

Как и большинство шифров формальной криптографии, шифр Плейфера также может быть легко взломан, если имеется достаточный объём текста. Получение ключа является относительно простым, если известны шифрованный и обычный текст. Когда известен только зашифрованный текст, можно провести частотный анализ, но не для 26 возможных символов латинского алфавита, а для 25 ⋅ 24 = 600 возможных биграмм (одна из букв и биграммы из двух одинаковых букв исключаются). Криптоаналитики анализируют соответствие между частотой появления биграмм в зашифрованном тексте и известной частотой появления биграмм в языке, на котором написано сообщение^[8]^[9].

Впервые алгоритм взлома шифра Плейфера был описан в брошюре лейтенанта Джозефа О. Моуборнома в 1914 году^[3]^[4]. Позднее, в 1939 году, криптоанализ шифра был приведен в книге Х. Ф. Гейнс^[англ.] "Cryptanalysis - a study of ciphers and their solution"^[9]. Однако более подробное руководство для нахождения ключа для шифра Плейфера можно найти в главе 7 «Solution to polygrafic substitution systems» руководства Field Manual 34-40-2 Сухопутных Войск США.

Шифр Плейфера подобен шифру двух квадратов, хотя относительная простота системы шифрования Плейфера упрощает идентификацию текста. Примечательно, что биграмма шифра Плейфера и её инверсия (AB и BA) будет расшифрована как другая биграмма и её инверсия (RE и ER). В английском языке есть много слов, содержащих такие инверсные биграммы, например REceivER и DEpartED. Идентификация близко лежащих инверсных биграмм зашифрованного текста и нахождение им соответствий в списке известных слов исходного текста является одним из легких способов построения исходного текста и начала конструирования ключа^[8].

Существует другой подход к криптоанализу шифра Плейфера, который называется «поиск восхождением к вершине». Он основывается на матрице случайных символов. С помощью простейших итераций матрица случайных символов максимально приближается к оригинальной матрице. Очевидно, что этот метод слишком сложен для человека, но компьютеры с помощью данного алгоритма могут взломать данный шифр, даже имея небольшой объём текста. Другой отличительной особенностью шифра Плейфера от шифра с двумя квадратами является то, что в нём никогда не встречаются биграммы с повторяющимися символами (например ЕЕ). Если в шифрованном тексте отсутствуют биграммы с повторяющимися символами и его длина достаточно велика, то можно предположить, что исходный текст зашифрован шифром Плейфера^[3].

Немецкая армия, ВВС и полиция использовали двойную систему шифрования Плейфера во Второй мировой войне как шифр «среднего сорта». Они добавили второй квадрат, так как во время Первой мировой войны шифр Плейфера был взломан. Из этого квадрата брали второй символ каждой биграммы, не используя ключевое слово и помещая символы в произвольном порядке. Но и этот шифр был взломан в Блечли-парк, потому что немцы использовали один и тот же шаблон сообщения. В восьми сообщениях, зашифрованных двойным шифром Плейфера, были использованы числа от одного до двенадцати, это и дало возможность достаточно легко взломать его^[1]^[10].

Позднее были предприняты попытки усовершенствовать шифр при помощи использования матрицы 7x4 и добавлением символов «*» и «#». Несмотря на то, что анализ шифра усложнился, его все равно можно взломать теми же методами, что и первоначальный^[11].

Упоминания в культуре

В новелле «Have His Carcase^[англ.]» автора Дороти Сэйерc приведено детальное описание механизма шифрования методом Плейфера, а также и пошаговое руководство для его криптоанализа.
В книге «The Trojan Horse» автора Хэммонда Иннеса шифр Плейфера используется для сокрытия формулы нового высокопрочного сплава.
В фильме «Сокровище нации: Книга тайн» ключ от сокровищ закодирован шифром Плейфера.

Примечания

↑ ¹ ² ³ Bauer, 1997, pp. 61-63.
↑ Singh, 2000, pp. 377-378.
↑ ¹ ² ³ ⁴ Bauer, 2013, pp. 166-178.
↑ ¹ ² Mauborgne, 1914.
↑ Joseph Oswald, An Advanced Problem in Cryptography and Its Solution (Fort Leavenwoth, Kansas: Army Service Schools Press, 1914)
↑ ¹ ² Stallings, 2011, pp. 44-46.
↑ Tilborg, 2000, pp. 20.
↑ ¹ ² ³ Klima, Sigmon, 2013, pp. 26-29.
↑ ¹ ² Gaines, 1956, pp. 198-207.
↑ Smith, 1998, pp. 74-75.
↑ Alam, Khalid, Salam, 2013.