AOP_Tom2 (1021737), страница 123
Текст из файла (страница 123)
Важным является тот факт, что нпкшо не знает простых чисел р и 4, даже то лицо (или организация), которому принадлежит устройство или которое имеет доступ к нему. Не может быть и речи о подкупе, шантаже или захвате заложников с целью получения информации о простых числах числа Х. Чтобы отослать секретное сообщение владельцу ВБА-блока, для которого произведение двух чисел равно Х, нужно преобразовать сообщение в последовательность чисел (хы...,хь), в которой каждое из чисел х, принимает значения в интервале между 0 и Х, а затем передать числа (х~шобй ...
хзшодЖ). ВБА-блок, зная р и 4, может декодировать сообщение, поскольку в нем уже имеется вычисленное заранее число с( < М, такое, что 34— : 1 [по модулю (р — 1)(4 — 1)). Теперь ВБА-блок может, используя рассмотренный в разделе 4.6.3 метод, за приемлемое время вычислить (хз)зшобй = х. Естественно, ВБА-блок хранит это магическое число И внутри себя; фактически можно было бы запоминать в Н5А- блоке только число д вместо чисел р и д, поскольку в обязанности блока после вычисления числа Х входит только защита своих секретов и вычисление кубических корней па модулю Х. Подобная схема кодирования не дает эффекта, если х с КЖ, так как хэ щи А' = хз, а кубический корень легко можно найти.
Из описанного в разделе 4.2.4 логарифмического закона ведущих разрядов следует, что старшая позиция х~ й-размерного сообщения (хм...,хь) будет меньше м7т' примерно в — случаев, поэтому зг— 1 данная проблема требует своего решения. В упр. 32 рассмотрен один из способов, позволяющих избежать этих сложностей. Надежность схемы кодирования при помощи Н8А базируется на том факте, что никто не может узнать, как вычислять кубический корень по модулю № не зная множителей числа № Похоже, что не существует методов, позволяющих это сделать, однако абсолютной уверенности нет. Все, что можно сказать по данному поводу,— это то, что обычные методы обнаружения кубических корней задачу не решают.
Например, бесполезно пытаться вычислять число о как функцию числа Х; причина в том, что если известно д или фактически если известно любое число го разумной длины, такое, что равенство х'" шод Х = 1 справедливо для значительного количества величин х, то потребуется намного больше шагов для поиска множителей числа А' (упр. 34). Таким образом, любой из методов, основанных на явной или скрытой попытке нахождения такого числа гп, не может оказаться лучше, чем метод разложения на простые множители. Тем не менее нужно соблюдать осторожность. Если адно и то же сообщение по компьютерной сети отослано трем лицам, то некто, кому известно х по модулю №, з № и оз, может восстановить хз шод №№№ = хз, используя китайскую теорему об остатках, после чего число х уже не будет секретом.
Фактически даже в случае, когда одно и то же сообщение отослано семерым разным лицам с отметками времени (29ЯП)я+Г;) шод Х<, в которых времена 1; известны или могут быть с достаточной достоверностью предугаданы, значение величины я может быть найдено (упр. 44). В связи с этим некоторые криптографы рекомендуют кодировать информацию с использованием числа 2'е + 1 = б5 537 вместо 3. Данный показатель степени является пробтым, поэтому на вычисление числа хеээз~ шод У затрачивается примерно в 8.5 раз больше времени, чем на вычисление числа яэ шод Х. [СС1ТТ Весопипепдайопэ В!ие Воо)с (Сепета: 1псегпайюпа1 Те)есопнпншсаС!оп Пп)оп, 1989), Раас)с1е 1ПП.8, НесопппепбаПоп Х.509, Аппех С, 74-78.) В оригинальном описании методики шифрования Р.
Л. Ривест, А. Шамир и Л. Эдлеман предлагали кодировать число х числом х~ шоб № где а — любой простой показатель функции р(Х), а не только а = 3. Тем не менее на практике предпочтение отдается показателю, для которого кодирование выполняется быстрее, чем декодирование. Чтобы схема, реализуемая в Н8А, была эффективной, числа р и д не должны оказаться "случайно" близкими простыми. Как подчеркивалось выше, чтобы обеспечить существование единственных кубических корней по модулю Х, числа р — 1 и д -1 не должны делиться на 3. Другое условие сводится к тому, что для числа р-1 должен существовать по крайней мере один очень большой простой множитель. То же самое относится и к числу д — 1; в противном случае число Х может быть рвз- ложено на простые множители по алгоритму из упр. 19.
Фактически этот алгоритм сводится к поиску малого числа т, характеризуемого тем, что х"' шо»1 Х быстро становится равным 1, а мы уже знаем, что использовать такое число небезопасно. Если для чисел р — 1 и»7 — 1 существуют болыпие простые множители р, и»1», то согласно теории, изложенной в упр. 34, число ш будет либо кратным р»д» (тогда его будет трудно найти), либо вероятность того, что х"' = 1, будет меньше, чем 1(р»»7» (поскольку число х шо»1»»» почти никогда не равно 1). К тому же нежелательно, чтобы числа р и д были близки одно к другому; иначе их можно будет довольно просто найти, используя алгоритм П.
Нежелательно также, чтобы отношение этих чисел р/д было близко к простой дроби, в противном случае эти числа можно будет получить, используя обобщение Лемана из алгоритма С. Предлагаемая процедура генерирования чисел р и 9 почти всегда выполняется безошибочно. Начинаем с правдоподобного случайного числа ре, принадлежащего интервалу, скажем, между 10аэ и 10э». Находим первое простое число р», большее, чем рэ, 'для этого потребуется проверить» )про — 90 нечетных чисел.
Будет вполне достаточно, если после 50 пробных делений, выполняемых алгоритмом Р, число р» окажется "вероятно, простым" с вероятностью > 1 — 2 '~~. После этого выбираем другое правдоподобное случайное число р» между, скажем, 10'э и 10»е. Находим первое простое чишю р вида йр» + 1, где й > рм й — -четное и Й = р» (по модулю 3). Для этого, прежде чем простое число р будет найдено, потребуется проверить -'!и р»рэ и» 90 чисел. Простое число р будет длиной около 120 разрядов; подобная конструкция может быть применена и для поиска простого числа в длиной около 130 ршзрядов.
Чтобы обеспечить супернадежность, желательно убедиться в том, что числа р+1 и 4+1 не содержат малых простых множителей (упр. 20). Теперь произведение А» = рд, величина которого имеет порядок 10~~~, удовлетворяет всем требованиям, и в настоящее время такое число не может быть разложено на простые множители. Например, предположим, что известен метод разложения 250-разрядного числа А», время выполнения которого имеет порядок А»э» мс. Следовательно, для разложения такого числа на простые множители потребуется 10ы мс, но в году имеется только 31556952000000 мкс, так что для завершения процесса разложения потребуется более 3х10" лет мвп»инного времени. Если предположить, что закуплено 10 млрд компьютеров и все они задействованы в решении этой проблемы, пройдет более 31 года, прежде чел» адин из них разложит число А' на простые множители. Но пока правительство будет закупать так много специализированных компьютеров, люди начнут применять 300-разрядные числа А». Поскольку метод кодирования х»-» хз шоб А» известен, он обладает еще и дополнительными достоинствами, помимо того факта, что расшифровать код можно только при помощи ВВА-блока.
Такие системы "общедоступных ключей" были впервые рассмотрены В. Диффи (»1'. П!йе) и М. Э. Хелль»аном (34. Е. НеИ»пап) в журнале 1ЕЕЕ 71ипв. 1Т-22 (1976), 644 — 654. Как пример того, что можно сделать, когда метод кодирования широко известен, предположим, что Алиса желает связаться с Бобом по электронной почте и при этом они оба хотят, чтобы их письма были подписана» так, чтобы получатели были уверены, что никто не подделывает сообщение. Пусть Ея(М) — кодирующая функция для сообщений М, направляемых Алисе, а Ря(М) — декодирующая функция ВВА-блока, установленного у Алисы. Пусть так- же Ее(М), Рн(М)- — соответственно кодирующая и декодирующая функции 113А- блока, принадлежащего Бобу.
Тогда Алиса может отослать подписанное сск~бщение, поставив свою подпись и дату, а затем переслать Бобу сообщение Еп(Рл(ЛХ)), использовав для вычисления Рл(ЛХ) свой компьютер. Когда сообщение получает Боб, его ВБА-блок преобразует это сообщение в сообщение Рл(ЛХ); Бобу известно Ел, так что он может вычислить М = Ел (Рл(М)). Это должно убедить его, что сообщение поступило именно от Алисы: никто другой не мог отослать сообщение с кодом Рд (М).
(Ну хорошо, теперь Бобу известен и код Рд (М), поэтому он, посылая сообщение Ех(Рл(ЛТ)) Ксавьеру, может представлять Алису. Чтобы защититься от таких попыток подделки, в содержимом кода Л1 должно быть четко указано, что оно предназначено только для Боба.) Естественно задать вопрос, каким образом Алиса и Боб узнают кодируюпьче функции Ел и Ен друг друга? Простого хранения этих функций в общедоступном файле явно недостаточно, поскольку некто Чарли может проникнуть в этот файл, подставив вычисленный им код Ж. Затем Чарли получит возможность тайно перехватывать и декодировать чужие сообщения до того, как Алиса или Боб чтонибудь заподозрят.
Выход из этой ситуации заключается в том, чтобы хранить такие произведения?Ул и Хн в специальном общедоступном каталоге, который имеет собственный ВБА-блок и широко известное произведение Юо. Когда Алиса пожелает узнать, как связаться с Бобом., она запросит в этом каталоге произведение для Боба:, компьютер, управляющий каталогом, отправит ей подписанное сообщение, выдав значение Хн. Такое сообщение должно быть легитимным, поскольку подделать его никто не сможет. Интересную альтернативу НБА-схеме предложил Майкл Рабин (М!сЬае! ВаЬ!и). В работе, опубликованной в М1Т ЬаЬ.
1ог Сотр. Бс!., герогс ТВ-212 (1979), он описал способ кодирования функцией х~ щи % вместо функции хз шоб М. В этом случае механизм декодирования, который можно было бы назвать бс)11Т-блоком, возвращает четыре различных сообщения; суть в том, что четыре различных сообщения содержат один и тот же квадрат по модулю Х, а именно — х, -х, 7хшог! Х и (-ух) шос1?У, где ( = (рт ' — е" ') шод Х. Если условиться на будущее, что х — четное число или что х ( -Х, то двусмы- 1 гленность коснется двух сообщений, из которых предположительно только одно имеет смысл. Эта двусмысленность может быть легко устранена, как показано в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
