Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
НАВЧАЛЬНА ДИСЦИПЛІНА ПРИКЛАДНА КРИПТОГРАФІЯ Частина II ЗАБЕЗПЕЧЕННЯ ЦІЛІСНОСТІ
Содержание
- 1. НАВЧАЛЬНА ДИСЦИПЛІНА ПРИКЛАДНА КРИПТОГРАФІЯ Частина II ЗАБЕЗПЕЧЕННЯ ЦІЛІСНОСТІ
- 2. МОДУЛЬ № 5ВИКОРИСТАННЯ ХЕШ-ФУНКЦІЙ ДЛЯ ЗАБЕЗПЕЧЕННЯ ЦІЛІСНОСТІ ДАНИХ (ПОВІДОМЛЕНЬ)
- 3. Лекція № 26КРИПТОСТІЙКІСТЬ ХЕШ-ФУНКЦІЙ ДЛЯ ЗАБЕСПЕЧЕННЯЦІЛІСНОСТІ ДАНИХ (ПОВІДОМЛЕНЬ)
- 4. ПИТАННЯ ЛЕКЦІЇ № 261. Випадкова модель Oracle2.
- 5. 1. ВИПАДКОВА МОДЕЛЬ ORACLE
- 6. Випадкова модель Oracle була запро понована в
- 7. 2. Коли передається повідомлення, для якого існує
- 8. Приклад 1. Оберемо модель Oracle з таблицею
- 9. Модель Oracle уже створила три дайд жести.Таблиця 26.1Таблиця Oracle після створення перших трьох дайджестів
- 10. Тепер припустимо, що виникають дві події: 1. Надходить
- 11. у якому буква О представляє "Орел", буква
- 12. Таблиця 26.2Таблиця Oracle після створення четвертого дайджесту
- 13. 2. Повідомлення4523AB1352CDEF45126подається для обчислення дайджесту. Oracle перевіряє свою
- 14. якщо n ящиків зайняті n+1 голубами, то
- 15. Це говорить про те, що принаймні один
- 16. Друге поняття, яке ми повинні знати перед
- 17. Проблема 1. Яке мінімальне число k студентів у
- 18. Проблема 2. Яке мінімальне число k студентів у
- 19. Проблема 3. Яке мінімальне число k студентів у
- 20. Проблема 4. Ми маємо два класи, кожний з
- 21. Яке мінімальне число k, таке, що з
- 22. Результати розв'язківТаблиця 26.3Результати розв'язків чотирьох проблем днів народження
- 23. Порівняння проблем Значення k у проблемах 1 або
- 24. Рис. 26.1. Граф чотирьох проблем дня народження
- 25. Для першої й другої проблем показано один
- 26. ВИСНОВКИ 1. Як видно з аналізу результатів рі
- 27. 2. АТАКИ ВИПАДКОВОЇ МОДЕЛІ ORACLE
- 28. 2.1. АТАКА ПРООБРАЗУ Єва перехопила дайджест D =
- 29. Щоб знайти ймовірність цього, ми ви користовуємо
- 30. Приклад. Криптографічна хеш-функція використовує довжину дайджеста 64
- 31. Це означає, що дайджест повідомлен ня розміром
- 32. 2.2. АТАКА ДРУГОГО ПРООБРАЗУ Єва перехопила дайджест D
- 33. Ми вже вказали це значення в табл.
- 34. 2.3. АТАКА КОЛІЗІЇ Єва повинна знайти два повідомлення,
- 35. Інакше кажучи, щоб Єва добилася сво го
- 36. Якщо Єва може перевірити 220 (майже один
- 37. 2.4. ДОДАТКОВА АТАКА КОЛІЗІЇРозглянути самостійно
- 38. 2.5. ПІДСУМКИ АТАК Таблиця 26.4 показує рівень склад-ності
- 39. ВИСНОВКИ Проблеми чотирьох днів народження використовуються, щоб проаналізувати
- 40. Скачать презентанцию
МОДУЛЬ № 5ВИКОРИСТАННЯ ХЕШ-ФУНКЦІЙ ДЛЯ ЗАБЕЗПЕЧЕННЯ ЦІЛІСНОСТІ ДАНИХ (ПОВІДОМЛЕНЬ)
Слайды и текст этой презентации
Слайд 1НАВЧАЛЬНА ДИСЦИПЛІНА
ПРИКЛАДНА КРИПТОГРАФІЯ
Частина II
ЗАБЕЗПЕЧЕННЯ ЦІЛІСНОСТІ ТА АУТЕНТИЧНОСТІ ДАНИХ
Слайд 6 Випадкова модель Oracle була запро понована в 1993 р. Белларом
(Bellare) і Роджеем (Rogaway).
Це ідеальна математична модель для хеш-функції. Функція,
яка заснована на цій моделі, має наступні властивості.1. Коли надходить нове повідомлення будь-якої довжини, Oracle породжує й ви робляє на виході дайджест-повідомлення фіксованої довжини, які складаються з ви падкових рядків нулів і одиниць. Це Oracle-запис повідомлення й дайджесту-повідом лення.
Слайд 7 2. Коли передається повідомлення, для якого існує дайджест, Oracle просто
вставляє дайджест у запис.
3. Дайджест для нового повідомлення повинен бути
обраний незалежно від усіх попередніх дайджестів. Це має на увазі, що модель Oracle не може використовувати формулу або алгоритм для обчислення дайджесту.
Слайд 8 Приклад 1. Оберемо модель Oracle з таблицею й правильною монетою.
Таблиця
має два стовпці. Лівий стов пець - повідомлення, дайджести яких
були вироблені. Другий стовпець перераховує дайджести, створені для цих повідомлень.Приймемо, що дайджест - завжди 16 бі тів незалежно від розміру повідомлення.
Табл. 26.1 показує приклад такої табли ці, у якій повідомлення й дайджест пові домлення наведені в шістнадцятковому ви гляді.
Слайд 9 Модель Oracle уже створила три дайд жести.
Таблиця 26.1
Таблиця Oracle після
створення перших трьох дайджестів
Слайд 10 Тепер припустимо, що виникають дві події:
1. Надходить повідомлення
AB1234CDS765BDAD
для обчислення дайджесту.
Oracle
перевіряє свою таблицю. Цього повідомлення немає в таблиці, так що
спів робітник, що використовує Oracle, підкидає в повітря свою монету 16 раз. Припустимо, що результатООРОООРРОРООРРРО,
Слайд 11у якому буква О представляє "Орел", буква Р представляє "Решка".
Oracle
інтерпретує О як 1 біт і Р як біт 0
і видає 1101 1100 1011 0001 у двійковому коді або DCB1 у шістнадцятковому, як дайджест повідомлення для цього пові домлення, і складає повідомлення й дайд-жест у таблиці (табл. 26.2).
Слайд 13 2. Повідомлення
4523AB1352CDEF45126
подається для обчислення дайджесту.
Oracle перевіряє свою таблицю й зна
ходить, що є дайджест для цього повідом лення в таблиці
(перший рядок).Oracle просто видає відповідний дайд жест (13AB).
Перше поняття, з яким ми повинні бути знайомі для того, щоб зрозуміти аналіз випадкової Моделі Oracle, - принцип голу биних ящиків:
Слайд 14 якщо n ящиків зайняті n+1 голубами, то принаймні один ящик
зайнято двома голу бами.
Узагальнена версія принципу голуби них ящиків: якщо
n ящиків зайняті k∙n+1 го лубами, то принаймні один ящик зайнятий k + 1 голубами.Припустимо, що повідомлення в хеш -функції довжиною 6 бітів, дайджести тільки довжиною 4 біта. Тоді можливе число дайджестів (ящики) - 24 = 16 і можливе чис ло повідомлень (голуби) - 26 = 64. Це оз начає n = 16 і k∙n+1 = 64, так що k більше, чим 3.
Слайд 15 Це говорить про те, що принаймні один дайджест відповідає чотирьом
(k+1) повідомленням.
Оскільки основна ідея хешування дик тує, що дайджест повинен
бути коротше, чим повідомлення, згідно із принципом го лубиних ящиків можуть бути конфлікти.Інакше кажучи, є деякі дайджести, які відповідають більше чому одному пові домленню.
Слайд 16 Друге поняття, яке ми повинні знати перед аналізом випадкової моделі
Oracle, відомо як проблема дня народження.
Звичайно в курсах теорії ймовірностей
зустрічаються із чотирма різними проб лемами дня народження, і третя з них іноді називається парадокс дня народження.
Слайд 17 Проблема 1.
Яке мінімальне число k студентів у класній кімнаті, таке,
що з деякою ймовір ністю (P ≥ 0,5) принаймні один
студент має заздалегідь заданий день народження?Ця проблема може бути узагальнена в такий спосіб. Ми маємо однородно розпо ділену випадкову змінну з N можливими значеннями (між 0 і N-1).
Яке мінімальне число екземплярів, та-ких, що з деякою ймовірністю принаймні один екземпляр рівний заздалегідь задано му значенню?
Слайд 18 Проблема 2.
Яке мінімальне число k студентів у класній кімнаті, таке,
що з деякою ймовір ністю принаймні один студент має той
же самий день народження, як і студент, обра ний викладачем?Ця проблема може бути узагальнена в такий спосіб. Ми маємо однородно розподі лену випадкову змінну з N можливими зна ченнями (між 0 і N-1).
Яке мінімальне число екземплярів, k, таких, що з деякою ймовірністю принаймні один екземпляр є рівним обраному?
Слайд 19 Проблема 3.
Яке мінімальне число k студентів у класній кімнаті, таке,
що із заданою ймовір ністю принаймні два студенти мають той
же самий день народження?Ця проблема може бути узагальнена в такий спосіб. Ми маємо однородно розподі лену випадкову змінну з N можливими зна ченнями (між 0 і N-1).
Яке мінімальне число екземплярів k, таких, що з деякою ймовірністю принаймні два екземпляри рівні?
Слайд 20 Проблема 4.
Ми маємо два класи, кожний з k сту-дентами. Яке
мінімальне значення k, таке, щоб принаймні один студент із першої
клас-ої кімнати з деякою ймовірністю мав той же самий день народження, що й сту дент із другої класної кімнати?Ця проблема може бути узагальнена в такий спосіб. Ми маємо однородно розподі лену випадкову змінну N зі значеннями (між 0 і N-1). Ми генеруємо дві множини ви падкових значень, кожне величиною k.
Слайд 21 Яке мінімальне число k, таке, що з де якою ймовірністю
принаймні один екземп ляр першої множини рівний одному зразку в
другій множині?
Слайд 23Порівняння проблем
Значення k у проблемах 1 або 2 про порційно
N; значення k у проблемах 3 або 4 є пропорційним
N1/2.Як ми побачимо коротко, перші дві проблеми пов'язані з атаками прообразу й другого прообразу; третя й четверта проб леми пов'язані з атакою колізії.
Порівняння показує, що набагато більш важко почати атаку прообразу або атаку другого прообразу, чому атаку колізії.
Рис. 26.1 дає граф P при різних k.
Слайд 25 Для першої й другої проблем показано один граф (значення ймовірностей
- дуже близькі).
Графи для другий і третьої проблем відрізняються сильніше.
Слайд 26ВИСНОВКИ
1. Як видно з аналізу результатів рі шення чотирьох проблем
днів народження, найбільш безпечними є проблеми 3 та 4. Тобто
найбільш слабким містом хеш -функцій є стійкість до колізій.2. Якщо не приймати ні якіх дій, Єва може знайти два повідомлення, які при водять до того ж самого дайджесту.
Слайд 282.1. АТАКА ПРООБРАЗУ
Єва перехопила дайджест D = h(M); во на
прагне знайти будь-яке повідомлення М', таке, що D = h(М').
Єва може створити список k повідомлень М' та може знайти повідомлення, для якого D є дайджестом, або може зазнати невдачу.Яка ймовірність успіху цього алгорит му?
Очевидно, це залежить від розміру списку, k, обраного Євою.
Слайд 29 Щоб знайти ймовірність цього, ми ви користовуємо першу проблему дня
народ ження.
Який повинен бути розмір k, якщо Єва повинна досягтися
успіху принаймні в 50 відсотках випадків?Ми показали це значення в табл. 26.3.
Для першої проблеми дня народження: k ≈ 0,69 × N, або k ≈ 0,69 × 2n.
Інакше кажучи, щоб Єва добилася сво го більш ніж в 50 відсотках випадків, вона повинна створити список дайджесту, який пропорційний 2n.
Слайд 30 Приклад. Криптографічна хеш-функція використовує довжину дайджеста 64 біта. Скільки дайджестів
Єва повинна створити, щоб знайти первісне повідомлення з імо вірністю
більшої, ніж 0,5?Розв'язок. Число дайджестів, які бу дуть створені - k ≈ 0,69×2n = 0,69 × 264.
Ми показали це значення в табл. 24.3.
Це велике значення. Навіть якщо Єва зможе генерувати 230 (майже один мільярд) повідомлень у секунду, потрібно 0,69 × 234 секунди або більше чому 500 років.
Слайд 31 Це означає, що дайджест повідомлен ня розміром 64 біта є
безпечним щодо ата-ки прообразу, але, як ми побачимо далі, він
не захищений від атаки колізії.
Слайд 322.2. АТАКА ДРУГОГО ПРООБРАЗУ
Єва перехопила дайджест D = h(M) і
відповідне повідомлення М; вона прагне знайти інше повідомлення M', таке,
щоб h(M') = D. Єва може створити список з k-1 повідомлень М' та може знайти повідом лення, для якого D є дайджестом, або може зазнати невдачу.Яка ймовірність успіху цього алгорит му?
Очевидно, це залежить від розміру списку, k, обраного Євою.
Слайд 33 Ми вже вказали це значення в табл. 26.3 для другої
проблеми дня народження: k ≈ 0,69×N+1, або k ≈ 0,69×2n.
Інакше кажучи, щоб Єва добилася свого більш ніж в 50 відсотках випадків, вона повинна створити список дайджесту, який пропорційний 2n.
Слайд 342.3. АТАКА КОЛІЗІЇ
Єва повинна знайти два повідомлення, М и М',
такі, що h(M) = h(М'). Вона може створити список k
повідомлень М', таки що М ≠ М' для яких дайджести однокові, або може зазнати невдачу.Яка ймовірність успіху цього алгоритму?
Очевидно, це залежить від розміру списку, k, обраного Євою. Ми вже вказали це значення в табл. 26.3 для третьої проб леми дня народження: k ≈ 1,18 × 2n/2.
Слайд 35 Інакше кажучи, щоб Єва добилася сво го більш ніж в
50 відсотках випадків, вона повинна створити список дайджесту, який пропорційний
2n/2.Приклад. Криптографічна хеш-функція використовує дайджест довжиною 64 біта. Скільки дайджестів Єва повинна створити, щоб знайти два пові-омлення з тим же са мим дайджестом з імовірністю не менш 0,5?
Розв'язок. Число дайджестів, які бу дуть створені, k ≈ 1,18×2n/2=1,18 × 232.
Слайд 36 Якщо Єва може перевірити 220 (майже один мільйон) повідомлень у
секунду, буде потрібно 1,18 × 212 секунд, або менше ніж
дві години. Це означає, що дайджест пові домлення розміру 64 бита небезпечний що-до атаки колізії.
Слайд 382.5. ПІДСУМКИ АТАК
Таблиця 26.4 показує рівень склад-ності для кожної атаки,
якщо дайджест має довжину n біт.
Таблиця 26.4
Рівні складності для кожного
типу атаки
Слайд 39ВИСНОВКИ
Проблеми чотирьох днів народження використовуються, щоб проаналізувати ви падкову модель
Oracle:
- перша проблема використовується, щоб проаналізувати атаку прообразу;
- друга проблема
- щоб проаналізувати атаку другого прообразу;третя й четверта проблеми націлені на атаку колізії.
