Главная | Обратная связь

Алгоритмы асимметричного шифрования

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

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

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

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

Рассмотрим построение ассиметричных алгоритмов на примере системы, разработанной в 1978 году американцами Р.Ривестом, Э.Шамиром и Л.Адлеманом. По их именам эта система получила название RSA. Вообще она является первой и наиболее известной системой с открытым ключом.

Пусть абоненты A и B решили организовать для себя возможность секретной переписки. Для этого каждый из них независимо выбирает два больших простых числа ( , и , ), находит их произведение (r_A и r_B), функцию Эйлера от этого произведения (j(r_A) и j( r_B)) и случайное число (a и b), меньшее вычисленного значения функции Эйлера и взаимно простое с ним. Кроме того, A из уравнения

aa º 1 (mod j(r_A))

находит a (0 < a < j(r_A)), а B из уравнения

bb º 1 (mod j(r_B))

находит b (0 < b < j(r_B)). Затем A и B публикуют доступную всем информацию вида:

A: r_A, a;

B: r_B, b.

Теперь кто угодно может отправлять конфиденциальные сообщения A или B. Например, если пользователь C хочет отправить сообщение m для B (m должен быть меньшим r_B или делится на куски, меньшие r_B), то он использует ключ b для получения шифрованного сообщения m₁ по формуле

m₁ º m^b (mod r_B),

которое и отправляется B. Получатель сообщения B для дешифрирования m₁ использует ключ b в формуле

º m^bb º m (mod r_B),

так как bb º 1 (mod j(r_B)), следовательно, bb = kj(r_B) + 1 для некоторого целого k и m^{kj(rB) + 1} º (m^j(rB) )^km º m (mod r_B), так как m^j(rB) º 1 (mod r_B) по теореме Эйлера-Ферма.

Функция Эйлера j(n), где n – натуральное число, определяется следующим образом:

j(1) = 1; ,

где p_i – простые сомножители числа n, a_i – кратности простых сомножителей числа n.

Задача нахождения секретного ключа в алгоритме RSA будет иметь такую же сложность, что и задача разложения числа на простые множители, поскольку здесь использовалась соответствующая односторонняя функция. Рассмотрим алгоритм RSA на примере. Пусть для A имеем = 7 и = 23. Тогда r_A = = 161, j(r_A) = j(161) = 6 ´ 22 = 132, a = 7, a = 19. Если кто-то захочет отправить A секретное сообщение m = 3, то он должен будет преобразовать его в m₁ º 3⁷ º 94 (mod 161). Когда A получит m₁ = 94, он дешифрирует его по формуле m = 94¹⁹ º 3 (mod 161).

 

Цифровая подпись

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

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

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

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

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

 

Хэш-алгоритмы

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