Тогда для любого простого с (p - 1)(q - 1) и удовлетворяющего условиям:

f Pij ф \ (modp), « = l,...,r, j = l,...,ri, t Яг, l(modg.), « = l,...,s, i = l,...,Si,

доля сообщений x € Z" mmopых ordordn(x)(t) не кратна числу Н0Д(Ь1,..., Ь;, 6/,..., Ь;,), «е превышает Е + Е •

i=1 i=1

Доказательство. Аналогично теореме Поклингтона можно

показать, что 6i ordpi (t дая i = 1, , отательно 6i ordpai (t), а также 6i ordFp (t щи i = 1, , r. Таким образом,

HOK(6l,,6r) ordFp (t),

Аналогично получаем

Отсюда

HOK(6l,,6S) ordFq(t),

H0K(6i, , 6Г, 61, , 6S) K(F,,Fp)(t)

Согласно лемме, доля x € Z", для которых выполняется условие HOK(Fp,Fg) ordn(x), составляет не менее

i=1 i i=1 i

Поскольку для таких x € Z" должно быть

K(Fp,F,) (t) ordord„(x)(t),

получаем требуемое. Теорема доказана. □

Данная теорема показывает, что условие Ривеста о том, чтобы для

p1 q1 p q p1 - 1 q1 - 1

так же имело большой простой делитель не является необходимым для защиты от метода с использованием итерации процесса зашифрования.

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

pi qi

pij qij

Согласно теореме для обеспечения высокой стойкости относительно метода итерирования процесса зашифрования достаточно взять по-

pij qij

e = t x

pij qij

на втором уровне рекурсии.

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

14.3. Выбор параметров ж d

Рассмотрим теперь вопрос о выборе экспонент шифрования и рас-

вания и расшифрования, то можно назвать ряд ситуаций, в которых

системы RSA при защите электронных платежей с применением кредитных карточек естественным является требование использования

опасным по ряду соображений. Если малым является секретный па-d

открытых сообщений, удовлетворяющих неравенству t< -/п будут зашифровываться простым возведением в степень te = шльце Z, и

Другая аналогичная ситуация может сложиться, когда у несколь-

что та одинаковую экспоненту e k, отправляют сообщения s1 = tf (mod n1),,sk = tk (mod nk), можно считать,

(ni, nj) =1 ni, nj)

IV. КРИПТОГРАФИЧЕСКАЯ СИСТЕМА RSA

теореме об остатках существуют числа те что t = ti (mod U), s = s (mod U), i = 1,..., числа si,..., sk известны, то чис-

ло 0 € s < Ui - ... - Uk можно вычислить. Поэтому в случае, когда набор ti,..., отено неравенство te < ui - ... - Uk, то te

t1 , . . . , tk

очевидна в случае, когда всем абонентам отправлено одно и то же циркулярное сообщение t,t< ... пи- В данном случае сразу получаем уравнение te = s в кольце целых чисел, которое решается путем

Комментарии

При написании раздела 1 использовались книги [2], [9], [34] и [1]. Более подробную информацию по оценке сложности арифметических операций, алгоритмов Евклида, дискретному преобразованию Фурье и др. алгоритмам можно прочитать, например, в книгах [9] и [13], содержащих также большое число упражнений и задач, или в [14].

Раздел 2 написан на основе книг [10], [16]. Исторические сведения взяты из книг [3], [18].

Раздел 3 основан на книгах [10], [34]. Много дополнительных сведений можно получить в [9]. Свойства чисел Кармайкла опубликованы в [36]. Тест Соловея-Штрассена - в статье [53] с дополнением [54]. Тест Миллера-Рабина опубликован сначала в детерминированном варианте в [41], а затем в вероятностном в работе [49]. Тесты простоты для маленьких простых чисел приведены по курсу лекций К. Кал-двела (С. К. Caldwell. Primality Proving. University of Tennessee, 1995), доступном в Интернет. В 1980 г. Л. Эдлеман предложил детерминированный метод проверки на простоту, основанный на теории целых алгебраических чисел. Его модификации описаны в работе X. Лен-стры [12]. Теорема Н. Диемитко [30] лежит в основе алгоритма построения ключей первого российского стандарта цифровой подписи. Методы построения простых чисел подробно описаны в [39] и [40]. Методы квадратичного решета предложен в [47] и модифицирован в [52]. Приведенная информация об истории открытия и поиска первых простых чисел Мерсенна, доступна в сети Интернет. За рамками курса лекций остался метод эллиптических кривых для факторизации чисел, подробно описанный в [10]. В отличие от методов Полларда и Полларда-Штрассена, которые ориентированы на поиск маленьких простых делителей чисел, метод эллиптических кривых позволяет находить достаточно большие делители. В настоящее время одними из наиболее действенных методов факторизации являются методы на основе решета числового поля (см. [38]). С историей развития теоретико-числовых алгоритмов можно ознакомиться, например, по обзору [37].

Раздел 4 опирается на книгу [17], а также статьи [33] и [39]. Дополнительную информацию по приложениям системы RSA можно получить, например, в книгах [55], [21] или [15].

Литература

Акритас А. Основы компьютерной алгебры с приложениями.-М.: Мир, 1994.

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979.

[3] Бухштаб А. А. Теория чисел. -2-е изд.-М.: Просвещение, 1966.

[41 Василенко О. Н. Современные способы проверки простоты чисел Киберн. сборник.-1988.-Т.25.-С. 162-188.

Виноградов И. М. Основы теории чисел.-9-е изд., перераб.-М.: Наука, 1981.

Галочкин А. И., Нестеренко Ю. В., Шидловский А. В. Введение в теорию чисел -М.: Изд-во МГУ, 1995.

Гашков С. В., Чубариков В. Н. Арифметика, алгоритмы, сложность вычислений. "Учебное пособие. -М.: ВШ, 2000.

Дэвенпорт Дж., Сиро И., Турнье Э. Компьютерная алгебра.-М.: Мир, 1991.

Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы.-3-е изд. -М.: Вильяме, 2000.

Коблиц Н. Курс теории чисел и криптографии. - М.: Научное издательство ТВП, 2001.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.-М.: МЦНМО, 1999.

Ленстра X. У. Алгоритмы проверки на простоту Алгебра и теория чисел (с приложениями): Сб. статей.-М.: Мир, 1987.- Вып. 43.-С. 47-66.

Ноден П., Китте К. Алгебраическая алгоритмика. - М.: Мир, 1999.

Ростовцев А. Алгебраические основы криптографии. - СПб.: Мир и семья-Интерлайн, 2000.

Ростовцев А., Маховенко Е. Введение в криптографию с открытым ключом. - СПб.: Мир и семья-Интерлайн, 2001.

16] Прахар К. Распределение простых чисел.-М.: Мир, 1967.

17] Саломаа А. Криптография с открытым ключом. -М.: Мир, 1996.

ЛИТЕРАТУРА

[18] Сушкевич А. К. Теория чисел. Элементарный курс. - Харьков: Изд. Харьковского ун-та, 1954.

[19] Трост Э. Простые числа.-М.: ГИФМЛ, 1959.

[20] Хассе Г. Лекции по теории чисел. -М.: ИЛ, 1953.

[21] Введение в криптографию / Под общ. ред. В. В. Ященко. - 3-е изд., доп.-М.: МЦНМО: «ЧеРо», 2000.

[22] Adleman L. М. Factoring numbers using singular integers Proc. 23rd ACM Symp. on Theory of Comput., N.O., LA.-1991.-P. 64-71.

[23] Adleman L. M., Pomerance C, Rumely R. S. On distinguishing prime numbers from composite numbers Ann. Math. (2). - 1983.- V.117, No. 1.-P. 173-206.

[24] Baker R. C, Harman G. The Brun-Titchmarsh Theorem on average Proceedings of a conference in Honor of Heini Halberstam. - 1996. Vol.1.-P. 39-103.

[25] Brent R. P. Analysis of the binary Euclidean algorithm Algorithms and Complexity: New Directions and Recent results / J.F.Traub Ed. -New York: Academic Press, 1976. -P. 321-355.

[26] Brillhart J., Morrison M. A. A method of factoring and the factorization of F Math. Comp. -1975. V. 29. - P. 183-205.

[27] Canfield E., Erdos P., Pomerance C. On a problem of Oppenheim concerning Factorisatio Numerorum Journal of Number Theory. - 1983.-V. 17.-P. 1-28.

[28] Carmichael R. D. On composite numbers which satisfy the Fermat congruence American Mathematical Monthly. - 1912. - "V. 19.- P. 22-27.

[29] Cohen H., Lenstra H. W., Jr. Primarility testing and Jacobi sums Report 8218 / Mathematical Institut of the University of Amsterdam.-Amsterdam, 1982.

[30] Diemitko N. Generating multiprecision integer with guaranted primality Proc. of the SIFIP Int. Conf. on Comp. Sei., IFIP/Security 88, Amsterdam, 19-21 May, 1988.-P. 1-8.

[31] Dixon J. D. Asymptotically fast factorization of integers Math. Comput. -1981.-V. 36. - P. 255-260.

[32] Fouvry E. Theoreme de Brun-Titchmarsh; application au theoreme de Fermat. - Invent. Math. -1985. -V. 79. - P. 383-407.