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

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

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

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

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

Целочисленное умножение

Вычисление произведения двух очень больших целых чисел P и Q (N=P*Q) является несложной задачей для ЭВМ. Однако, решение обратной задачи, заключающейся в нахождении делителей P и Q большого числа N (в особенности, когда P и Q – большие простые числа), является практически неразрешимой задачей. Если N2⁶⁴ и PQ, то задача факторизации не разрешима за приемлемое время на современных ЭВМ. Поэтому целочисленное умножение является однонаправленной функцией.

Модульная экспонента

Возведение очень большого числа A в очень большую степень x (), то есть вычисление, где модульM тоже большое число, является несложной задачей для ЭВМ. Однако решение обратной задачи – нахождения степени x по известным у, A, M такой, что (задача дискретного логарифмирования,), практически не разрешима за приемлемое время на современных ЭВМ (эффективного алгоритма вычисления дискретного логарифма пока не найдено).Поэтому модульная экспонента является однонаправленной функцией.

Рассмотрим простую интерпретацию сказанного. Пусть задано: А=2, х=2, М=4. Тогда = 0. Пусть А=2, х=3, М=4. Тогда = 0. Отсюда видно, что по у вычислить х можно только полным перебором всех вариантов даже, если известны А и М.

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

4.5.3. Алгоритм шифрования rsa

Алгоритм RSA был предложен в 1978 году Р.Райвестом, А. Шамиром, А. Адлеманом и был назван по первым буквам фамилий его авторов. Данный алгоритм стал первым алгоритмом шифрования с открытым ключом. Надежность данного алгоритма основывается на трудности факторизации больших чисел и вычисления дискретных логарифмов [14,2].

В криптосистеме RSA открытый ключ ОК, секретный ключ СК, исходное сообщение М и шифротекст С являются целыми числами от 0 до N-1, где N – модуль.

Пусть пользователь А является получателем сообщения, которое ему должен переслать отправитель B.

Пользователь A должен вначале сгенерировать ключевую пару RSA, это он делает следующим образом.

Алгоритм формирования ключевой пары пользователем а

1. Выбираем случайные большие простые числа P и Q. Для обеспечения максимальной безопасности P и Q выбирают примерно равной длины и хранят в секрете.

2. Вычисляем модуль . Формируем функцию Эйлера.

3. Открытый ключ ОК_А выбирается случайно таким образом, чтобы выполнялись следующие условия:

1<ОКA<, НОД(ОКА, )=1

(4.8)

4. Секретный ключ СК_A находится по сформированному открытому ключу так, что

СКАОКА (mod )1 или СКА=ОКА^-1 (mod (P-1)  (Q-1))

(4.9)

Здесь функция mod - взятия остатка от деления. Пользователь A может легко сформировать СК_А, используя расширенный алгоритм Евклида, зная числа P и Q, а значит и .

Любой другой пользователь не может, зная открытый ключ ОК_А вычислить СК_А, так как ему не известны числа P и Q. Для их нахождения ему потребуется факторизовать известное ему большое число N, что является вычислительно сложной задачей.