Криптосистемы с открытым ключом

Основы криптографии с открытыми ключами были выдвинуты Уитфилдом Диффи(Whitfield Diffie) и Мартином Хеллманом(Martin Hellman), и независимо Ральфом Мерклом(Ralph Merkle). Их вкладом в криптографию было убеждение, что ключи можно использовать парами - ключ шифрования и ключ дешифрирования - и что может быть невозможно получить один ключ из другого. Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции 1976г., через несколько месяцев была опубликована их основополагающая работа "New Directions in Cryptography" ("Новые направления в криптографии"). Первая работа Меркла вышла в 1978г.

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

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

• Разложение больших чисел на простые множители (RSA)
• Вычисление логарифма в конечном поле (криптосистема Эль-Гамаля)
• Вычисление корней алгебраических уравнений (на основе эллиптических уравнений)

Криптосистемы с открытым ключом можно использовать в трех назначениях:

• Как самостоятельные средства защиты передаваемых и хранимых данных.
• Как средства для распределения ключей.
• Средства аутентификации пользователей.

Все криптосистемы с открытым ключом достаточно медлительны и ниодна из них неможет сравниться по быстродействию с симметричными криптосистемами. Так быстродействие RSA в тысячи раз ниже чем у DES или ГОСТ 28147-89. Поэтому используют гибридные криптосистемы.

• На начальном этапе участники информационного обмена, используя протокол выработки общего секретного ключа, формируют общую секретную информацию (сеансовый ключ). На следующем этапе обмена используется криптосистема с секретным ключом.
• Отправитель вырабатывает секретный ключ - случайное число, используемое только один раз и поэтому называемое одноразовым или сеансовым ключом. Этот ключ используется для шифровки сообщения при помощи симметричного алгоритма. Сеансовый ключ зашифровывается на открвтом ключе получателя и присоединяется к ранее зашифованному документу. Сформированное таки образом сообщение отсылается получателю. Последний, получив сообщение, повторяет те же процедуры, но в обратном порядке - с помощью своего секретного ключа он восстанавливает сеансовый ключ и расшифровывает сообщение.

Алгоритм RSA

Криптосистема RSA была разработана в 1977 году и получила название в честь ее создателей: Рона Ривеста(Ron Rivest), Ади Шамира(Adi Shamir) и Леонарда Адлмана(Leonard Adleman). Они воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. Доказано (теорема Рабина), что раскрытие шифра RSA эквивалентно такому разложению. Поэтому для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время. Возможность гарантированно оценить защищенность алгоритма RSA стала одной из причин популярности этой криптосистемы на фоне десятков других схем. Поэтому алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (обслуживание кредитных карточек).