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