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

Лабораторна робота №1.7.1

Основи криптографічного захисту інформації

Ціль роботи

Дослідження основних методів криптографічного захисту інформації

Вказівки до роботи

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

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

Криптоаналіз – займається розкриттям шифру без знання ключа (перевірка стійкості шифру).

Кодування– (не ставиться до криптографії) – система умовних позначок, застосовуваних при передачі інформації. Застосовується для збільшення якості передачі інформації, стиску інформації й для зменшення вартості зберігання й передачі.

Криптографічні перетворення мають мета забезпечити неприступність інформації для осіб, що не мають ключа, і підтримка з необхідною надійністю виявлення несанкціонованих викривлень.

Більшість засобів захисту інформації базується на використанні криптографічних шифрів і процедур шифрування-розшифрування. У відповідності зі стандартом ГОСТ 28147-89 під шифром розуміють сукупність оборотних перетворень безлічі відкритих даних на безліч зашифрованих даних, що задаються ключем і алгоритмом перетворення.

У криптографії використовуються наступні основні алгоритми шифрування:

• алгоритм заміни (підстановки) – символи шифрованого тексту заміняються символами того ж або іншого алфавіту відповідно до заздалегідь обумовленої схеми заміни;
• алгоритм перестановки – символи шифрованого тексту переставляються за певним правилом у межах деякого блоку цього тексту;
• гаммування – символи шифрованого тексту складаються із символами деякої випадкової послідовності;
• аналітичне перетворення – перетворення шифрованого тексту по деякім аналітичнім правилу (формулі).

Процеси шифрування й розшифрування здійснюються в рамках деякої криптосистеми. Для симетричної криптосистеми характерне застосування того самого ключа як при шифруванні, так і при розшифруванні повідомлень. В асиметричних криптосистемах для зашифрування даних використовується один (загальнодоступний) ключ, а для розшифрування – інший (секретний) ключ.

Симетричні криптосистеми

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

У шифрах середніх століть часто використовувалися таблиці, за допомогою яких виконувалися прості процедури шифрування, засновані на перестановці букв у повідомленні. Ключем у цьому випадку є розміри таблиці. Наприклад, повідомлення “Неясное становится еще более непонятным” записується в таблицю з 5 рядків і 7 стовпців по стовпцях.

Для одержання шифрованого повідомлення текст зчитується по рядках і групується по 5 букв:

НОНСБ НЯЕЕО ЯОЕТЯ СВЕЛП НСТИЩ ЕОЫНА ТЕЕНМ

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

До перестановки Після перестановки

У верхньому рядку лівої таблиці записаний ключ, а номера під буквами ключа визначені відповідно до природнього порядку відповідних букв ключа в алфавіті. Якщо в ключі зустрілися б однакові букви, вони б нумерувалися ліворуч праворуч. Виходить шифровка: СНЯНН БОЯЕТ ЕООЕЕ ПНЯВЛ СЩОЫС ИЕТЕН МНТЕА. Для забезпечення додаткової скритності можна повторно шифрувати повідомлення, яке вже було зашифровано. Для цього розмір другої таблиці підбирають так, щоб довжини її рядків і стовпців відрізнялися від довжин рядків і стовпців першої таблиці. Найкраще, якщо вони будуть взаємно простими.

Крім алгоритмів одиночних перестановок застосовуються алгоритми подвійних перестановок. Спочатку в таблицю записується текст повідомлення, а потім по черзі переставляються стовпці, а потім рядка. При розшифруванні порядок перестановок був зворотний. Приклад даного методу шифрування показаний у наступних таблицях:

Подвійна перестановка стовпців і рядків

У результаті перестановки отримана шифровка АЗЮЖЕ_СШГТООИПЕР. Ключем до шифру служать номера стовпців 2413 і номера рядків 4123 вихідної таблиці.

Число варіантів подвійної перестановки досить швидко зростає зі збільшенням розміру таблиці: для таблиці 3 х 3 їх 36, для 4 х 4 їх 576, а для 5*5 їх 14400.

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

Кількість магічних квадратів дуже різко зростає зі збільшенням розміру його сторін: для таблиці 3*3 таких квадратів -1; для таблиці 4*4 - 880; а для таблиці 5*5-250000.