Практические соображения

В реальных приложениях генерация простых чисел происходит быстро. В [6] описан следующий алгоритм:

1) Сгенерируйте случайное n -битовое число р.

2) Установите старший и младший биты равными 1. (Старший бит гара­нтирует требуемую длину простого числа, а младший бит обеспечи­ва­ет его нечетность.)

3) Убедитесь, что р не делится на небольшие простые числа: 3, 5, 7, 11 и т.д. Во многих реализациях проверяется делимость р на все простые числа, меньшие 256. Наиболее эффективной является проверка на дели­мость для всех простых чисел, меньших 2000.

4) Выполните тест Рабина-Миллера для некоторого случайного а. Если р проходит тест, сгенерируйте другое случайное а и повторите проверку. Выбирайте небольшие значения а для ускорения вычислений. Выпол­ните пять тестов. (Одного может показаться достаточным, но выполните пять.) Если р не проходит одной из проверок, сгенерируйте другое р и попробуйте снова.

Иначе, можно не генерировать р случайным образом каждый раз, но последовательно перебирать числа, начиная со случайно выбранного до тех пор, пока не будет найдено простое число.

Этап 3 не является обязательным, но это хорошая идея. Проверка, что случайное нечетное р не делится на 3, 5 и 7 отсекает 54% нечетных чисел еще до этапа 4. Проверка делимости на все простые числа, меньшие 100, убирает 76% нечетных чисел, проверка делимости на все простые числа, меньшие 256, убирает 80% нечетных чисел. В общем случае, доля нечетных кандидатов, которые не делятся ни на одно простое число, меньшее m, равна 1.12/1 n m. Чем больше проверяемое m, тем больше предварительных вычислений нужно выполнить до теста Рабина-Миллера.

Сильные простые числа.

Если m – произведение двух простых чисел p и q, то может понадобиться использовать в качестве и q сильные простые числа.

Такие простые числа обладают рядом свойств, которые усложняют разложение произведе­ния m определенными методами разложения на множители. Среди таких свойств были предложены [6]:

1. Наибольший общий делитель p- 1 и q- 1 должен быть небольшим.

2. И p- 1,и q- 1 должны иметь среди своих множителей большие простые числа, соответственно р' и q'.

3. И p'- 1,и q'- 1 должны иметь среди своих множителей большие простые числа.

4. И p+ 1,и q+ 1 должны иметь среди своих множителей большие простые числа.

5. И(p- 1)/2,и (q- 1)/2 должны быть простыми (обратите внимание, при выполнении этого условия выполняются и два первых).

Насколько существенно применение именно сильных простых чисел остается предметом продолжающихся споров. Эти свойства были разработаны, чтобы затруднить выполнение ряда старых алгоритмов разложения на множители. Однако самые быстрые алгоритмы одинаково быстры при разложении на множители любых чисел, как удовлетворяющих приведенным условиям, так и нет.

Некоторые авторы [6] выступают против специальной генерации силь­ных простых чисел, утверждая, что длина простых чисел гораздо важ­нее их структуры. Более того, сама структура уменьшает случайность числа и может снизить устойчивость системы.

Но все может измениться. Могут быть созданы новые методы разложения на множители, которые лучше работают с числами, обладающими определенными свойствами. В этом случае снова могут потребоваться сильные простые числа.

 

Электронная цифровая подпись

В последние годы повсеместно прослеживается тенденция перевода всего документооборота в электронную форму. Основная проблема, кото­рая при этом возникает — это установ­ление подлинности автора и отсутст­вия изменений в полученном документе т.е. проблема ау­тентифи­кации как автора документа так и самого документа. В обычном бумажном делопро­изводстве эти проблемы ре­шаются за счет того, что информация в доку­менте и рукописная подпись автора жестко связаны с физическим носите­лем, то есть бумагой. В электронных документах на машинных носителях такой связи нет.

Принципиально новым решением является электронная цифровая подпись (ЭЦП), используе­мая для аутенти­фикации документа, переданно­го по телекоммуни­кационным кана­лам. Функционально она аналогична обычной рукописной подписи и обладает ее основными достоинствами:

Ø гарантирует целостность подписанного текста, то есть отсутствие исправлений и подчисток;

Ø удостоверяет, что подписанный текст исходит от лица, поста­вившего подпись;

Ø не дает этому самому лицу возможности отказаться от обяза­тельств, связанных с подписанным текстом.

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

В качестве подписываемого документа может быть ис­пользован любой файл. Подписанный файл создается из непод­писанного путем добавления в него одной или более электронных подписей.

Каждая подпись содержит следующую информацию:

Ø дату подписи и срок окончания действия ключа данной подписи;;

Ø идентификатор подписавшего (имя открытого ключа);

Ø информацию о лице, подписавшем файл;

Ø собственно цифровую подпись.