Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 220
Текст из файла (страница 220)
Избранные тены Упражнении 31.б.1 Составьте таблицу, в которой был бы показан порядок каждого элемента группы Ж;,. Выберите наименьший первообразный корень д и вычислите таблицу значений 1пс)ы д(я) для всех х е Еы. 31.б.2 Разработайте алгоритм модульного возведения в степень, в котором биты числа 6 проверяются не слева направо, а справа налево. 31.6.3 Считая величину ф(п) известной, объясните, как с помощью процедуры Мопцьлк-Ехгомлытитюы вычислить величину а ' шос) п для любого а е Е„'. 31.7. Криптосистема с открытым ключом КВА Криптографическую систему с открытым ключом можно использовать для шифровки сообщений, которыми обмениваются два партнера, чтобы посторонний, перехвативший зашифрованное сообщение, не смог его расшифровать. Кроме того, криптографическая система с открытым ключом позволяет партнерам добавлять в конце электронных сообщений цифровые подписи.
Такая подпись представляет собой электронную версию подписи, поставленной от руки на бумажном документе. Кто угодно без труда может ее проверить, но подделать не сможет никто, Кроме того, при изменении хотя бы одного бита в электронном сообщении оно теряет свою достоверность. Таким образом, цифровая подпись позволяет не только идентифицировать автора сообщения, но и обеспечить целостность его содержимого. Она является прекрасным инструментом для подписанных с помощью электронных средств деловых контрактов, электронных чеков, оформляемых в электронном виде заказов на поставку и других электронных документов, которые необходимо идентифицировать.
Криптографическая система с открытым ключом КБА основана на драматическом различии в том, насколько легко находить большие простые числа н насколько сложно раскладывать на множители произведение двух больших простых чисел. В разделе 31.8 описана эффективная процедура поиска больших простых чисел, а в разделе 31.9 обсуждается проблема разложения больших целых чисел на множители.
Криптографические системы с открытым ключом В криптографической системе с открытым ключом каждый участник располагает как открытым ключам (рпЫ)с 1сеу), так и секретным ключом (зесгез 1сеу). Каждый ключ — это часть информации. Например, в криптографической системе КБА каждый ключ состоит из пары целых чисел. Пусть в процессе обмена сооб- Глава ЗХ Теоретико-числовые алгоритма ТООл М = БА(РА(М)), М = Рд(Бд(М)) . (31.35) (31,36) Произведя последовательное преобразование сообщения М с помощью ключей РА и Яд (в любом порядке), мы снова получим сообщение М.
В криптографической системе с открытым ключом существенное обстоятельство заключается в том, чтобы никто, кроме Алисы, не мог вычислить функцию Яд О за приемлемое с практической точки зрения время. Секретность сообщений электронной почты, зашифрованных и отправленных Алисе, а также подлинность цифровых подписей Алисы основываются на предположении о том, что только Алиса способна вычислить функцию ЯА(). Это требование является причиной, по которой Алиса должна держать в секрете ключ Ях. Если бы она этого не делала, то ее ключ потерял бы секретность н криптографическая система не смогла бы предоставить Алисе упомянутые выше возможности.
Предположение о том, что только Алиса может вычислить функцию ЯА(), должно соблюдаться даже несмотря на то, что каждому известен ключ Ра и каждый может эффективно вычислить функцию Рд(), обратную функции ЯлО. Основная сложность, возникающая при разработке работоспособной криптографической системы с открытым ключом, заключается в создании системы, в которой можно легко найти преобразование РА(), но невозможно (или очень сложно) вычислить соответствующее обратное преобразование ЯАО.
Это условие выглядит угрожающе, но мы увидим, как добиться его выполнения. щенками принимают участие Алиса и Борис. Обозначим открытый и секретный ключи Алисы через Рх и ЯА, а Бориса — через Рн и Яв. Каждый участник создает свой открытый и секретный ключ самостоятельно. Секретный ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно и даже публиковать. Фактически часто удобно предполагать, что открытый ключ каждого пользователя доступен в каталоге общего пользования, поэтому любой участник общения может легко получить открытый ключ любого другого участника.
Открытый и секретный ключи определяют функции, применимые к любому сообщению. Обозначим через Р множество допустимых сообщений. Например, 'П может быть множеством всех битовых последовательностей конечной длины. В простейшей первоначальной формулировке криптографии с открытым ключом требуется, чтобы открытый и секретный ключи задавали взаимно однозначную функцию, отображающую множество П само на себя.
Обозначим функцию, соответствующую открытому ключу Алисы РА, как Рл(), а функцию, соответствующую ее секретному ключу Ях, — как ЯА(). Таким образом, функции РА() и Яд() являются перестановками множества Э. Предполагается, что существует эффективный алгоритм вычисления функций РА() и ЯдО по заданным ключам Рл и Яд. Открытый и секретный ключи каждого участника обмена сообщениями образуют "согласованную пару" в том смысле, что они являются взаимно обратными.
Другими словами, для любого сообщения М е Э выполняются соотношения Часть рц. Избранные тсмм 1004 Борис Шифрование Алиса Расшифровка Коммуникационный канал Рнс. ЗК5. Шифрование в системе с открытым ключом. Борце шнфруег сообщение М с помщ щью открытого ключа Алисы Ра н передает полученное зашифрованное сообщение С = Ра(М) по коммуникационному каналу Алисе. Если кто-то перехватит зто сообщение, не получат никакой информации о сообщении М. Алиса получает С н расшнфровыыет его с помощью своего секретного ключа, получив исходное сообщение М = Ял(С).
В криптографической системе с открытым ключом кодирование проводится так, как показано на рис. 31.5. Предположим, Борис хочет отправить Алисе сообщение М, зашифрованное таким образом, чтобы для постороннего оно выглядело как бессмысленный набор символов. Сценарий отправки сообщения можно представить следующим образом. Борис получает открытый ключ Алисы РА (из каталога общего пользования или непосредственно от Алисы). Борис выполняет вычисления С = РА(М), результатом которых является за- шифрованный шексш (с)рЬезтех1), соответствующий сообщению М, и отправ- ляет Алисе сообщение С.
Алиса вычисляет свою цифровую подпись (с))я)га! 5)япаппе) с для сообщения М' с помощью своего секретного ключа ЯА и уравнения сг = ЯА(М'). Алиса отправляет пару "сообщение/подпись" (М',сг) Борису. Получив пару (М',о), Борис может убедиться, что автор сообщения М'— действительно Алиса, использовав открытый ключ Алисы для проверки ра- венства М' = РА(гг). (Сообщение М' может содержать имя Алисы, чтобы ° Получив зашифрованное сообщение С, Алиса применяет свой секретный ключ ЯА, чтобы преобразовать его в исходное сообщение: ЯА(С) оА(~ А(М)) Поскольку функции ЯА() и РА() являются обратными по отношению одна к другой, Алиса имеет возможность вычислить сообщение М, располагая сообщением С.
Поскольку только Алиса может вычислять функцию ЯА(), она — единственная, кто способен расшифровать сообщение С. Шифрование сообщения М с помощью функции РА () защищает его содержимое от всех, кроме Алисы. Реализовать цифровые подписи в сформулированной модели криптографической системы с открытым ключом столь же просто. (Заметим, что существуют и другие подходы к проблеме создания цифровых подписей, которые здесь не рассматриваются.) Предположим, что Алисе нужно отправить Борису ответ М', подтвержденный цифровой подписью.
Сценарий создания цифровой подписи проиллюстрирован на рис. 31.б. Глава зй Теоретико-кисловые алгаритмм Алиса Подпись Борис Провсрка Принятие Коммуникационный канал Рис. 3!.б. Цифровые подписи в системе с открытым ключом. Алиса подписывает сообщсннс М', добавляя к нему цифровую подпись о = Бя (М'). Она передает пару "сообщснис/подпись" (М', о) Борису, который проверяет соабщснис, выясняя, выполнястся ли условие М' = Рл(а).
Если условна выполнено, он приннмаст (М', о) как сообщение, подписанное Алисой. Борис знал, чей открытый ключ использовать.) Если равенство выполняется, можно смело делать вывод, что сообщение М' действительно подписано Алисой. В противном случае Борис с полным основанием сможет заподозрить, что либо сообщение М' или цифровая подпись сг были искажены в процессе передачи, либо что пара (М', ж) — попытка подлога.
Поскольку цифровая подпись обеспечивает как аутентификацию автора сообщения, так и подтверждение целостности содержимого подписанного сообщения, она служит аналогом подписи, сделанной от руки в конце рукописного документа. Важное свойство цифровой подписи заключается в том, что каждый, кто имеет доступ к открытому ключу ее автора, должен иметь возможность ее проверить. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение еше кому-то, кто тоже в состоянии проверить эту подпись. Например, Алиса может переслать Борису в сообщении электронный чек.
После того как Борис проверит подпись Алисы на чеке, он может передать его в свой банк, служщцие которого также имеют возможность проверить подпись и осуществить соответствующую денежную операцию. Заметим, что подписанное сообщение не зашифровано; оно пересылается в исходном виде и его содержимое не защищено. Совместно применив приведенные выше схемы, можно создавать сообщения, которые будут и зашифрованными, и содержащими цифровую подпись. Для этого автор должен сначала добавить к сообщению свою цифровую подпись, а затем зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открьпого ключа, принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
