Aсимметричные криптосистемы

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

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

f: X ® Y

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

y=f(x), где yОY.

И в то же время для большинства yОY достаточно сложно получить значение хОХ, такое, что f(x)=y (при этом полагают, что существует по крайней мере одно такое значение х).

Основным критерием отнесения функции f к классу однонаправленных функций является отсутствие эффективных алгоритмов обратного преобразования Y®X.

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

N = P * Q, (3)

является относительно несложной задачей для ЭВМ.

Обратная задача - разложение на множители большого целого числа, т.е. нахождение делителей Р и Q большого целого числа N=P*Q, является практически неразрешимой задачей при достаточно больших значениях N. По современным оценкам теории чисел при целом N»2664 и P»Q для разложения числа N потребуется около 1023 операций, т.е. задача практически неразрешима на современных ЭВМ.

Следующий характерный пример однонаправленной функции - это модульная экспонента с фиксированными основанием и модулем. Пусть А и N - целые числа, такие, что 1ЈА<N. Определим множество ZN:

ZN= {0,1,2,…,N-1 }

Тогда модульная экспонента с основанием А по модулю N представляет собой функцию

где x-целое число, 1Ј x Ј N-1.

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

Если , то естественно записать .

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

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

.

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

По современным оценкам теории чисел при целых числах А»2664 и N»2664 решение задачи дискретного логарифмирования (нахождение показателя степени х для известного у) потребует около 1026 операций, т.е. эта задача имеет в 103 раз большую вычислительную сложность, чем задача разложения на множители. При увеличении длины чисел разница в оценках сложности задач возрастает.

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

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

f: X ® Y

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

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

[Предыдущий раздел][Содержание][Следующий раздел]

Hosted by uCoz