Глава 19 Алгоритмы с открытыми ключами 19.1 Основы

Концепция криптографии с открытыми ключами была выдвинута Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman), и независимо Ральфом Мерклом (Ralph Merkle). Их вкладом в крипто­графию было убеждение, что ключи можно использовать парами - ключ шифрования и ключ дешифрирования -и что может быть невозможно получить один ключ из другого (см. Раздел 2.5). Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции (National Computer Conference) 1976 года [495], через несколько месяцев была опубликована их основополагающая работа "New Directions in Cryptogra­phy" ("Новые направления в криптографии") [496]. (Из-за бесстрастного процесса публикации первый вклад Меркла в эту область вышел появился только в 1978 году [1064].)

С 1976 года было предложено множество криптографических алгоритмов с открытыми ключами. Многие из них небезопасны. Из тех, которые являются безопасными, многие непригодны для практической реализации. Либо они используют слишком большой ключ, либо размер полученного шифротекста намного превышает ра з-мер открытого текста.

Немногие алгоритмы являются и безопасными, и практичными. Обычно эти алгоритмы основаны на одной из трудных проблем, рассмотренных в разделе 11.2. Некоторые из этих безопасных и практичных алгоритмов подходят только для распределения ключей. Другие подходят для шифрования (и для распределения ключей). Третьи полезны только для цифровых подписей. Только три алгоритма хорошо работают как при шифровании, так и для цифровой подписи: RSA, EIGamal и Rabin. Все эти алгоритмы медленны. Они шифруют и дешифри­руют данные намного медленнее, чем симметричные алгоритмы. Обычно их скорость недостаточна для шифр о-вания больших объемов данных.

Гибридные криптосистемы (см. раздел 2.5) позволяют ускорить события: для шифрования сообщения ис­пользуется симметричный алгоритм со случайным ключом, а алгоритм с открытым ключом применяется для шифрования случайного сеансового ключа.