Хеш-функции.
Хеш-функция – функция, преобразовывающая входную последовательность данных произвольного размера в выходную последовательность фиксированного размера. Процесс преобразования данных называется хешированием. Результат хеширования – хеш-код (хеш-сумма, хеш).
При решении класса практических задач выбирается такая хеш-функция, которая является наиболее оптимальной именно для данного класса. В общем случае следует использовать «хорошую» функцию. Когда хеш-функцию называют «хорошей», то подразумевают под этим, что она:
Предотвратить коллизии могут далеко не все хеш-функции, но «хорошие» способны минимизировать вероятность их появления. При определенных обстоятельствах (известна некоторая информация о ключах), можно найти идеальную хеш-функцию, т. е. такую, которая полностью исключает возможность появления коллизий.
Использовать хеш-функцию или нет, зависит от того насколько целесообразно применение ее свойств, а также свойств алгоритма, по которому она может быть реализована на ЯП. В одних ситуациях наиболее важна высокая скорость работы, в других равномерное распределение хеш-кодов и т. п. Далее будут рассмотрены два наиболее известных метода хеширования.
Метод деления.
Пусть k – ключ (тот, что необходимо хешировать), а N – максимально возможное число хеш-кодов. Тогда метод хеширования посредством деления будет заключаться во взятии остатка от деления k на N:
h(k)=k mod N, где mod – операция взятия остатка от деления.
Например, на вход подаются следующие ключи:
3, 6, 7, 15, 32, 43, 99, 100, 133, 158.
Определим N равным 10, из чего последует, что возможные значения хешей лежат в диапазоне 0…9. Используя данную функцию, получим следующие значения хеш-кодов:
h(3)=3, h(6)=6, h(7)=7, h(15)= 5, h(32)=2, h(42)=2, h(99)=9, h(100)=0, h(133)=3, h(158)=8.
Что такое хэш и хэш-функция: практическое применение, обзор популярных алгоритмов
Цифровые технологии широко применяют хеширование, несмотря на то, что изобретению более 50 лет: аутентификация, осуществление проверки целостности информации, защита файлов, включая, в некоторых случаях, определение вредоносного программного обеспечения и многие другие функции. Например, множество задач в области информационных технологий требовательны к объему поступающих данных. Согласитесь, проще и быстрее сравнить 2 файла весом 1 Кб, чем такое же количество документов, но, к примеру, по 10 Гб каждый. Именно по этой причине алгоритмы, способные оперировать лаконичными значениями, весьма востребованы в современном мире цифровых технологий. Хеширование – как раз решает эту проблему. Разберемся подробно, что такое хэш и хэш-функция.
Что за «зверь» такой это хеширование?
Чтобы в головах читателей не образовался «винегрет», начнем со значения терминологий применительно к цифровым технологиям:
Исходя из пояснений, делаем вывод: хеширование – процесс сжатия входящего потока информации любого объема (хоть все труды Уильяма Шекспира) до короткой «аннотации» в виде набора случайных символов и цифр фиксированной длины.
Коллизии
Коллизии хэш-функций подразумевает появление общего хэш-кода на два различных массива информации. Неприятная ситуация возникает по причине сравнительно небольшого количества символов в хэш. Другими совами, чем меньше знаков использует конечная формула, тем больше вероятность итерации (повтора) одного и того же хэш-кода на разные наборы данных. Чтобы снизить риск появления коллизии, применяют двойное хеширование строк, образующее открытый и закрытый ключ – то есть, используется 2 протокола, как, например, в Bitcoin. Специалисты, вообще, рекомендуют обойтись без хеширования при осуществлении каких-либо ответственных проектов, если, конечно же, это возможно. Если без криптографической хэш-функции не обойтись, протокол обязательно нужно протестировать на совместимость с ключами.
Важно! Коллизии будут существовать всегда. Алгоритм хеширования, перерабатывающий различный по объему поток информации в фиксированный по количеству символов хэш-код, в любом случае будет выдавать дубли, так как множеству наборов данных противостоит одна и та же строчка заданной длины. Риск повторений можно только снизить.
Технические параметры
Основополагающие характеристики протоколов хеширования выглядят следующим образом:
Здесь стоит так же отметить важные свойства алгоритмов: способность «свертывать» любой массив данных, производить хэш конкретной длины, распределять равномерно на выходе значения функции. Необходимо заметить, любые изменения во входящем сообщении (другая буква, цифра, знак препинания, даже лишний пробел) внесут коррективы в итоговый хэш-код. Он просто будет другим – такой же длины, но с иными символами.
Требования
К эффективной во всех отношениях хэш-функции выдвигаются следующие требования:
Данные требования выполнимы исключительно тогда, когда протокол базируется на сложных математических уравнениях.
Практическое применение
Процедура хеширования относительно своего функционала может быть нескольких типов:
Разберемся детальней в сфере применения протоколов хеширования.
Скачивание файлов из Всемирной Паутины
Этим занимается фактически каждый активный пользователь Всемогущей Сети, сталкиваясь с хэш-функциями сам того не осознавая, так как мало кто обращает внимание при скачивании того или иного файла на череду непонятных цифр и латинских букв. Однако именно они и есть хэш или контрольные суммы – перед вереницей символов стоит название используемой категории протокола хеширования. В общем-то, для обывателей абсолютно ненужная «инфа», а продвинутый юзер может выяснить, скачал ли он точную копию файла или произошла ошибка. Для этой процедуры необходимо установить на собственный ПК специальную утилиту (программу), которая способна вычислить хэш по представленному протоколу.
Важно! Установив на ПК пакет утилит, прогоняем через него файлы. Затем сравниваем полученный результат. Совпадение символов говорит о правильной копии – соответствующей оригиналу. Обнаруженные различия подразумевают повторное скачивание файла.
Алгоритм и электронно-цифровая подпись (ЭЦП)
Цифровая резолюция (подпись) – кодирование документа с использованием ключей закрытого и открытого типа. Другими словами, первоначальный документ сопровождается сообщением, закодированным закрытым ключом. Проверка подлинности электронной подписи осуществляется с применением открытого ключа. При обстоятельствах, когда в ходе сравнения хэш двух информационных наборов идентичен, документ, который получил адресат, признается оригинальным, а подпись истинной. В сухом остатке получаем высокую скорость обработки потока наборов данных, эффективную защиту виртуального факсимиле, так как подпись обеспечивается криптографической стойкостью. В качестве бонуса – хэш подразумевает использование ЭЦП под разнообразными типами информации, а не только текстовыми файлами.
Ревизия паролей
Очередная область применения хэш-функции, с которой сталкивается практически каждый пользователь. Подавляющее большинство серверов хранит пользовательские пароли в значении хэш. Что вполне обоснованно, так как, сберегая пароли пользователей в обычной текстовой форме, можно забыть о безопасности конфиденциальных, секретных данных. Столкнувшись с хэш-кодом, хакер даже время терять не будет, потому что, обратить вспять произвольный набор символов практически невозможно. Конечно же, если это не пароль в виде «12345» или что-то на подобии него. Доступ осуществляется путем сравнения хэш-кода вводимого юзером с тем, который хранится на сервере ресурса. Ревизию кодов может осуществлять простейшая хэш-функция.
Важно! В реальности программисты применяют многоярусный комплексный криптографический протокол с добавлением, в большинстве случаев, дополнительной меры безопасности – защищенного канала связи, чтобы виртуальные мошенники не перехватили пользовательский код до того, как он пройдет проверку на сервере.
Как появилось понятие хэш?
Сделаем небольшую паузу, чтобы интеллект окончательно не поплыл от потока сложных для простых пользователей терминов и информации. Расскажем об истории появления термина «хэш». А для простоты понимания выложим «инфу» в табличной форме.
| Дата (год) | Хронология событий |
| 1953 | Известный математик и программист Дональд Кнут авторитетно считает, что именно в этот промежуток времени сотрудник IBM Ханс Питер Лун впервые предложил идею хеширования. |
| 1956 | Арнольд Думи явил миру такой принцип хеширования, какой знают его подавляющее большинство современных программистов. Именно эта «светлая голова» предложила считать хэш-кодом остаток деления на любое простое число. Кроме этого, исследователь видел идеальное хеширование инструментов для позитивной реализации «Проблемы словаря». |
| 1957 | Статья Уэсли Питерсона, опубликованная в «Journal of Research and Development», впервые серьезно затронула поиск информации в больших файлах, определив открытую адресацию и ухудшение производительности при ликвидации. |
| 1963 | Опубликован труд Вернера Бухгольца, где было представлено доскональное исследование хэш-функции. |
| 1967 | В труде «Принципы цифровых вычислительных систем» авторства Херберта Хеллермана впервые упомянута современная модель хеширования. |
| 1968 | Внушительный обзор Роберта Морриса, опубликованный в «Communications of the ACM», считается точкой отсчета появления в научном мире понятия хеширования и термина «хэш». |
Интересно! Еще в 1956 году советский программист Андрей Ершов называл процесс хеширования расстановкой, а коллизии хэш-функций – конфликтом. К сожалению, ни один из этих терминов не прижился.
Стандарты хеширования: популярные варианты
Итак, от экскурса в историю перейдем вновь к серьезной теме. Опять-таки, ради простоты восприятия предлагаем краткое описание популярных стандартов хеширования в табличном виде. Так проще оценить информацию и провести сравнение.
На этом, пожалуй, закончим экскурсию в мир сложных, но весьма полезных и востребованных протоколов хеширования.