Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2), страница 14

Следующее число Ферма было в два раза длиннее предыдущего, но при помощи метода эллиптических кривых 20 октября 1995 года был получен результат: 21эы + 1 45592577. 6487031809 4 659 775 785 220 018 543 264 560 743 076 778 192 897. рзвз. [В!сЬагг( Вгепг, МагЬ.

Согпр. 68 (1999), 429- 45Ц На самом деле Брент уже применял метод эллиптических кривых в 1988 году для решения следующей задачи: 2эввв + 1 = 319489 974849. 167988556341760475,137 3560841906445833920513 рввв Все простые множители, кроме одного, оказались, хотя и с некоторой долей везения, меньшими < 10~э,. так что метод эллиптических кривых стал победителем. А как насчет числа 2~~э + 17 К наспзящему моменту эта задача кажется слишком сложной для решения. Данное число содержит пять множптелей < 10'~, но остаток, который не удается разложить на множители, содержит 1187 десятичных разрядов. Бще один случай: число 2э гэз+1 содержит четыре известных множителя < 10т' и очень большой неразложенный остаток.

[Сгапба11, Ра81п, Мага. Сотр. 62 (1994), 321; Вгепс, Сгапдай, 011сЬег, тап На1ежуп, 66 (1999), 429-451.] Секретные множители. Всеобщий интерес к проблеме разложения на простые множители резко возрос в 1977 году, когда Р. Л. Ривест (К. 1.. К1теэс), А. Шамир (А. Бйащ(г) и Л.

Эдлеман (1., АсИетап) нашли способ кодирования сообщений, которые могут быть декодированы в явном аиде толью по известным множителям, на которые разлагается большое число Ф, даже в там случае, когда метод кодирования известен всем и каждому. Так как большинство величайших математиков мира не могут до сих пор найти эффективный метод разложения чисел на простые множители, этот метод [САСМ 21 (1978), 120-126) позволяет почти гарантированно защитить засекреченные данные и сообщения в компьютерной сети. Представим себе маленькое электронное устройство (назовем его КЯА-блоком), в памяти которого хранятся два больших простых числа р и д. Будем считать, что числа р — 1 и д — 1 пе делятся на 3. КБА-блок, подсоединенный какнм-то образом к компьютеру, передал последнему произведение Ю = рй, поэтому ни один человек не может обнаружить значения чисел р н д, не разложив число Х на простые множители.

При попытке взлома КЯА-блок запрограммирован на самоуничтожение. Другими словами, блок сотрет информацию в своей памяти, если будет предпринята попытка доступа к нему или он подвергнется воздействию внешнего излучения, которое может изменить или считать данные, хранящиеся в памяти. Кроме того, КБА-блок достаточно надежен с точки зрения эксплуатации; в случае его выхода из строя вследствие неполадок в системе питанпя или износа нужно выбросить имеющееся устройство и купить новое. Простые множители р и д генерируются самим КБА-блоком с помощью схемы, основанной на явлениях, которые случайны по самой своей природе (например, космические лучи).

Важным является тот факт, что никколо не знает простых чисел р и д, даже то лицо (или организация), которому принадлежит устройство или которое имеет доступ к нему. Не может быть и речи о подкупе, шантаже или захвате заложников с целью получения информации о простых числах числа Ф. Чтобы отослать секретное ссюбщение владельцу КЯА-блока, для которого произведение двух чисел равно Х, нужно преобразовать сообщение в последовательность чисел (яы ..хь), в которой каждое нз чисел я; принимает значения в интервале между 0 и Ю, а затем передать числа (я~~ щи Х, ..., яь зпих1 Х).

ВЯА-блок, зная р и д, может декодировать сообщение, поскольку в нем уже имеется вычисленное заранее число Ы < Ю, такое, что Ы гй 1 (по модулю (р — 1)(ч — 1)). Теперь КБА-блок может, используя рассмотренный в разделе 4.6.3 метод, за приемлемое время вычислить (яэ)и щи У = х. Естественно, КБА-блок хрэпиг это магическое число И внутри себя; фактически можно было бы запоминать в НЯА- блоке только число д вместо чисел р и О, поскольку. в обязанности блока после вычисления числа Ю входит только защита своих секретов и вычисление кубических корней по модулю й~. Подобная схема кодирования не дает эффекта, если я < ТХ, так как лз шоб Ю = яз, а кубический корень легко можно найти.

Нз описанного в разделе 4.2.4 логарифмического закона ведущих разрядов следует, что старшая позиция х1 й-размерного сообщения (хы..., Ть) будет меньше ~/Ю примерно в ~У случаев, поэтому данная проблема требует своего решении. В упр. 32 рассмотрен одни из способов, позволяющих избежать этих сложностей. Надежность схемы кодирования при помощи ВЯА базируется на том факте, что нихто не может узнать, как вычислять кубический корень по модулю Ю, не зная множителей числа Х. Похоже, что не существует методов, позволяющих это сделать, однако абсолютной уверенности нет.

Все, что можно сказать по данному поводу,— это то, что обычные методы обнаружения кубических корней задачу не решают. Например, бесполезно пытаться вычислять число б как функцию числа Ф; причина в том, что если известно 0 или фактически если известно любое число пз разумной длины, такое, что равенство х щи г7 = 1 справедливо для значительного количества величин х, то потребуется намного больше шагов для поиска множителей числа 11' (упр. 34). Таким образом, любой из методов, основанных на явной или скрытой попытке нахождения такого числа гz, не может оказаться лучше, чем метод разложения на простые множители, Тем ие менее нужно соблюдать осторожность. Если одно и то же сообщение по компьютерной сети отослано трем лицам, то некто, кому известно хз по модулю Юы АЗ и дз~ может восстаиОВить яз щоо д'1Хздз = ад~ используя китВйскую теорему об остатках, после чего число х уже не будет секретом.

Фактически даже в случае, когда один и то же сообщение отослано семерым разным лицам с отметками времени (2~~а ") х+ гз) з шоб дь в которых времена З; известны или могут быть с достаточной достоверностью предугаданы, значение величины л может быть найдено (упр. 44). В связи с этим некоторые криптографы рекомендуют кодировать информацию с использованием числа 2'е + 1 = 65 537 вместо 3.

Данный показатель степени является простым, поэтому иа вычисление числа лез ззг шоб Ф затрачивается ирнмерно в 8.5 раз больше времени, чем иа вычисление числа хз шоб Ю. '1СС1ТТ Весопппепйьбопэ В1це Воо)г (Оепета: 1псегпайопа) Те1есопппцпзсайоп ПИ1оп, 1969), Раас!с!е ЪЧ11.6, Васогпщепба21оп Х,509, Аппех С, 74-76.] В оригинальном описании методики шифрования Р.

Л. Ривест, А. Шамир и Л. Вдлеман предлагали кодировать число х числом л' щоб Ю, где а — любой простой показатель функции у(Ю), а не только а = 3, Тем не менее на практике предпочтение Отдангся показателю, для которого кодирование выполняется быстрее, чем декодирование. Чтобы схема, реализуемая в ВБА, была эффективной, числа р и д и» должны оказаться "случайно" близкими простыми. Как подчеркивалось выше, чтобы обеспечить существование единственных кубических корней по модулю 57, числа р — 1 и о-1 не должны делиться на 3.

Другое условие сводится к тому, что для числа р-1 должен существовать по крайней мере один очень большой простой множитель. То же самое относится и к числу Π— 1; в противном случае число Аг может быть раз- ложено на простые множители по алгоритму из упр. 19, Фактически этот алгоритм сводится к поиску малого числа т, характеризуемого тем„что я шоб У быстро становится равным 1, а мы уже знаем, что использовать такое число небезопасно. Если для чисел р — 1 и е — 1 существуют большие простые множители р~ и ем то согласно теории, изложенной в упр, 34, число гп будет либо кратным р1е, (тогда его будет трудно найти), либо вероятность того, что х'" ьз 1, будет меньше, чем 1/р1е1 (поскольку число х"' пнх1 Х почти никогда не равно 1).

К тому же нежелательно, чтобы числа р и д был~ близки одно к другому; иначе их можно будет довольно просто найти, используя алгоритм Э. Нежелательно также, чтобы отношение этих чисел р/4 было близко к простой дроби, в противном случае эти числа можно будет получить, используя обобщение Лемана из алгоритма С. Предлагаемая процедура генерирования чисел р и д почти всегда выполняется безошибочно. Начинаем с правдоподобного случайного числа ре, принадлежащего интервалу, скажем, между 10эе н 108'.

Находим первое простое число рм большее, чем ре; для этого потребуется проверить -' 1пре ш 90 нечетных чисел. Будет вполне достаточно, если после 50 пробных делений, выполняемых атгоритмом Р, число р1 окажется "вероятно, простым" с вероятностью > 1 — 2 'ее, После этого выбиРаем дРУгое пРавдоподобное слУчайное число Рт междУ, скажем, 10ээ и 104е. Находим первое простое число р вида йр1 + 1, где й > рю и — четное и Й ш р| (по модулю 3).

Для этого, прежде чем простое число р будет найдено, потребуется проверить 1 1пр1рт ш 90 чисел, Простое число р будет длиной около 120 разрядов; подобная конструкция может быть применена и для поиска простого числа е длиной около 130 разрядов. Чтобы обеспечить супернадежность, желательно убедиться в том, что числа р+1 и о+1 не содержат малых простых множителей (упр. 20). Теперь произведение Х = ре, величина которого имеет порядок 10ыэ, удовлетворяет всем требованиям, и в настоящее время такое число не может быть разложено на простые множители. Например, предположим, что известен метод разложения 250-разрядного числа АГ, время выполнения которого имеет порядок Агел мс. Следовательно, для разложения такого числа на простые множители потребуется 10зэ мс, но в году имеется только 31556 952000000 мкс, твк что для завершения процесса разложения потребуется более 3 х 10" лет машинного времени.