Теория информационных систем. Страница 17.

Шифры с открытым ключом называются также двухключевыми. Если в алгоритмах со скрытым ключом для кодирования и декодирования сообщений используется один и тот же ключ, то здесь используются два ключа: публичный и приватный. Для прочтения сообщения, закодированного публичным ключом, необходим приватный, и наоборот.

Помимо обычных соображений криптостойкости, к таким алгоритмам предъявляется дополнительное требование: невозможность восстановления приватного ключа по публичному иначе как полным перебором пространства ключей.

Двухключевые схемы шифрования намного сложнее в разработке, чем схемы с секретным ключом: требуется найти преобразование, не поддающееся обращению при помощи применявшегося в нем публичного ключа, но такое, чтобы с применением приватного ключа его все-таки можно было обратить. Известные криптоустойчивые схемы основаны на произведениях простых чисел большой разрядности, дискретных логарифмах и эллиптических кривых. Наиболее широкое применение получил разработанный в 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].