Схеми електронного цифрового підпису — основна сфера застосування геш-функцій. Оскільки використовувані на практиці схеми електронного підпису не пристосовані для підписання повідомлень довільної довжини, а процедура, що полягає в розбивці повідомлення на блоки і генерації підпису для кожного блоку окремо украй неефективна, єдиним розумним рішенням представляється застосування схеми підпису до геш-коду повідомлення.
Геш-функції можуть будуватися за допомогою різних алгоритмів, на основі різних методів шифрування. Ми розглянемо геш-функцію, побудовану на основі обчислювально важкої математичної задачіз рекомендацій МККТТ Х.509 [5].
Криптографічна стійкість даної функції заснована на складності рішення наступної складновирішуємої теоретико-числової задачі. Задача множення двох великих (довжиною в кілька сотень біт) простих чисел є простою з обчислювальної точки зору, у той час як факторизація (розкладання на прості множники) отриманого добутку є складновирішуємою задачею для зазначених розмірностей.
Слід зазначити, що задача розкладання числа на прості множники еквівалентна наступній складновирішуємій математичній задачі. Нехай п = pq добуток двох простих чисел р и q. У цьому випадку можна легко обчислити квадрат числа по модулю п: x2(mod n), однак обчислювально важко знайти квадратний корінь по цьому модулю [16].
Таким чином, геш-функцію МККТТ Х.509 (у спрощеному варіанті) можна записати в такий спосіб:
Hi = [(Hi-1 + Mi)2] (mod n), (1)
Де i змінюється від 1 до n, Hi – проміжні значення гешу, Mi – блоки гешуємого тексту (у нашому прикладі це звичайні букви, але в загальному випадку це блоки символів). Hn – кінцеве значення, результат гешування. (Слід зазначити, що звичайне додавання в (1) може бути замінено побітовим додаванням по модулю 2, тоді в програмі потрібно знак операції «+» замінити на «xor»)
Розглянемо приклад. Гешуєме слово «ДВА». Коефіцієнти р = 7, q = 3. Вектор ініціалізації Н0 виберемо рівним 6 (вибирається випадковим чином). Визначимо п = pq = 7 • 3 = 21. Слово «ДВА» у числовому еквіваленті можна представити як 531 (по номеру букви в алфавіті). Тоді геш-код повідомлення 531 виходить у такий спосіб:
перша ітерація:
М1 + H0 = 5 + 6= 11; [M1 + H0]2 (mod n) = 112 (mod 21) = 16 = H1;
друга ітерація:
М2 + H1 = 3 + 16 = 19; [М2 + H1]2 (mod n) = 192 (mod 21) = 4 = H2;
третя ітерація:
М3 + H2 = 1 + 4 = 5; [М3 + H2]2 (mod n) = 52 (mod 21) = 4 = H3.
У підсумку одержуємо геш-код повідомлення «ДВА», рівний 4.
В останній час найбільше поширення дістали наступні алгоритми гешування:
MD4 – функція, винайдена компанією RSA DSI. Діє з найбільшою швидкістю. Нещодавно була зламана.
MD5 – функція, що є удосконаленою модифікацією MD4. Найбільш поширена в даний момент.
SHA – функція, що входить до Державного стандарту цифрового підпису (DSS), виробленого АНБ.
Пояснення: геш-коди можуть виходити різної довжини, але це відбувається тому, що ми беремо різні значення p і q. Якби ми користувалися однаковими значеннями p і q, то довжина геш-коду в бінарному вигляді завжди дорівнювала б [log2 n] +1 = [log2 p×q] +1, де квадратні дужки означають цілу частину.
Виконання гешування в ручному режимі аналогічно розглянутому в прикладі теоретичної частини. Покажемо на прикладі виконання операції mod на звичайному калькуляторі. Обчислимо, наприклад, 313 mod 23. Ділимо 313 на 23:
313/23 » 13,6.
Тоді множимо 23 на 13 (беремо цілу частину від результату ділення) і віднімаємо від 313:
23*13 = 299; 313 – 299 = 14.
Результат операції 14, тобто 313 mod 23 = 14.
У загальному виді:
A mod B = A – [A/B]*B,
Де квадратні дужки позначають узяття цілої частини [16].
Порядок виконання лабораторної роботи.
1. Вивчити основні відомості про геш-функції.
2. Гешувати слово вручну. Слово, що гешується вибирається відповідно до номеру студента у списку групи. Завдання представлені в додатку 1.
3. Алфавіт для шифрування: _АБВГДЕЄЖЗИІЇЙКЛМНОПРСТУФХЦЧШЩЬЮЯ
4. Геш
повідомлення обчислюється за наступною формулою:
Hі=[Mі + Hі-1]2 mod
(pq), H0=13;
5. Скласти звіт, у якому необхідно навести свої вихідні данні, поновлений текст і відповіді на контрольні запитання
Контрольні питання
1. Що таке геш-функція?
2. Де застосовується геш-функція?
3. Що таке колізії?
4. Яким чином можна позбутись колізій у геш-функціях?
5. Які існують геш-функції?
Частина III. Криптоаналіз
3.1. Лабораторна робота № 13. Первинний аналіз шифровки. Іспити збігу.
Тема роботи: Первинний аналіз шифровки. Іспити збігу.
Ціль роботи: на практиці відпрацювати вміння визначення типу шифрування лише за шифртекстом. Закріпити знання про типи шифрів та їх особливості.
Загальні відомості
PHI-тест призначений для визначення імовірного методу шифрування шляхом оцінки нерівномірності розподілу частот в порівнянні з абсолютно випадковим набором символів. Тест заснований на деяких положеннях теорії імовірності та комбінаторики.
Теоретичні відомості
Оцінку того, чи має даний розподіл частот (тут під частотою розуміється кількість символів у тексті) ту ж саму нерівномірність що і звичайний або випадковий текст, непросто робити на око. Щоб допомогти криптоаналітику в цьому, була розроблена безліч статистичних іспитів. Іспити засновані на теорії імовірностей, але ви можете використовувати іспити, навіть якщо ви не знайомі з основами цієї теорії. Найбільш загальні іспити називаються іспитами збігу[2].
Якщо Ви вибираєте будь-які два символи з повідомлення, порівнюєте їх разом, і вони виявляються однаковими, то говорять, що ці символи збігаються. Порівняння символу із самим собою вважається збігом. Це порівняння може бути зроблене для окремих символів, пар символів (біграм) або більш довгих послідовностей символів.
 |
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.