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

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

В криптографических алгоритмах основными однонаправленными функциями являются:

- функция целочисленного умножения или как ее определяют функция факторизации (разложения на простые множители) больших чисел;

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

Однако, в любом представлении однонаправленная функция определяется как:

- для любых произвольных множеств X и Y определено, что f: X → Y, т.е. существует функция однозначного преобразования элементов множества X во множество Y, устанавливается однозначное соответствие между элементами множества X и Y. Запись f: X → Y читается как «каждому элементу множества X ставится в однозначное соответствие элемент множества Y» или «функциональное преобразование (f) множества X (:) влечет за собой (→) множество Y.

Функция f: X → Y является однонаправленной, если для всех элементов x_i множества X (x_i є X) функция y_i = f(x_i) является легко вычисляемой для любого элемента y_i, принадлежащего множеству Y, т.е. y_iєY. Решение же обратной задачи при x_i є X и y_i є Y для однонаправленных функций должно быть вычислительно неразрешимой задачей, т.е. если y_i = f (x_i), то x_i ≠ f (y_i). В практической криптографии однонаправленным функциональным преобразованием для криптографической системы защиты и аутентификации электронных сообщений, построенным по алгоритму RSA (Райвест-Шамир-Адлеман) является вычисление произведения двух больших простых чисел (порядка 100 десятичных знаков). Прямое решение задачи, т.е. нахождение значения их произведения для современных вычислительных комплексов является достаточно простой задачей, т. е.

N = P * Q. Однако решение обратной задачи нахождения чисел P и Q заданного большого числа N является неразрешимой задачей (если разрядность чисел P и Q одинакова и каждое число содержит не менее 100 десятичных знаков).

Для криптографических систем с алгоритмом функционирования Эль Гамаля – модульная экспонента с фиксированным основанием и модулем – Y = a^X mod P, где: Р – большое простое число; а – целое число, причем а < Р; х – случайное целое число, причем х < Р.

Нахождение значения y_i = a^X mod P является достаточно простой задачей. Нахождение же обратного значения x_i = log_a y_i mod P, при значениях «а» и «Р» порядка 150 десятичных знаков является относительно неразрешимой задачей. Эту задачу называют задача дискретного логарифмирования, решение которой за приемлемое время невозможно, в соответствии с чем модульная экспонента относится к классу однонаправленных функций, что и определило ее широкое применение в криптографических системах защиты и аутентификации электронных сообщений в компьютерных технологиях.