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

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

Аналогом однонаправленной функции в быту является разбитая вдребезги стеклянная бутылка. Расколотить ее на мелкие осколки очень легко, однако попробуйте снова собрать целую бутылку из осколков!

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

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

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

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

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

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

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