Эта статья входит в число добротных статей

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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Шифр Playfair»)
Перейти к: навигация, поиск

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

История[править | править вики-текст]

Лорд Лайон Плейфер

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

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

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

Описание шифра Плейфера[править | править вики-текст]

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

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

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

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

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

4. Если символы биграммы исходного текста находятся в разных столбцах и разных строках, то они заменяются на символы, находящиеся в тех же строках, но соответствующие другим углам прямоугольника.

Для расшифровки необходимо использовать инверсию этих четырёх правил, откидывая символы «Х» (или «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

Пример[править | править вики-текст]

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

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».

Криптоанализ шифра Плейфера[править | править вики-текст]

Как и большинство шифров формальной криптографии, шифр Плейфера также может быть легко взломан, если имеется достаточный объём текста. Получение ключа является относительно простым, если известны шифрованный и обычный текст. Когда известен только зашифрованный текст, криптоаналитики анализируют соответствие между частотой появления биграмм в зашифрованном тексте и известной частотой появления биграмм в языке, на котором написано сообщение[7][8].

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

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

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

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

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

Упоминания в культуре[править | править вики-текст]

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

Примечания[править | править вики-текст]

  1. 1 2 3 Friedrich L.Bauer «Decrypted Secrets: Methods and Maxims of Cryptology» — p.61-63
  2. Simon Singh. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. — Anchor, 2000. — С. 377-378. — 410 с. — ISBN 0-385-49532-3.
  3. 1 2 3 4 Craig P. Bauer. Secret History: The Story of Cryptology. — CRC Press, 2013. — С. 166-178. — 575 с. — ISBN 978-1-4665-6187-8.
  4. 1 2 Mauborgne, Joseph Oswald, An Advanced Problem in Cryptography and Its Solution (Fort Leavenwoth, Kansas: Army Service Schools Press, 1914).
  5. 1 2 William Stallings. Cryptography and Network Security: Principles and Practice. — 5. — Pearson, 2011. — С. 44-46. — ISBN 978-0-13-609704-4.
  6. Henk C.A. van Tilbor. Fundamentals of Cryptology: A Professional Reference and Interactive Tutorial. — Kluwer Academic Publishers, 2000. — С. 20. — ISBN ISBN 0-792-38675-2.
  7. 1 2 3 Richard E. Klima, Neil P. Sigmon. Cryptology: Classical and Modern with Maplets. — CRC Press, 2013. — С. 26-29. — 534 с. — ISBN 978-1-4665-6904-1.
  8. 1 2 Helen Fouché Gaines. Cryptanalysis - a study of ciphers and their solution. — Dover, 1956. — С. 198-207. — ISBN ISBN 0-486-20097-3.
  9. Michael Smith. Station X: The Codebreakers of Bletchley Park. — Channel 4 Books/Macmillan, 1998. — С. 74-75. — ISBN 0-7522-2189-2.
  10. A. Aftab Alam, B. Shah Khalid, and C. Muhammad Salam A Modified Version of Playfair Cipher Using 7×4 Matrix (англ.) // International Journal of Computer Theory and Engineering. — 2013. — Август (т. 5, № 4). — С. 626-628.

Литература[править | править вики-текст]

  • Friedrich L.Bauer. Decrypted Secrets: Methods and Maxims of Cryptolog. — Springer, 1997. — P. 61-65. — 448 p. — ISBN 978-3-662-03454-5.
  • William Stallings. Cryptography and Network Security: Principles and Practice. — Pearson, 2011. — P. 44-46. — 711 p. — ISBN 978-0-13-609704-4.
  • Henk C.A. van Tilbor. Fundamentals of Cryptology: A Professional Reference and Interactive Tutoriale. — Kluwer Academic Publishers, 2000. — P. 20. — 500 p. — ISBN 0-792-38675-2.
  • Craig P. Bauer. Secret History: The Story of Cryptology. — CRC Press, 2013. — P. 166-178. — 575 p. — ISBN 978-1-4665-6187-8.
  • Бабаш А. В., Шанкин Г. П. 1 // История криптографии. — СОЛОН-ПРЕСС, 2007. — С. 95-96. — 512 с. — ISBN 5-93455-135-3.