Шифр Плейфера (), известный также как Шифр Уитстона — Плейфера () или квадрат Плейфера () — ручная симметричная техника шифрования, основанная на замене биграмм. Шифр изобретён в 1854 году английским физиком Чарльзом Уитстоном, но получил название в честь лорда , который внёс большой вклад в продвижение использования этого шифра в государственной службе. Шифр использовался британскими вооружёнными силами в ряде войн и локальных конфликтов. Одним из первых криптоанализ шифра Плейфера осуществил в 1914 году лейтенант Армии США Джозеф О. Моборн.
Шифр Плейфера предусматривает шифрование не одиночных символов, как в шифре подстановки или более сложных системах шифрования Виженера, а пар символов (биграмм). В качестве ключа для этого шифра используется матрица (таблица) размером 5 × 5, в которую вписывается предварительно выбранное слово, повторяющиеся буквы которого опускаются. Вслед за этим словом в остальные ячейки матрицы вписываются оставшиеся буквы английского алфавита. Исходное сообщение предварительно делится на биграммы, и каждая из этих биграмм преобразуется — буква каждой из биграмм заменяется на другую по определённым правилам с помощью ключа. Подобный шифр более устойчив к взлому по сравнению с шифром простой замены: частотный анализ усложняется в связи с применением биграмм, число вариантов которых намного больше, чем символов; также для успешного криптоанализа требуется больший объём зашифрованного текста.
Создание шифра
Фактическим разработчиком этого шифра был британский физик сэр Чарльз Уитстон, который был известен тем, что изобрёл систему электрического телеграфа ещё до того, как современную систему телеграфа запатентовал Самюэль Морзе. Однако название шифру было дано по имени лорда Лайона Плейфера, популяризовавшего подобный способ шифрования информации. Согласно одной из версий, выдвигаемой Крисом Кристенсеном, впервые шифр был продемонстрирован высшему британскому руководству в январе 1854 года: на ужине, организованном лордом-председателем Совета Гренвилем, присутствовали муж королевы Виктории принц Альберт, будущий премьер-министр Палмерстон и непосредственно сам лорд Плейфер. Последний описал Палмерстону суть системы шифрования, а через несколько дней, находясь в Дублине, получил от Палмерстона и Гренвиля зашифрованные подобным методом письма.
Первое официальное описание этого шифра было зарегистрировано в документе, подписанном Чарльзом Уитстоном 26 марта 1854 года. Плейфер, друг Уитстона, рекомендовал этот шифр к использованию высшими государственными и военными деятелями, но Министерство иностранных дел Великобритании отклонило эту идею из-за сложности восприятия, поскольку негативно относилось к сложным по их меркам шифрам. Уитстон выразил готовность продемонстрировать чиновникам простоту шифра — он сказал, что трое из четырёх мальчиков в соседней школе научатся использовать этот шифр за пятнадцать минут. В ответ на это заместитель министра иностранных дел заявил, что Уитстон никогда не сможет научить этому кого-либо из британских атташе. Тем не менее, британское военное министерство всё же втайне приняло эту систему.
Согласно Крэйгу П. Бауэру, подобный шифр стал первым биграммным шифром, который не требовал напрямую от шифровальщика записывать ключ и держать его при себе, чтобы иметь возможность зашифровывать и расшифровывать сообщения.
Общие характеристики шифра Шифр Плейфера классифицируется как полиграммный подстановочный шифр, при использовании которого текст делится на пары или тройки символов, которые заменяются другими парами или тройками символов по определённым правилам. Он использует матрицу 5 × 5, содержащую ключевое слово или фразу — по сути матрица, содержащая ключевое слово и остальную часть алфавита, и представляет собой ключ всего шифра. Для создания матрицы нужно выбрать ключевое слово и заполнить его буквами верхние ячейки матрицы, не записывая повторы символов, а оставшиеся ячейки заполнить по порядку символами алфавита, не встречающимися в ключевом слове. Оптимальным ключевым словом является именно такое слово, каждая буква которого встречается ровно один раз.
При шифровании текста на английском языке обычно буквы «I» и «J» объединяются в одну ячейку и считаются за одну букву. Как правило, из окончательной таблицы опускается буква «J», хотя иногда для сокращения символов до 25 может опускаться буква «Q». Ключевое слово обычно записывается в верхней строке матрицы слева направо по горизонтали с переходом на следующую строчку. Однако возможно сделать это и другим способом — например, записывать слово справа налево; начинать его запись не с верхней строки, а с самой нижней; указывать первую букву не в первом столбце, а в четвёртом или комбинировать какие-то из вышеперечисленных способов. Теоретически при использовании всех 26 букв английского алфавита можно получить 676 различных вариантов матриц размера 5 × 5.
Процедура шифрования Чтобы зашифровать сообщение, его необходимо разделить на биграммы (группы из двух символов) и отыскать эти биграммы в таблице. Два символа биграммы соответствуют углам прямоугольника в ключевой матрице. Нужно определить положения углов этого прямоугольника относительно друг друга, а затем зашифровать все пары символов, руководствуясь определёнными правилами. Основными тремя правилами являются следующие:
Если символы биграммы исходного текста встречаются в одной строке, то эти символы замещаются на символы, расположенные в ближайших столбцах справа от соответствующих символов. Если символ является последним в строке, то он заменяется на первый символ этой же строки. Если символы биграммы исходного текста встречаются в одном столбце, то они преобразуются в символы того же столбца, находящиеся непосредственно под ними. Если символ является нижним в столбце, то он заменяется на первый символ этого же столбца. Если символы биграммы исходного текста находятся в разных столбцах и разных строках, то они заменяются на символы, находящиеся в тех же строках, но противоположных столбцах. Визуально через координаты должен проходить прямоугольник, углам которого соответствуют эти четыре символа. Математически это может интерпретироваться как произведение отображений; также этот шаг называют «перекрещиванием».
Предположим, что создана матрица 5 × 5, в основе которой лежит ключевое слово CULPER. Ниже приводятся примеры шифрования трёх разных биграмм.
Изначальная матрица C U L P E R A B D F G H I K M N O Q S T V W X Y Z Ключевое слово — CULPER В одном столбце * U * * * * A * * * * H * * * * O * * *
HA → OH, WA → UH В одной строке
N * Q S T
OS → QT, ST → TN Формируют прямоугольник * U L * * * A B * *
BU → AL (не LA)
Иногда выделяется и четвёртое правило шифрования, которое признаётся не всеми авторами, так как реализуется непосредственно перед заменой символов. Если биграмма содержит две одинаковые буквы (или если в данной биграмме не хватает одного символа), то после её первого символа нужно поставить символ-разделитель (null), чтобы новая пара символов могла быть формально готовой для зашифровки. Как правило, в роли разделителя служит буква «Х», хотя допускается использование букв «Y», «Z» или «Q». Разделитель не ставится, если сдвоенные буквы содержатся в разных биграммах. При шифровании слова balloon разделение на биграммы потребует добавления X между двумя буквами l, и на выходе будут биграммы BA LX LO ON. Добавление разделителя необходимо каждый раз, когда при делении на биграммы остаётся хотя бы одна биграмма с одинаковыми символами: фраза LESS SEVEN после разделения на биграммы и добавления нескольких разделителей X получит итоговый вид LE SX SX SE VE NX.
Зашифрованное сообщение передаётся группами по пять символов. Пробелы не отмечаются ни в исходном тексте, ни в зашифрованном. Для расшифровки сообщения получатель, имеющий при себе ключ-матрицу, самостоятельно делит шифртекст на биграммы и выполняет указанные выше операции в обратном порядке, опираясь на имеющуюся у него матрицу 5 × 5. Это значит, что буквы из одной биграммы, находящиеся в одной строке, меняются на буквы, стоящие левее, и т. д.. Единственной возможной трудностью для получателя может стать выбор между буквами I и J при расшифровке, однако выбор буквы для восстановления исходного сообщения здесь зависит исключительно от контекста. При использовании всех 26 букв английского алфавита для шифрования биграмм теоретически возможно составить всего 26 × 26 = 676 различных биграмм вне зависимости от ключевого слова.
Математические характеристики шифра Обозначим созданную матрицу как , шифруемую биграмму как с координатами первого символа и второго . Для описанных выше правил можно формально описать шифрование с получаемой на выходе биграммой: символы формируют прямоугольник — биграмма (, ), если символы в одной строке — биграмма (, ), если символы в одном столбце — биграмма (, ), если
Комбинаторная сложность перебора класса методов для шифра Плейфера — .
Информация о классе методов приблизительно равна 79,038 бит; десятичный логарифм составляет примерно 237,93 .
Расстояние единственности для данного шифра составляет 22,69 символов (то есть для сообщения размером больше 23 символов есть возможность однозначно определить ключ шифрования и восстановить открытый текст).
Примеры
Пример 1 Пример Джозефа Моборна. Пусть ключевым словом является GRANT, тогда мы составим соответствующую матрицу:
G R A N TB C D E FH I/J K L MO P Q S UV W X Y Z
Имеем следующий открытый текст «THE ENEMY MOVES AT DAWN». Используя озвученные выше правила шифрования, преобразуем открытый текст в биграммы:
TH EX EN EM YM OV ES AT DA WN
Используя соответствующие правила, на выходе получим шифртекст:
GM DY LE FL ZL VG LY NG KD YR
Пример 2 Пример Уильяма Фридмана. Примем в качестве ключевого слова CLIQUE, буквы I и J считаем как одну. Составим следующую матрицу 5 × 5:
C L I/J Q UE A B D FG H K M NO P R S TV W X Y Z
В качестве исходного сообщения имеется «Local attacks of the enemy north of 'Lens' have been repelled». Разделим его на биграммы, используя в качестве разделителя X:
LO CA LA TX TA CK SO FT HE EN EM YN OR TH OF LE NS HA VE BE EN RE PE LX LE DX
Следуя трём озвученным правилам, произведём замены элементов биграмм и получим новый набор биграмм:
CP LE AH RZ PF IG TP NZ GA FG DG ZM PS PN TE CA MT PH CG DA FG OB OA IW CA BY
Поскольку передача зашифрованного подобным образом сообщения производится группами по 5 символов, при передаче оно обретёт следующий вид:
CPLEA HRZPF IGTPN ZGAFG DGZMP SPNTE CAMTP HCGDA FGOBO AIWCA BY
Пример 3 Пример . Пусть ключевым словом является . Получим следующую матрицу 5 × 5 в качестве ключа (буквы I и J считаются как одна, поэтому в таблицу впишем I):
C U L P ER A B D FG H I K MN O Q S TV W X Y Z
Для зашифровки выберем текст «Send diamonds to Amsterdam monday week without fail». Разобьём его на биграммы, разместив X между двумя одинаковыми буквами, а недостающую биграмму в конце текста дополним X. Получим на выходе следующий набор биграмм:
SE ND DI AM ON DS TO AM ST ER DA MX MO ND AY WE EK WI TH OU TF AI LX
Опираясь на указанные правила, произведём замены элементов биграмм и получим следующий шифртекст:
TP SR BK FH QO KY NQ FH TN CF FB IZ HT SR DW ZU PM XH OM WA ZM BH BL
Пример 4 Пример Криса Кристенсена. Пусть ключевым словом будет GALOIS. Составим матрицу 5 × 5, вписав в первые шесть элементов указанный ключ:
G A L O I/JS B C D EF H K M NP Q R T UV W X Y Z
В качестве исходного сообщения выберем «COMSEC means communications security». Разобьём его на биграммы, используя X в качестве разделителя между двумя одинаковыми буквами в биграмме (в данном случае возможно использовать и букву Q в качестве альтернативы). Получим на выходе следующую последовательность биграмм:
CO MS EC ME AN SC OM MU NI CA TI ON SX SE CU RI TY
Опираясь на озвученные выше правила, произведём замену элементов каждой биграммы в соответствии с элементами таблицы. Если соединить все биграммы в одно цельное слово (без пробелов), то на выходе получится следующий текст: