Методичні вказівки до практичних занять з дисципліни “Оcнови теорїї захисту інформації”, страница 15

Приклад 4. Нехай є деяка функція хешування h=H(M), де М – інформація довільної довжини, причому h може приймати n=2^m значень. Скільки випадкових повідомлень k треба подати на вхід перетворювача Н, щоб відбулось з ймовірністю Р_з хоча б одне співпадання виду

,

тобто відбулась колізія.

Розв’язок задачі ґрунтується на “парадоксі” про день народження (див. Приклад 3). Але ця задача носить більш загальний характер.

У нашому випадку є цілочислова випадкова величина з рівноймовірним розподілом значень від 1 до n, та мається вибірка із k значень випадкової величини (). Знайдемо ймовірність P(n,k) того, що серед значень H(M) у виборці, у крайньому випадку, дві співпадають

                                                     (14)

Використовуючи підхід, викладений вище при розв’язку задачі 5.5.3, одержимо узагальнення виразу (13)

                                           (15)

Для спрощення розрахунків вираз (15) можна спростити. Для цього використовуємо те, що справедливо

 , для усіх                                    (16)

Крім того, при малих значеннях х (наприклад, ) можна розрахувати, що:

                                                              (17)

Далі запишемо (15) в вигляді:

                                       (18)

Оскільки в нашому випадку , то зробимо в (18) заміну, використовуючи (16).

У результаті маємо

                                (19)

Розв’язок можна одержати, розв’язавши (19)

, так як Р_з відомо. Оскільки реально Р_з1,

то

або

і далі

У кінцевому виді маємо рівняння

                                                  (20)

Нехай Р_з=0,5, тоді маємо

При n=2^m рівняння приймає вид

                                                         (21)

Дамо оцінку значення k, враховуючи що k достатньо велике і .

Тоді із (20) маємо

При Р_з =0,5 маємо

і

                                                   (19)

При n=2¹⁶⁰ , маємо k==2⁸⁰

При n=2²⁵⁶, k=2¹²⁸

При довільному значенні Р_з

                               (20)

Співвідношення (20) дозволяє оцінити число експериментів, які необхідно виконати для здійснення колізії типу (14)

5.6. Перелік задач для самостійного розв’язання.

1. Оцініть імовірність обману в режимі виробки та використання для забезпечення цілісності та справжності кодів автентифікації повідомлень (КАП) з довжиною , та 256 бітів. Визначте які криптоалгоритми для автентифікації з вказаною довжиною можна застосувати.

2. Визначите мінімальне значення k, при якому ймовірність того, що по крайній мірі у двох осіб із групи в k осіб дні народження співпадуть з ймовірністю Р_з=0,5+0,01×r , де r – номер по журналу реєстрації.

3. Визначте скільки випадкових повідомлень необхідно подати на вихід засобу розрахунку хеш-функції Н(Мі) щоб з ймовірністю Р_з=0,5+0,01×r була здійснена колізія, якщо n=2^m+k, m=192, r – номер реєстрації по журналу.

4. Розв’яжіть рівняння

якщо

Визначте складність та безпечний час здійснення колізії для одержаного значення k, якщо потужність криптоаналітичної системи складає 10⁸,10¹⁰, 10¹² та 10¹⁶ опер./сек., а r – номер реєстрації по журналу.

5. Дайте оцінку числа експериментів k здійснення колізій, використовуючи співвідношення (20)

якщо Р_з=0,5+0,01r, n=2^192+r

Де r – номер реєстрації по журналу.

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

1. Визначте поняття цілісності та справжності, яким чином вони забезпечуються?

2. Для чого здійснюється автентифікація повідомлень?

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

4. Оцініть ймовірність обману в інформаційній технології, якщо для цього використовується алгоритм Rijendael з довжиною блоку 128 бітів.

5. Які основні переваги та недоліки методу автентифікації, що базується на використанні імітовкладки?

6. В чому суть парадоксу дня народження?

7. В чому суть методу створення колізій та як його можна реалізувати.

8. За якими показниками можна оцінити складність створення колізій?

9. Як залежить складність створення колізій від довжини хеш-функції.