Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 203
Текст из файла (страница 203)
Поскольку числа е и Н являются взаимно обратные относительно умножения по модулю ф (и) = (р — 1) (д — 1), еЫ = 1 + lс (р — 1) (д — 1) Глава 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. Теоретико-числовые алгоритмы 995 имел в распоряжении ее открытый ключ и смог проверить ее подпись. Поскольку ключ Алисы подписан источником Т, получатель убеждается, что ключ Алисы действительно принадлежит ей. Упражнения 31.7-1.
Рассмотрим набор значений р = 11, д = 29, п = 312 и е = 3, образующих ключи в системе КБА. Какое значение Н следует использовать в секретном ключе? Как выглядит результат шифровки сообщения М = = 100? 31.7-2. Докажите, что если показатель степени е в открытом ключе Алисы равен 3, и если постороннему известен показатель степени Н секретного ключа Алисы, где 0 < д < ф (и), то он может разложить на множители входящее в состав ключа число и в течение времени, которое выражается полиномиальной функцией от количества битов в числе и. (Читателю может быть интересен тот факт (хотя в упражнении не требуется его доказать), что этот результат остается истинным даже без условия е = 3. Дополнительные сведения можно почерпнуть из статьи Миллера (Мй1ег) [221].) *31.7-3. Докажите, что схема КБА является мультипликативной в том смысле, что Рд (М1) Рд (Мз) ив ь Рд (М1 Мг) (шодп) .
Докажите с помощью этого факта, что если злоумышленник располагает процедурой, способной эффективно расшифровать 1 процент зашифрованных с помощью ключа Рд сообщений из Е„, то он может воспользоваться вероятностным алгоритмом, чтобы с высокой степенью вероятности расшифровывать все сообщения, зашифрованные с помощью ключа Рд. * 31.8 Проверка простоты В этом разделе рассматривается задача поиска больших простых чисел. Начнем с того, что обсудим плотность распределения простых чисел на числовой оси, после чего перейдем к исследованию правдоподобного (но неполного) подхода к проверке простоты чисел. Затем будет представлен эффективный рандомизированный тест простоты, предложенный Миллером (М(Нег) и Рабином (КИЬ1п).
Часть ЧП. Избранные темы Плотность распределения простых чисел Во многих приложениях (например, в криптографии) возникает необходимость поиска больших "случайных" простых чисел. К счастью, большие простые числа встречаются достаточно часто, поэтому для поиска простого числа путем проверки случайных целых чисел соответствующего размера потребуется не так уж много времени. Функции распределения простых чисел (ргппе йз1г1Ьаюп Йпсбоп) я(п) определяется как количество простых чисел, не превышающих числа и.
Например, я (10) = 4, поскольку количество простых чисел, не превышающих 10, равно 4 (зто числа 2, 3, 5 и 7). В теореме о распределении простых чисел приводится полезное приближение функции я (и). Теорема 31.37 (Теорема о простых числах). 11гп = 1. к (п) о п/1пп Приближенная оценка и/1пп дает достаточно точную оценку функции я (и) даже при малых и. Например, при п = 10в, когда я (и) = 50847534, а и/1п и = - 48254942, отклонение не превышает 6%. (Для специалиста в области теории чисел 10з — число небольшое.) С помощью теоремы о простых числах вероятность того, что случайным образом выбранное число и окажется простым, можно оценить как 1/1пп. Таким образом, чтобы найти простое число, длина которого совпадает с длиной числа и, понадобится проверить приблизительно 1пп целых чисел, выбрав их случайным образом в окрестности числа и.
Например, чтобы найти 512-битовое простое число, понадобится перебрать приблизительно 1п 2ыз = 355 случайным образом выбранных 512-битовых чисел, проверяя их простоту. (Ограничившись только нечетными числами, это количество можно уменьшить в два раза.) В оставшейся части этого раздела рассматривается задача по определению того, является ли простым большое целое число и. Для удобства обозначений предположим, что разложение числа п на простые множители имеет вид (31.37) где т > 1, ры рз,...,р„— простые множители числа и, а ем ез,..., е„— положительные целые числа. Конечно же, число п является простым тогда и только тогда, когда т = 1 и е1 = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
