Хеш-функция (хэш-функция) — это функция, преобразующая входные данные (произвольного размера) в выходную строку фиксированного размера, называемую хешем, или дайджестом сообщения.
Основные свойства хеш-функций:
- Детерминированность: Одинаковые входные данные всегда дают одинаковый хеш.
- Вычислительная эффективность: Вычисление хеша должно быть быстрым.
- Чувствительность к изменениям: Даже небольшое изменение входных данных должно приводить к значительному изменению хеша ("эффект лавины").
- Односторонность: По хешу практически невозможно восстановить исходные данные.
- Устойчивость к коллизиям: Должно быть очень трудно найти два разных входных сообщения, которые дают одинаковый хеш.
Типы хеш-функций:
- Криптографические хеш-функции: Используются в криптографии для обеспечения целостности данных, цифровых подписей (MD5, SHA-1, SHA-256, SHA-3). MD5 и SHA-1 считаются менее безопасными из-за найденных уязвимостей.
- Некриптографические хеш-функции: Используются для ускорения поиска данных (например, в хеш-таблицах), контрольных сумм (CRC32). Не обладают свойствами устойчивости к коллизиям или односторонности.
Применение хеш-функций в Python:
- Хеш-таблицы (словари): Внутренне используют хеширование для быстрого доступа к элементам по ключу. Ключи словарей должны быть хешируемыми (immutability).
- Множества (sets): Аналогично, используют хеши для хранения уникальных элементов.
- Проверка целостности файлов: Сравнение хешей до и после передачи данных.
- Хранение паролей: Вместо хранения самих паролей хранят их хеши (с использованием соли для усложнения атак по словарю).
- Криптографические операции: Библиотека
hashlib предоставляет доступ к различным криптографическим хеш-функциям.
Пример использования hashlib:
python
Свойства хешируемых объектов в Python:
- Объект должен иметь метод
__hash__, возвращающий целое число.
- Объект должен иметь метод
__eq__ для сравнения на равенство.
- Если
a == b, то hash(a) должно быть равно hash(b).
- Как правило, только неизменяемые (immutable) объекты (строки, числа, кортежи) хешируемы по умолчанию. Изменяемые объекты (списки, словари) нехешируемы.