Порядок виконання лабораторної роботи

1. Розібрати принцип криптоаналізу багатоалфавітних шифрів.

В завданні (додаток 1), відповідно до порядкового номеру студента в журналі подані тексти, зашифровані шифром Гронсфельда. Алфавіт для шифрування: _АБВГДЕЄЖЗИІЇЙКЛМНОПРСТУФХЦЧШЩЬЮЯ

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

3. Провести порівняння імовірностей найчастіших символів відкритого і шифрованого тексту.

3.4. Лабораторна робота №16. Криптоаналіз шифру подвійної перестановки.

Тема роботи: Криптоаналіз шифру подвійної перестановки.

Ціль роботи: Віпрацювати основні принципи криптоаналізу шифрів перестановки (зокрема шифру подвійної перестановки) та провести статистичний аналіз шифру подвійної перестановки за допомогою таблиці імовірності біграм.

Загальні відомості

Шифр подвійної перестановки належить до так званих табличних шифрів. Крипостійкість такого шифру досить невелика. Імовірність простих елементів тексту (окремих символів) зберігається. Тому ефективний статистичний криптоаналіз можливий лише з використанням елементів тексту більшого порядку (n-грам, n>1) [15].

Теоретичні відомості

Розглянемо приклад використання криптоаналізу для дешифрування повідомлення, зашифрованого методом подвійної перестановки. Нехай маємо шифровку МА_ВННЯЕВОІПМОЛД, що укладається в таблицю 4х4:

	1	2	3	4
1	М	А	_	В
2	Н	Н	Я	Е
3	В	О	І	П
4	М	О	Л	Д

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

Імовірність того, що два стовпця будуть знаходитись поруч, дорівнює добутку імовірностей біграм у рядках цих стовпців. Оскільки в таблиці подані логарифми біграм, то їх досить підсумовувати, а потім вибрати сполучення стовпців з максимальним логарифмом імовірності (це походить від того, що логарифм – постійно зростаюча функція) [2]. Розрахуємо логарифми імовірностей для всіх можливих сполучень першого стовпця з іншими:

р(1-2) = р(МА)+р(НН)+р(ВО)+р(МО) = 36,2

р(1-3) = р(М_)+р(НЯ)+р(ВІ)+р(МЛ) = 32,24

р(1-4) = р(МВ)+р(НЕ)+р(ВП)+р(МД) = 18,94

Аналогічну операцію виконаємо з іншими стовпцями. Для таблиці 4х4 таких логарифмів імовірностей буде 12.

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

Таблиця 16.1. Імовірності пар сполучень різних стовпців

P(1-2-3-4)	83,19		P(3-1-2-4)	93,93
P(1-2-4-3)	98,15		P(3-1-4-2)	79,71
P(1-3-2-4)	94,56		P(3-2-1-4)	83,43
P(1-3-4-2)	85,45		P(3-2-4-1)	78,35
P(1-4-2-3)	86,92		P(3-4-1-2)	68,34
P(1-4-3-2)	75,09		P(3-4-2-1)	89,44
P(2-1-3-4)	84,58		P(4-1-2-3)	83,11
P(2-1-4-3)	83,06		P(4-1-3-2)	76,53
P(2-3-1-4)	73,49		P(4-2-1-3)	105,57
P(2-3-4-1)	63,02		P(4-2-3-1)	91,65
Продовження таблиця №16.1.
P(2-4-1-3)	82,33		P(4-3-1-2)	87,76
P(2-4-3-1)	85,62		P(4-3-2-1)	92,38

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

	4	2	1	3			4	2	1	3
1	В	А	М	_		1	В	А	М	_
2	Е	Н	Н	Я		3	П	О	В	І
3	П	О	В	І		4	Д	О	М	Л
4	Д	О	М	Л		2	Е	Н	Н	Я

Отже, розставивши рядки в порядку (1342), одержуємо розшифровку: ВАМ_ПОВІДОМЛЕННЯ.

Однак, не завжди сполучення біграм із найбільшою імовірністю є шуканим. У такому випадку необхідно, починаючи від сполучення біграм із більшою імовірністю, перебрати всі можливі комбінації, поки не одержимо зв'язний текст [16].