Система Вернама
Рисунок 1.10. Система Вернама
Если ключ порожден надежным генератором случайных чисел (например, правильно настроенным оцифровщиком теплового шума), никакая информация об автокорреляциях в исходном тексте сообщения взломщику не поможет: перебирая полное пространство ключей, взломщик вынужден будет проверить все сообщения, совпадающие по количеству символов с исходным, в том числе и все сообщения, удовлетворяющие предполагаемому автокорреляционному соотношению.
Это преимущество теряется, если один и тот же ключ будет использован для кодирования нескольких сообщений: взломщик, перехвативший их все, сможет использовать эти сообщения и предположения об их содержимом при попытках отфильтровать ключ от полезной информации — отсюда и второе название алгоритма. Применение системы Вернама, таким образом, сопряжено с дорогостоящей генерацией и, главное, транспортировкой ключей огромной длины, и поэтому она используется лишь в системах экстренной правительственной и военной связи.
Более практичным оказалось применение в качестве ключа псевдослучайных последовательностей, порождаемых детерминированными алгоритмами. В промежутке между первой и второй мировыми войнами широкое распространение получили шифровальные машины, основанные на механических генераторах таких последовательностей. Чаще всего использовались сочетания, получаемые при вращении колес с взаимно простыми количествами зубцов.
Основной опасностью при использовании таких методов шифрования является возможность определить текущую точку последовательности — узнав ее (например, по косвенным признакам догадавшись, что в данной точке сообщения должно быть такое-то слово, и восстановив использовавшийся при ее шифровании элемент ключа), взломщик может продолжить генерацию с той же точки и расшифровать весь дальнейший поток.
В системах цифровой связи широкое применение получили блочные алгоритмы, выполняющие над блоками данных фиксированной длины последовательности -- иногда довольно сложные — перестановок, подстановок и других операций, чаще всего двоичных сложений данных с ключом по какому-либо модулю. В операциях используются компоненты ключевого слова относительно небольшой разрядности.
Например, широко применяемый блочный алгоритм DES шифрует 64-битные блоки данных 56-битным ключом. Полное описание алгоритма приводится в документе [NBS FIPS PUB 46, 1977]. Русский перевод этого документа может быть найден в приложениях к книге [Дейтел 1987]. Для современной вычислительной техники полный перебор 56-битного пространства — "семечки", поэтому сейчас,все большее распространение получают алгоритмы с большей разрядностью ключа — Blowfish, IDEAL и др. [Анин 2000].
Шифры с открытым ключом называются также двухключевыми. Если в алгоритмах со скрытым ключом для кодирования и декодирования сообщений используется один и тот же ключ, то здесь используются два ключа: публичный и приватный. Для прочтения сообщения, закодированного публичным ключом, необходим приватный, и наоборот.
Помимо обычных соображений криптостойкости, к таким алгоритмам предъявляется дополнительное требование: невозможность восстановления приватного ключа по публичному иначе как полным перебором пространства ключей.
Двухключевые схемы шифрования намного сложнее в разработке, чем схемы с секретным ключом: требуется найти преобразование, не поддающееся обращению при помощи применявшегося в нем публичного ключа, но такое, чтобы с применением приватного ключа его все-таки можно было обратить. Известные криптоустойчивые схемы основаны на произведениях простых чисел большой разрядности, дискретных логарифмах и эллиптических кривых. Наиболее широкое применение получил разработанный в 1977 г. алгоритм RSA [www.rsa.com FAQ].
Известные двухключевые алгоритмы требуют соответствия ключей весьма специфическим требованиям, поэтому для достижения криптостойкости, сопоставимой с блочными алгоритмами, необходимо использовать ключи намного большей разрядности. Так, снятые в 2000 году ограничения Министерства торговли США устанавливали ограничения разрядности ключа, который мог использоваться в экспортируемом за пределы США программном обеспечении: для схем с секретным ключом устанавливался предел, равный 48 битам, а для схем с открытым — 480.
Использование ключей большой разрядности требует значительных вычислительных затрат, поэтому двухключевые схемы чаше всего применяются в сочетании с обычными: обладатель публичного ключа генерирует случайную последовательность битов, кодирует ее и отправляет обладателю приватного ключа. Затем эта последовательность используется в качестве секретного ключа для шифрования данных. При установлении двустороннего соединения стороны могут сначала обменяться своими публичными ключами, а затем использовать их для установления двух разных секретных ключей, используемых для шифрования данных, передаваемых в разных направлениях.
Такая схема делает практичной частую смену секретных ключей: так, в протоколе SSH ключ генерируется на каждую сессию [www.cs.hut.fi SSH]; в протоколе виртуальных приватных сетей IPSEC время жизни ключа ограничено восемью часами [redbooks.ibm.com sg245234.pdf].
Еще более широкое применение двухключевые схемы нашли в области аутентификации и электронной подписи. Электронная подпись представляет собой контрольную сумму сообщения, зашифрованную приватным ключом отправителя. Каждый обладатель соответствующего публичного ключа может проверить аутентичность подписи и целостность сообщения. Это может использоваться для проверки аутентичности как сообщения, так и самого отправителя. Использование в качестве контрольной суммы обычного CRC (см. разд. Контрольные суммы) невозможно, потому что генерация сообщения с заданным CRC не представляет вычислительной сложности. Для применения в электронной подписи были разработаны специальные алгоритмы вычисления контрольных сумм, затрудняющие подбор сообщения с требуемой суммой [RFC 1320, RFC 1321].
