Однонаправленная функция
(по материалам http://cryptor.narod.ru/glava4/glava4_2.html)
Концепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных функций. Неформально однонаправленную функцию можно определить следующим образом.
Пусть Х
и Y - некоторые произвольные множества.
Функция f: X ® Y является однонаправленной, если для всех хОХ
можно легко вычислить функцию y=f(x), где yОY. И в то же время для большинства yОY
достаточно сложно получить значение хОХ, такое, что f(x)=y (при этом полагают, что существует по крайней мере одно такое значение х).
Основным критерием отнесения функции f к классу однонаправленных функций является отсутствие эффективных
алгоритмов обратного преобразования Y®X.
В качестве первого примера однонаправленной функции рассмотрим целочисленное умножение. Прямая задача - вычисление произведения двух очень больших целых чисел Р
и Q, т.е. нахождение значения N = P • Q, является относительно несложной задачей для ЭВМ.
Обратная задача - разложение на множители большого целого числа, т.е. нахождение делителей Р
и Q большого целого числа N = P • Q, является практически неразрешимой задачей при достаточно больших значениях N. По современным оценкам теории чисел при целом N»2664
и соизмеримых значениях P и Q,
для разложения числа N
потребуется около 1023
операций, т.е. задача практически неразрешима на современных ЭВМ.
Еще один пример однонаправленной функции - это модульная экспонента с фиксированными основанием и модулем. Пусть А и N - целые числа, такие, что 1ЈА<N.
Определим множество ZN, как ZN= {0,1,2,…,N-1 }.
Тогда модульная экспонента с основанием А
по модулю N представляет собой функцию
fA,N: ZN > ZN такую, что fA,N(x)= Ax(mod N)
где x-целое число, 1Ј x Ј N-1.
Существуют эффективные алгоритмы, позволяющие достаточно быстро вычислить значения функции fA,N(x). Если y=Ax, то естественно записать x=logA(y).
Поэтому задачу обращения функции fA,N(x) называют задачей нахождения дискретного логарифма или задачей дискретного логарифмирования.
Задача дискретного логарифмирования формулируется следующим образом. Для известных целых A, N, у
найти целое число х,
такое, что Ax(mod N)=y.
Алгоритм вычисления дискретного логарифма за приемлемое время пока не найден. Поэтому модульная экспонента считается однонаправленной функцией.
По современным оценкам теории чисел при целых числах А»2664
и N»2664
решение задачи дискретного логарифмирования (нахождение показателя степени х
для известного у) потребует около 1026
операций, т.е. эта задача имеет в 103
раз большую вычислительную сложность, чем задача разложения на множители. При увеличении длины чисел разница в оценках сложности задач возрастает.
Следует отметить, что пока не удалось доказать, что не существует эффективного алгоритма вычисления дискретного логарифма за приемлемое время. Исходя из этого, модульная экспонента отнесена к однонаправленным функциям условно, что, однако, не мешает с успехом применять ее на практике.
Вторым важным классом функций, используемых при построении криптосистем с открытым ключом, являются так называемые однонаправленные функции с "с секретом".
Дадим неформальное определение такой функции.
Определение. 8 Функция f: X ® Y относится к классу однонаправленных функций с "секретом" в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление обратной функции, если известен "секрет" (секретное число, строка или другая информация, ассоциирующаяся с данной функцией).
В качестве примера однонаправленной функции с "секретом" можно указать используемую в криптосистеме RSA модульную экспоненту с фиксированными модулем и показателем степени. Переменное основание модульной экспоненты используется для указания числового значения сообщения P либо криптограммы E.
Приведенное позволяет заключить, что на базе описанных выше Машин, Сохраняющих Информацию можно построить однонаправленную функцию, так как при этом будет создан алгоритм кодирования, в котором для кодирования и декодирования применяются разные алгоритмы. Тем не менее, полученная однонаправленная функция будет иметь одинаковую сложность построения обратной функции для всех участников информационного обмена, то есть, такая однонаправленная функция не буде обладать «секретом».
