Криптография с открытым ключом

Криптографическая система с открытым ключом или Асимметричное шифрование, Асимметричный шифр — это система шифрования или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по незащищенному от постороннего наблюдения каналу, и используется для проверки ЭЦП и шифрования сообщения. Генерация и расшифровака сообщения осуществляется посредством секретного ключа.

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

---

Схема передачи информации лицом А лицу В

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

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

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

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

---

Рисунок иллюстрирует, как кто-то, выполняющий роль активного перехватчика, может захватить систему без взламывания системы шифрования

Существует пять основных принципов построения криптосистем с открытым ключом:

• Начальный этап — решение трудной задачи P. Сложность этой задачи заключается в отсутствие алгоритма, который мог бы подобрать все возможные варианты решения задачи P за полиномиальное время относительно размера задачи.
• Решение легкой подзадачи P’ из P, которое должно быть осуществлено за линейное время.
• «Перетасовываем и взбалтываем» P’. Для того, чтобы получить задачу P’’, абсолютно отличную от первоначальной, необходима задача P’’ ввиде оригинальной труднорешаемой задачи P.
• Использование P’’ с описанием в роли ключа шифрования. Процесс получения P’ из P’’ держится в секрете как секретная лазейка.
• В итоге, криптосистема организована таким образом, что алгоритмы расшифрования для легального пользователя и криптоаналитика существенно различны. В то время как первый решает P’’ задачу, второй использует секретную лазейку и решает P’ задачу.

Для того, чтобы понять идеи и методы криптографии с открытым ключом необходимо привести следующий пример — хранение паролей в компьютере. У каждого пользователь в сети имеется свой секретный пароль. При входе в сеть, пользователь указывает свое имя и вводит пароль. Важно отметить, что хранение пароля на жестком диске компьютера облегчает доступ злоумышленников к секретной информации. Как уже говорилось, для решения задачи используется односторонняя или необратимая функция. В процессе создания секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Приведем наглядный пример, пользователь Маруся придумала пароль «Баранки». При сохранении этих данных вычисляется результат функции f(МАРУСЯБАРАНКИ), пусть в результате вычисления будет выбрана строка Сухари, которая и будет сохранена в системе. В результате файл паролей будет иметь следующий вид:

Вход в систему выглядит так:

При введении пользователем Маруся секретного пароля, компьютер проверяет, даёт или нет функция, применяемая к МАРУСЯБАРАНКИ, правильный результат Сухари, хранящийся на диске компьютера. Изменение одной буквы в пароле или имени приведет к совершенно другому результату функции.

В другом примере будет рассмоторена возможность восстановление открытого сообщения с помощью «секретной лазейки», то есть труднодоступной информации. Для шифрования текста можно воспользоваться большим абонентским справочником, который состоит из нескольких толстых томов. Этот справочник позволяет без труда найти номер любого жителя города, однако найти абонента по известному номеру практически невозможно. Итак, для каждой буквы шифруемого сообщения подбирвается имя, начинающееся на ту же букву. В результате, каждой букве соответствует номер телефона абонента. К примеру, отправляемое сообщение «ВОРОНКА» будет зашифровано следующим образом:

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

---

Еще одна форма атаки — вычисление закрытого ключа, зная открытый

Для успешной дешифрации текста, необходимо иметь справочник, составленный по возрастанию номеров. В таком случае телефонный справочник является секретной лазейкой, которая помогает получить исходный текст, известной только легальным пользователям. Отсутствие справочника или его копии значительно увеличит время криптоаналитика на расшифровку.

К главным достоинствам ассиметричных шифров относятся:

• Отсутствие необходимости предварительной передачи секретного ключа по надёжному каналу.
• В ассиметричной криптосистеме только один ключ держится в секрете.
• В ассиметричных криптосистемах пару секретных ключей можно не менять на протяжении длительного периода времени.
• Количество ключей в асимметричной криптосистеме значительно меньше, чем в симметричной.

Однако ассиметричная система шифрования имеет и ряд недостатков. Среди них выделяют:

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