Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Для английского термина «trapdoor function* в русскоязычной литературе используется также перевод «функция с лазейкой». — Прим. ред.
94
ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ
при вычислении /. Обратная функция /~ , однако, легко вычислима, если известна дополнительная информация KD — ключ дешифрования.
Очень близким является понятие однонаправленной функции. Это такая функция, которую легко вычислить, но для которой обратную функцию / вычислить трудно даже при наличии некоторой дополнительной информации. В то время как понятие функции с замком появилось впервые в 1978 году в связи с разработкой криптосистемы RSA с открытым ключом, понятие однонаправленной функции немного старше. По-видимому, впервые использование однонаправленных функций в криптографии было описано в книге Уилкеса о системах разделения времени, опубликованной в 1968 году. Автор описывает новый однонаправленный шифр, использованный Нидхамом для того, чтобы компьютер мог проверять пароли, не храня информацию, которая позволила бы злоумышленнику выдавать себя за легального пользователя.
В системе Нидхама при установлении или смене пароля он немедленно шифруется и хранится в компьютере в зашифрованном виде. Когда пароль вводится в ответ на запрос при идентификации пользователя, пароль снова шифруется и результат сравнивается с хранящейся версией. Для злоумышленника нет прямого смысла добывать список хранящихся зашифрованных паролей, так как прежде, чем им пользоваться, эти пароли надо расшифровать. Для этого, даже имея доступ к компьютеру и зная во всех деталях алгоритм шифрования, придется затратить массу времени для процедуры дешифрования.
В 1974 году Дж. Парди впервые подробно описал такую однонаправленную функцию. Исходный пароль и зашифрованный пароль рассматриваются как целые числа по большому простому модулю р, а однонаправленное отображение Fp —» Fp задается многочленом f(x), который нетрудно вычислить на компьютере, но обратить его за разумное время невозможно. Парди использовал р — 264 — 59,
2 ^ -I-17 2^4-г-3 3 2
f(x) = X А-а\Х + а2х + а3х + а4 ж + а5, где коэффициентами являются произвольные 19-разрядные целые числа.
Данные выше определения криптосистемы с открытым ключом, однонаправленной функции и функции с замком строгими с математической точки зрения не являются. Они опираются на понятие «практической вычислимости». Но это понятие — эмпирическое, на его содежание влияют как достижения вычислительной техники (например, появление компьютеров с параллельными процессорами), так и открытие новых алгоритмов, ускоряющих решение арифметических
§ 1. СУТЬ КРИПТОГРАФИИ С ОТКРЫТЫМ ключом
95
задач. Поэтому шифрующее преобразование, с полным основанием рассматривавшееся в 1994 году как однонаправленная функция или функция с замком, может потерять этот статус в 2004 или 2994 году.
Не исключено, что для некоторых преобразований можно доказать, что они являются функциями с замком. Например, может существовать теорема, дающая нетривиальную нижнюю границу для числа двоичных операций, необходимых («в среднем», при случайном выборе ключевых параметров) для того, чтобы описать и реализовать дешифрующий алгоритм, не зная ключ дешифрования. При этом следовало бы допускать возможность использования большого числа соответствующих друг другу элементов открытого и шифрованного текстов (как это делалось при частотном анализе простых систем в главе III), так как, по определению системы с открытым ключом кто угодно может выработать произвольно большое число таких пар. Необходимо было бы также учесть возможность использования «вероятностных» методов, которые, не гарантируя вскрытия кода при однократном применении, рано или поздно дают нужный результат, если применять их много раз. (Примеры вероятностных алгоритмов будут приведены в следующей главе.) К сожалению, ни одной такой теоремы не доказано ни для одной из функций, используемых как шифрующие отображения. Таким образом, хотя сейчас есть много криптосистем, представляющихся заслуживающими названия «систем с открытым ключом», нет ни одной криптосистемы, для которой это свойство было бы доказано.
Смысл названия «открытый ключ» состоит в том, что информация, используемая при отправке секретных сообщений — ключ шифрования КЕ — может быть раскрыта без риска, что кто-либо получит возможность прочесть секретные сообщения. Так, пусть имеется некоторая группа пользователей криптосистемы, каждый из которых хочет иметь возможность принимать и дешифрировать конфиденциальные сообщения от любого другого без участия третьих лиц (как пользователей, так и посторонних). Какой-нибудь центральный узел может собрать ключи шифрования Ke,а от каждого пользователя А и опубликовать их в «телефонной книге» в следующем виде
AAA Banking Company (9974398087453939,2975290017591012) Aardvark, Aaron (8870004228331,7234752637937)
Желающий послать сообщение просто должен найти ключ шифрования получателя в такой «телефонной книге» и использовать его в общем шифрующем алгоритме как ключевой параметр. Только этот получатель имеет в своем распоряжении ключ дешифрования, необхо-
