Хэш функция python своими руками

Добавил пользователь Morpheus
Обновлено: 05.10.2024

Если вам нужны хэш-функции adler32 или crc32, они доступны в модуле zlib .

Алгоритмы хеширования¶

Для каждого типа хеша существует один метод конструктора. Все они возвращают хэш-объект с одним и тем же простым интерфейсом. Например: воспользуемся sha256() для создания хеш-объекта SHA-256. Теперь вы можете заполнить этот объект байтоподобными объектами (обычно bytes ) с помощью метода update() . В любой момент вы можете запросить у него дайджест конкатенации данных, переданных ему до сих пор, с помощью методов digest() или hexdigest() .

Для повышения производительности многопоточности Python GIL отпускается для данных размером более 2047 байт при создании или обновлении объекта.

Подача строковых объектов в update() не поддерживается, поскольку хеши работают с байтами, а не с символами.

Например, чтобы получить дайджест байтовой строки b'Nobody inspects the spammish repetition' :

Общий конструктор, который принимает строку name желаемого алгоритма в качестве первого параметра. Он также существует, чтобы разрешить доступ к перечисленным выше хешам, а также к любым другим алгоритмам, которые может предложить ваша библиотека OpenSSL. Именованные конструкторы намного быстрее, чем new() , и им следует отдавать предпочтение.

Использование new() с алгоритмом, предоставленным OpenSSL:

Hashlib предоставляет следующие постоянные атрибуты:

Множество, содержащее имена хэш-алгоритмов, доступных в работающем интерпретаторе Python. Имена будут распознаны при передаче в new() . algorithms_guaranteed всегда будет подмножеством. Один и тот же алгоритм может появляться в этом множестве несколько раз под разными именами (благодаря OpenSSL).

Следующие значения предоставляются как постоянные атрибуты хэш-объектов, возвращаемых конструкторами:

Размер результирующего хэша в байтах.

Размер внутреннего блока хеш-алгоритма в байтах.

У хэш-объекта есть следующие атрибуты:

Каноническое имя этого хеша, всегда в нижнем регистре и всегда подходящее в качестве параметра для new() для создания другого хеша этого типа.

Изменено в версии 3.4: Атрибут name присутствует в CPython с момента его создания, но до тех пор, пока Python 3.4 не был официально указан, поэтому может не существовать на некоторых платформах.

У хэш-объекта есть следующие методы:

hash. update ( data ) ¶

Обновить хэш-объект с помощью байтоподобного объекта . Повторные вызовы эквивалентны одному вызову с объединением всех аргументов: m.update(a); m.update(b) эквивалентен m.update(a+b) .

Изменено в версии 3.1: Python GIL отпускается, чтобы позволить другим потокам работать, пока происходит обновление хэша для данных, размер которых превышает 2047 байт, при использовании алгоритмов хеширования, предоставляемых OpenSSL.

Вернуть дайджест данных, переданных на данный момент методу update() . Является байтовым объектом размером digest_size , который может содержать байты во всем диапазоне от 0 до 255.

Подобно digest() , за исключением того, что дайджест возвращается как строковый объект двойной длины, содержащий только шестнадцатеричные цифры. Можно использовать для безопасного обмена значениями по электронной почте или в других небинарных средах.

SHAKE дайджесты переменной длины¶

shake. digest ( length ) ¶

Вернуть дайджест данных, переданных на данный момент методу update() . Байтовый объект размером length, который может содержать байты во всем диапазоне от 0 до 255.

shake. hexdigest ( length ) ¶

Ключевой вывод¶

Алгоритмы получения и расширения ключей предназначены для безопасного хеширования паролей. Наивные алгоритмы, такие как sha1(password) , не устойчивы к атакам методом перебора. Хорошая функция хеширования паролей должна быть настраиваемой, медленной и включать соль.

hashlib. pbkdf2_hmac ( hash_name, password, salt, iterations, dklen=None ) ¶

Строка hash_name — желаемое имя алгоритма хеш-дайджеста для HMAC, например sha1 или sha256. password и salt интерпретируются как байтовые буферы. Приложения и библиотеки должны ограничивать password разумной длиной (например, 1024). salt должен быть около 16 или более байтов из правильного источника, например os.urandom() .

Номер iterations следует выбирать в зависимости от алгоритма хеширования и вычислительной мощности. По состоянию на 2013 год предлагается не менее 100 000 итераций SHA-256.

dklen — длина производного ключа. Если dklen — None , то используется размер дайджеста алгоритма хеширования hash_name, например 64 для SHA-512.

Быстрая реализация pbkdf2_hmac доступна с OpenSSL. Реализация Python использует встроенную версию hmac . Он примерно в три раза медленнее и не выпускает GIL.

Функция генерации ключей на основе пароля scrypt, как определено в RFC 7914.

password и salt должны быть байтоподобными объектами . Приложения и библиотеки должны ограничивать password разумной длиной (например, 1024). salt должен быть около 16 или более байтов из правильного источника, например os.urandom() .

n — коэффициент стоимости ЦПУ/памяти, r — размер блока, p коэффициент распараллеливания, а maxmem — ограничивает память (OpenSSL 1.1.0 по умолчанию равен 32 MiB). dklen — длина производного ключа.

BLAKE2¶

BLAKE2 — криптографическая хеш-функция, определенная в RFC 7693, которая бывает двух видов:

BLAKE2b, оптимизирован для 64-битных платформ и производит дайджесты любого размера от 1 до 64 байтов
BLAKE2s, оптимизирован для платформ от 8 до 32 бит и создает дайджесты любого размера от 1 до 32 байтов.

BLAKE2 поддерживает ключевой режим (более быстрая и простая замена HMAC), соленое хэширование, персонализация и древовидное хеширование.

Хеш-объекты из этого модуля следуют API объектов стандартной библиотеки hashlib .

Создание хеш-объектов¶

Новые хеш-объекты создаются путём вызова функций-конструкторов:

Функции возвращают соответствующие хэш-объекты для вычисления BLAKE2b или BLAKE2. При желании они принимают общие параметры:

data: начальный фрагмент данных для хеширования, который должен быть байтоподобным объектом . Его можно передать только как позиционный аргумент.
digest_size: размер выходного дайджеста в байтах.
key: ключ для хеширования с ключом (до 64 байтов для BLAKE2b, до 32 байтов для BLAKE2).
salt: соль для рандомизированного хеширования (до 16 байтов для BLAKE2b, до 8 байтов для BLAKE2).
person: строка персонализации (до 16 байтов для BLAKE2b, до 8 байтов для BLAKE2).

В следующей таблице показаны ограничения для общих параметров (в байтах):

Хэш	digest_size	len(key)	len(salt)	len(person)
BLAKE2b	64	64	16	16
BLAKE2s	32	32	8	8

Спецификация BLAKE2 определяет постоянную длину для параметров соли и персонализации, однако для удобства эта реализация принимает байтовые строки любого размера до указанной длины. Если длина параметра меньше указанной, она дополняется нулями, например, b'salt' и b'salt\x00' — это одно и то же значение. (Не относится к key.)

Размеры доступны как модуль Константы, описанный ниже.

Функции-конструкторы также принимают следующие параметры древовидного хеширования:

См. раздел 2.10 в BLAKE2 спецификации для всестороннего обзора хеширования дерева.

Константы¶

Длина соли (максимальная длина, принимаемая конструкторами).

blake2b. PERSON_SIZE ¶ blake2s. PERSON_SIZE ¶

Длина строки персонализации (максимальная длина, принимаемая конструкторами).

blake2b. MAX_KEY_SIZE ¶ blake2s. MAX_KEY_SIZE ¶

Максимальный размер ключа.

blake2b. MAX_DIGEST_SIZE ¶ blake2s. MAX_DIGEST_SIZE ¶

Максимальный размер дайджеста, который может вывести хэш-функция.

Примеры¶

Простое хеширование¶

Чтобы вычислить хэш некоторых данных, вы должны сначала создать хеш-объект, вызвав соответствующую функцию-конструктор ( blake2b() или blake2s() ), затем обновить его данными, вызвав update() для объекта, и, наконец, получить дайджест из объекта вызвав digest() (или hexdigest() для строки в шестнадцатеричной кодировке).

В качестве ярлыка вы можете передать первый фрагмент данных для обновления непосредственно в конструктор в качестве позиционного аргумента:

Вы можете вызвать hash.update() столько раз, сколько вам нужно для итеративного обновления хэша:

Использование дайджеста разного размера¶

У BLAKE2 настраиваемый размер дайджестов до 64 байтов для BLAKE2b и до 32 байтов для BLAKE2. Например, чтобы заменить SHA-1 на BLAKE2b без изменения размера вывода, мы можем указать BLAKE2b создавать 20-байтовые дайджесты:

У объектов хеширования с разными размерами дайджеста совершенно разные выходные данные (более короткие хеши не являются префиксом более длинных хешей); BLAKE2b и BLAKE2s производят разные выходные данные, даже если длина выходного файла одинакова:

Ключевое хеширование¶

В качестве практического примера веб-приложение может симметрично подписывать файлы cookie, отправленные пользователям, а затем проверять их, чтобы убедиться, что они не были подделаны:

Несмотря на то, чт. е. собственный режим хеширования с ключом, BLAKE2, конечно, можно использовать в построении HMAC с модулем hmac :

Рандомизированное хеширование¶

Установив параметр salt, пользователи могут ввести рандомизацию в хэш- функцию. Рандомизированное хеширование полезно для защиты от коллизионных атак на хеш-функцию, используемую в цифровых подписях.

В BLAKE2 соль обрабатывается как однократный ввод в хеш-функцию во время инициализации, а не как ввод для каждой функции сжатия.

Соленое хеширование (или просто хеширование) с BLAKE2 или любой другой криптографической хеш-функцией общего назначения, такой как SHA-256, не подходит для хеширования паролей. См. BLAKE2 FAQ для получения дополнительной информации.

Персонализация¶

Иногда полезно заставить хеш-функцию создавать разные дайджесты для одного и того же ввода для разных целей. Цитата авторов хеш-функции Skein:

Мы рекомендуем всем разработчикам приложений серьезно подумать об этом; мы видели много протоколов, в которых хэш, вычисляемый в одной части протокола, может использоваться в совершенно другой части, потому что два вычисления хэша были выполнены для похожих или связанных данных, и злоумышленник может заставить приложение сделать входные данные хэша одно и тоже. Персонализация каждой хэш-функции, используемой в протоколе, в целом останавливает этот тип атаки.

(Семейство функций Skein Hash, p. 21)

BLAKE2 можно персонализировать, передав байты аргументу person:

Персонализация вместе с ключевым режимом также может использоваться для получения разных ключей из одного.

Древовидный режим¶

Вот пример хеширования минимального дерева с двумя листовыми узлами:

В данном примере используются 64-байтовые внутренние дайджесты и возвращается 32-байтовый окончательный дайджест:

Благодарности¶

BLAKE2 был разработан Жан-Филиппом Аумассоном, Сэмюэлом Невесом, Зооко Уилкокс-О’Хирном и Кристианом Уиннерлейном на основе SHA-3 финалиста BLAKE, созданного Жан-Филиппом Аумассоном, Лукой Хенценом, Вилли Мейером и Рафаэльем К.-В. Фаном.

Он использует основной алгоритм из шифра ChaCha, разработанного Дэниелем Дж. Бернштейнм.

Реализация stdlib основана на модуле pyblake2. Он был написан Дмитрием Честных на основе реализации C, написанной Сэмюэлом Невесом. Документация была скопирована с pyblake2 и написана Дмитрием Честных.

Код C был частично переписан для Python Кристианом Хеймсом.

Следующее посвящение общественному достоянию относится как к реализации хэш- функции C, так и к коду расширения и к этой документации:

Насколько это возможно в соответствии с законом, автор(ы) передал(и) все авторские, а также смежные и смежные права на это программное обеспечение в общественное достояние всего мира. Данное программное обеспечение распространяется без каких-либо гарантий.

Вы должны были получить копию CC0 Public Domain Dedication вместе с этим программным обеспечением. Если нет, см. официальный сайт.

Следующие люди помогли с разработкой или внесли свои изменения в проект и общественное достояние в соответствии с Creative Commons Public Domain Dedication 1.0 Universal:

В хеш-таблице обработка новых индексов производится при помощи ключей. А элементы, связанные с этим ключом, сохраняются в индексе. Этот процесс называется хешированием.

Пусть k — ключ, а h(x) — хеш-функция.

Тогда h(k) в результате даст индекс, в котором мы будем хранить элемент, связанный с k .

Коллизии

Когда хеш-функция генерирует один индекс для нескольких ключей, возникает конфликт: неизвестно, какое значение нужно сохранить в этом индексе. Это называется коллизией хеш-таблицы.

Есть несколько методов борьбы с коллизиями:

метод цепочек;
метод открытой адресации: линейное и квадратичное зондирование.

1. Метод цепочек

Суть этого метода проста: если хеш-функция выделяет один индекс сразу двум элементам, то храниться они будут в одном и том же индексе, но уже с помощью двусвязного списка.

Если j — ячейка для нескольких элементов, то она содержит указатель на первый элемент списка. Если же j пуста, то она содержит NIL .

Псевдокод операций

2. Открытая адресация

В отличие от метода цепочек, в открытой адресации несколько элементов в одной ячейке храниться не могут. Суть этого метода заключается в том, что каждая ячейка либо содержит единственный ключ, либо NIL .

Существует несколько видов открытой адресации:

a) Линейное зондирование

Линейное зондирование решает проблему коллизий с помощью проверки следующей ячейки.

h(k, i) = (h′(k) + i) mod m ,

Если коллизия происходит в h(k, 0) , тогда проверяется h(k, 1) . То есть значение i увеличивается линейно.

Проблема линейного зондирования заключается в том, что заполняется кластер соседних ячеек. Это приводит к тому, что при вставке нового элемента в хеш-таблицу необходимо проводить полный обход кластера. В результате время выполнения операций с хеш-таблицами увеличивается.

b) Квадратичное зондирование

Работает оно так же, как и линейное — но есть отличие. Оно заключается в том, что расстояние между соседними ячейками больше (больше одного). Это возможно благодаря следующему отношению:

c₁ и c₂ — положительные вспомогательные константы,
i =

c) Двойное хэширование

Если коллизия возникает после применения хеш-функции h(k) , то для поиска следующей ячейки вычисляется другая хеш-функция.

h(k, i) = (h1(k) + ih2(k)) mod m

1. Метод деления

Если k — ключ, а m — размер хеш-таблицы, то хеш-функция h() вычисляется следующим образом:

Например, если m = 10 и k = 112 , то h(k) = 112 mod 10 = 2 . То есть значение m не должно быть степенью 2. Это связано с тем, что степени двойки в двоичном формате — 10, 100, 1000… При вычислении k mod m мы всегда будем получать p-биты низшего порядка.

2. Метод умножения

kA mod 1 отделяет дробную часть kA;
⌊ ⌋ округляет значение;
A — произвольная константа, значение которой должно находиться между 0 и 1. Оптимальный вариант ≈ (√5-1) / 2, его предложил Дональд Кнут.

3. Универсальное хеширование

В универсальном хешировании хеш-функция выбирается случайным образом и не зависит от ключей.

Метод hash() возвращает хеш-значение объекта, если оно есть.

Значения хэша – это просто целые числа, которые используются для быстрого сравнения ключей словаря во время поиска в словаре. Внутренне метод вызывает __hash __() объекта, который установлен по умолчанию для любого объекта. Мы рассмотрим это позже.

Параметры

Метод hash() в Python принимает единственный параметр:

object – объект, хеш-значение которого должно быть возвращено (целое число, строка, число с плавающей запятой).

Хэш возвращает значение объекта, если оно есть.

Если у объекта есть собственный метод __hash __(), он обрезает возвращаемое значение до размера Py_ssize_t.

Пример 1

Пример 2: Для неизменяемого объекта кортежа

Хеш-ункция работает только для неизменяемых объектов в виде кортежа.

Как работает с настраиваемыми объектами?

Как указано выше, функция внутренне вызывает метод __hash __(). Итак, любые объекты могут переопределить __hash __() для пользовательских значений хеша.

Но для правильной реализации хеша __hash __() всегда должен возвращать целое число. И должны быть реализованы оба метода __eq __() и __hash __().

Ниже приведены примеры правильного переопределения __hash __().

Пример 3: Для настраиваемых объектов путем переопределения hash ()

Примечание: Не нужно реализовывать метод __eq __() для хэша, поскольку он создается по умолчанию для всех объектов.

В этой статье будет продемонстрировано, как использовать хеш MD5 с помощью модуля Python hashlib .

Что такое хеш?

Хеш - это функция, которая принимает данные переменной длины и преобразует их в фиксированную длину. Значение, возвращаемое хеш-функцией, называется хеш-значением, хеш-кодом или дайджестом. Хеш-значения обычно используются для индексации таблицы фиксированного размера, называемой хеш-таблицей.

Что такое MD5?

Модуль Python hashlib

Чтобы использовать алгоритмы хеширования, импортируйте модуль hashlib .

Теперь мы можем использовать алгоритмы хеширования, поддерживаемые этим модулем. Чтобы проверить доступные хеш-алгоритмы в работающем интерпретаторе Python, используйте постоянный атрибут algorithmms_available .

В списке выше представлены доступные алгоритмы в hashlib , включая доступные алгоритмы OpenSSL.

Чтобы проверить, какие алгоритмы хеширования гарантированно поддерживаются этим модулем на всех платформах, используйте постоянный атрибут algorithmms_guaranteed .

Примечание: md5 находится в списке алгоритмов_гарантия , но некоторые совместимые с FIPS поставщики апстрима предлагают сборку Python, исключающую его.

Используйте алгоритм MD5 в Python

Чтобы использовать алгоритм md5, мы воспользуемся конструктором md5() и загрузим хэш-объект байтовыми объектами с помощью метода update() или передадим данные в качестве параметра конструктора.

Для получения хеш-значения используйте метод digest() , который возвращает байтовый дайджест данных, переданных в хеш-объект.

Вы также можете передать данные в качестве параметра конструктору и получить хеш-значение.

Подобно методу digest() , вы также можете использовать hexdigest() , который возвращает строковый объект дайджеста, содержащий только шестнадцатеричные цифры.

Обратите внимание, что перед строковым литералом, переданным в метод update() , стоит буква b . Используется для создания экземпляра типа bytes вместо типа str . Поскольку функция хеширования принимает в качестве параметра только последовательность байтов. Передача строковых объектов в метод update() не поддерживается.

Вы также можете выполнить несколько вызовов метода update() , что эквивалентно одному вызову со всеми объединенными аргументами.

Таким образом, мы можем использовать алгоритм хеширования md5 через модуль hashlib , в который можно загружать данные, передавая их в качестве параметра конструктора md5() или используя метод update() . Мы можем получить хеш-значение с помощью метода digest() , который возвращает объект bytes метода digest() или hexdigest() , который возвращает строковый объект дайджеста, содержащий только шестнадцатеричные цифры.

report this ad

Читайте также: