Алгоритмы - построение и анализ (1021735), страница 203
Текст из файла (страница 203)
Случайным образом выбираются два больших (скажем, длиной 512 битов) простых числа р и 9, причем р ф д. 2. Вычисляется число и = рд. 3. Выбирается маленькое нечетное целое число е, взаимно простое со значением функции ф (и) (которое, согласно уравнению (31.19), равно (р — 1) х х (д — 1)). 4. Вычисляется число а, мультипликативное обратное по модулю ф(п) к е. (В соответствии со следствием 31.26, такое число существует и является его в свой банк, служащие которого также имеют возможность проверить подпись и осуществить соответствующую денежную операцию.
Заметим, что подписанное сообщение не зашифровано; оно пересылается в исходном виде и его содержимое не защищено. Путем совместного применения приведенных выше схем можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем — зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа, принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа. Таким образом он получит исходное сообщение и цифровую подпись отправителя, которую он затем сможет проверить с помощью соответствующего открытого ключа.
Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою подпись, а затем положил его в бумажный конверт н запечатал, с тем чтобы конверт был распечатан только тем человеком, кому адресовано сообщение. Часть Чй. Избранные темы 992 единственным.
Чтобы вычислить Н по заданным ф (и) и е, можно воспользоваться методом, описанным в разделе 31.4.) 5. Пара Р = (е, и) публикуется в качестве открытого ключа ЯЯА (КБА риЬ|с 1сеу). 6. Пара Я = (д, и), играющая роль секретного ключа й',эА (В5А зесгег 'кеу), сохраняется в секрете. В этой схеме в роли области Х> выступает множество Е„. Преобразование сообщения М, связанное с открытым ключом Р = (е, и), имеет вид Р(М) = М'(пюс1п), (31.35) а преобразование зашифрованного текста С, связанное с секретным ключом 5 = = (Н, и), выполняется как Я (С) = С" (пюс1 п) . (31.36) Эти уравнения можно использовать для создания как зашифрованных сообщений, так и цифровых подписей.
Чтобы создать подпись, ее автор применяет свой секретный ключ не к зашифрованному, а к подписываемому сообщению. Для проверки подписи открытый ключ подписавшегося применяется именно к подписи, а не для шифровки сообщения. Операции с открытым и секретным ключами можно реализовать с помощью процедуры Мооиьлк Ехгоыент1кйом, описанной в разделе 31.6. Чтобы проанализировать время выполнения этих операций, предположим, что открытый ключ (е, и) и секретный ключ (д, п) удовлетворяют соотношениям 1яе = О (1), 1яс( < ~3 и 1яп <,3. Тогда в процессе применения открытого ключа выполняется 0 (1) умножений по модулю и используется О (13э) битовых операций. В ходе применения секретного ключа выполняется 0 ()3) умножений по модулю и используется 0 (13з) битовых операций.
Теорема 31.36 (Корректность схемы КБА). Уравнения (31.35) и (31.36), на ко- торых основана схема КБА, определяют взаимно обратные преобразования мно- жества г.„, удовлетворяющие уравнениям (31.33) и (31.34). Поскольку числа е и Н являются взаимно обратные относительно умножения по модулю ф (и) = (р — 1) (д — 1), еН = 1 + lс (р — 1) (д — 1) Доказательство. Из уравнений (31.35) и (31.36) для любого М Е г.„получаем, что Р(Я(М)) = Я(Р(М)) = М'~(пюви). Глава 31. Теоретико-числовые алгоритмы 993 при некотором целом й.
Тогда, если М9сО (шос1р), можно записать М' =М(М' ) (шос1р)= = М (1) 1Я 1 (пюс1р) ва = М (пюс1р), спе второе тождество следует из теоремы 31.31. Если же М вв О (пюс1р), то М'а вэ =— М (шос1р). Таким образом, при всех М выполняется равенство М = М (пюс1р) . Аналогично можно показать, что для всех М Ме = М (тпос1д) . Таким образом, согласно следствию 31.29 из Китайской теоремы об остатках, для всех М выполняется равенство М'" = М (шос(гт) .
Безопасность криптографической системы КБА в значительной мере основана на сложностях, связанных с разложением больших целых чисел на множители. Если бы кто-нибудь посторонний мог разложить на множители элемент открьпого ключа и, то он смог бы использовать множители р и д точно так же, как это сделал создатель открытого ключа, и получить таким образом секретный ключ из открытого. Поэтому если бы разложение больших целых чисел было простой задачей, то так же легко было бы взломать криптографическую систему КЯА. Обратное утверждение, которое состоит в том, что сложность взлома схемы КЯА обусловлена сложностью разложения больших целых чисел на множители, не доказано.
Однако на протяжении двадцатилетних исследований не удалось найти более простой способ взлома, чем тот, при котором необходимо разложить на множители число и. В разделе 31.9 будет показано, что задача разложения больших целых чисел на множители оказалась на удивление сложной. Путем случайного выбора и перемножения друг на друга двух 512-битовых простых чисел можно создать открытый ключ, который не удается "разбить" за приемлемое время с помощью имеющихся в наличии технологий.
Если в разработке теоретикочисловых алгоритмов не произойдет фундаментального прорыва, и если реализовывать криптографическую схему КЗА, придерживаясь сформулированных ниже рекомендаций, то эта схема способна обеспечить высокую степень надежности. Однако для достижения безопасности в криптографической схеме КБА желательно работать с целыми числами, длина которых достигает нескольких сотен битов.
Это позволит уберечься от возможных достижений в искусстве разложения 994 Часть ЧП. Избранные темы чисел на множители. Во время написания этой книги (2001 год) в ВБА-модулях обычно использовались числа, длина которых находилась в пределах от 768 до 2048 битов. Для создания таких модулей необходимо иметь возможность эффективно находить большие простые числа. Этой задаче посвящен раздел 31.8. Для повышения эффективности схема КБА часто используется в "гибридном", или "управляемом ключом" режиме совместно с криптографическими системами, не обладающими открытым ключом. В такой системе ключи, предназначенные для зашифровки и расшифровки, идентичны.
Если Алисе нужно в приватном порядке отправить Борису длинное сообщение М, она выбирает случайный ключ К, предназначенный для производительной криптографической системы без открытого ключа, и шифрует с его помощью сообщение М. В результате получается зашифрованное сообщение С, длина которого совпадает с длиной сообщения М. При этом ключ К довольно короткий. Затем Алиса шифрует ключ К с помощью открытого КБА-ключа Бориса. Поскольку ключ К короткий, величина Рн(К) вычисляется быстро (намного быстрее, чем величина Рн (М)). После этого Алиса пересылает пару (С, Рн (К)) Борису, который расшифровывает часть Рн (К), получая в результате ключ К, позволяющий расшифровать сообщение С. В результате этой процедуры Борис получит исходное сообщение М.
Аналогичный гибридный подход часто используется для эффективной генерации цифровых подписей. В этом подходе схема КБА применяется совместно с открытой устойчивой к калнизинм хэшфункцией Ь (со1йяоп-геязгапс ЬазЬ йшсйоп Ь) — функцией, которую легко вычислить, но для которой нельзя вычислительными средствами найти пару сообщений М и М', удовлетворяющих условию Ь (М) = Ь (М'). Величина Ь (М) представляет собой короткий (скажем, 160-битовый) "отпечаток'* сообщения М. Если Алиса захочет подписать сообщение М, то она сначала применяет функцию Ь к сообщению М, получив в результате отпечаток Ь (М), который она затем шифрует с помощью своего секретного ключа.
После этого она отправляет Борису пару (М, ЯА (Ь(М))) в качестве подписанной версии сообщения М. Чтобы проверить подпись, Борис может вычислить величину Ь (М) и убедиться, что она совпадает с величиной, полученной в результате применения ключа Ря к полученной компоненте ЯА (Ь(М)). Поскольку никто не может создать двух сообщений с одинаковыми отпечатками, невозможно вычислительными средствами изменить подписанное сообщение и в то же время сохранить достоверность подписи. Наконец, заметим, что распространение открытых ключей значительно облегчается благодаря сертификатам (сегг(бса1ез). Например, предположим, что существует "авторитетный источник" Т, чей открытый ключ широко известен.
Алиса может получить от Т подписанное сообщение (свой сертификат), в котором утверждается, что РА — открытый ключ Алисы. Этот сертификат является "самоаутентифицируемым", поскольку ключ Рг известен всем. В свое подписанное сообшение Алиса может включить свой сертификат, чтобы получатель сразу Глава 31.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
