Однонаправлені хеш-функції - Студопедія
Хеш-функція призначена для стиснення документа, що підписується, до декількох десятків або сотень біт. Хеш-функція приймає як аргумент повідомлення (документ) довільної довжини і повертає хеш-значення фіксованої довжини. Зазвичай хешована інформація є стислим двійковим поданням основного повідомлення довільної довжини. Слід зазначити, що значення хеш-функції складно залежить від документа і дозволяє відновити сам документ .
Хеш-функція повинна задовольняти цілу низку умов:
- хеш-функція має бути чутливою до всіляких змін у тексті М, таких як вставки, викиди, перестановки тощо;
- хеш-функція повинна мати властивість незворотності, тобто завдання підбору документа, який мав би необхідне значення хеш-функції, має бути обчислювально нерозв'язною;
- ймовірність того, що значення хеш-функції двох різних документів (незалежно від їх довжин) збігатимуться, має бути мізерно мала.
Більшість хеш-функції будується з урахуванням односпрямованої функції , аргументами, якої є дві величини: блок вихідного документа і хеш-значення , попереднього блоку документа (рис.7.1): .
Хеш-значення, що обчислюється при введенні останнього блоку тексту, стає хеш-значенням всього повідомлення . В результаті односпрямована хеш-функція завжди формує вихід фіксованої довжини (незалежно від довжини вхідного тексту).
Часто функції хешування будують, використовуючи як односпрямовану функцію – симетричний блоковий алгоритм шифрування (DES, ГОСТ 28147-89) в режимі зі зворотним зв'язком, приймаючи останній блок шифротексту за хеш-значення всього документа. Оскільки довжина блоку у зазначених алгоритмах невелика(64 біта), то часто як хеш-значення використовують два блоки шифротексту. Одна з можливих схем хешування на основі блокового алгоритму шифрування зображена на рис.7.2.
Першою і найвідомішою у всьому світі конкретною системою ЕЦП стала система RSA, математична схема якої була розроблена в 1977 р. у Массачусетському технологічному інституті США.
Допустимо, що відправник хоче підписати повідомлення перед його відправкою. Спочатку повідомлення (блок інформації, файл, таблиця) стискають за допомогою хеш-функції ціле число . Потім обчислюють цифровий підпис під електронним документом, використовуючи хеш-значення та секретний ключ: . Пара передається партнеру-отримувачу як електронний документ, підписаний цифровим підписом, причому підпис сформований власником секретного ключа. Після прийому пари одержувач обчислює хеш значення повідомлення двома різними способами. Насамперед, він відновлює хеш-значення , застосовуючи криптографічне перетворення підписи з допомогою відкритого ключа : . Крім того, він знаходить результат хешування прийнятого повідомлення за допомогою такої самої хеш-функції: . Якщо дотримується рівність обчислених значень, тобто. , то одержувач визнає пару справжньою. Доведено, що тільки власник секретного ключа може сформувати цифровий підпис за документом, а визначити секретне число за відкритим числом не легше, ніж розкласти модуль на множники. Крім того, можна суворо математично довести, що результат перевірки цифрового підпису буде позитивним лише в тому випадку, якщо при обчисленні був використаний секретний ключ, який відповідає відкритому ключу. Тому відкритий ключ іноді називають "ідентифікатором" підпису.
Недоліками алгоритму цифрового підпису RSA є:
1. При обчисленні модуля , ключів та системи цифрового підпису RSA необхідно перевіряти велику кількість додаткових умов, що зробити практично важко. Невиконання будь-якої з цих умов уможливлює фальсифікацію цифрового підпису з боку того, хто виявить таке невиконання під час підписання важливих документів, не можна допускати таку можливість навіть теоретично.
2. Для забезпечення криптостійкості цифрового підпису RSA стосовно спроб фальсифікації лише на рівні, наприклад, національного стандарту США шифрування інформації (алгоритм DES), тобто. , необхідно використовувати при обчисленнях і цілі числа не менше (або близько ) кожне, що вимагає великих обчислювальних витрат, що перевищують на 20..30% обчислювальні витрати інших алгоритмів цифрового підпису при збереженні того ж рівня криптостійкості.
3. Цифровий підпис RSA вразливий до так званої мультиплікативної атаки. Інакше висловлюючись, алгоритм цифрового підпису RSA дозволяє зловмиснику без знання секретного ключа сформувати підписи під тими документами, які мають результат хешування можна визначити як добуток результатів хешування вже підписаних документів.
Приклад 7.1. Припустимо, що зловмисник може сконструювати три повідомлення , і , у яких хеш-значення , , , Причому . Допустимо також, що для двох повідомлень та отримано законні підписи та
Тоді зловмисник може легко вирахувати підпис S3 для документа Мз, навіть не знаючи секретного ключа