Однонаправленные хэш-функции

Однонаправленные функции

Однонаправленная функция – это функция f(x), которую несложно рассчитать для каждого значения аргумента x, но по известному значению f(x) очень трудно вычислить х.

Т.е. это функция для которой, даже зная функцию и ее значение нельзя вычислить аргумент.

Например, функцию x² вычислить не сложно, однако обратную функцию x^1/2 рассчитать гораздо сложнее (4586²=21031396).

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

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

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

днонаправленные функции с потайным входом (с люком) – это особый тип однонаправленной функции, с тайной лазейкой. Т.е. существует небольшая секретная информация y, позволяющая при знании f(x) и y, легко вычислить x.

Однонаправленные хэш-функции – это математические или иные функции, которые принимают на входе строку переменной длины (называемую прообразом), и преобразовывают ее в выводную строку фиксированной (обычно меньшей) длины, называемую значением хэш-функции или сверткой.

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

Пример простейшей хэш-функции – ко всем байтам сообщения поочередно применяется операция XOR и на выходе – один байт.

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

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

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

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

Код проверки подлинности сообщения (Message Authentication Code, MAC, имитовставка) представляет собой однонаправленную хэш-функцию с добавлением закрытого ключа. Значение хэш-функции зависит не только от прообраза, но и от ключа. Т.е. для проверки значения хэш-функции нужно знать ключ.

Дата добавления: 2014-01-07