Перспективы развития и использования асимметричных алгоритмов в криптографии

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

Введение

Краткая предыстория

Традиционно считается, что концепция асимметричной криптографии впервые была предложена в 1976 году Уитвелдом Диффи и Мартином Хеллманом на национальной компьютерной конференции [1] и опубликована в том же году в основополагающей работе "Новые направления в криптографии" [2]. К числу отцов-основателей асимметричной криптографии относят также и Ральфа Меркля, который независимо от Диффи и Хеллмана пришел к тем же конструкциям, однако опубликовал свои результаты только в 1978 году [3].
На приоритет в открытии асимметричной криптографии претендует и Агентство национальной безопасности США. В статье энциклопедии "Британника" директор АНБ Симмонс заявляет, что "двухключевая криптография была известна в Агентстве за 10 лет до публикации Диффи и Хеллмана" [4].

Терминология

В настоящее время термином "асимметричная криптография" обозначают большую группу механизмов, алгоритмов, протоколов и идей, применяемых при разработке систем защиты информации. Перечислим основные из них и кратко прокомментируем, что конкретно понимается под каждым термином (систематический словарь терминов из области асимметричной криптографии приведен в работе [5]).
1) односторонняя функция (One-way function);
2) односторонняя функция с секретом (One-way trap-door function) - это некоторая функция FK: X®Y, зависящая от параметра K (ее можно рассматривать также как параметризованное семейство функций) и обладающая следующими свойствами: a) при любом значении параметра K существует полиномиальный алгоритм вычисления значения функции в любой точке FK(x) при условии, что параметр K неизвестен;
б) при неизвестном значении параметра K не существует полиномиального алгоритма инвертирования функции FK;
в) при известном значении параметра K существует полиномиальный алгоритм инвертирования функции FK (здесь не обсуждается модель вычислений, в рамках которой мы говорим об их полиномиальности).
Понятие односторонней функции с секретом явилось исходным для асимметричной криптографии. Собственно, тот факт, что для вычисления самой функции с полиномиальной сложностью и для ее инвертирования требуется различная исходная информация (то есть наличие определенной асимметрии), и дал название новому направлению в криптографии.
3) криптографические протоколы - это такая процедура взаимодействия абонентов, в результате которой они достигают своей цели, а их противники - не достигают. Под это неформальное определение подпадают все практически интересные способы применения асимметричной криптографии:
· протоколы открытого распределения ключей;
· протоколы открытого шифрования;
· протоколы электронной цифровой подписи;
· протоколы аутентификации;
· "электронные деньги" (здесь, на самом деле, имеется в виду целая совокупность протоколов взаимодействия между различными участниками системы).
Формальные определения для перечисленных протоколов даны в книге [5]. В последнее время число различных типов криптографических протоколов стремительно растет, но, поскольку большая их часть представляет (пока) чисто теоретический интерес, мы на них останавливаться не будем.
4) доказательства (интерактивные) с нулевым разглашением - это общая теоретическая модель, к которой в 1985-1986 годах пришли исследователи различных криптографических протоколов: [6], [7]).
Качественно, доказательство (интерактивное) с нулевым разглашением можно определить как протокол взаимодействия двух абонентов: Доказывающего (обозначение - P от английского Prover) и Проверяющего (обозначение - V от английского Verifier). Абонент P хочет доказать проверяющему V, что некоторое утверждение S истинно. Протокол при этом должен удовлетворять условиям: а) полноты - если S истинно, то P убедит абонента V признать это; б) корректности - если S ложно, то P вряд ли убедит V, что S истинно; в) свойству нулевого разглашения - в результате выполнения протокола Проверяющий V не сможет извлечь никакой дополнительной информации о том, почему S истинно (см. например, [8]).
Доказательства с нулевым разглашением заслуживают отдельного упоминания не только потому, что их идея позволяет с единой позиции взглянуть на большинство криптографических протоколов, но также и потому, что они, по-видимому, будут основным объектом изучения нового, бурно развивающегося направления в математике и теоретической криптографии. Кроме того, доказательства с нулевым разглашением находят важные практические сферы применения (например, в области разработки протоколов для интеллектуальных карточек [5]).

Объективные потребности

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