2021-05-31 10:45:04
Про хэш-функции
Хэш-функции (
hash functions) – крайне важное понятие в мире вычислений, особенно в криптографии.
С математической точки зрения, хэш-функция – это преобразование набора данных произвольной длины в набор данных фиксированной длины:
h(
M) =
H,
где
M – это исходное сообщение произвольной длинны,
h(
M) – хэш-функция (преобразование, хэш-алгоритм),
H – значение хэш-функции, т.е результат выполнения преобразования или просто хэш.
Для каждой функции хэш имеет свою фиксированную длину, как правило, от 128 до 512 бит.
С точки зрения практического использования хэш-функция должна быть быстро вычисляемой.
Общая схема работы хэш-функции выглядит примерно так: исходное сообщение
M разбивается на блоки. Алгоритм хэш-функции (хэш-алгоритм) получает на входе блок исходного сообщения и некоторое числовое значение, а на выходе выдает значение хэша для комбинации этих двух входных параметров. Затем берётся следующий блок исходного сообщения и результат вычисления хэша с предыдущего шага, для них вычисляется хэш текущего шага. Далее процедура повторяется необходимое количество раз, чтобы "покрыть" всё исходное сообщение.
Таким образом, хэш-функция работает подобно измельчителю, нарезая сообщение на кусочки и перемешивая их с подсыпаемыми специями. Слово
hash в переводе с английского означает "мешанина", "крошево". В русской литературе можно встретить термин "функция свёртки".
Для использования хэш-функции в криптографии нужно, чтобы она обладала следующими свойствами:
1. Имея в распоряжении только результат хэширования
H, невозможно или крайне сложно подобрать исходное сообщение
M (свойство необратимости).
2. Крайне сложно или невозможно подобрать другой исходный набор данных (
M’), который даст тот же хэш:
h(
M) =
h(
M’) =
H. Если такие случаи происходят, то их называют
коллизиями или
конфликтами.
Часто вводится ещё одно дополнительное свойство:
3. Изменение хотя бы одного бита в исходном сообщении значительно меняет значение хэша. Это свойство ещё называют лавинным эффектом (
Avalanche effect).
Если математически можно доказать, что хэш-функция не содержит коллизий (
инъективна), то это – идеальная хэш-функция (
Perfect hash function).
Основные сферы применения хэш-функций:
• вычисление контрольных сумм,
• хранение паролей (в виде хэшей),
• построение свёртки текста при формировании электронной подписи.
Об этих вопросах поговорим подробнее в дальнейшем.
#ИБ #термин
96 views07:45