Алгоритмы - построение и анализ (1021735), страница 202
Текст из файла (страница 202)
Составьте таблицу, в которой был бы показан порядок каждого элемента группы Е1 . Выберите наименьший первообразный корень д и вычислите таблицу значений 1пйы (ж) для всех х е Езп 31.6-2. Разработайте алгоритм модульного возведения в степень, в котором биты числа Ь проверяются не слева направо, а справа налево. 31.6-3. Считая величину ф (и) известной, объясните, как с помощью процедуры Мори~ли Ехгоннмт~лт!ом вычислить величину а 1 шос1 и для любого аЕ 2ы. 31.7 Криптосистема с открытым ключом КЯА Криптографическую систему с открытым ключом можно использовать для шифровки сообщений, которыми обмениваются два партнера, чтобы посторонний, перехвативший зашифрованное сообщение, не смог его расшифровать.
Кроме того, криптографическая система с открытым ключом позволяет партнерам Часть ЧП. Избранные темы 988 добавлять в конце электронных сообщений "цифровые подписи". Такая подпись представляет собой электронную версию подписи, поставленной от руки на бумажном документе. Любой без труда сможет ее проверить, но подделать не сможет никто. Кроме того, при изменении хотя бы одного бита в электронном сообщении оно теряет свою достоверность.
Таким образом, цифровая подпись не только позволяет идентифицировать автора сообщения, но и обеспечивает целостность его содержимого. Она является прекрасным инструментом для подписанных с помощью электронных средств деловых контрактов, электронных чеков, оформляемых в электронном виде заказов на поставку и других электронных документов, которые необходимо идентифицировать. Криптографическая система с открытым ключом КЯА основана на драматическом различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел. В разделе 3!.8 описана эффективная процедура поиска больших простых чисел, а в разделе 31.9 обсуждается проблема разложения больших целых чисел на множители. Криптографические системы с открытым ключом В криптографической системе с открытым ключом каждый участник располагает как открытым ключам (риЬ11с 1сеу), так и секретным ключам (зесге1 кеу).
Каждый ключ — это часть информации. Например, в криптографической системе КБА каждый ключ состоит из пары целых чисел. Пусть в процессе обмена сообщениями принимают участие "Алиса" и "Борис". Обозначим открытый и секретный ключи Алисы через Рд и Яд, а Бориса — через Рн и Ян. Каждый участник создает свой открытый и секретный ключ самостоятельно. Секретный ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Фактически, часто удобно предполагать, что открытый ключ каждого пользователя доступен в каталоге общего пользования, поэтому любой участник общения может легко получить открытый ключ любого другого участника.
Открытый и секретный ключи задают функции, применимые к любому сообщению. Обозначим через Х> множество допустимых сообщений. Например, ТЗ может быть множеством битовых последовательностей конечной длины. В простейшей первоначальной формулировке криптографии с открытым ключом требуется, чтобы открытый и секретный ключи задавали взаимно однозначную функцию, отображающую множество ь само на себя. Обозначим функцию, соответствующую открытому ключу Алисы Рд, через Рд (), а функцию, соответствующую ее секретному ключу Яд — через Яд ().
Таким образом, функции Рд () и Яд () являются перестановками множества ь. Предполагается, что существует эффек- Глава 31. Теоретико-числовые алгоритмы 989 тивный алгоритм вычисления функций Рд() и Яд() по заданным ключам Рд и Яд. Открытый и секретный ключи каждого участника обмена сообщениями образуют "согласованную пару" в том смысле, что они являются взаимно обратными.
Другими словами, для любого сообщения М Е ь выполняются соотношения М = Яд(Рд (М)), М = Рд (Яд (М)) . (31.33) (31.34) Произведя последовательное преобразование сообщения М с помощью ключей Рд и Яд (в любом порядке), снова получим сообщение М. В криптографической системе с открытым ключом существенное обстоятельство заключается в том, чтобы никто, кроме Алисы, не мог вычислить функцию Яд () за приемлемое с практичесюй точки зрения время. Секретность сообщений электронной почты, зашифрованных и отправленных Алисе, а также подлинность цифровых подписей Алисы основывается на предположении о том, что только Алиса способна вычислить функцию Яд ().
Это требование является причиной, по которой Алиса должна держать в секрете ключ Яд. Если бы она этого не делала, то ее ключ потерял бы секретность и криптографическая система не смогла бы предоставить Алисе упомянутые выше возможности. Предположение о том, что только Алиса может вычислить функцию Яд (), должно соблюдаться даже несмотря на то, что каждому известен ключ Рд и каждый может эффективно вычислить функцию Рд (), обратную к функции Яд (). Основная сложность, возникающая при разработке работоспособной криптографической системы с открытым ключом, заключается в создании системы, в которой можно легко найти преобразование Рд (), но невозможно (или очень сложно) вычислить соответствующее обратное преобразование Яд (). В криптографичесюй системе с открытым ключом юдирование производится так, как показано на рис. 31.1.
Предположим, Борис хочет отправить Алисе сообщение М, зашифрованное таким образом, чтобы для постороннего оно выглядело как бессмысленный набор символов. Сценарий отправки сообщения можно представить следующим образом. ° Борис получает открытый ключ Алисы Рд (из каталога общего пользования или каталога Алисы). ° Борис производит вычисления С = Рд (М), результатом которых является зашифрованный текст (с1рЬенех1), соответствующий сообщению М, и отправляет Алисе сообщение С. ° Получив зашифрованное сообщение С, Алиса применяет свой секретный ключ Яд, чтобы преобразовать его в исходное сообщение: М = Яд (С). Поскольку функции Яд () и Рд () являются обратными по отношению друг к другу, Алиса имеет возможность получить сообщение М, располагая сообщением С.
Часть Ч!!. Избранные темы ь ев~ чкз Хсвч1нвюильвкуи ха В.~ Лв.фромма г, 1 г = Рди~ г —— Лзрзхзм саобвс ых г Рис. 31.1. Процесс шифрования в схеме с сткрьпым ключом Поскольку только Алиса может вычислять функцию Ял (), она — единственная, кто способен расшифровать сообщение С. Шифрование сообщения М с помощью функции Рх () защищает его содержимое от всех, кроме Алисы. Реализовать цифровые подписи в сформулированной модели криптографической системы с открытым ключом так же просто.
(Заметим, что существуют другие подходы к проблеме создания цифровых подписей, которые здесь не рассматриваются.) Предположим, что Алисе нужно отправить Борису ответ М', подтвержденный цифровой подписью. Сценарий создания цифровой подписи проиллюстрирован на рис. 31.2. ° Алиса создает цифровую подпись (йа!1а! з!япаюге) и для сообщения М' с помощью своего цифрового ключа Ял и уравнения о = Ял (М').
° Алиса отправляет Борису пару (М', и), состоящую из сообщения и подписи. ° Получив пару (М', и), Борис с помощью открытого ключа Алисы может проверить, что автор сообщения М' — действительно Алиса. (Сообщение М' может содержать имя Алисы, чтобы Борис знал, чей открытый ключ использовать.) Для проверки используется уравнение М' = Рх (и). Если уравнение выполняется, можно смело делать вывод, что сообщение М' действительно подписано Алисой. В противном случае Борис с полным основанием сможет заподозрить, что сообщение М' или цифровая подпись о были искажены в процессе передачи, либо что пара (М', и) — попытка подлога. Поскольку цифровая подпись обеспечивает как аутентификацию автора сообщения, так и подтверждение целостности содержимого подписанного сообщения, она служит аналогом подписи, сделанной от руки в конце рукописного документа.
Важное свойство цифровой подписи заключается в том, что ее может проверить каждый, кто имеет доступ к открытому ключу ее автора. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение еще кому-то, кто тоже в состоянии проверить эту подпись. Например, Алиса может переслать Борису в сообщении электронный чек.
После того как Борис проверит подпись Алисы на чеке, он может передать Глава 31. Теоретико-числовые алгоритмы 991 Папы«« 1е= з <пз и; ОВ«г«« ; ~" РД, 1 М«а«пк Х и Ксх.«увк«ацкоаамв «в~аы Рнс. 31.2. Цифровые подписи в системе с открытым ключом Криптографическая система КЯА В криптографической системе с открытым ключом ЛБА (КБА рпЫ1с-кеу сгургозуз~еш) участники обмена сообщениями создают свои открытые и секретные ключи в соответствии с описанной ниже процедурой. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
