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

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

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

М = (M^e)^d mod n = М^ed mod n = M^de mod n = (M^e)^d mod n = M.

Это обстоятельство позволяет применять различные приемы, известные как цифровая (или электронная) подпись.

Рассмотрим следующую схему взаимодействия корреспондентов X и Y. Отправитель X кодирует сообщение S своим закрытым ключом (С: = M^d mod n) и посылает получателю Y пару <S, С>, то есть подписанное сообщение. Получатель Y, получив такое сообщение, кодирует подпись сообщения открытым ключом X, то есть вычисляет S': = C^e mod п. Если оказывается, что S = S", то это означает, что (нешифрованное!) сообщение S действительно было отправлено корреспондентом X. Если же S  S', то сообщение было искажено при передаче или фальсифицировано.

В подобного рода схемах возможны различные проблемы, которые носят уже не математический, а социальный характер. Например, допустим, что злоумышленник Z имеет техническую возможность контролировать всю входящую корреспонденцию Y незаметно для последнего. Тогда, перехватив сообщение X, в котором сообщался открытый ключ е, злоумышленник Z может подменить открытый ключ X своим собственным открытым ключом. После этого злоумышленник сможет фальсифицировать все сообщения X подписывая их своей цифровой подписью, и, таким образом, действовать от имени X. Другими словами, цифровая подпись удостоверяет, что сообщение S пришло из того же источника, из которого был получен открытый ключ е, но не более того.

Можно подписывать и шифрованные сообщения. Для этого отправитель X сначала кодирует своим закрытым ключом сообщение 5, получая цифровую подпись С, а затем кодирует полученную пару <S, С> открытым ключом получателя У. Получив такое сообщение, У сначала расшифровывает его своим закрытым ключом, а потом убеждается в подлинности полученного сообщения, сравнив его с результатом применения открытого ключа X к подписи С.

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

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

Упражнения

1. Является ли схема алфавитного кодирования

<а 0, b 10, c  011, d  1011, е  1111>

префиксной? разделимой?

6.2. Построить оптимальное префиксное алфавитное кодирование для алфавита {а, b, с, d} со следующим распределением вероятностей появления букв:

р_а = 1/2, p_b = 1/4, p_с = 1/8, p_d = 1/8.

6.3. Показать, что для несимметричных ошибок функция

является расстоянием.

6.4. Проследить работу алгоритма сжатия Лемпела—Зива на примере следующего исходного текста: abaabaaab.

6.5. Пусть в системе программирования имеется процедура Randomize, которая получает целочисленный параметр и инициализирует датчик псевдослучайных чисел, и функция без параметров Rnd, которая выдает следующее псевдослучайное число в интервале [0,1]. Составить алгоритмы шифровки и расшифровки с закрытым ключом.