Слайд 1МОДУЛЬ № 5
ВИКОРИСТАННЯ ХЕШ-ФУНКЦІЙ ДЛЯ ЗАБЕЗПЕЧЕННЯ ЦІЛІСНОСТІ ДАНИХ (ПОВІДОМЛЕНЬ)
1
Слайд 2Лекція № 29
ЗАХИСТ ЦІЛІСНОСТІ ДАНИХ З ВИКОРИСТАННЯМ ХЕШ-ФУНКЦІЇ SECURE HASH
ALGORITHM
(SHA-2)
2
Слайд 3ПИТАННЯ ЛЕКЦІЇ № 29
1. Структура алгоритму ітеративно го хешування SHA-512
2.
Структура функції стиску алго ритму ітеративного хешування SHA-512
3. Логіка роботи
кожного з раундів функції стиску алгоритму ітера тивного хешування SHA-512
Література: Л3, с. 177 – 181.
3
Слайд 44
1. СТРУКТУРА АЛГОРИТМУ ІТЕРАТИВНОГО ГЕШУВАННЯ SHA-512
Слайд 55
SHA (англ. Secure Hash Algorithm) – сі мейство алгоритмів безпечного
хешуван ня. Алгоритми цього сімейства засновані на схемі Меркеля-Дамгарда.
Розглянемо хеш-функцію
SHA-512 з 512-бітовим дайджестом повідомлення. Чи сло раундів у кожній ітерації - 80.
Вона сама пізня, має більш повну стру ктуру, що інші, і найбільш довгим дайджес том повідомлення.
Слайд 66
SHA-512 вимагає, щоб довжина пер вісного повідомлення була менше, чим
2128 бітів. Якщо довжина повідомлення рівна або більше, чим 2128,
воно не буде оброб лено SHA-512. Це звичайно не проблема, тому що 2128 бітів перевершують можливу сьогодні повну ємність зберігання будь -якої системи.
SHA-512 створює дайджест повідом лення на 512 бітів з повідомлення меншого, чому 2128.
Слайд 77
Перш ніж дайджест повідомлення мо же бути створений, SHA-512 вимагає
дода вання поля довжини - це ціле число без знака
на 128 бітів, яке визначає довжину повідомлення в бітах з повідомленням. Це довжина первісного повідомлення перед заповненням.
Поле цілого числа без знака 128 бітів можна визначити як число між 0 і 2128 - 1, яке є максимальною довжиною повідом-лення, прийнятого в SHA-512 (рис. 29.1).
Слайд 8 Рис. 29.1. Заповнення й поле довжини в SHA-512
8
Перед додаванням поля
довжини нео-бхідно доповнити первісне повідомлення, щоб зробити довжину кратної 1024
біт.
Слайд 99
Довжина області заповнення може бу ти розрахована в такий спосіб.
Нехай
nM - довжина первісного пові домлення й nД - довжина
поля заповнення:
(nM + nД + 128) mod 1024 = 0.
Звідки
nД = (- nM - 128) mod 1024.
Формат заповнення - це одна 1, супро воджувана необхідним числом нулів (0).
Слайд 1010
SHA-512 створює дайджест із повідом лення, що містить багато блоків.
Кожний блок має довжину 1024 біта, як це показане на
рис. 29.2.
Слайд 1111
Рис. 29.2. Створення дайджесту повідомлення SHA-512
Слайд 1212
Дайджест спочатку встановлюється на певне заздалегідь значення 512 бітів. Алго
ритм змішує це початкове значення з пер шим блоком повідомлення,
щоб створити перший проміжний дайджест повідомлен ня 512 бітів. Цей дайджест потім змішуєть ся із другим блоком, щоб створити другий проміжний дайджест. Нарешті, L-1-й дайд жест змішується з L-м блоком - вони ство рюють L-й дайджест. Коли останній блок оброблений, то результуючий дайджест - це дайджест повного повідомлення.
Слайд 1313
2. СТРУКТУРА ФУНКЦІЇ СТИСКУ АЛГОРИТМУ ІТЕРАТИВНОГО ХЕШУВАННЯ SHA-512
Слайд 1414
SHA-512 створює 512 бітів дайджесту для повідомлення (вісім слів по
64 біта) з повідомлення, яке складається із множини блоків, де
кожний блок містить 1024 біта. Дайджест повідомлення - тільки вісім слів (8 x 64 = 512), і слова позначають A, B, C, D, E, F, G і H, як показано на рис. 29.3.
Слайд 1515
Рис. 29.3. Блок повідомлення й дайджест у вигляді окремих слів
Слайд 1616
Алгоритм використовує вісім констант для ініціалізації дайджесту повідомлення. Позначимо їх
від A0 до H0, що відповідає позначенню слів, використовуваних для
дайджесту. Табл. 29.1 показує значення цих констант.
Слайд 1717
Таблиця 29.1
Значення констант при ініціалізації дайджесту повідомлення SHA-512
Слайд 1818
Вони розраховані з перших восьми простих чисел (2, 3, 5,
7, 11, 13, 17 і 19).
Кожне значення - дробова частина
квадратного кореня відповідного простого числа після перетворення до двійкової форми й збереження тільки перших 64 бі тів.
Наприклад, восьме просте число - 19 має квадратний корінь
191/2 = 4,35889894354.
Перетворюючи число до двійкової форми тільки з 64 бітами в дробовій час тині, ми маємо
Слайд 1919
(100.0101 1011 1110... 1001)2 →
→ (4,5BEOCD19137E2179)16
SHA-512 зберігає дробову
частину 5BEOCD19137E217916 як ціле число без знака.
Обробка кожного блоку даних
в SHA -512 включає 80 раундів. Рис. 29.4 показує загальну схему стиску функції.
Слайд 2020
Рис. 29.4. Функція стиску в SHA-512
Слайд 2121
У кожному раунді зміст восьми попе редніх буферів, одне слово
з розширеного блоку (Wi), і одна константа на 64 біта
(Ki), змішані разом. Вони обробляються, щоб створити нову множину з восьми буферів. На початку обробки значення восьми буфе рів збережені як вісім тимчасових змінних. Наприкінці обробки, після того як зробле ний крок 79, ці значення додаються до зна чень, створених на кроці 79. Позначимо цю останню операцію фінальним додаванням, як це показане на рис. 29.4.
Слайд 2222
Перед обробкою кожний блок повідом лення повинен бути розширений. Блок
ут ворений з 1024 бітів, або шістнадцяти слів по 64
біта. Як видно з рис. 27.3, при оброб ки потрібно 80 слів. Так що блок з 16-ю сло вами повинен бути розширений до 80 слів: від W0 до W79. Рис. 29.5 показує процес роз ширення слів.
Слайд 2323
Рис. 29.5. Розширення слів в SHA -512
Слайд 2424
На рис. 29.5 представлені функції RotShift, які мають такий вигляд
де
Rotr i (x) - команда циклічного переміщен-ня (зсуву) аргументу x
на i біт вправо;
Shl n (x) – команда логічного переміщення (зсуву) аргументу x на n біт вліво.
Приклад. Нехай x має вісім розрядів і рівний: x = 11100101.
Слайд 2525
Якщо виконати команду y = Rotr 3 (x), то результат
буде рівний: y = 10111100.
Якщо виконати команду y = Shl
2 (x), то результат буде рівний: y = 10010100.
Блок на 1024 біта породжує перші сло ва (16); інша частина слів виходить від уже зроблених слів згідно з операціями, які по казані на рис. 29.6.
Приклад.
Показати, як одержати W60.
Слайд 2626
Розв'язок.
Кожне слово в діапазоні від W16 до W79 отримується в
результаті обробки чотирь ох слів, створених на попередніх кроках. W60
отримується як
W60 = W44 RotShift 1-8-7 (W45)
W53 RotShift 19-61-6(W58).
Слайд 2727
Є 80 констант, K0 до K79, кожна по 64 бі
та, як показано в табл. 29.2 у шістнадцяти річної формі
(чотири в кожному рядку таб лиці).
Ці значення обчислені з перших 80 простих чисел (2, 3, …, 409) аналогічно по чатковим значенням для восьми буферів.
Слайд 2828
Таблиця 29.2
Вісімдесят констант, використовуваних для вісімдесяти раундів в SHA-512
Слайд 2929
Таблиця 29.2
Вісімдесят констант, використовуваних для вісімдесяти раундів в SHA-512
Слайд 3030
Кожне значення - дробова частина ку бічного кореня з відповідного
простого чис ла після перетворення цього числа до двій кової
форми, зберігаються тільки перші 64 біта. Наприклад, 80-е просте число - 409. Кубічний корінь 4091/3 = 7,42291412044. Перетворюючи це число до двійкового ви гляду тільки з 64 бітами в дробовій частині, ми одержуємо
111,0110 1100 0100 0100...01112 →
→ 7,6C44198C4A47581716.
Слайд 3131
SHA-512 зберігає дробову частину
6C44198C4A47581716
як ціле число без знака.
Слайд 3232
3. СТРУКТУРА ФУНКЦІЇ СТИСКУ АЛГОРИТМУ ІТЕРАТИВНОГО ХЕШУВАННЯ SHA-512
Рис. 29.5 показує
загальну схему стис ку функції.
Слайд 3333
Рис. 29.6. Структура кожного раунду в
SHA-512
Слайд 3434
У кожному раунді створюються вісім нових, у порівнянні з попереднім
раундом, значень буферів по 64 біта. На рис. 29.6 ми
бачимо, що шість буферів - точні копії по переднього раунду, як це показане нижче:
B ← A C ← B D ← C F ← E G ← F H ← G.
Два нові буфери, A і E, одержують від повідні значення від деяких складних фун кцій, які містять у собі деякі значення попе редніх буферів, які залежать від слова для цього раунду (Wi) і константи для цього раунду (Ki).
Слайд 3535
На рис. 29.6 наведені два змішувача, три функції й кілька
операторів (шість). Кожний змішувач обробляє дві функції. Опис функцій і
операторів наведене нижче.
1. Мажоритарна функція (Ma - на рис. 29.6), є порозрядної функцією. Вона вико-ристовує три відповідні біти в трьох буфе-рах (A, B і C) і обчислює
(Aj AND Bj) (Bj AND Cj) (Cj AND Aj),
j = 0,1,…,63.
Слайд 3636
Результат - це значення, яке має біль шість із трьох
біт. Якщо два або три біти дорівнюють одиниці (1), то
результат має значення біт 1; інакше він рівний 0.
2. Умовна функція додавання (Ch - на рис. 27.6) - також порозрядна функція. Вона використовує три біти, які втри муються в трьох буферах (E, F і G), і обчис лює
(Ej AND Fj) (NOT Ej AND Gj),
j = 0,1,…,63.
Слайд 3737
Результат підкоряється логіці "Якщо E, те F; інакше G".
2. Функція
циклічного переміщення (Σ - на рис. 27.6) обробляє три значення
одного буфера (A або E) і застосовує операцію xor з результатом мажоритарної функції:
Σ0 =Σ(A) = Rotr28(A) Rotr34(A) Rotr39(A);
Σ1 =Σ(E) = Rotr14(E) Rotr18(E) Rotr41(E).
Слайд 3832
3. Функція циклічного переміщення вправо (Rotr i (x)) - та
ж сама, яку ми вико ристовували в процесі розширення слів.
4.
Оператор додавання, застосовува ний у процесі, - додавання по модулю 264. Він визначає результат додавання двох або більше буферів, що містять завжди слово на 64 біта.
Приклад.
Застосуємо мажоритарну функцію до значень буферів A, B і C. Якщо крайні ліві шістнадцяткові цифри цих буферів - 0x7, 0xa і 0xe відповідно, то яка цифра буде крайньою лівою частиною результату?
Слайд 3939
Розв'язок
Цифри у двійковій формі - 0111, 1010 і 1110. Перші
біти - 0, 1 і 1. Мажоритарна фун кція рівна
1. Ми можемо довести це, вико ристовуючи визначення мажоритарної функції:
(0 AND 1) (1 AND 1) (1 AND 0) =
= 0 1 0 = 1.
Другі біти - 1, 0 і 1. Мажоритарна функ ція рівна 1. Треті біти - 1, 1 і 1. Мажоритарна функція рівна 1. Четверті біти - 1, 0 і 0. Мажоритарна функція рівна 0.
Слайд 4040
Результат - 1110, або 0xe у шістнад цяткової формі.
Приклад.
Застосовуємо умовну
функцію дода-вання для буферів E, F і G. Якщо крайні
ліві шістнадцяткові цифри цих буферів - 0x9, 0xa і 0xf відповідно, то яка цифра буде крайньою лівою частиною результату?
Розв'язок
Цифри у двійковій формі - 1001, 1010 і 1111.
Слайд 4141
Перші біти - 1, 1 і 1. Отже, E1 =
1, F1 = 1 і G1 = 1. Результат –
1. Щоб довести резуль тат, ми можемо також використовувати ви значення функції додавання для буферів E, F і G:
(1 AND 1) (NOT 1 AND 1) = 1 0 = 1
Другі біти - 0, 0 і 1. Отже, E2 = 0, F2 = 0 і G2 = 1. Результат – 1.
Треті біти утворюють дугу 0, 1 і 1. Отже, результат рівний 1.
Четверті біти - 1, 0 і 1. Отже, результат рівний 0.
Слайд 4242
Разом, загальний результат - 1110, або 0xe у шістнадцятирічної формі.
Слайд 4343
ВИСНОВКИ ЗА ЛЕКЦІЄЮ
З дайджестом повідомлення 512 бітів від SHA-512 очікувалося,
що він буде більш стійким до всіх типів атак, включаючи
ата ки колізії.
Він повинен був бути кращим проек том цієї версії: більш ефективним і більш безпечним, чому попередні.
Однак необхідні були серйозні дослід ження й випробування, для того щоб це підтвердити.