Число d хранится в строжайшем секрете — это и есть “закрытый ключ”, который позволит читать все послания, зашифрованные с помощью пары чисел (е,n)

Шифрование с помощью этих чисел производится следующим образом:

1) Отправитель разбивает свое сообщение на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

2) Подобный блок может быть интерпретирован как число из диапазона (0;2^k -1). Для каждого такого числа (назовем его m_i) вычисляется выражение c_i = ((m_i)^e)mod n.

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

Обратная ей задача носит название " логарифмирование в конечном поле" и является на несколько порядков более сложной задачей.

Даже, если злоумышленник знает числа е и n, то по с_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i).

А вот на приемной стороне процесс дешифрования все же возможен, и поможет в этом хранимое в секрете число d.

В 18-ом веке была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел р и q, то для любого х имеет место равенство (x^(р-1)(q-1)) mod n = 1.

Для дешифрования RSА -сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-у): (х^{(-у)(р-1)(q-1)}) mod n = 1^(-у) = 1. Теперь умножим обе ее части на х: (х^{(-y)(p-1)(q-1)+1} ) mod n =1*х = х.

А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что

c*d+(р-1)(q-1)*у=1, то есть е*d=(-у)(р-1)(q-1)+1.

А следовательно в последнем выражении предыдущего абзаца можно заменить показатель степени на число (е*d).

Получаем (х^е*^d) mod n = х.

Таким образом, для того чтобы прочесть сообщение

с_i=((m_i^е) mod n достаточно возвести его в степень d по модулю m: ((с_i)^d)mod n = ((m_i)^е*d) mod n = m_i

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

Механизм распространения открытых ключей

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

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

1) Алиса зашифрует сообщение тем ключом, который по её мнению является открытым ключом Боба

2) Злоумышленник, перехватив сообщение дешифрует его парным закрытым ключом, прочтет и более того:

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

Точно так же, но по инверсной схеме, он может подменить и электронную подпись Алисы под её письмом.

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

Но в асимметричной криптографии есть оригинальный способ очень значительного снижения риска подобной атаки.

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

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

На самом деле никуда ходить с дискетой, получив просьбу от своего знакомого передать открытый ключ мистера V.М.В. мистеру R.Н.J, не нужно. Ведь Алиса общается со своим знакомым лично, значит, у Алисы есть его открытый ключ, полученный каким-либо надежным способом. А следовательно, он может Алисе прислать этот открытый ключ мистера V.М.В., подписав сообщение своей электронной подписью. А от Алисы в свою очередь требуется всего лишь отправить этот ключ дальше по цепочке в направлении мистера R.Н.J., подписав уже своей электронной подписью. Таким образом, минуя несколько переподписываний, открытый ключ дойдет от места отправления к месту требования по надежному пути. В принципе от Алисы даже может не требоваться никаких действий - просто ей нужно поставить на своей ЭВМ специальный сервер распространения ключей, и он все только что описанные действия будет выполнять автоматически.

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