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

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

Схема шифрования с открытым ключом

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

Е_е(т) = с

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

D_d(c) = т

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

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

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

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

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

D m

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

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

_______________________________________________________________

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

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

E_e (m) = c m

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

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

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

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

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

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

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

Уа=а^хахь

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

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

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