Для известных целых A, N, y найти целое число x, такое, что

A^x mod N = y.

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

По современным оценкам теории чисел при целых числах A » 2⁶⁶⁴ и

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

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

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

Дадим неформальное определение такой функции.

Функция: f : X ® Y

относится к классу однонаправленных функций с "потайным ходом" в том случае, если:

· она является однонаправленной

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

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

Способы передачи секретного ключа по открытому каналу

Идея передавать "секретный" ключ по открытому каналу кажется на первый взгляд невозможной, но если, отказавшись от совершенной секретности, ограничиться практической стойкостью, то можно придумать способ обмена ключами.

Первым из получивших распространение способов – экспоненциальный ключевой обмен.

Принципы и методы криптосистемы с открытым ключом

Принцип криптографии с открытым ключом очень тесно связана со свойством односторонних функций, то есть таких функций f(х), что по известному х довольно просто найти значение f(x), тогда как определение хиз f(х) сложно в смысле теории.

Но сама односторонняя функция бесполезна в применении:

ею можно зашифровать сообщение, но расшифровать нельзя.

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

Ловушка — это некий секрет (инструкция), который помогает расшифровать.

Функцией-ловушкойназывается односторонняя функция, для которой обратную функцию вычислить просто, если имеется некоторая дополнительная информация, и сложно, если такая информация отсутствует. То есть существует такой у, что зная f(x), можно вычислить х.

eи d— ключи шифрования и расшифрования соответственно.

Е_е— функция шифрования для произвольного ключа е&K, (&- принадлежит) такая что: Е_е(т) = с

т&M, где М— пространство сообщений.

D_d(c)— функция расшифрования, с помощью которой можно найти исходное сообщение т, знаяшифротекст с :

D_d(c) = т

{Е_е.: е&K) — набор шифрования,

{D_d:: d&K }— соответствующий набор для расшифрования.

Каждая пара (Е,D) имеет свойство: зная Е_е,(m)невозможно решить уравнение Е_е(т) = с,то есть для данного произвольного шифротекста с&С,невозможно найти сообщение т&М.Это значит, что по данному еневозможно определить соответствующий ключ расшифрования d.

Е_еявляется односторонней функцией, а d— ловушкой.

Ниже показана схема передачи информации лицом А лицу В. Они могут быть как физическими лицами, так и организациями и так далее. Но для более лёгкого восприятия принято участников передачи отождествлять с людьми, чаще всего именуемых АлисаиБоб. Участника, который стремится перехватить и расшифровать сообщения Алисы и Боба, чаще всего называют Евой.

D m

А Генерирование > Расшифрование > Пункт назначения

Ключа (d) D_d(c) = m

_______________________________________________________________

e Открытый канал c Открытый канал

В Шифрование Исходный текст

E_e (m) = c m

1. Боб выбирает пару (е,d)и шлёт ключ шифрования е (открытый ключ) Алисе по открытому каналу, а ключ расшифрования d (закрытый ключ) защищен и секретен (он не должен передаваться по открытому каналу, либо его подлинность должна быть гарантирована некоторым сертифицирующим органом).

2 Чтобы послать сообщение тБобу, Алиса применяет функцию шифрования, определённую открытым ключом е: Е_е(т) = с, с— полученный шифротекст.

3. Боб расшифровывает шифротекст с, применяя обратное преобразование D_dоднозначно определённое значением d.

Алгоритм метода связи с экспоненциальным ключевым обменом

Суть его в следующем:

- Алиса и Боб(традиционные образы в криптологии) выбирают
случайные числа Ха и Хб соответственно.

- Алиса передает Бобу У_а =а^Ха (mod q),

аБоб Алисе - У_b =а^хь (mod q).

Здесь а - так называемый примитивный элемент конечного поля Галуа GF(q), замечательное свойство которого заключается в том, что его степени дают все ненулевые значения элементов поля.

В качестве секретного ключа используется значение

Уа=а^хахь

которое Алиса получает возведением переданного Бобом числа в степень Ха, известную только ей, а Боб - полученного от Алисы числа в известную только ему степень Х_Ь.

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

Устойчивость экспоненциального ключевого обмена базируется на так называемой односторонности функции возведения в степень: вычислительная сложность получения Уа из Хапри qдлиной 1000 битов составляет порядка 2000 умножений 1000 битовых чисел. Обратная операция потребует примерно 1030 операций.

ОДНОСТОРОННИЕ функции, обладающие подобной асимметрией вычислительной сложности прямой и обратной задачи,играют ведущую роль в криптографии с открытым ключом.

Еще более интересна односторонняя функция с потайным ходом ("ловушкой").

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

Тогда параметры функции «ловушки» служат открытым ключом.

Принцип действия метода

1) Алиса передаёт понезащищенному каналу Бобу свой открытый ключ (параметры функции «ловушки»);

2) Боб, используя полученный открытый ключ, выполняет шифрование (вычисление прямой функции) и передает по тому жеканалу результат Алисе;

3) Алиса, зная "ловушку" (секретный ключ), легко вычисляет обратную функцию.