Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
98
ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ
было быть послано от Алисы, то он применит к добавку /д (ключ Алисы открыт и ему известен) и получит Р. Так как никто, кроме Алисы, не может воспользоваться функцией /д1, обратной к /д, то он удостоверяется в том, что сообщение послано Алисой.
Хеш-функции. Обычно документы подписывают с помощью хеш-функции. Образно говоря, хеш-функция — это легко вычислимое отображение /: х ь-> h очень длинного входа х во много более короткий выход h (например, отрезок в 106 бит отображается в отрезок длиной 150 или 200 бит), обладающее следующим свойством: вычислительная сложность нахождения двух различных входов х их , для которых f(x) = f(x'), чрезвычайно велика. Если «подпись» Алисы содержит значение хеш-функции h = 1{х), гДе х — полный текст ее сообщения, то Боб может не только проверить, что сообщение действительно послано Алисой, но и убедиться, что оно не было изменено при передаче. А именно, Боб применяет хеш-функцию к дешифрованному открытому тексту и проверяет, совпадает ли результат с величиной h из подписи Алисы. По предположению, никто не в состоянии изменить х, не меняя h = f(x).
Обмен ключами. Существующие криптосистемы с открытым ключом работают медленнее, чем современные системы классического типа. Число элементов открытого текста, которые могут быть переданы за одну секунду, у них меньше. Однако, если группа пользователей предпочитает традиционный тип криптосистем, она может воспользоваться криптосистемой с открытым ключом как вспомогательным
СреДСТВОМ ДЛЯ раССЫЛКИ Друг Другу своих КЛЮЧеЙ К = (КEt КJj) для
классической системы. Таким образом, можно соблюдать основные правила классической криптосистемы и периодически проводить обмен ключами при помощи сравнительно медленной системы с открытым ключом, в то время как основной поток сообщений пересылается с использованием более быстрых прежних методов.
Вероятностное шифрование. Большинство криптосистем для передачи сообщений, основанных на теоретико-числовых идеях, является детерминированными в том смысле, что один и тот же открытый текст всегда шифруется в один и тот же шифртекст. Такое шифрование имеет два недостатка: (1) если злоумышленник знает, что имеется мало возможных вариантов для открытого текста (например, «да» или «нет»), то он может зашифровать все эти варианты и определить, который из них составляет сообщение, и (2) очень трудно доказать содержательное утверждение о надежности системы детерминированного шифрования. По этим причинам было введено
§ 1. СУТЬ КРИПТОГРАФИИ С ОТКРЫТЫМ ключом
99
понятие вероятностного шифрования. В этой книге мы не будем обсуждать этот вопрос подробнее или приводить примеры. Ознакомиться с ним можно по основопологающим работам Голдвассера и Микали (Proceedings of the 14th ACM Symposium on the Theory of Computing, 1982, c. 365-377, и J. Comput. System Sei., 1984, т. 28, с. 270-299).
УПРАЖНЕНИЯ
1. Пусть 771 пользователей хотят обеспечить возможность связи каждого с каждым с помощью классической криптосистемы. При этом каждый настаивает на том, чтобы его переписка с любым другим пользователем была недоступна для остальных та — 2 пользователей. Сколько для этого потребуется ключей К = (К?, Кд)? Сколько потребуется ключей, если в этой ситуации используется система с открытым ключом? Сколько требуется ключей для криптосистем каждого типа при m = 1000?
2. Пусть в сети, обслуживающей инвесторов и биржевых брокеров, используется криптосистема с открытым ключом. Инвесторы опасаются, что их брокеры будут покупать акции без согласования с ними (чтобы присвоить комиссионные), а если деньги инвестора будут потеряны, заявят, что они лишь выполняли их инструкции (предъявив в доказательство шифрованное распоряжение о покупке акций, полученное якобы от инвестора). Брокеры, со своей стороны, опасаются, что в случае, если они купят акции согласно инструкции клиента, а акции упадут в цене, инвестор может заявить, что никакой инструкции не посылал или что она послана посторонним или самим брокером. Объяснить, как можно решить эту проблему применением криптографии с открытым ключом, так что когда все они потянут друг друга в суд, можно будет доказать, кто именно виноват в неосторожном вложении денег и последующей их потере. (Предполагается, что в случае тяжбы между инвестором А и брокером В суду будут предъявлены вся относящаяся к делу информация о шифровании и дешифровании — ключи Ka = (Ke,a, Kd,а) и Kb = (Ке,В , Кd,b), а также программное обеспечение, необходимое для шифрования и дешифрования.)
3. Предположим, что две страны А и В пытаются достичь соглашения о запрещении подземных ядерных испытаний. Ни одна из сторон не доверяет другой, имея на это веские причины. Тем не менее, они вынуждены согласиться разместить в различных точках территории обеих стран системы контрольного оборудования. Каждый набор оборудования состоит из сложного сейсмографа, небольшого компьютера для обработки наблюдений сейсмографа и составления сообщений, а также радиопередатчика. Объяснить, как криптография с открытым ключом позволяет удовлетворить всем следующим условиям (которые, на первый взгляд, кажутся несовместимыми).
