Опис шифру Плейфера
1. Шифр Плейфера: алгоритм і приклади
Нехай у нас є якийсь алфавіт і якесь ключове слово, а також задані розміри майбутньої таблиці. Складаємо таблицю наступним чином. Спочатку виписуємо через порядково букви ключового слова. З одним "але": якщо поточна буква вже потрапила в таблицю, другий раз її не вносити. Потім по порядку дописуємо букви алфавіту, пропускаючи ті, що були в ключовому слові.
Припустимо, наш алфавіт складається з 25 англійських букв, крім J. Ключове слово - DEVELOPER. Тоді виходить ось що:
Букви D, E, V сміливо пишемо - їх точно ще не було в таблиці. Четверта буква слова DEVELOPER вже була - не пишемо і т.д. Оскільки E зустрічається тричі, слово DEVELOPER "дасть" тільки 7 заповнених клітин таблиці. Тепер алфавіт. A, B, C ще не траплялися = їх немає в ключовому слові, на відміну від D. Тому D не пишемо - вона вже є в таблиці.
Тепер виникає питання, як шифрувати і розшифровувати. Використовуються біграми - поєднання з двох букв. Нехай s1, c1 - рядок і стовпець першої літери, s2, c2 - другий. Нехай S - число рядків таблиці, C - стовпців.
Зашифруємо слово PROPERTY. Ділимо на біграми: PR OP ER TY. P і R в одному рядку, тому замість кожної з цих букв беремо по суті правого сусіда (правило 1). Отримуємо RA. З OP так не пройде - тут і рядки, і стовпці різні. Беремо правило 3. Отримуємо DC. E і R в одному стовпці. Беремо сусідів знизу (правило 2). Отримуємо RG. TY замінюється на SZ - правило 3. Підсумок - RADCRGSZ. Якось не зовсім схоже на PROPERTY.
А що робити, якщо слів кілька і потрібні пропуски? Або ще якісь знаки пунктуації? Включити їх в алфавіт. Тільки один момент важливий - якщо в алфавіті кількість символів дорівнює простому числу (наприклад, 23, 31, 43), то доведеться ще щось додавати, інакше не можна скласти ніякої прямокутної таблиці.
Також зауважимо: якщо відомий алфавіт, досить задати лише один розмір таблиці - другий буде дорівнювати відношенню кількості символів в алфавіті до першого розміру.
Якщо в тексті непарна кількість символів, доведеться додати щось в кінець.
Нарешті, самий неприємний момент: що робити, якщо в біграмі однакові символи? Потрібно щось додати попереду цього рядка, щоб ці два символи потрапили в різні біграми. Наприклад, потрібно зашифрувати слово ТЕРРОР (ТЕ РР ОР). Як бачимо, є біграма РР. Це погано. Поставимо перед ним точку або пробіл (головне, щоб вони були включені в алфавіт). Отримуємо _ТЕРРОР. Непарне число символів. Тепер ставимо пробіл ще й в кінці. Отримуємо _ТЕРРОР_ (_Т ЕР РО Р_). Тепер проблем немає.
Є випадки складніші. Наприклад, АФФИННЫЕ ПРОСТРАНСТВА. Заважає біграма НН. Якщо перед словом АФФИННЫЕ ПРОСТРАНСТВА ставимо пробіл, заважає ФФ. Інший приклад: www.secretdomen.ru. Тут взагалі три однакових символи поспіль - як їх не змістити, все одно буде біграма ww. Тут потрібні хитрощі кращі. Як варіант - перед кожною "паршивою" біграмою ставити рідкісний символ. Тоді хоч поставте в одному рядку 10 поєднань з двох однакових букв і ще 100 з п'яти, програма пробіжить по рядку і все виправить. Ось тільки неестетично зовсім... Але розібрати можна. Так, замість тексту "АФФИННЫЕ_ПРОСТРАНСТВА" вийде "АФФИ.ННЫЕ_ПРОСТРАНСТВА".
Припустимо, наш алфавіт складається з 25 англійських букв, крім J. Ключове слово - DEVELOPER. Тоді виходить ось що:
| D | E | V | L | O |
| P | R | A | B | C |
| F | G | H | I | K |
| M | N | Q | S | T |
| U | W | X | Y | Z |
Букви D, E, V сміливо пишемо - їх точно ще не було в таблиці. Четверта буква слова DEVELOPER вже була - не пишемо і т.д. Оскільки E зустрічається тричі, слово DEVELOPER "дасть" тільки 7 заповнених клітин таблиці. Тепер алфавіт. A, B, C ще не траплялися = їх немає в ключовому слові, на відміну від D. Тому D не пишемо - вона вже є в таблиці.
Тепер виникає питання, як шифрувати і розшифровувати. Використовуються біграми - поєднання з двох букв. Нехай s1, c1 - рядок і стовпець першої літери, s2, c2 - другий. Нехай S - число рядків таблиці, C - стовпців.
- Якщо s1 = s2, то позиції букв шифрованого комбінації обчислюються так: для першої (s1, (c1 + 1) mod C), для другої (s2, (c2 + 1) mod C), де (x, y) означає, що буква знаходиться в стовпці y рядка x. Нумерація рядків і стовпців ведеться з нуля, рядків - зверху вниз, стовпців - зліва направо.
- Якщо c1 = c2, то для першої ((s1 + 1) mod S, c1), для другої ((s2 + 1) mod S, c2).
- Якщо ж обидва попередніх умови невірні, то для першої (s1, c2), для другої (s2, c1). І найцікавіше, що в цьому випадку расшірованіе ведеться ТАК САМО. У двох попередніх же користуємося таким нехитрим властивістю: якщо x2 = (x1 + d) mod n, то x1 = (x2 - d + n) mod n.
Зашифруємо слово PROPERTY. Ділимо на біграми: PR OP ER TY. P і R в одному рядку, тому замість кожної з цих букв беремо по суті правого сусіда (правило 1). Отримуємо RA. З OP так не пройде - тут і рядки, і стовпці різні. Беремо правило 3. Отримуємо DC. E і R в одному стовпці. Беремо сусідів знизу (правило 2). Отримуємо RG. TY замінюється на SZ - правило 3. Підсумок - RADCRGSZ. Якось не зовсім схоже на PROPERTY.
А що робити, якщо слів кілька і потрібні пропуски? Або ще якісь знаки пунктуації? Включити їх в алфавіт. Тільки один момент важливий - якщо в алфавіті кількість символів дорівнює простому числу (наприклад, 23, 31, 43), то доведеться ще щось додавати, інакше не можна скласти ніякої прямокутної таблиці.
Також зауважимо: якщо відомий алфавіт, досить задати лише один розмір таблиці - другий буде дорівнювати відношенню кількості символів в алфавіті до першого розміру.
Якщо в тексті непарна кількість символів, доведеться додати щось в кінець.
Нарешті, самий неприємний момент: що робити, якщо в біграмі однакові символи? Потрібно щось додати попереду цього рядка, щоб ці два символи потрапили в різні біграми. Наприклад, потрібно зашифрувати слово ТЕРРОР (ТЕ РР ОР). Як бачимо, є біграма РР. Це погано. Поставимо перед ним точку або пробіл (головне, щоб вони були включені в алфавіт). Отримуємо _ТЕРРОР. Непарне число символів. Тепер ставимо пробіл ще й в кінці. Отримуємо _ТЕРРОР_ (_Т ЕР РО Р_). Тепер проблем немає.
Є випадки складніші. Наприклад, АФФИННЫЕ ПРОСТРАНСТВА. Заважає біграма НН. Якщо перед словом АФФИННЫЕ ПРОСТРАНСТВА ставимо пробіл, заважає ФФ. Інший приклад: www.secretdomen.ru. Тут взагалі три однакових символи поспіль - як їх не змістити, все одно буде біграма ww. Тут потрібні хитрощі кращі. Як варіант - перед кожною "паршивою" біграмою ставити рідкісний символ. Тоді хоч поставте в одному рядку 10 поєднань з двох однакових букв і ще 100 з п'яти, програма пробіжить по рядку і все виправить. Ось тільки неестетично зовсім... Але розібрати можна. Так, замість тексту "АФФИННЫЕ_ПРОСТРАНСТВА" вийде "АФФИ.ННЫЕ_ПРОСТРАНСТВА".
2. Коротко про поліграмні шифри
Поліграмний шифр заміни працює не з окремими символами, а з їх групами. При використанні m-граммного шифру відкритий текст розбивається на групи з m символів. Кожній групі з m символів відкритого тексту ставиться в заміну група з m символів шифрованого тексту. При цьому зміна деякого символу з m-символьного групи відкритого тексту, як правило, призводить до зміни всіх m символів шифртекста. Тобто поміняли один символ у вихідному повідомленні - і відразу m символів зміняться в зашифрованому.
Шифр Плейфера - біграмний шифр. Інший приклад біграмного шифру, в чомусь схожий, - подвійний квадрат Уітстона.
Зазвичай при розмові про те, що таке поліграмний шифр, справа йде до демонстрації якогось біграмного шифру, на чому і закінчується. Але є приклад крутіший: шифр Хілла. Він може бути пристосований до групи символів будь-якої довжини. На сторінці, куди веде посилання, наведено приклад при m = 3. І навіть будь-який чайник в області шифрування здогадається, як виходить шифр Хілла для груп з 4, 5, ..., як завгодно якого числа символів.
Шифр Плейфера - біграмний шифр. Інший приклад біграмного шифру, в чомусь схожий, - подвійний квадрат Уітстона.
Зазвичай при розмові про те, що таке поліграмний шифр, справа йде до демонстрації якогось біграмного шифру, на чому і закінчується. Але є приклад крутіший: шифр Хілла. Він може бути пристосований до групи символів будь-якої довжини. На сторінці, куди веде посилання, наведено приклад при m = 3. І навіть будь-який чайник в області шифрування здогадається, як виходить шифр Хілла для груп з 4, 5, ..., як завгодно якого числа символів.
Немає коментарів:
Дописати коментар