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

Чарльз Вітстон

Шифр Плейфера або квадрат Плейфера — ручна симетрична техніка шифрування, в якій вперше використано заміну біграм. Шифр у 1854 році винайшов англійський фізик Чарльз Вітстон, але він отримав ім'я лорда Лайона Плейфера, який просував використання цієї системи у державній службі. Цей метод передбачає шифрування пар символів (біграм) замість одиночних символів, як у шифрі підстановки й у більш складних системах шифрування Віженера. Через це шифр Плейфера стійкіший до злому методом частотного аналізу. Знаходження закономірності розподілу 26 х 26 = 676 можливих біграм потребує суттєво більших зусиль і обсягу зашифрованого тексту, ніж для 26 монограм (літер латинського алфавіту).

Історія

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

Незважаючи на те, що шифр був винаходом Вітстона, він став відомий як шифр Плейфера. Його перший опис зареєстровано в документі, підписаному Вітстоном 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 році[7]. Пізніше, в 1939 році, криптоаналіз шифру був наведений в книзі Х. Ф. Гейнс «Cryptanalysis — a study of ciphers and their solution»[7]. Однак більш докладний посібник для знаходження ключа для шифру Плейфера можна знайти в розділі 7 «Solution to polygrafic substitution systems» керівництваField Manual 34-40-2 [Архівовано 3 квітня 2019 у Wayback Machine.] Сухопутних Військ США.

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

Існує інший підхід до криптоанаіизу шифру Плейфера, за допомогою Алгоритм сходження на вершину. Він починається із матриці випадкових символів. За допомогою найпростіших ітерацій матриця випадкових символів максимально наближається до оригінальної матриці. Очевидно, що цей метод дуже складний для людини, але комп'ютери за допомогою такого алгоритму можуть зламати шифр, навіть маючи невеликий обсяг тексту.

Шифр Плейфера можна відрізнити від шифру двох квадратів за тою ознакою, що в ньому ніколи не зустрічаються біграми з повторюваними символами (наприклад ЇЇ). Якщо в зашифрованому тексті відсутні біграми з повторюваними символами і його довжина досить велика, то можна припустити, що вихідний текст зашифрований шифром Плейфера[7].

Німецька армія, ВВС і поліція використовували подвійну систему шифрування Плейфера у Другій світовій війні як шифр «середнього ґатунку». Вони додали другий квадрат, оскільки під час Першої світової війни шифр Плейфера був зламаний. З цього квадрата брали другий символ кожної біграми, не використовуючи ключове слово й поміщаючи символи в довільному порядку. Але і цей шифр був зламаний в Блечлі-парку, тому що німці використовували один і той же шаблон повідомлення. У восьми повідомленнях, зашифрованих подвійним шифром Плейфера, були використані числа від одного до дванадцяти записані літерами, це і дало можливість досить легко зламати його[1][9].

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

Згадки в культурі

Посилання

Примітки

  1. ↑ а б в 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
  3. ↑ а б Craig P. Bauer Secret History: The Story of Cryptology
  4. ↑ Mauborgne, Joseph Oswald, An Advanced Problem in Cryptography and Its Solution (Fort Leavenwoth, Kansas: Army Service Schools Press, 1914).
  5. ↑ а б William Stallings Cryptography and Network Security: Principles and Practice
  6. ↑ Henk CA van Tilbor Fundamentals of Cryptology: A Professional Reference and Interactive Tutorial
  7. ↑ а б в г д е Richard E. Klima, Neil P. Sigmon Cryptology: Classical and Modern with Maplets
  8. ↑ Helen Fouché Gaines Cryptanalysis — a study of ciphers and their solution
  9. ↑ Michael Smith Station X: The Codebreakers of Bletchley Park
  10. ↑ A. Aftab Alam, B. Shah Khalid, and C. Muhammad Salam A Modified Version of Playfair Cipher Using 7 × 4 Matrix

Література

  • Friedrich L.Bauer Decrypted Secrets: Methods and Maxims of Cryptolog, Springer, 1997
  • William Stallings Cryptography and Network Security: Principles and Practice, Pearson,2011
  • Henk C.A. van Tilbor Fundamentals of Cryptology: A Professional Reference and Interactive Tutoriale, Kluwer Academic Publishers,2000