Hash функції

Що таке хеш функція? В математичному сенсі, це функція що для будь-якого довільного значення має єдине та незмінне значення з фіксованого діапазону.
Для прикладу, хеш-функція SHA256 видає значення в діапазоні від 0 до ²²⁵⁶, яке зазвичай представляють у hex.

Результат SHA256 при обчисленні тексту “TechMaker”

Вимогами до хеш-функцій є

  • Незворотність: для заданого значення хеш-функції m має бути обчислювально неможливо знайти блок даних X, для якого H(X)=m.
  • Стійкість колізіям першого роду: для заданого повідомлення M має бути обчислювально неможливо підібрати інше повідомлення N, для якого H(N) = H(M)
  • Стійкість до колізій другого роду: має бути обчислювально неможливо підібрати пару повідомлень (M, M’), що мають однаковий хеш.

Цікаво, що швидкість обчислення значення хеш-функції може бути як бажаною так і небажаною властивістю і залежить від сфери використання. Для структур даних як hash map потрібні швидкі хеші з хорошою розподільністю, а для хешування паролей — функції, що обмежують використання FPGA, ASIC, GPU та створені бути обчислювально складними (Argon2, bcrypt, scrypt).

Приклади використання хеш-функцій:

  • Кеш
  • Хеш таблиці та інші структури даних
  • Цифрові підписи (цілістність та автентифікація)
  • Пошук дублікатів
  • Перевірка цілістності інформації по аналогії роботи контрольних сум

Корисний лінк по темі криптографії, правильні відповіді:


Про такі речі ми пишемо на нашій сторінці TechMaker в Facebook та розповідаємо на курсах