Концепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных функций. Неформально однонаправленную функцию можно определить следующим образом. Пусть X и Y – некоторые произвольные множества. Функция
f: X ® Y
является однонаправленной, если для всех xÎX можно легко вычислить функцию
y = f (x), где yÎY.
И в то же время для большинства yÎY достаточно сложно получить значение xÎX, такое, что f (x)=y (при этом полагают, что существует по крайней мере одно такое значение x).
Основным критерием отнесения функции f к классу однонаправленных функций является отсутствие эффективных алгоритмов обратного преобразования Y ® X.
В качестве первого примера однонаправленной функции рассмотрим целочисленное умножение. Прямая задача – вычисление произведения двух очень больших целых чисел P и Q, т.е. нахождение значения
N = P*Q, (4.3)
является относительно несложной задачей для ЭВМ.
Обратная задача – разложение на множители большого целого числа, т.е. нахождение делителей P и Q большого целого числа N = P*Q, является практически неразрешимой задачей при достаточно больших значениях N. По современным оценкам теории чисел при целом N»2664 и P»Q для разложения числа N потребуется около 1023 операций, т.е. задача практически неразрешима на современных ЭВМ.
|
|
Следующий характерный пример однонаправленной функции – это модульная экспонента с фиксированными основанием и модулем. Пусть A и N – целые числа, такие, что 1£ А < N. Определим множество ZN:
ZN = {0, 1, 2,..., N –1}.
Тогда модульная экспонента с основанием А по модулю N представляет собой функцию
fA,N : ZN ® ZN,
fA,N (x) = Ax (mod N), (4.4)
где X – целое число, 1£ x £ N –1.
Существуют эффективные алгоритмы, позволяющие достаточно быстро вычислить значения функции fA,N (x).
Если y = Ax, то естественно записать x = logA (у).
Поэтому задачу обращения функции fA,N(x) называют задачей нахождения дискретного логарифма или задачей дискретного логарифмирования.
Задача дискретного логарифмирования формулируется следующим образом. Для известных целых A, N, Y найти целое число X, такое, что
Ax mod N = y.
Алгоритм вычисления дискретного логарифма за приемлемое время пока не найден. Поэтому модульная экспонента считается однонаправленной функцией.
По современным оценкам теории чисел при целых числах A» 2664 и N» 2664 решение задачи дискретного логарифмирования (нахождение показателя степени x для известного y) потребует около 1026 операций, т.е. эта задача имеет в 103 раз большую вычислительную сложность, чем задача разложения на множители. При увеличении длины чисел разница в оценках сложности задач возрастает.
|
|
Следует отметить, что пока не удалось доказать, что не существует эффективного алгоритма вычисления дискретного логарифма за приемлемое время. Исходя из этого, модульная экспонента отнесена к однонаправленным функциям условно, что, однако, не мешает с успехом применять ее на практике.
Вторым важным классом функций, используемых при построении криптосистем с открытым ключом, являются так называемые однонаправленные функции с "потайным ходом" (с лазейкой). Дадим неформальное определение такой функции. Функция
f: X ® Y
относится к классу однонаправленных функций с "потайным ходом" в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление обратной функции, если известен "потайной ход" (секретное число, строка или другая информация, ассоциирующаяся с данной функцией).
В качестве примера однонаправленной функции с "потайным ходом" можно указать используемую в криптосистеме RSA модульную экспоненту с фиксированными модулем и показателем степени. Переменное основание модульной экспоненты используется для указания числового значения сообщения M либо криптограммы C