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

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

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

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

В качестве примера однонаправленной функции  рассмотрим широко известную функцию дискретного возведения в степень: , где  – целое число от 1 до  включительно, а вычисление производится по модулю , где  – очень большое простое число;  – целое число ().

Напомним, что простым числом называется целое число, которое не делится ни на какие числа, кроме себя самого и единицы.

Пример 10.1.  Для примера возьмем небольшое простое число ; тогда для осуществления преобразований можно выбрать примитивный элемент , так как , , , , , .

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

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

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

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

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

Открытое значение  вместе с именем пользователя может быть помещено в список паролей доступа, хранящихся в ЭВМ. Законный пользователь для получения доступа в автоматизированную систему предъявляет свое число . ЭВМ вычисляет по этому числу значение однонаправленной функции  и сравнивает с хранящимся значением . При совпадении этих значений пользователь становится идентифицированным и получает требуемый доступ.

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

Однонаправленные функции с потайным ходом

Быстрое развитие криптографии в последние два десятилетия во многом стало возможным благодаря открытию американскими учеными В. Диффи и М. Хэлманом однонаправленных функций с потайным ходом и их использованием для различных криптосистем защиты информации [1, 31].

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

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

Однонаправленные функции с потайным ходом относятся к вычислительно необратимым функциям.

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

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

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

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

отыскание дискретного логарифма элемента в большом конечном поле или группе (криптосистема открытого распространения ключей Диффи-Хэллмана, криптосистема шифрования и криптосистема цифровой подписи сообщений Эль-Гамаля, криптосистема цифровой подписи сообщений Шнорра и другие криптосистемы) [1, 31, 36];

разложение больших чисел на простые множители (криптосистема шифрования и криптосистема цифровой подписи сообщений РША, криптосистема цифровой подписи сообщений Рабина и другие криптосистемы) [1, 19];

задача об укладке целочисленного ранца (класс ранцевых систем шифрования информации Меркля-Хэллмана) [1, 36];

декодирование неизвестных получателю кодов Гоппы (класс систем шифрования информации Мак-Эллиса) [1].

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

Однонаправленная функция РША с потайным ходом

В 1978 году была предложена первая однонаправленная функция с потайным ходом, положенная в основу широко используемой на практике несимметричной криптографической системы РША. Первые буквы фамилий ее авторов (Р. Ривеста, А. Шамира и Л. Адлемара) образовали общепринятое название предложенной ими функции и криптосистемы. Для описания однонаправленной функции РША с потайным ходом требуются некоторые сведения из элементарной теория чисел [1, 19, 31].

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

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

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

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

Однонаправленная функция Эль-Гамаля c потайным ходом

Ранее была рассмотрена однонаправленная функция на основе вычисления дискретных логарифмов в алгебраической группе. Поле Галуа , где  – простое число, является более сложной алгебраической структурой по сравнению с группой, над его элементами можно выполнять операции сложения и умножения, а в группе - только сложение или только умножение. Например, рассмотренная ранее однонаправленная функция Диффи и Хеллмана, послужившая основой криптосистемы открытого распространения ключей, использует операцию умножения над элементами группы [1, 31, 36].

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

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

На основе однонаправленной функции Эль-Гамаля с потайным ходом, как для функции РША, можно построить несимметричную систему шифрования информации.

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

Однонаправленная функция с потайным ходом на основе  алгебраических уравнений по модулю 2

Значение однонаправленной функции  с потайным ходом зависит от аргументов  и :

где    – вектор сообщения, состоящий из двух частей  и  длиной по  бит каждая: ;  – вектор ключа, который определяется совокупностью подвекторов: .

Над вектором  циклически выполняются  раз операции вида:

где    – некоторое фиксированное нелинейное преобразование, а знак  означает сложение по модулю два.

Рассмотренный принцип построения однонаправленной функции с потайным ходом используется при построении широкого класса блочных систем шифрования (класс блочных шифров Фейстеля) к которому принадлежат известный американский алгоритм шифрования данных DES и отечественный алгоритм шифрования согласно ГОСТ 28147–89 [1, 31, 36].