Основы современной криптографии


Односторонние функции и функции-ловушки - часть 2


и получить с указанной вероятностью некоторое значение r' из прообраза. Далее злоумышленник подает r' на вход алгоритма G и получает пару ключей (k1, k2'). Хотя k2' не обязательно совпадает с k2, по определению криптосистемы

 для любого открытого текста m. Поскольку k2' найден с вероятностью по крайней мере 1/p(n), схема нестойкая.

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

В качестве задач, приводящих к односторонним функциям, можно привести следующие.

1. Разложение числа на простые сомножители.

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

2. Дискретное логарифмирование в конечном простом поле.

Допустим, задано большое простое число p и пусть g

– примитивный элемент поля GF(p). Тогда для любого a

вычислить ga(mod p) просто, а вычислить a

по заданным k = ga(mod p) и p

оказывается затруднительным.

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

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

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




- Начало -  - Назад -  - Вперед -