Односторонние функции

Все алгоритмы шифрования с открытым ключом основаны на использовании так называемых односторонних функций. Односторонней функцией (one-way function) называется математическая функция, которую относительно легко вычислить, но трудно найти по значению функции соответствующее значение аргумента. То есть, зная х легко вычислить f(x), но по известному f(x) трудно найти подходящее значение x. Под словом "трудно вычислить" понимают, что для этого потребуется не один год расчетов с использованием ЭВМ. Односторонние функции применяются в криптографии также в качестве хеш-функций. Использовать односторонние функции для шифрования сообщений с целью их защиты не имеет смысла, так как обратно расшифровать зашифрованное сообщение уже не получится. Для целей шифрования используются специальные односторонние функции – односторонние функции с люком (или с секретом) – это особый вид односторонних функций, имеющих некоторый секрет (люк), позволяющий относительно быстро вычислить обратное значение функции.

Для односторонней функции с люком f справедливы следующие утверждения:

- зная х, легко вычислить f(x),

- по известному значению f(x) трудно найти x,

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