Исследование и реализация хеш-функции SHA-2

Коллизии
X
Y

Коллизии

Типы хеш-функций
Хеш-функции для ускорения поиска информации. Применяется для построения хеш-таблиц – особых структур, в которых скорость поиска достигается с помощью использования свёртки, как ключа в таблице.
Протокол для аудита целостности информации. Используется для проверки целостности полученных данных.
Криптографические хеш-функции. Используются для защиты информации, о них пойдёт речь далее.

Структура Меркла-Дамгарда

Структура Меркла-Дамгарда
Применяется в таких хеш-функциях, как MD5, SHA-1, SHA-2, о которых речь пойдёт позже.

Атака методом «грубой силы»

Атака «дней рождения»

Атака «дней рождения»

Атака методом удлинения сообщения

Запрос: from=alice&to=bob&amount=30000
Подпись запроса h(ключ | запрос )
Учитывая паддинг: ключ | запрос | паддинг
Паддинг (рассчитано помощью функции pad из программы [2] sha256.py в приложении):
: \x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01
Припишем к сообщению рассчитанный паддинг и «00», чтобы увеличить размер перечисляемой платы в 100 раз, отправим запрос.
Далее, алгоритм находящейся в правильном состоянии хеш-функции, обработает оставшуюся часть нового сообщения и создаст новую действительную подпись (вычислено с помощью функции sha256 из программы [2] sha256.py в приложении):
c154aa5feff7ac1db7b5dcd6dfe1038a884277bdc7d71149c748f87a449d20ae
Атака методом удлинения сообщения

Общее сопоставление характеристик

Тесты скорости были проведены с помощью функции calc_hash из программы [1], calc_time.py
Время вычисления хеш-функции от сообщения «The quick brown fox jumps over a lazy dog», записанного 5120000 раз подряд.
Была выбрана фраза на латинице, т.к. кириллица в кодировке UTF-8 обозначается с помощью 2-х байт, а не одного, как ASCII символы.
Сравнение скорости вычисления

Зависимость скорости вычисления от длины
Характеристики компьютера, на котором проводились расчёты: Win10/x64, 8GB RAM, GTX 1050, Intel Core i5.
График построен с помощью программы [1], calc_time.py из приложения.

SHA-256. Предварительная обработка сообщения

SHA-256. Сжимающая функция

Демонстрация работы хеш-функции SHA-256
Для демонстрации работы SHA-256 была использована функция sha256 из [2].

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

Заключение

Приложение
Все программы доступны по ссылке github.com/ulnsig/hash-functions .