Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 152
Текст из файла (страница 152)
Можно показать также, что Р(С,) = М;, используя в каждом случае тот же самый алгоритм с ключом (п,4) = (2993,217). Сравнительно небольшая величина числа и в этом примере не позволяет полностью раскрыть возможности шифровальной функции Е, поскольку малое п можно легко разложить на множители. Кроме того, размер блока, как правило, выбирается большим, чем один символ, иначе мы бы имели шифр простой замены, который легко поддается криптоанализу. П ВБА-метод используют следующим образом.
Оба простых числа р и д, которые дают и = р9, а также целое число Н, взаимно простое с ф(п), сохраняются в тайне. Вместе с тем, целые числа и и е становятся общедоступными; известен также и общий метод. Поэтому всякий, знающий ключ шифрования (п, е), может зашифровать сообщение М, получив в результате зашифрованное сообщение С, прочесть которое может только тот, кто обладает ключом (п,Н). Каждый может иметь собственный набор ключей криптосистемы ВБА. Ключ общего пользования каждого человека, (п,е), может быть внесен в список, например, в регистр, как это сейчас сделано для телефонных номеров.
Если некая особа, например, Алиса, хочет послать Бобу тайное послание Мд, то Алисе необходимо найти его ключ общего пользования, (пн,ен) в общедоступном регистре. Затем Алисе нужно зашифровать сообщение Мд следующим образом: Ен(Мд) = [[Мл [[н — — Сл. Зашифрованное сообщение Сл следует передать Бобу любым удобным способом. Всякий, помимо Боба, перехвативший сообщение Сл, не сможет за приемлемое время восстановить сообщение Мд. Получив зашифрованное сообщение Сл, Боб сможет восстановить оригинал, воспользовавшись своим личным ключом (пн, Ыв) следующим образом: РАЗДЕЛ 22.3. Прилояение: криптография 847 Особенность ЙБА, отличающая этот метод от обычных криптосистем, заключается в том, что часть ключа является общеизвестной.
Такие методы назывеются криптосистемами с ключами общего пользования. Они были введены У. Диффи и М. Э. Хеллман в работе Фею Р~гес1»олз!и СгурГодгарйу [28]. Согласно теореме 22ЗБ Р(Е(1)) = 1 и Е(Р(1)) = 1, поэтому криптосистема йБА обладает очень полезной характерной особенностью, на которую указали Диффи и Хеллмэн. Ключ Боба общего пользования (пн, ен) доступен для каждого, поэтому каждый может послать ему собщение; поэтому, если Алиса посылает Бобу сообщение, то как он может быть уверен, что сообщение пришло от Алисы, а не от кого-то другого? Алиса может набрать подписанное сообщение Яд, содержащее ее имя и другую идентифицирующую информацию. Далее, Алиса использует собственный секретный дешифрирующий ключ (пд, ад) Рд(бд) = ~~Яд" 1] = Тд и включает Тд вместе или как часть основного зашифрованного текста Сд сообщения Мд.
Когда Боб получает сообщение Алисы, он выделяет Тд и применяет ключ шифрования общего пользования Алисы, (пд, ед), что дает Ед(Тд) = Ед(Рд(Бд)) = бд. Учитывая, что, по-видимому, только Алиса могла создать сообщение Тд, которое преобразуется в Яд при помощи ключа общего пользования Алисы (пд,ед), соответствующее сообщение Мд является подлинным. Инструмент установления подлинности для такого применения не должен зависеть от сообщения и подписывающего лица. Простой способ реализации такого определения подлинности сообщения Алисы для Боба, состоящего из блоков МыМю,.,,Мю мог бы состоять в том, что Алиса создаст подпись Я, состоящую из блоков Я,, Яз,..., Я», которая преобразуется в Т, = Рд($,) путем использования дешифрующего ключа Алисы.
Можно даже положить Я» = М„после чего Т, = Рд(М,). Комбинация суперблоков Т,М„ТзМю.,,,Т»М» шифруется ключом Боба общего пользования. Может возникнуть необходимость переписать целые числа Т»М„ТзМз,..., Т»М» в виде 1ы.?з,...,.1, где 0 <,7, < по, чтобы они удовлетворяли модулю Боба, пн. Таким образом, имеем У, = ЕнЯ). Получив последовательность Уы»Уз,..., У», Боб воспользуется своим секретным ключом и получит » РВ(К)1 что может быть разблокировано и снова даст Т,М,,ТзМю..., Т»М». Затем Боб сверит подпись с Ед(Т,) = М; в предположении, что было использовано Я, = М,. Поскольку Т,, преобразуемое в М, = Ед (Т»), могло быть создано только Алисой, сообщение является подлинным.
Безопасность криптосистемы йБА зависит от того, насколько сложно найти разложение на множители п = р д, получая посредством этого р и у. Поскольку 848 ГЛднд 22. Приложения теории чисел А= [[д ]] и передает А Бобу любым удобным способом. Со своей стороны, Боб вычисляет В = [[д')) и передает В любым способом Алисе. Алиса вычисляет к, = [[в']]„, Кз = [[АЬ)) и Боб вычисляет Но К1 = Кз, потому что [[АЬ)) [[(да)Ь)) [[(дЬ)а]) цВа]] Таким образом, Боб и Алиса имеют теперь один и тот же ключ, К = Кь = Кз. Поскольку В, А, р и д могут быть известны, криптоаналитик может взломать шифр, решая сравнение А = д (пюь( р) для а или решая В э— з дь (пюс) р) для Ь, т.е. нужно иметь возможность вычислить 1пдеА или 1пь)еВ по модулю р, что в каждом случае связано с большими вычислительными трудностями.
Сложность е общеизвестно, то Н можно определить, решая, при условии, что известны р и д, сравнение ех = 1 (пюд (р — 1)(д — 1)). Безопасность метода зависит также от сложности определения индексов. Если М известно, то С = [[М']]„можно вычислить, используя общедоступную информацию. Криптоаналитику потребуется решить сравнение М = С (пюд и), если с) = 1пс)сМ по модулю п, что также является непростым делом. Кроме того, р и д — случайным образом выбранные большие простые числа, что делает разложение на множители числа п трудно- выполнимым.
Более того, Ы выбирается случайным образом так, чтобы оно было взаимно простым с сЬ(п) и достаточно большим, чтобы сделать быстрый полный перебор при малых й неэффективным. Традиционные методы шифрования требуют, чтобы обе стороны, и только они, владели одинаковым ключом. Примером является 56-битовый ключ, используемый в стандарте кодировке данных РЕБ — Тйе ()п11ед алагез Рага Епсгур11оп 31апь(агд (см, работу Мейера и Матиаса Сгургоргарйу: А Аьеьв Р~телз1оп )п Сотри1ег Ра1а 5есигму [71]).
Для передачи сообщений большого объема использование РЕБ может быть предпочтительнее, чем использование метода ВЯА, т.к. РЕБ требует меньших вычислительных затрат. Вопрос состоит в том, как стороны могут сообщать ключ друг другу? Диффи и Хелмэн [28] предложили следующий метод обмена ключами. Предположим, что р — простое число и д — первообразный корень простого числа р. Числа р и д могут быть общеизвестны.
Предположим, что Алиса и Боб хотят пользоваться одним ключом. Алиса выбирает случайное целое число а такое, что 1 < а < р — 2, и Боб выбирает случайное целое число Ь такое, что 1 < Ь < р — 2. Числа а и Ь хранятся в секрете и известны только Алисе и Бобу, соответственно. Алиса вычисляет РАЗДЕЛ 22.3. Приложение: крипгпогрефия 849 этого вычисления, согласно обсуждениям, проведенным в разделе 3.14, имеет порядок /р, поэтому р должно быть большим простым числом, а р — 1 должно иметь в разложении хотя бы один большой простой множитель. Общие сведения о криптографии можно найти в работе Дэвида Кана Тйе Сог(ебгеа)геггп Тйе 51огу о('Бесге1 %гЛ1пу (54). Вопросы криптографии с ключами обшего пользования рассмотрены в работе М.
Э. Хеллмана Т)ге Ма1петаНсз о7' РибДс-Кеу Сгур1одгар)гу [43). ВБА-метод был запатентован Райвестом, Шамиром и Адлеманом в 1983 году; срок патента истек осенью 2000 года. ° УПРАЖНЕНИЯ 1. В примере 22.16 проверьте, что Р(7) = [[,У~'"~) зээз дешифрует сообшение 1683, 79, 2560, 872, 2571. 2.
Создайте ВБА-криптосистему, используя п = 83 107, путем нахождения ключа общего пользования (п, е) и личного ключа (м,Н). а) Используйте эти ключи, чтобы зашифровать сообщения "НЕТР". б) Пусть ВБА-ключи из примера 22.16 принадлежат Алисе, а ключи для и = 83 107 принадлежат Бобу. Используйте метод подписей, описанный в этом разделе, для пересылки Бобу подписанного сообщения "МО)т'ЕУ" от Алисы. в) Используя личный ключ Боба и ключ Алисы обшего пользования, дешифруйте сообшение из части (б) н проверьте, что оно пришло от Алисы. 3. Покажите, что в ВБА-криптосистеме с ключом общего пользования (п,е), если ф(п) может быть найдено, то криптосистема может быть взломана посредством вычисления й. 4. Рассмотрите ВБА-криптосистему, когда п = р у и ф(п) — известны, но простые числа р и д — неизвестны. а) Покажите, что р+ д можно выразить через п и ф(п).
а и, ю п, ~-р= Iи.:-и -4 . в) Определите р и д. г) Выполните пример 22.16 в предположении, что и = 2993 и ф(п) = 2880. Используйте метод, приведенный выше, для нахождения р и ц. Литературе 861 [!8] С. С. СЬапд ап6 3. С. 5Ь!еЬ, "А Гая1 А!дог!1Ьт 1ог Сопя!гас!!пд йес!ргоса! НаяЬ!пц Гипсйопя," Ргос, !и1егла1, Бутр. №ге 01гес11оия Сотри!. (1985), 232-236. [19) С. С. СЬапд апд 3, С. 5Ь!еЬ, "Ра!гчч!яе йе1аНче1у Рпгпе бепега1!пд Ро!упогп!а!я апг! ТЬе!г АррйсаПопя," Ргос. lлгеглаг. УЬгуяЬор Р1ясгеге А!дог11Ьтя Сотр!ехйу, ИочетЬег (1989), 137-139. [20) Ыап-х!ап СЬеп, "Мог(!Пег! МЗЬшя !пчегя!оп Гоппи!а апг! 11я Аррйса1!оп 1о РЬуя!ся," РЬуя.
йео. Ее!1., Чо!игпе 64, Ыо. 11 (1990), 1193-1195. [2Ц !.. %. СоЬеп апг( б. ЕЬгйсЛ, ТЬе 51гис1иге о[ йе )геа! 7ЧитЬег 5уя1ет, Чап Иояггапб йе!пЬо1с1, Иечг гогК 1963. [22] Н. СоЛп, Аг(оаисег1 А(итЬег ТЬеогу, Почет, Ыечч 'гогК 1980. [23) О. Соррегят!1Ь, "Сгур1одгарЬу," !ВМ У. йея. Оеое(ор., Чо!игпе 31, Ыо. 2 (1987), 244-248.
[24) й. Сгапг!аП, Л. 0оеп!ая, С. Ь!огг!е, апг! 3. Уоипд, "ТЬе Тчгеп1у-Зесопб Геггпа1 1ЯшпЬег !я Сотроя!1е," Май. Сотриг., Чо!игле 64 (1995), 863-868. [25] Т. Рап1к!д, ИитЬег; ТЬе Еаидиаде о[ Бс1елсе, 41Ь ед., Мастй!ап, Ыечч ЪогК 1954. [26] Н. Рачепрог1, ТЬе Н1цЬег АВ11Ьте11с, 61Ь ед., СатЬгЫде 1)п!чегя!1у Ргеяя, Ыечч Уог1с, 1992. ]27] 1.. Е. Ис(сяоп, 51иг(1ея 1л йе ТЬеогу о] ИитЬегя, СЬе!яеа, Ыечг Уог!с, 1957.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
