Рис. 33.4 Работа процедуры MODULAR-ExPONENTATION при а = 7, Ъ = 560 = (1000110000) и п = 561. Показаны значения переменных после очередного исполнения тела цикла for. Процедура возвращает ответ 1.

33.6-1

Найдите порядки всех элементов вНайдите наименьшую

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

33.7-2

Предложите алгоритм вычисления ab mod га, который обрабатывает биты двоичной записи Ь справа налево (от старших к младшим).

33.7-3

Объясните, как вычислить a~l mod га для а £ Z* при помощи процедуры Modular-Exponentation, если известно значение <р(п).

33.7. Криптосистема RSA с открытым ключом

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

Криптосистема RSA основана на таком обстоятельстве: в настоящее время известны эффективные алгоритмы поиска больших простых чисел, но не известно сколько-нибудь приемлемого по времени работы алгоритма разложения произведения двух больших простых чисел на множители. Мы рассмотрим эти задачи (проверка простоты и разложение на множители) в разделах 33.8 и 33.9.

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

При использовании таких систем каждый участник переговоров имеет открытый ключ (public key) и секретный ключ (secret key).

В системе RSA ключ состоит из пары целых чисел. Участников переговоров может быть несколько, но для примера мы будем говорить о переговорах Алисы (А) и Боба (В). Их открытые ключи мы будем обозначать Ра и Рв, а секретные - Sb и Sb-

Каждый участник сам создаёт два своих ключа. Секретный ключ он хранит в тайне, а открытый сообщает остальным участникам (и вообще всем желающим, например, через газеты или Internet; открытые ключи всех заинтересованных лиц можно публиковать в специальных справочниках и т.п.).

Обозначим через V множество всех возможных сообщений (например, это может быть множество всех битовых строк). Потребуем, чтобы каждый ключ задавал перестановку множества V, и через Ра() и Sa() будем обозначать перестановки, соответствующие ключам Алисы. Мы считаем, что каждая из перестановок Ра() и $а() может быть быстро вычислена, если только известен соответствующий ключ.

Мы хотим, чтобы ключи одного участника задавали взаимно обратные перестановки, то есть чтобы

M = SA(PA(M)),(33.37)

и

M = PA(SA(M)).(33.38)

было выполнено для любого сообщения М £ V.

Самое главное - чтобы никто, кроме Алисы, не мог вычислять функцию Sa() за разумное время; именно на этом основаны все полезные свойства криптосистемы, перечисленные выше. Потому-то Алиса и держит значение Sa в секрете: если кто-либо узнает её секретный ключ, он сможет расшифровывать адресованные ей сообщения, подделывать её подпись или перевирать сообщения, которые она отправляет от своего имени. Главная трудность при разработке криптосистем состоит в том, чтобы придумать функцию SaQ, Для которой трудно было бы найти быстрый способ вычисления, даже зная такой способ для обратной функции PaQ-

Опишем процесс пересылки шифрованного сообщения. Допустим, Боб желает послать Алисе секретное сообщение. Это происходит так:

•Боб находит Ра - открытый код Алисы (по справочнику или прямо от Алисы)

•Боб зашифровывает своё сообщение М и посылает Алисе шифровку (ciphertext) С = Ра(М).

•Алиса получает С и восстанавливает изначальное сообщение M = SA(C).

Этот процесс показан на рис. 33.5.

надписи:

encrypt - шифрование communication channel - линия связи eavesdropper - злоумышленник decrypt - расшифровка Боб, Алиса

Рис. 33.5 33.5 Шифрование с открытым ключом. Боб шифрует сообщение М с помощью функции Ра и получает шифровку С = Ра(М). Функции Sa() и Ра{) взаимно обратны, поэтому Алиса может восстановить исходное сообщение М по шифровке: М = Sa(C). Никто, кроме Алисы, не знает способа вычисления Sa (), поэтому сообщение М останется секретным, даже если злоумышленник подслушает С и знает Ра-

sign - вычисление подписи verify - проверка подписи accept - сообщение подлинное

Рис. 33.6 33.6 Цифровая подпись в системе с открытым ключом. Алиса подписывает своё сообщение М, прикладывая к нему цифровую подпись <т = Sa(M). Боб, получая от Алисы пару (М, <т), проверяет соотношение М = Ра(&)- Если оно выполняется, подпись и само сообщение подлинны.

Теперь объясним, как снабдить сообщение электронной подписью. Пусть Алиса хочет послать Бобу ответ М, подписанный электронной подписью (рис. 33.6).

•Алиса вычисляет электронную подпись (digital signature) а = Sa(M).

•Алиса посылает Бобу пару (М,а), состоящую из сообщения и подписи.

•Боб получает пару (М7, а) и убеждается в подлинности подписи, проверив равенство М = Ра(сг).

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

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

При таком сценарии содержимое подписанного сообщения не