Симметричные и асимметричные шифры

Все рассмотренные ранее классические шифры, а также алгоритмы блочного шифрования являлись симметричными.

Симметричным называют криптографический алгоритм, в котором как для шифрования, так и для и расшифровки, применяют один и тот же ключ. Такие алгоритмы именуются одноключевыми, или алгоритмами с секретным ключом (рис. 3.1).

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

Рис. 3.1. Симметричная схема шифрования секретного ключа получателю при обмене сообщениями). Применение шифрования обусловлено тем, что абоненты не доверяют каналу передачи данных. Неизбежно возникает вопрос: как передать ключ в недоверенной среде и при этом не позволить злоумышленникам перехватить его.

Преимущества криптографии с симметричными ключами:

• • высокая производительность — позволяет использовать алгоритмы симметричной криптографии для шифрования данных в режиме реального времени;
• • высокая стойкость. При прочих равных условиях стойкость криптографического алгоритма определяется длиной ключа. В настоящее время для современных блочных алгоритмов симметричного шифрования считается достаточной длина ключа в 128 бит, в то время как асимметричные системы используют ключи не менее 1024 бит, криптография на эллиптических кривых — ключи длиной 256 бит.

Недостатки криптографии с симметричными ключами:

• • проблема распределения ключей. Поскольку для шифрования и расшифровки используется один и тот же ключ, требуются очень надежные механизмы для их распределения между абонентами;
• • масштабируемость. Поскольку и отправитель, и получатель используют единый ключ, количество необходимых ключей возрастает в геометрической прогрессии в зависимости от числа участников коммуникации. Для организации обмена зашифрованными сообщениями между N пользователями потребуется порядка N²/2 ключей. Для двух пользователей достаточно одного ключа, для трех потребуется три, а для четырех — шесть ключей. 10 пользователям необходимо иметь 45 ключей, а для 1000 пользователей потребуется уже 499 500 ключей;
• • ограниченное использование. Криптография с секретным ключом обеспечивает только конфиденциальность (секретность) защищаемой информации, с ее помощью невозможно обеспечить такие свойства информации, как подтверждение или невозможность отказа от авторства (аутентичность и неотрекаемость).

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

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

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

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

Один из ключей (например, ключ шифрования) может быть сделан общедоступным — открытым (public key), и в этом случае проблема получения общего секретного ключа для связи отпадает. Поскольку один ключ из пары делается общедоступным, такие системы получили также название криптосистем с открытым ключом.

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

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

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

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

Обозначим отправителя сообщения как А, а получателя — В. Для обеспечения секретности (рис. 3.2) отправитель А шифрует сообщение открытым ключом получателя ОК(В), а получатель В расшифровывает полученное сообщение своим личным ключом ЛК(В). Поскольку никто, кроме получателя, не знает его личного ключа ЛК(В), расшифровать сообщение сможет только он один.

Рис. 3.2. Криптография с открытым ключом: обеспечение секретности

Рис. 3.3. Криптография с открытым ключом: обеспечение аутентичности

и неотрекаемости

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

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

Пусть дана функция /: X —? У, у = /(х), определенная на конечном множестве Х_ух е Х_у для которой существует обратная функция х = /~у), у? У.

Функция / называется односторонней {однонаправленной)у если выполняются следующие условия:

• • для всякого х g X легко вычислить значение функции у =/(х);
• • для произвольного у е У нахождение значения х е X, такого, что х = - f-y) (т.е. вычисление обратной функции), является трудной вычислительной задачей.

Односторонней функцией с секретом {функцией-лазейкой) называется односторонняя функция, для которой обратную функцию вычислить просто, если имеется некоторая дополнительная информация, и сложно, если такая информация отсутствует.

 

Односторонняя функция с секретом к — такая функция fk: X —> У, для которой выполняются следующие условия:

• • для всякого х е X легко вычислить значение функции у = fk{x)y где у е У, даже в том случае, если значение к неизвестно;
• • не существует легкого (эффективного) алгоритма вычисления обратной функции fk y) без знания секрета к;
• • при известном к вычисление fk y) для у е У не представляет существенной сложности.

В качестве задач, приводящих к односторонним функциям, можно привести следующие.

• 1. Разложение числа на простые сомножители. Вычислить произведение двух простых чисел очень просто. Однако для решения обратной задачи в общем случае — разложения любого заданного числа на простые сомножители — эффективного алгоритма в настоящее время не существует.
• 2. Дискретное логарифмирование в конечном простом поле (проблема Диффи — Хеллмана). Допустим, задано большое простое числор их — целое число: 0 < х < р. Тогда для любого заданного х вычислить у = a* mod/? просто {а — примитивный элемент поля), а нахождение дискретного логарифмах = og_aymo< p< i=" " > по заданным у и р является сложной вычислительной задачей.< /p< >

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

Пусть М — исходное сообщение. Получатель выбирает одностороннюю функцию с секретом, и тогда любой, кто знает эту функцию, может зашифровать сообщение для данного получателя, вычислив значение криптограммы С = fk(M). Расшифровать же данную криптограмму сможет только законный получатель, которому известен секрет к.

Таким образом, прямое направление односторонней функции с секретом используется для шифрования и верификации цифровых подписей, а обратное — для расшифровки и выработки цифровой подписи.

 

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

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

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

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

⇐ Предыдущая12

Поделиться: