Шифр вертикальної перестановки.

Шифри перестановки.

Теорема. Підстановки подібні в тім і тільки тім випадку, коли їхні циклові структури однакові.

Розв’язок рівняння подоби полягає в наступному.

1. Записуємо в цикловій формі.

2. Якщо циклові структури не однакові, то розв’язків немає.

3. Підписуємо циклові записи підстановок друг під другом таким чином, щоб під кожним циклом з’явився цикл рівної довжини.

4. У кожній групі циклів однакової довжини, в одному з рядків, скажемо нижньому, довільно переставляємо цикли місцями. При кожній конфігурації розташування циклів у групі, кожен цикл незалежно від інших виписуємо з кожного місця. Перетворення робимо з кожною групою циклів незалежно.

Кожна з множини отриманих дворядкових записів (підстановок) є розв’язком рівняння подібності.

Відмінність цього типу шифра від шифрів заміни полягає в тому, що при зашифруванні буква відкритого тексту переходить не у фіксований знак алфавіту, а в іншу букву того ж відкритого тексту, скажемо , у результаті чого букви розташовуються на нових місцях, тобто переставляються. Ключом для даного шифра служить таблиця заміни індексів (номерів місць) елементів тексту. У загальному випадку розмір таблиці заміни дорівнює довжині відкритого тексту. Такі таблиці зручно формувати (і записувати) у вигляді підстановок.

Припустимо, що номера букв відкритого тексту довжиною в N знаків розбито якимось чином на множини , що не перетинаються. Впливаючи на кожну множину своєю підстановкою (циклом) , ми реалізуємо процес зашифрування шифром перестановки, причому підстановка, що відповідає шифрперетворенню, дорівнює . Змінюючи розбиття множини індексів і вибираючи різними способами відповідні підстановки , ми будемо одержувати різні перетворення відкритого тексту виду . Рано чи пізно, ми побудуємо всі підстановки ступеня N, оскільки будь-яка підстановка розкладається в добуток циклів. Звідси випливає, що вдалий спосіб генерації підстановок міг би, у принципі, забезпечити досить якісний шифр перестановки, при якому використовувалися би підстановки ступеня меншої, чим довжина відкритого тексту. Саме способами генерації підстановок і розрізняються різні види шифрів перестановки.

Відкритий текст: "В связи с создавшимся положением отодвигаем сроки возвращения домой Рамзай ".

Для зашифрування побудуємо прямокутну таблицю, кількість рядків якої визначається довжиною тексту, а кількість колонок дорівнює шести. Як ключове слово, «гасло», виберемо слово «ЗАПИС» (кількість букв у гаслі повинне дорівнювати кількості стовпчиків у нашій таблиці). Замінимо тепер кожну букву ключового слова на число від 1 до 6 таким чином, щоб буква, що має менший номер проходження в алфавіті, замінялася на менше число. Одержимо ключ: (2,1,4,3,5,6). Елементи ключа проставимо як нові номера колонок. Впишемо відкритий текст у таблицю, переходячи звичайним образом з рядка на рядок. У результаті одержимо:

Випишемо тепер букви по стовпцях, відповідно до їхніх нових номерів. У підсумку, одержимо наступний шифротекст: