67308

Методи та механізми автентифікації на основі симетричних криптоперетворень

Лекция

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

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

Украинкский

2014-09-07

323.44 KB

8 чел.

Лекція № 14 (4.1 ) з

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

Тема лекції

«Методи та механізми автентифікації на основі симетричних крипто перетворень»

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

14.1 Основні поняття та визначення.

14.2   Структурна схема та математична модель захищеної інформаційної – телекомунікаційної системи(ІТС).

   14.3 Вступ у теорію автентичності Сімонсона

   14.4 Методи автентифікації в класі симетричних шифрів

14.5. Висновки та рекомендації

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

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

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

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

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

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

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

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

14.1 Основні поняття та  визначення

        Надзвичайно важливими послугами, що повинні надаватися користувачам ІТС є послуги цілісності та автентичності інформації та ресурсів. По суті сьогодні ці послуги в ряді випадків є навіть більш важливими ніж послуга конфіденційності. В цьому розділі цілісність інформації ми будемо розглядати як властивість захищеності інформації від випадкової чи навмисної її модифікації, яка забезпечується за рахунок застосування криптографічного перетворення інформації[142,273, 4, 12, 94, 95  ].

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

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

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

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

Автентифікація мережі – це процедура встановлення дійсності мережі чи інформаційної технології, до яких отриманий доступ даним об'єктом чи суб'єктом.

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

Автентифікація повідомлень – це процедура перевірки цілісності і справжності повідомлення, отриманого від визначеного об'єкта.

Автентифікація здійснюється за рахунок застосування систем паролів,  кодів автентифікації повідомлень та взагалі інформації, електронних підписів та електронних цифрових підписів[4 - 6, 12, 32,  46, 49],  а також механізмів автентифікації у вигляді різних протоколів автентифікації.[4. 12, 38, 46, 67 ].   В подальшому  будемо зважати на основні принципи, що були закладені в [273], що були закладені при розгляді сутності автентифікації.

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

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

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

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

                                             

                                                             Mia = Mi; Fa ( Si , Ej),                                                  (4.1)  

де :  Si  -  реальний стан джерела інформації,  Ej  - j  правило шифрування інформації, а Fa – функція автентифікації.   Також Fa ( Si , Ej) називають  у відповідності з перекладом [273  ] назвали автентифікатором – ми в подальшому будемо називати кодом автентифікації повідомлення ( КАП),  або в англомовному поданні –  МАС кодом.   

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

  

14.2   Структурна схема та математична модель захищеної інформаційної – телекомунікаційної системи(ІТС).

            Наступним кроком розглянемо спрощену структурну схему ІТС,  з використання якої розглянемо механізми автентифікації в мережі користувачів [13].

На рис. 4.1 наведена спрощена  структурна схема  ІТС, в якій реалізуються механізми автентифікації .

На рисунку 4.1 використані такі позначення:

D1, D2 – джерела інформації( користувачі ІТС);

ЗАІ – засоби автентифікації  інформації (повідомлень);

ТС (НI) – телекомунікаційна система (носій інформації);

КРА – крипто аналітик (порушник));

ДК – джерело ключів.

Таким чином, по суті, в ІТС на рисунку 4.1 ми виділяємо таких 4 суб'єкти:

  1.  джерела інформації( передавач та приймач)  D1  та D2;
  2.  телекомунікаційна система або носії інформації на яких зберігається відповідна інформація;
  3.  крипто аналітик(порушник, зловмисник) – КРА, який протидіє в системі з метою нанесення її втрат;
  4.  джерело ключів (DK), що забезпечує управління ключами;
  5.  арбітр ІТС, що забезпечує розгляд суперечок між користувачами та підготовку матеріалів розслідування.

.

   Рисунок 1.4 – Спрощена   структурна схема  ІТС з забезпеченням автентифікації.

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

Розглянемо в спрощеному вигляді які погрози та втрати можуть бути нанесені сторонами при їх  протидії та виконанні несанкціонованих дій[13, 273].

Так, як  D1  не довіряють один одному то вони можуть  робити спроби реалізувати такі погрози.

Основні погрози, що може реалізувати джерело D1(D2) :

1) формує повідомлення , а потім відмовляється від факту передачі його в мережу;

2) джерело стверджує, що він сформував деяку інформацію і передав у мережу, а насправді він її не формував і не передавав;

3) стверджує, що він сформував і передав інформацію у визначений час, хоча насправді він її сформував і передав іншим часом;

4) формує і передає інформацію , а потім стверджує, що була передана інформація тощо;

Джерело також може робити спроби обманути .

Основні погрози, що може реалізувати джерело (D1)

1) сам формує деяку інформацію, а потім стверджує, що він її отримав від ;

2) отримує інформацію від , модифікує її в , а потім стверджує, що він отримав цю інформацію від ;

3)  стверджує, що він отримав інформацію в момент часу , а насправді він отримав інформацію під час ;

4) отримує інформацію , а потім стверджує, що він її не отримав тощо.

 В 2 та 3  розділах ми уже розглядали погрози, які може здійснювати порушник( зловмисник). Тут конкретизуємо дещо їх.

Основні погрози, що може реалізувати КРА:

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

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

Задача систем забезпечення автентифікації ,  в умовах протидії, зводяться, як правило, до  мінімізації втрат в ІТС  при дії безлічі погроз.

14.3 Вступ у теорію автентичності Сімонсона

У 70-і роки вперше була опублікована теорія захисту від обману (автентичності), що отримала найменування теорії Сімонсона [142, 12, 13, 273].

Сутність теорії Сімонсона:

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

Вважатимемо, що простір повідомлень може бути сформований з повідомлень.

Захист інформації здійснюється в ЗЗІ (рис. 1.4).

В ЗЗІ формується криптограма

.                                       (4.2   )

В подальшому - передається по ТС, а потім ЗЗІ відновлює інформацію:

.                                       (4.3   )

Вважатимемо, що джерело криптограм формує – криптограм. Якщо КРА сформує безліч криптограм і одну з них передав, то він може обманути з імовірністю [13, 142. 273]

                                               (4.4  )

де – імовірність обману.

Якщо , то імовірність нав'язування повідомлення, тобто обману, дорівнює 1.

Наша задача – зменшити , для цього необхідно збільшити простір криптограм:

або .                                (4.5)

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

В теорії Сімонсона прийнято визначати імовірність обману, використовуючи (4.4 ).

Якщо = , то в системі може бути нав'язане повідомлення випадкового змісту. Так КРА в моделі рис.4.1 може реалізувати такі загрози:

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

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

У своїй теорії Сімонсон здійснює оцінку за однією найбільш небезпечною загрозою

.                                   (  4.6  )

Він визначив як максимальну загрозу із всієї множини загроз.

Покладемо, що джерело разом з ЗЗІ формують криптограму та відомий апріорний ряд для . При відомому можна знайти ентропію джерела криптограм :

.                                  (4.7 )

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

             (4.8  )

причому – вважаємо відомою.

Визначимо, яку кількість інформації отримав КРА при переході від до :

.

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

.                                     (4.9 )

Знайдемо із (4.9) :

.                                            (4.10 )

Вираз (4.10) у теорії Сімонсона визначає межу ймовірностей обману в системі.

Розглянемо (4.10).

  1.  Криптосистеми, у яких досягається рівність (4.10), називаються системами з найкращим способом автентичності (повністю автентичні).
  2.  Для зменшення ймовірності обману необхідно збільшувати , тобто кількість інформації, що міститься в криптограмі про ключ автентифікації.
  3.  Для забезпечення цілісності та достовірності необхідно вводити до-датковий ключ автентифікації . Таким чином у нашій системі з'являється 2 ключі – ключ шифрування та ключ автентифікації .
  4.  Імовірність обману

,                                                  (4.11 )

де – довжина імітоприкладки (коду автентифікації).

Розглянемо (4.4) та (4.11). Нехай довжина повідомлення буде бітів. Довжина контрольної суми . Тоді довжина криптограми:

.                                                    (4.12 )

Для двійкового алфавіту

.                                     (4.13 )

Підставимо (4.13) у (4.4 ):

.                                          (4.14)

Тобто (4.14) співпадає з (4.11).

14.4 Методи автентифікації в класі симетричних шифрів

Всі методи автентифікації можна розділити на 2 класи: ті, що реалізуються збитковістю, і ті, які без збитковості [12, 13,  54, 61, 94, 95, 142, 273].

Твердження 4.1  

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

Доведення. Розглянемо поточне двійкове шифрування. Нехай є повідомлення. – функція зашифрування

,                                              (4.15  )

де – початковий j-й ключ. Тоді

.                                             (4.16 )

Покладемо, що КРА може перехопити тільки та зможе сформувати послідовність (яку-небудь). Тоді він формує . Вважатимемо, що ЗЗІ має синхронізацію по і. Тоді при відновленні повідомлення отримаємо: . Таким чином, можна нав'язати хибне повідомлення. Твердження доведено.

У більшості додатків джерело не довіряє . Більш того, обоє прагнуть захисту засобом арбітражу. Це може бути досягнуто, якщо в системі використовується асиметрична криптографія.

Твердження 4.2   

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

Доведення. Нехай М – інформація. – блоки інформації М. При груповому кодуванні обчислюються контрольні символи як

.                                             (4.17)

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

.                                             (4.18 )

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

.

Якщо КРА може нав'язати хибну інформацію методом модифікації, до-давши , то декодер прийме і цієї модифікації не виявить.

Твердження доведено.

Висновок: відповідно до Твердження 4.2 у поточних системах, які використовують групові коди, може нав'язуватися інформація як випадкового так і визначеного змісту.

Твердження  4.3

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

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

Роздивимося рис. 4.2   та 4.3

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

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

,                                               (4.19 )

де .                                                         (4.20 )

У нашому випадку зашифрування

,                     (4.21)

а розшифрування

  (4.22 )

Якщо , тобто її сформувано правильно, то . І вирази з сумами відповідно дорівнюють 0. При  інформацію прийнято пра-вильно.

Якщо , то - повідомлення розшифровано з помилками.

 14.5  Висновки, пропозиції та  рекомендації

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

14.5.2 В інформаційно – телекомунікаційній системі необхідно розглядати чотири взаємодіючі сторони:

  1.  джерела інформації( передавачі та приймачі) ;
  2.  телекомунікаційна система або носії інформації;
  3.  крипто аналітик(порушник, зловмисник) або криптоаналітики;
  4.  джерело або джерела ключів  (DK), що забезпечує управління ключами;
  5.  арбітр ІТС, що забезпечує розгляд суперечок.

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

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

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

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

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

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

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

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

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

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

Додаток А

Оцінка автентичності захисту інформації з використанням
симетричних алгоритмів. Приклади розв’язку задач та задачі для
самостійного розв’язання

Задача 1.

Оцініть імовірність обману, якщо для забезпечення цілісності та справжності використовується імітоприкладка згідно з ГОСТ 28147 – 89 або FIPS-197.

Розв'язок задачі:

Імітоприкладка виробляється згідно з ГОСТ 28147 – 89, 4-й режим. Вона є функцією повідомлення М, ключа зашифрування К та ключа автентифікації К

= f(М, К, К).                                       (1.173)

Згідно з теорією Сімонсена імовірність обману можна оцінити нерівністю

Р,

де – є довжина імітоприкладки.

Оскільки = 64 бітів, то

Р>.

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

Враховуючи, що довжина коду автентифікації для FIPS-197 біт, розв’яжіть задачу за аналогією з вищенаведеним.

Задача 2.

Розробіть та обґрунтуйте алгоритм блокового симетричного шифрування зі зв’язком по шифртексту, використавши алгоритм FIPS-197 з двома ключами - ключем зашифрування та ключем автентифікації.

Розв'язок задачі:

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

.   (1.174)

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

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

за шифрованим текстом

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

.

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

Задача 3.

“Парадокс” днів народження. Ця задача може бути сформульована таким чином. Чому дорівнює мінімальне значення k, при якому ймовірність того, що, у крайній мірі, у двох осіб із групи в k осіб дні народження співпадуть, буде Рз.

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

Розв’язок задачі:

Введемо ймовірність та знайдемо ймовірність того, що в групі із k осіб дні народження не співпадуть, позначивши її як . Зрозуміло, що:

,

тому

.

Зрозуміло також, що k365.

Знайдемо число різних способів N, якими можна отримати k значень без повторень. Для першого елемента ми маємо 365 значень без повторень, для другого 364, які залишилися, і так далі. Тому загальне число підходящих
способів

.

Якщо виключити умову відсутності співпадань днів народження, то кожний елемент (подія) може набувати будь-якого із 365 можливих значень. Загальна сума можливих подій дорівнює 365k. Тому ймовірність відсутності співпадань дорівнює відношенню числа варіантів без співпадань до загального числа варіантів.

.  (1.175)

Тому

.

В таблиці 1.9 наведено наближені значення P(365,k).

Таблиця 1.9 – Значення P(365,k)

k

10

20

30

40

50

60

70

P

0,13

0,4

0,71

0,89

0,97

0,99

0,999

При інтуїтивному розгляді в розв’язку можна знайти парадокс. Це пов’язано з тим, що для кожної окремої особи в групі імовірність того, що з його днем народження співпадає день народження ще когось із групи, достатньо мала. Але тут необхідно розглядати усі пари людей. Наприклад, в групі із 40 осіб буде

різних пар,

тому й імовірність для k=40 в таблиці достатньо велика.

Задача 4.

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

,

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

Розв’язок задачі:

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

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

.     (1.176)

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

.                                      (1.177)

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

, для усіх .                                  (1.178)

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

.                                                 (1.179)

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

  (1.180)

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

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

  (1.181)

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

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

то

або

,

і далі

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

.                                    (1.182)

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

.

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

.                                         (1.183)

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

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

.

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

і

.                                    (1.184)

При n=2160 , маємо k==280.

При n=2256, k=2128.

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

.                     (1.185)

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

1.11.2 Задачі для самостійного розв’язання

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

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

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

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

,

якщо .

Визначте складність та безпечний час здійснення колізії для отриманого значення k, якщо потужність криптоаналітичної системи складає 108,1010, 1012 та 1016 опер./с., а r – номер реєстрації за журналом.

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

,

якщо Рз=0,5+0,01r, n=2192+r, де r – номер реєстрації за журналом.

1.11.3 Контрольні запитання та завдання

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

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

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

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

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

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

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

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

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

10. Побудуйте графіки залежності

та

для х=0;0,1;0,2;0,3;0,4;0,5;0,6;0,7;0,8;0,9;1,0 та знайдіть значення параметра, при якому похибка складає не більше 10%.

11. Яка ймовірність того, що в групі студентів із 50 осіб двоє з них народилися в один день?

12. Яка ймовірність колізії на виході функції хешування, якщо довжина вихідного значення 128, 160, 192, 224, 256, 512 бітів і зроблено k=2128  експериментів?

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

14. Знайдіть ймовірність перекриття гами шифруючої з періодом 2128, якщо згенеровано відрізок 2100.

14. Знайдіть довжину відрізка гами шифруючої потокового шифру при якій ймовірність перекриття не перевищує 0,6 , якщо період гами 2128.

114. Як обчислити ймовірність колізії, якщо в (1.178) .


 

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

71221. Исследование программного комплекса RPS2 86.45 MB
  Рассчитаем область прямой видимости каждой из станций: Зона прямой видимости для БС1 для антенны высотой 30 м: Зона прямой видимости для БС2 для антенны высотой 40 м: Зона прямой видимости для БС2 для антенны высотой 50 м: Зона прямой видимости для БС3 для антенны высотой 30 м...
71222. Базы данных, лабораторный практикум 1.8 MB
  Компьютерную базу данных можно создать несколькими способами: С помощью алгоритмических языков программирования, таких как Basic, Pascal, C++ и т.д. Данный способ применяется для создания уникальных баз данных. С помощью прикладной среды, например Visual Basic.
71223. Разработка узкополосного малошумящего усилителя 924.5 KB
  Изучить получение оценок характеристик модели усилителя Изучить средства оптимизации и настройки параметров схемы. Осуществить оптимизацию параметров МШУ. Используя средства настройки схемы определить влияние параметров элементов согласующих цепей на характеристики МШУ.
71225. Оперативное запоминающее устройство 2.98 MB
  Цель работы Разработка оперативного запоминающего устройства. Содержание работы Реализация схемы статического оперативного запоминающего устройства и ее исследование. Порядок выполнения работы 1. Оформлен отчет по результатам выполнения лабораторной работы.
71226. ОСНОВЫ РАБОТЫ В ADOBE PHOTOSHOP CS 25.36 MB
  В лабораторных работах изучаются основы работы с редактором растровой графики Adobe Photoshop CS. Для этого рассматриваются элементарные файловые операции: запуск программы, открытие и закрытие файлов. Рассматриваются основные элементы интерфейса и некоторые особенности растровых изображений.
71227. Измерение коэффициента трансформации трансформатора тока 25.7 KB
  У встроенных трансформаторов тока коэффициент трансформации проверяется на всех ответвлениях. В случае, когда ответвления встроенных трансформаторов тока не имеют маркировки или она недостаточно четка, необходимо проверить ее и маркировать на основании результатов...
71228. Изучение испытательных стендов и измерительных приборов 157.11 KB
  Для пуска электродвигателя и регулирования нагрузки реостат с пультом управления. На щетке приборов вмонтирован тахометр об термометр воды тв манометр масла м и циферблат цф показывает силу торможения испытываемого двигателя кг датчик тахометра соединен с карданным валом...
71229. Створення проекту у середовищі Visual Fox Pro 9.0. Проектування бази даних, таблиць у складі бази даних та вільних таблиць 71.72 KB
  Мета: Засвоїти методи створення баз даних. Вивчити типи полів таблиць. Хід роботи Створіть новий проект за допомогою майстра. Створено проект під назвою KompShop за допомогою майстра.