Модель системы с открытым ключом

В своей основополагающей работе Диффи и Хеллман ввели в рассмотрение понятие однонаправленной функции с лазейкой (или с секретом), ставшее центральным в криптографии с открытым ключом. Оно является обобщением известного до 1976 года понятия однонаправленной функции.

ОПРЕДЕЛЕНИЕ 1. Функция F: X ® Y называется однонаправленной функцией (ОФ), если она обладает двумя свойствами:

1) для каждого xÎX легко посчитать значение F(x) = y (легко вычислима);

2) почти для всех yÎY сложно найти решение xÎX уравнения F(x) = y.

Второй пункт определения 1 означает, что почти для всех yÎY функцию трудно инвертировать. Мы говорим «почти для всех» имея в виду, что существует небольшое по мощности множество у-ов, для которых несложно найти их прообразы при отображении F.

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

N = P∙Q,

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

Обратная задача – разложение на множители большого целого числа, т.е. нахождение делителей P и Q большого целого числа N = P∙Q, является практически неразрешимой задачей при достаточно больших значениях N. По современным оценкам теории чисел при целом N»2⁶⁶⁴ и P»Q для разложения числа N потребуется около 10²³ операций, т.е. задача практически неразрешима на современных компьютеров.

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

Z/N = {0, 1, 2,...,N –1}.

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

f_A,N: Z/N ® Z/N,

f_A,N (x) = а ^x (mod N),

где х – целое число, 1£ x £ N –1.

Существуют эффективные алгоритмы, позволяющие достаточно быстро вычислить значения функции f _{а ,N} (x).

Если y = а ^x, то естественно записать x = log _а (у).

Поэтому задачу обращения функции f_A,N(x),то есть определения x из уравнения y = а ^x mod N, называют задачей дискретного логарифмирования.

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

По современным оценкам теории чисел при целых числах а» 2⁶⁶⁴ и N» 2⁶⁶⁴ решение задачи дискретного логарифмирования (нахождение показателя степени x для известного y) потребует около 10²⁶ операций, т.е. эта задача имеет в 10³ раз большую вычислительную сложность, чем задача разложения на множители. При увеличении длины чисел разница в оценках сложности задач возрастает.

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

ОПРЕДЕЛЕНИЕ 2. Функция F_c: X ® Y, зависящая от параметра cÎК, называется однонаправленной функцией с лазейкой, если она обладает тремя свойствами:

1) при любом c функция F_c легко вычислима;

2) почти для всех yÎY сложно найти такие xÎX и cÎК что F_c(x) = y;

3) при известных c и y легко решить уравнение F_c(x) = y относительно неизвестного x (функцию F_c легко инвертировать)

Определения 1 и 2 являются математически нестрогими. Математические формализации понятий сложности и простоты алгоритмов можно найти в книгах по сложности алгоритмов.

В настоящее время не построено ни одной функции, для которой было бы доказано, что она является однонаправленной или однонаправленной функцией с лазейкой. Более того, не доказано даже их существование. Для практических целей криптографии построено несколько функций, которые могут оказаться ОФЛ. Для них пока строго не доказано второе свойство – отсутствие полиномиального алгоритма их инвертирования, но считается, что эта задача эквивалентна некоторой давно изучаемой трудной математической проблеме. Одним из самых известных и широко используемых «кандидатов» в однонаправленные функции с лазейкой является функция шифрования RSA. Наиболее распространенным «кандидатом» в однонаправленные можно считать функцию возведения в степень в мультипликативной группе простого поля, предложенную Диффи и Хеллманом для организации открытого распределения ключей.

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

Для решения проблемы распространения ключей было предложено два основных подхода.

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

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

Рассмотрим сначала второй подход. Причина, по которой ключи в обычных криптографических системах должны тщательно защищаться, состоит в том, что функции зашифрования и расшифрования в них неразделимы. Любое лицо, имеющее ключ, использованный для зашифрования какого-либо сообщения, может это сообщение расшифровать. В криптосистемах с открытым ключом процессы зашифрования и расшифрования разделены и зависят от различных ключей, причем по алгоритму зашифрования (определяемому ключом зашифрования), практически невозможно восстановить алгоритм расшифрования. Это означает, что для восстановления алгоритма необходимо провести такой объем вычислений, который можно считать практически неосуществимым. Поэтому стойкость таких систем не зависит от того, знает противник ключ зашифрования или нет. Этот ключ не нужно держать в секрете, его можно публиковать и передавать по незащищенному каналу связи. Отсюда название криптографических систем такого вида – «криптосистемы с открытым ключом».