67325

Коди автентифікації на основі БСШ та їх властивості

Лекция

Информатика, кибернетика и программирование

Визначення та класифікація кодів автентифікації повідомлень Коди автентифікації повідомлень КАП МАС коди відомі також як коди забезпечення справжності повідомлень є криптографічними примітивами що використовуються для забезпечення цілісності та автентичності даних.

Украинкский

2014-09-07

411.63 KB

3 чел.

Лекція № 16 о (4.2 ) з

Дисципліни     «Прикладна криптологія»

Тема лекції

«Коди автентифікації на основі БСШ та їх властивості »

                            ОСНОВНІ НАВЧАЛЬНІ ПИТАНННЯ

16.1 Визначення та класифікація кодів автентифікації повідомлень

16.2  Оцінки стійкості МАС кодів при імітації та підміні

Додаток А Приклади оцінки стійкості КАП

Завдання для самостійної роботи:

  1.  доопрацювати лекцію;
  2.  розібрати задачі із додатку А 

Джерела, що рекомендуються  до самостійної роботи

  1.  Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Монографія (електронний варіант). Харків, ХНУРЕ, 2011 р.
  2.  Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Електронний конспект лекцій. Харків, ХНУРЕ, 2011 р.
  3.  Горбенко І. Д. Гриненко Т. О. Захист інформації в інформаційно-телекомунікаційних системах: Навч. посібник. Ч.1. Криптографічний захист інформації - Харків: ХНУРЕ, 2004 - 368 с.
  4.  Горбенко Ю.І., Горбенко І.Д. Інфраструктури відкритих ключів . Системи ЕЦП. Теорія та практика. Харків.  Форт. 2010 , 593с.

Додаткова лтература

1.В. Задірака . Компьютерная криптологія. Підручник. К, 2002 ,504с.

2. А. Менезис, П. Ван Аршот, С. Ватсон. Руководство по прикладной криптографии CRC Press, 1997, электронная копия, 662 с

3. Брюс Шнайер. Прикладная криптография. М., изд. Триумф. 2002 г., 797 с

16.1 Визначення та класифікація кодів автентифікації повідомлень

Коди автентифікації повідомлень (КАП, МАС коди), відомі також як коди забезпечення справжності повідомлень, є криптографічними примітивами, що використовуються для забезпечення цілісності та автентичності даних.

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

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

.  

Тому Сп по суті є криптографічною контрольною сумою і може використовуватися як імітоприкладка Імп (згідно з міжнародною термінологією коду автентифікації повідомлень).

М1

М2

М3

Мп

БСШШ

БСШ

БСШ

БСШ

С1

С2

С4

С3

Кш

Кш

Кш

Кш

Ка

Рисунок 1– Алгоритм зашифрування зі зв’язком за шифрованим текстом

Оскільки довжина іміто прикладки дорівнює lімп=128 біт, то граничне значення ймовірності обману можна оцінити як:

.

Необхідно зазначити, що одночасно з формуванням імітоприкладки здійснено

зашифрування повідомлення М. При цьому довжина зашифрованого повідомлення дорівнює довжині вихідного повідомлення, тобто автентифікацію здійснено без збільшення довжини зашифрованого повідомлення. Особливістю цього режиму є те, що додатково використовується ключ автентифікації. Якщо повідомлення не має зашифровуватися, то в цьому випадку до нього додається імітоприкладка і довжина автентифікованого повідомлення збільшується на lб=128 бітів, а саме автентифіковане повідомлення має вигляд {M, Іімп}. Основною перевагою такого методу автентифікації є висока швидкість перетворення і, як наслідок, можливість обчислення значення імітоприкладки в реальному плині часу. Основним недоліком є те, що використовувані ключі Кз та Ка є симетричними, а тому не дозволяють реалізувати захист на основі моделі взаємної недовіри.

Визначення кодів автентифікації повідомлень. Згідно  [274], МАС код це функція відображення : , де – простір ключів, – простір повідомлень, а   – простір МАС значень для . Для заданих значень ключа та повідомлення , функція виробляє МАС значення .

Більшість МАС кодів є ітеративними конструкціями, що використовують функцію стискання , попередню розбивку даних на  менші за довжиною блоки та зв'язування по зворотному входу проміжних результатів з обчислення геш значень.

Узагальнена модель ітеративного МАС коду для під блоків визначається таким алгоритмом ітеративних обчислень:

,

,                                                                                      (4.23)

.

Секретний ключ може використовуватися у векторі ініціалізації , у функції стискання та в результуючому перетворенні .

При побудові КАП (МАС) можна виділити такі основні підходи:

  1.  коди автентифікації повідомлення, що побудовані із застосуванням блокових шифрів;
  2.  коди автентифікації повідомлення, що побудовані на основі використання безключових геш - функцій;
  3.  коди автентифікації повідомлення, що побудовані з використанням родини універсальних геш - функцій;
  4.   коди автентифікації повідомлення, що побудовані на основі використання спеціалізованих алгоритмів.

МАС коди, що побудовані на основі блокового шифру, використовують шифрування в режимі зчеплення шифр текстів[ 273, 142, 4, 13 ].

Визначення 4..1 МАС код, що використовує блоковий шифр у СВС режимі визначається виразом .

Згідно визначення 4.1 довжина блоку даних має дорівнювати довжині даних блокового шифру, а довжина МАС коду встановлюється рівній довжині блоку блокового шифру. На кожному кроці ітерації ключ MAC коду використовується як ключ шифру, а блок повідомлення, після побітового додавання з результатом обчислення шифр тексту, що отриманий на попередньому кроці, подається на вхід блоку шифрування.

Але основна CBC- конструкція є вразливою до атаки типу exor підробки і отже може використовуватися лише в додатках, де повідомлення мають фіксовану довжину. Також існують декілька більш захищених різновидів цього алгоритму: EMAC та RMAC схеми. EMAC код використовує додаткове шифрування вихідного результату перетворень, ключ для цієї операції шифрування може бути отримано із ключа MAC. RMAC алгоритм заміняє останнє шифрування на шифрування з двома ключами. Безпечність цих конструкцій може бути доведено за умови, що основний блоковий шифр є псевдовипадковим [275]. Усі ці схеми містяться в ISO/IEC 9797-1, що є міжнародним стандартом для кодів автентифікації повідомлень, що використовують блокові шифри [94].

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

Визначення 4.2. HМАС код визначається виразом .

Для визначення 4.2 ключ доповнюється нульовими бітами до повного блоку, opad та ipad – постійні значення. Автор роботи  [276] та інші  довели безпечність цієї конструкції базуючись на таких припущеннях:

  1.  основна геш - функція є колізійно-стійкою за умови, що початкове значення – секретне;
  2.  ключова функція стискання за допомогою початкового значення є захищеним МАС алгоритмом (для повідомлень розміром в один блок);
  3.  функція стискання є слабкою псевдовипадковою функцією.

В деякому змісті альтернативою HMAC кодам є MDX-MAC конструкції [277], які засновані на MD5, SHA та RIPEMD геш - функціях. Тут, основна геш - функція перетворена в МАС код за рахунок внесення невеликих модифікацій: включення секретного ключа на початок, на кінець та до кожного кроку ітераційного обчислення геш - функції. Захищеність MDX-MAC може бути доведено за умови, що основна функція стискання є псевдовипадковою.

Замітимо, що HMAC та MDX-MAC алгоритми включено до ISO/IEC 9797-2 [95].

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

Визначення 4.3. МАС код на основі універсального гешування є відображенням (де для кожного , - функція з родини геш-функцій , – загальна область визначення, – кінцевий діапазон значень) таким, що для будь-яких різних імовірність того, що буде не більше , при випадковому виборі .

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

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

Визначення та вимоги безпечності до кодів автентифікації повідомлень.

Розглянемо випадок, коли зловмисник може підробити повідомлення для МАС коду , якщо, не знаючи випадкового ключа , він здатен створити нове повідомлення та МАС значення таке що .

Визначення 4.4 [1]. МАС код є – секретним, якщо, при випадково взятому ключі , зловмисник не може підробити нове повідомлення за час із імовірністю вищою від навіть якщо він (на свій вибір) має змогу отримати значень МАС кодів інших повідомлень.

Залежно від інформації, доступної зловмисникові, розрізняють такі типи атак на коди автентифікації повідомлень[142. 273, 11- 13 ]:

- Атака з відомим текстом. Зловмисник має можливість досліджувати деякі відкриті тексти та відповідні їм значення коду автентифікації повідомлень.

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

- Атака з адаптивним вибором тексту. Це найбільш загальна атака, коли зловмисник обирає текст і негайно одержує відповідні значення коду автентифікації повідомлення. Вибір тексту може залежати від результату попередніх спроб.

"Злом" алгоритму МАС коду може мати різні наслідки:

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

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

- Ключове відновлення. Зловмисник може визначити секретний ключ . Такий злам є найнебезпечнішим, оскільки дозволяє зловмиснику створювати довільні вибірні підробки.

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

Відомі на той час атаки на коди автентифікації повідомлення розглянуті в [273].

Розглянемо ці атаки детальніше.

Угадування коду автентифікації повідомлення (Guessing of the MAC). Це пряма атака на алгоритм МАС коду полягає у виборі довільного нового повідомлення, і згодом угадування значення коду автентифікації повідомлення. Вона може бути  зроблена такими способами :

  1.   вгадування МАС коду безпосередньо з імовірністю успіху ;
  2.   вгадування ключа, з подальшим обчислення значення МАС коду, з імовірністю успіху .

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

Вичерпний пошук ключа (Exhaustive Key Search). Це також  пряма атака, що може застосовуватися до будь-якого алгоритму. Атака вимагає приблизно відомих пар текст-MAC для даного ключа. Намагаючись визначити ключ, один за одним перебираються всі ключі. Очікуване число випробувань, що призведе до злому МАС алгоритму, дорівнює . На відміну від попередньої атаки, цю атаку можна здійснювати поза сеансом зв'язку (off-line).

Підробка, що заснована на внутрішній колізії (Internal Collision Based Forgery). Наслідок цієї атаки полягає в тому, що якщо виявити внутрішню колізію (збіг проміжних результатів при обчисленні значень МАС кодів), її можна використати, для підробки МАС коду на окремому обраному тексті.

В роботі  [277] показали, що внутрішню колізію для може бути знайдено, з використанням відомих пар текст-MAC та обраних текстів, де очікувані значення для і є такими (тут , позначає розмір у бітах пов'язаної змінної): , а , якщо вихід перетворення МАС коду є перестановкою; інакше, приблизно дорівнює .

Ключове відновлення на основі внутрішньої колізії (Internal Collision Based Key Recovery). Для ряду  функцій стискання, внутрішню атаку колізії можливо розширити до ключової атаки відновлення [278]. Ідея полягає в тому, щоб ідентифікувати одну або більше внутрішніх колізій; наприклад, якщо не є перестановкою для фіксованого , і внутрішня колізія після першого блоку повідомлення визначається рівнянням в якому та можливо є невідомим (передбачається, що залежать від ключа). Для деяких функцій стискання , можна одержати інформацію щодо секретного ключа, заснованого на таких відносинах.

Атака методом декомпозиції (Divide-and-Conquer Attack). Атака є спеціальним випадком ключового відновлення на основі внутрішньої колізії. Для деяких функцій стискання, які використовують два окремих ключа, можна використати внутрішні колізії для ключового відновлення [277]. Нехай ключі позначені як та . Загальна ідея полягає в тому, що порушник спочатку шукає деякі внутрішні колізії, а потім методом вичерпування визначає ключ , що зумовлює ці колізії. Після визначення для пошуку використовується вичерпний пошук. Тому  стійкість такого МАС коду залежить від його індивідуальних ключів, а не від їхньої загальної довжини. Вказана  атака менш практична, ніж простий вичерпний пошук ключа, оскільки необхідна велика кількість відомих пар текст - MAC.

Підробка Exor (Exor Forgery. Ця   підробка можлива, якщо значення обчислюється як функція та немає додаткового перетворення геш виходу. Найлегший варіант атаки вимагає одну відому пару текст - MAC. Припустимо, що вхід та його доповнююча версія складаються з одного блоку. Отже, якщо відомо , виходить що:

.    (4.24)

Таким чином, можна створити нове повідомлення (що буде підробкою) з тим же значенням МАС. Базова CBC-конструкція використовує обчислення та є вразливою до атаки типу exor підробки.

Визначення таємності та безпечності кодів автентифікації, оцінки колізійних характеристик розглянуті в [5, 106].

16.2  Оцінки стійкості МАС кодів при імітації та підміні

Аналіз показує,що для  підміни повідомлень, порушник має сформувати та відповідний автентифікатор . Це може бути зроблено двома способами: шляхом імітації та підміни.

У випадку імітації порушник робить автентифікацітор , ґрунтуючись на апріорних ймовірностях розподілів МАС значень та ключових даних. Імовірність імітації буде визначатися максимальною імовірністю того, що сформований автентифікатор є істинним:

.    (4.25)

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

,    (4.26)

де - кількість геш-функцій , що породжують для повідомлення значення МАС коду .

Зрозуміло , що

.      (4.27)

Крім того,  всі записи в стовпцях масиву МАС кодів зустрічаються однакову кількість разів, маємо:

.      

Тому верхня границя ймовірності імітації МАС коду по ключу визначається максимальним значенням по всьому просторі повідомлень, а значення імовірності обмежується таким співвідношенням:

.   (4.28)

Якщо не враховувати розподіл МАС значень для даного повідомлення по ключовому просторі, тоді ймовірність імітації позначимо як імовірність імітації по МАС значенню . Імітація через нав'язування МАС значення визначається тим, що з множини передбачуваних МАС кодів вибирається одне. Імовірність успіху буде визначатися виразом:

,    (4.29)

де – потужність множини можливих МАС значень для повідомлення .

Якщо МАС значення для повідомлення приймають повну множину значень , одержимо

.      

У загальному випадку справедлива така нижня границя:

.     (4.30 )

Якщо для повідомлення відомим є статистичний розподіл МАС значень, то оцінка для імовірності імітації по МАС значенню зводиться до оцінки імовірності імітації по ключу.

Верхня границя для імовірності імітації по МАС значенню буде визначається максимальним значенням по всьому простору повідомлень:

.   (4.31 )

Атака підміни заснована на тому, що порушник спостерігає та змінює його на , де . Імовірність підміни визначатиметься такою умовною імовірністю:

. (4.32 )

Вираз для імовірності підміни з використанням формули повної імовірності та статистики сприятливих спостережень матиме такий вигляд:

. (4.33 )

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

Аналіз показує,  що можливі два випадки, коли підміна повідомлення на , якщо здійснюється з тим самим автентифікатором, (підміна першого роду) і з різними (підміна другого роду).

Імовірність підміни за умови рівності визначається імовірністю колізії МАС коду та оцінюється виразом:

.(4.34 )

Для ймовірності підміни другого роду у випадку маємо:

(4.35)

Таким чином ля точного обчислення імітаційної та колізійної стійкості МАС кодів по наведеним формулах  необхідно використовувати статистику спільних розподілів МАС кодів по ключах для істинних та підроблених повідомлень. Для практичних МАС кодів визначення  такої статистики виглядає проблематичним через надзвичайно великі розміри масиву можливих МАС Нижні границі для імовірностей імітації та підміни не враховують статистичні властивості масивів автентификаторів, ґрунтуються на моделі псевдовипадковості функції та визначають мінімальні вимоги до розміру ключового простору, та простору МАС значень. Верхні границі для ймовірностей імітації та підміни пов'язані з комбінаторними властивостями МАС масивів та оцінюють значення колізій у просторі для найгіршого випадку вибору ключів та повідомлень.

16.3  Колізійні характеристики МАС кодів

Під стійкістю до колізій розуміють обчислювальну складність  знаходження двох повідомлень та таких, що[5, 12,13, 106  ]:

,     (4.36 )

де є відповідним перетворення. У [5, 12,13, 106  ] наводяться оцінки імовірності створення колізій, причому вважається, що для цього необхідно виконати не менш експериментів із загальної кількості можливих значень. Математична постановка задач імовірнісної оцінки колізій формулюється в такий спосіб.

Задача 1. Нехай є деяка функція перетворення повідомлення

,      (4.37 )

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

Задача 2. Нехай на виході перетворювача з повної множини значень формуються випадкових значень функції перетворення (4.37 1.14), причому та підкоряються рівно qмовірному закону розподілу. Нехай виконано експериментів, у кожному з яких отримано значень . Позначимо реалізації двох експериментів як та відповідно, причому та . Необхідно знайти ймовірність того, що ці множини містять у собі хоча б по одному елементу та , такі, що .

Розв’язання цих задач наведемо за результатами роботи [9].

Оцінка числа випробувань появи колізій . Проведений аналіз показав [106], що задача 1.1 може розв’язуватися з використанням «парадокса» про день народження, але при докладному розгляді з'ясувалося, що вона носить більш загальний характер. У нашому випадку є вибірка з значень цілочисленої випадкової величини з рівноймовірним законом розподілу, причому вона може приймати значення від 1 до , а . За цих умов необхідно знайти ймовірність того, що серед значень вибірки принаймні дві збігаються, тобто:

.

Для розв’язання задачі 1.1 знайдемо ймовірність того, що в групі з подій не відбудеться колізія, тобто співвідношення (1.13) не виконається жодного разу. Позначимо цю ймовірність як . Зрозуміло, що та складають повну групу подій, тобто:

та

.     (4. 38 )

Далі знайдемо загальну кількість  різних способів, якими можна одержати значень без повторень. Для першого елемента ми маємо значень без повторень, для другого , для третього – і т.д., для -го . Тому загальне число способів, при яких немає збігів виду (1.13) може розраховуватися як:

             (4.39 )

Оскільки при кожній з подій з однаковою ймовірністю може відбуватися кожне з подій, то загальне число подій можна оцінити як

.      (4.40 )

Далі, ймовірність відсутності збігів можна оцінити співвідношенням числа варіантів без збігів (4.39) до загального числа варіантів (4.40), тобто:

.    (4.41  1.18)

Використавши вираз (4.38 ), маємо:

.     (4.42 )

Вираз (4.42) може бути використаний для оцінки необхідної ймовірності, проте бажано одержати загальний розв’язок рівняння (4.42), наприклад, для значення .

З цією метою представимо у вигляді:

   (4.43  )

Далі скористаємося тим, що для всіх [5] справедливим є:

.     (4.44 )

За малих значень (наприклад, ) можна вважати, що:

.     (4.45  )

Враховуючи це, перетворимо вираз (4.43), підставивши значення (4.45). У результаті маємо:

. (4.46 )

Позначимо , тобто ймовірністю, з якої має виникнути колізія. У результаті маємо:

,

або

.     (4.47)

Виконавши логарифмування (1.24), маємо:

.     (4.48 )

Перетворюючи (4.48), маємо:

,

або

.

У кінцевому виді одержуємо:

.     (4.49 )

Таким чином, отримано рівняння, в якому пов’язані три величини – число подій , загальне число подій та ймовірність , з якої повинна виникати колізія. Знаючи відповідне значення та можна одержати точний розв’язок.

Нехай , тоді з використанням (4.49) маємо:

.   (4.50)

Якщо рівняння (1.27) матиме вигляд:

.     (4.51)

Дамо оцінку значення , з огляду на те, що . З (4.49) отримаємо:

.     (4.52  )

При маємо:

та

.     (4.53)

За довільного значення з рівняння (4.52  1.29) одержимо:

.   (4.54  )

Співвідношення (4.54 ) дозволяє оцінити число перетворень (експериментів) , які необхідно здійснити для виникнення колізії з ймовірністю .

Порівнюючи отримані для значення, наприклад, (4.53 ) та (4.54 ) з оцінкою, що приводиться в [5]

,      (4.55 )

можна оцінити ступінь наближеності та можливість її застосування.

Додаток А Приклади оцінки стійкості КАП

Приклад 4.1. Нехай у якості використовується

геш-функція SHA-1, в якій , і нехай та . Використавши вираз (4.54   1.31), одержуємо:

У випадку (4.55   1.32) одержуємо:

.

Із приклада величину похибки, яку має оцінка (4.55   1.32), що широко застосовується для аналізу колізій.

 Оцінка ймовірності виникнення колізій . Спираючись на результати розв’язання задачі 4.1, розглянемо розв’язок задачі 4.2. Друга задача виникає за умови розгляду та вибору способів створення колізій [5, 106]. Наприклад, у нашій постановці це завдання має сенс, якщо розгляд відразу двох або більшого числа множин з - реалізацій дозволяє прискорити процес створення колізій або витягти корисну для крипто аналітика інформацію.

У нашому випадку подія може відбутися з імовірністю . Отже ймовірність того, що :

.     (4.56 )

Якщо містить у собі подій, то ймовірність того, що всі значення не дорівнюватимуть , може бути обчислена як:

.     (4.57  )

Ймовірність того, що хоча б одне значення дорівнюватиме , є:

.     (4.58 )

Нехай усі елементи – різні. Це справедливо, тому що , наприклад, . Тоді ймовірність того, що

та

.    (4.59 )

Далі, ймовірність того, що хоча б одна подія з і співпаде, є:

.    (4.60 )

Позначимо та скористаємося співвідношенням (4.45). У результаті одержимо

.   (4.61)

Таким чином, ймовірність того, що у двох множинах і хоча б по одному елементу співпаде:

.     (4.62)

Перетворивши (4.62 ), маємо:

.     (4.63 )

Логарифмуючи (4.63 ), отримаємо:

і далі

.

На закінчення одержимо

.     (4.64 )

Розглянемо часті випадки.

Нехай , тоді:

.    (4.65 )

При одержимо:

.    (4.66 )

Приклад 2. Нехай у якості геш-функції використовується геш-функція SHA-1, а .

Тоді

Отримані в ході розв’язання другої задачі результати дозволяють зробити такі висновки.

Якщо на вхід перетворення (обчислювача значень геш-функції) подаються випадкових значень , причому вони утворюють множину , а потім ще раз випадкових , що утворюють множину , то для того щоб значення та множин і співпали з ймовірністю , необхідно виконати

експериментів.

Проведемо оцінки значень і для використовуваного в Україні алгоритму симетричного блокового шифрування ГОСТ 28147-89. У четвертому режимі довжина криптографічної контрольної суми (імитовставки) дорівнює 64 бітам. Тому та . Якщо , використавши (1.31), одержимо:

.

Якщо , використавши (1.31), одержимо:

.

Якщо , використавши (1.30), маємо:

.

З урахуванням вимог до криптографічних алгоритмів блокового шифрування, викладених в [4, 11, 13 ], можна зробити висновок, що режим 4 виробітки імітовставки ГОСТ 28147-89 істотно підданий можливості створення колізій.

Отримане в найбільш загальному вигляді рівняння (4.50) дозволяє точно розв’язати задачу визначення кількості експериментів , які необхідно виконати для створення колізії з ймовірністю на множині потужністю . Досить добрим наближенням оцінки є співвідношення (4.54). Разом з тим, прийнята в ряді джерел без пояснення оцінка дає грубий результат. Найбільш точне значення можна одержати при розв’язанні рівняння (4.50).

Застосування виразу (4.64) дозволяє оцінити умови колізій між двома незалежними експериментами залежно від розміру множини виходів та ймовірності, з якого колізія має відбуватися. Співвідношення (4.65) і (4.66) дають наближені оцінки.

Отримані вході розв’язку задач результати дозволяють одержати як залежність від та , так і залежність від  та .


 

А также другие работы, которые могут Вас заинтересовать

46569. Формирование гражданского общества в России 20.46 KB
  Зачатки гражданского общества в России начали складываться во второй половине ХIХ столетия в результате реформ Александра II отмена крепостного права реформа местного самоуправления судебная административная и другие реформы. Все это ускорило необходимые процессы модернизации русского общества. С развитием буржуазных отношений формируются крупные промышленные предприятия банки и другие субъекты капиталистических отношений что создало экономическую основу гражданского общества.
46570. Термінологічні словники як основне джерело фахової інформації 20.5 KB
  Термінологічні словники як основне джерело фахової інформації. Особливу категорію складають термінологічні словники це словники які включають терміни що стосуються окремої галузі знань або навіть певної теми та їх пояснення Словник термінів теорії груп.
46571. Особенности проблемного обучения изобразительному искусству 20.55 KB
  Особенности проблемного обучения изобразительному искусству. План: понятие ПО Проблемная ситуация и пробл вопрос проблемные задачи по изо структура проблемного урока классификация метолов обучениявывод 1Проблемное обучение это тип развивающего обучения в котором сочетается систематическая самостоятельная поисковая деятельность учащихся с усвоением ими готовых выводов науки. 3 учебнопознавательные задачи приемытехники изображ предмета 4 Структура процесса проблемного обучения представляет собой систему связанных между собой и...
46572. Метод дисконтирования при оценке недвижимости 20.6 KB
  Метод дисконтированных денежных потоков наиболее универсальный метод позволяющий определить настоящую стоимость будущих денежных потоков. Метод ДДП позволяет оценить стоимость недвижимости на основе текущей стоимости дохода состоящего из прогнозируемых денежных потоков и остаточной стоимости. Расчет стоимости объекта недвижимости методом ДДП осуществляется в следующей последовательности: 1.
46573. Роль ХХ столетия в мировой истории 20.67 KB
  Не случайно в большинстве экономически развитых стран у власти чередуются представители либеральных и умеренно-социалистических группировок. Однако подобное обстоятельство не устранило саму конкурентную борьбу лишь изменило ее формы. И хотя экономическое положение США в мировом сообществе уже не так прочно как преждетем не менее очевидно что правящая элита США будет прилагать все усилия для сохранения исключительного положения своей страны. Впрочем мировое развитие идет в направлении возрастания политического веса малых стран в мировой...
46575. Особенности и правовая охрана интеллектуальной собственности 20.7 KB
  Под объектом интеллектуальной собственности следует понимать конкретную разработку произведение представленную на материальном носителе. Объекты интеллектуальной собственности: Литературные художественные и научные произведения; Исполнительская деятельность артистов звукозаписи радио и телевизионные передачи; Изобретения во всех областях человеческой деятельности; Научные открытия; Промышленные образцы; Товарные знаки знаки обслуживания фирменные наименовании и коммерческие обозначения; Авторское право Авторское право...