Hash функції
Що таке хеш функція? В математичному сенсі, це функція що для будь-якого довільного значення має єдине та незмінне значення з фіксованого діапазону.
Для прикладу, хеш-функція SHA256 видає значення в діапазоні від 0 до ²²⁵⁶, яке зазвичай представляють у hex.
Вимогами до хеш-функцій є
- Незворотність: для заданого значення хеш-функції m має бути обчислювально неможливо знайти блок даних X, для якого H(X)=m.
- Стійкість колізіям першого роду: для заданого повідомлення M має бути обчислювально неможливо підібрати інше повідомлення N, для якого H(N) = H(M)
- Стійкість до колізій другого роду: має бути обчислювально неможливо підібрати пару повідомлень (M, M’), що мають однаковий хеш.
Цікаво, що швидкість обчислення значення хеш-функції може бути як бажаною так і небажаною властивістю і залежить від сфери використання. Для структур даних як hash map потрібні швидкі хеші з хорошою розподільністю, а для хешування паролей — функції, що обмежують використання FPGA, ASIC, GPU та створені бути обчислювально складними (Argon2, bcrypt, scrypt).
Приклади використання хеш-функцій:
- Кеш
- Хеш таблиці та інші структури даних
- Цифрові підписи (цілістність та автентифікація)
- Пошук дублікатів
- Перевірка цілістності інформації по аналогії роботи контрольних сум
Корисний лінк по темі криптографії, правильні відповіді:
Про такі речі ми пишемо на нашій сторінці TechMaker в Facebook та розповідаємо на курсах