Учбово-методичний посібник для виконання лабораторних робіт з дисципліни „Основи теорії криптографії і криптоаналізу”, страница 47

3.  Як потрібно модифікувати статистичний аналіз шифру Цезаря, щоб отримати спосіб статистичного аналізу шифру Гронсфельда?

4.  Чи можна шляхом статистичного аналізу визначити порядок розташування цифр ключа?

5.  Чому дорівнює кількість можливих ключів з n елементів?

6.  Запропонуйте способи суттєвого підвищення крипостійкості шифру Гронсфельда.


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].

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

1.  Вивчити основи криптоаналізу, описані в теоретичній частині лабораторної роботи.

2.  Завдання до лабораторної роботи приведені в додатку 1, номер варіанту за списом в журналі.

3.  Заповнити квадрат і пронумерувати стовпці і рядки;

4.  Обчислити імовірності всіх можливих пар стовпців;

5.  Оцінити імовірність пар сполучень різних стовпців і вибрати найбільше значення;

6.  Поставити стовпці в порядку, отриманому в п.3;

7.  Підібрати розташування рядків до одержання зв'язного тексту.

8.  У звіті вказати записані окремо сполучення цифр для стовпців і рядків (наприклад, стовпці: 4213, рядки: 1342), записаний отриманий текст і відповіді на контрольні запитання.

Контрольні питання

1.  Що таке біграма?

2.  Поясніть схему криптоаналізу шифру подвійної перестановки.

3.  Як розрахувати імовірність одночасного виконання кількох подій?

4.  Чому при статистичних розрахунках ми додавали логарифми імовірностей? Навіщо взагалі використання логарифмічних залежностей?

5.  Чи може ключ, що має не найбільшу імовірність, бути вірним? Як слід аналізувати текст в такому разі?