Информационная безопасность. Макаренко С.И. - 127 стр.

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

                                     f:X→Y

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

          11.3 Криптосистема шифрования данных RSA

      Алгоритм RSA предложили в 1978 г. три автора: Р. Райвест (Rivest),
А. Шамир (Shamir) и А. Адлеман (Adleman). Алгоритм получил свое
название по первым буквам фамилий его авторов. Алгоритм RSA стал
первым полноценным алгоритмом с открытым ключом, который может
работать как в режиме шифрования данных, так и в режиме электронной
цифровой подписи.
      Надежность алгоритма основывается на трудности факторизации
больших чисел и трудности вычисления дискретных логарифмов.
      Введем следующие понятия:
      1. Простое число - делится только на 1 и на само себя;
      2. Взаимно простым- не имеют ни одного общего делителя, кроме 1;
      3. Результат операции i mod j - остаток от целочисленного деления i на
         j.
      В криптосистеме RSA открытый ключ Кв, секретный ключ кв,
сообщение М и криптограмма С принадлежат множеству целых чисел

                  ZN = {0, 1, 2, … , N-1}, где N - модуль: N = P∙Q.

                                     127