Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 221
Текст из файла (страница 221)
Таким образом, он получит исходное сообщение и цифровую подпись отправителя, которую затем сможет проверить с помощью соответствующего открытого ключа. Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою подпись, а затем положил его в бумажный конверт и запечатал, чтобы конверт был распечатан только тем человеком, которому адресовано сообщение.
100б Часть !76 Избранныемени Криптографическая система КБА В криптографической системе с открытым ключом АЯА (КБА рцЫ(с-хеу сгур[озуз1еш) участники обмена сообщениями создают свои открытые и секретные ключи в соответствии с описанной ниже процедурой. 1. Случайным образом выбираются два больших (скажем, длиной по 1024 бит) простых числа р и ь1, причем р ф ц. 2. Вычисляется и = рд.
3. Выбирается маленыюе нечетное целое число е, взаимно простое со значением функции ф(п) (которое согласно уравнению (31.20) равно (р — 1)(а — 1)). 4. Вычисляется число а', мультипликагнвное обратное к е по модулю ф(п). (Следствие 31.26 гарантирует, что такое число существует и единственное. Чтобы вычислить а по заданным е и ф(п), можно воспользоваться методом, описанным в разделе 31.4.) 5. Пара Р = (е, и) публикуется в качестве открытого ключа ЯЯА (КБА раас кеу). 6. Пара Я = (Н,п), играющая роль секретного ключа ЯЯА (КБА зесгег кеу), сохраняется в секрете. В этой схеме областью определения гз является множество Ж„. Чтобы преобразовать сообщение М с помощью открытого ключа Р = (е, и), вычисляем Р(М) = М' шод и .
(3!.37) Преобразование зашифрованного текста С с помощью секретного ключа Я = (Н, п) вычисляется как Я(С) = С тпог! и. (31.38) Эти уравнения применимы для создания как зашифрованных сообщений, так и цифровых подписей. Чтобы создать подпись, ее автор применяет свой секретный ключ не к зашифрованному, а к подписываемому сообщению. Для проверки подписи открытый ключ подписавшегося применяется именно к ней, а не к шифруемому сообщению. Операции с открытым и секретным ключами можно реализовать с помощью процедуры Мопс!,хк-ЕхРомечт!Атюм, описанной в разделе 31.6.
Чтобы проанализировать время выполнения этих операций, предположим, что открытый ключ (е, и) и секретный ключ (а, и) удовлетворяют соотношениям 18 е = 0(1), 18 а < )3 и 18п <,9. Тогда в процессе применения открытого ключа выполняется О(1) умножений по модулю и используется 0()3з) битовых операций. В ходе применения секретного ключа выполняется О(,9) умножений по модулю и используется 0(бз) битовых операций. Теорема 31.36 (Корректность ЯЯА) Уравнения КБА (31.37) и (31.38) определяют взаимно обратные преобразования множества Т.„, удовлетворяющие соотношениям (31.35) и (31.36).
Глава 3!. Теоретико-числовые алгоритмы 7007 Доказалвельселво. Из уравнений (31.37) и (31.38) для произвольного М е а.о получаем Р(5(М)) = 5(Р(М)) = М'~ (щоб п) . Поскольку е и е( взаимно обратные относительно умножения по модулю ф(п) (р- 1)И вЂ” 1)* ее( = 1 + Й(р — 1)(д — 1) для некоторого целого числа к. Но тогда, если М ~ 0 (щог1 р), мы имеем М"'= М(МР-')"«-П (шоб р) = М((М щог1 р)' ~)~(а 11 (шос1 р) М ( 1 ) ь ( Я г ) ( щ о Д р ) кл М (щог( р) . (теорема 31.31) Кроме того, М'л гн М (щи р), если М = 0 (щоб р). Таким образом, М' щ М (щог1 р) для всех М. Аналогично для всех М М' =М (шобд).
Таким образом, согласно следствию 31.29 из Китайской теоремы об остатках М' гл М (щог) и) для всех М. Безопасность криптографической системы КБА в значительной мере основана на сложностях, связанных с разложением больших целых чисел на множители.
Если бы кто-нибудь посторонний мог разложить на множители элемент открытого ключа п, то он смог бы использовать множители р и д точно так же, как это сделал создатель открытого ключа, и получить таким образом секретный ключ из открытого. Поэтому, если бы разложение больших целых чисел было простой задачей, так же легко было бы взломать криптографическую систему КЗА.
Обратное утверждение, которое состоит в том, что сложность взлома схемы КБА обусловлена сложностью разложения больших целых чисел на множители, не доказано. Однако на протяжении двадцатилетних исследований не удалось найти более простого способа взлома, чем тот, прн котором необходимо разложить на множители число и. В разделе 31.9 будет показано, что задача разложения больших целых чисел на множители оказалась на удивление сложной.
Путем случайного выбора и перемножения между собой двух 1024-битовых простых чисел можно создать открытый ключ, который не удается взломать за приемлемое время с помощью имеющихся в настоящее время технологий. Если в разработке теоретико-числовых алгоритмов не произойдет фундаментального прорыва и если реализовывать Ибб Часть с'й Избранные тены криптографическую схему ВБА, придерживаясь реюмендуемых стандартов, то эта схема способна обеспечить высокую степень безопасности в приложениях. Однаю для достижения безопасности в криптографической схеме ВБА желательно работать с достаточно большими целыми числами — длиной в сотни нлн даже более тысячи битов, — чтобы уберечься от возможных достижений в искусстве разложения чисел на множители. Во время написания этой книги (2009) в ВБА-модулях обычно использовались числа, длина которых находилась в пределах от 7б8 до 2048 бит.
Для создания модулей таких размеров необходимо иметь возможность эффективно находить большие простые числа. Этой задаче посвящен раздел 3!.8. Для повышения эффективности схема ВБА часто используется в "гибридном" режиме совместно с криптографическими системами, не обладающими открытым ключом. В такой системе ключи, предназначенные для зашифровки и расшифровки, идентичны. Если Алисе нужно в частном порядке отправить Борису длинное сообщение М, она выбирает случайный ключ К, предназначенный для быстрой криптографической системы без открытого ключа, и шифрует с его помощью сообщение М.
В результате получается зашифрованное сообщение С, длина юторого совпадает с длиной сообщения М. При этом ключ К довольно короткий. Затем Алиса шифрует ключ К с помощью открытого ВБА-ключа Бориса. Поскольку ключ К юроткий, величина Рн(К) вычисляется быстро (намного быстрее, чем величина Рн(М)). После этого Алиса пересылает пару (С, Рн(К)) Борису, который расшифровывает часть Рн(К), получая в результате ключ К, позволяющий расшифровать сообщение С. В результате этой процедуры Борис получит исходное сообщение М. Аналогичный гибридный подход часто используется для эффективной генерации цифровых подписей.
В этом подходе схема ВБА применяется совместно с открытой устойчивой к коллизиям хеиз-фуикиией 6 (сойзз|оп-геяз~ап1 База йшсбоп) — функцией, которую легко вычислить, но для которой нельзя вычислительными средствами найти пару сообщений М и М', удовлетворяющих условию 6(М) = 6(М'). Величина 6(М) представляет собой юроткий (скажем, 256- битовый) "отпечаток" сообщения М. Если Алиса решит подписать сообщение М, то она сначала применит функцию 6 к сообщению М, получив в результате отпечаток 6(М), который она затем зашифрует с помощью своего секретного ключа. После этого она отправит Борису пару (М, ЯА(6(М))) в качестве подписанной версии сообщения М.
Чтобы проверить подпись, Борис может вычислить величину 6(М) и убедиться, что она совпадает с величиной, полученной в результате применения ключа РА к полученной компоненте Яд(6(М)). Поскольку никто не может создать двух сообщений с одинаковыми отпечатками, невозможно вычислительными средствами изменить подписанное сообщение н в то же время сохранить достоверность подписи. Наконец заметим, что распространение открытых ключей значительно облегчается благодаря серзиификашаи (сепьбса1ез). Например, предположим, что существует "'авторитетный источник" Т„открытый ключ которого широко известен.
Алиса может получить от Т подписанное сообщение (свой сертификат), в котором утверждается, что "Рд — открытый ключ Алисы". Этот сертификат является Глиеа ЗЬ Теоретиии-чиглоеые алгоритмы "самоаугентифицируемым", поскольку ключ Рг известен всем. В свое подписанное сообщение Алиса может включить свой сертификат, чтобы получатель сразу имел в распоряжении ее открытый ключ и смог проверить ее подпись. Поскольку ключ Алисы подписан источником Т, получатель убеждается, что ключ Алисы действительно принадлежит ей. Упражнении 31.7.1 Рассмотрим набор значений р = 11, д = 29, и = 312 и е = 3, образующих ключи в системе )с3А. Какое значение д следует использовать в секретном ключе? Как выглядит результат шифровки сообщения М = 100? 31.7.2 Докажите, что если показатель степени е в открытом ключе Алисы равен 3 и если постороннему известен показатель степени г( секретного ключа Алисы, где 0 < е( < ф(п), то он может разложить на множители входящее в состав ключа число и в течение времени, которое выражается полиномиальной функцией от количества битов в числе и.
(Читателю может быть интересен тот факт (хотя в упражнении не требуется его доказать), что этот результат остается истинным даже без условия е = 3. Дополнительные сведения можно почерпнуть из работы Миллера (Мй!ег) [253).) 31.7.3 * Докажите, что схема КВА является мультипликативной в том смысле, что Рд(М~)Рд(Мз) = Рд(МгМз) (той п) . Докажите с помощью этого факта, что если злоумышленник располагает процедурой, способной эффективно расшифровать один процент зашифрованных с помощью ключа Рд сообщений из е.и, то он может воспользоваться вероятностным алгоритмом, чтобы с высокой степенью вероятности расшифровывать все сообщения, зашифрованные с помощью ключа Рд.
* 31.8. Проверка простоты В этом разделе рассматривается задача поиска больших простых чисел. Начнем с того, что обсудим платность распределения простых чисел, после чего перейдем к исследованию правдоподобного (но неполного) подхода к проверке простоты чисел. Затем будет представлен эффективный рандомизированный тест простоты, предложенный Миллером (Мй!ег) и Рабином (йаЬш).
!О!О Часть Гтд Избранные темы Плотность распределении простых чисел Во многих приложениях, таких, как криптография, возникает необходимость поиска больших "случайных" простых чисел. К счастью, большие простые числа не столь уж редки, поэтому для поиска простого числа путем проверки случайных целых чисел соответствующего размера потребуется не так уж много времени. Функция распределения простых чисач (рпше б!зптЬпйоп Йшсйоп) я(п) определяется как количество простых чисел, не превышающих числа и. Например, я(10) = 4, поскольку количество простых чисел, не превышающих 10, равно 4 (это числа 2, 3, 5 и 7).
В теореме о распределении простых чисел приводится полезное приближение функции я(п). Теорема 31.37 (Теорема о простых числах) !пп я(п) =1 -ь ь п/1пп Приближенная оценка п/1пп дает достаточно точную оценку функции я(п) даже при малых и. Например, при и = 100, когда я(п) = 50847534, а и/!пи = 48254942, отклонение не превышает 6%. (Для специалиста в области теории чисел 100 — число небольшое.) Процесс случайного выбора простого числа и и проверку его простоты можно рассматривать как испытания Бернулли (см. раздел В.4). Согласно теореме о простых числах вероятность того, что случайным образом выбранное число п окажется простым, приблизительно равна 1/1п и. Геометрическое распределение говорит нам о том, какое юличество попыток требуется сделать, чтобы добиться успеха.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
