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