Современная прикладная криптография (стр. 18 )

Все сказанное справедливо для произвольного модуля n. Но системе RSA модуль n есть произведение двух больших простых чисел р и q, . Поэтому=(p-1)(q-1) (В общем случае … для ).

При любое простое число будет взаимно просто с , и при выработке ключа е можно просто воспользоваться быстрыми тестами проверки чисел на простоту [64] и не применять алгоритм Евклида.

Без знания простых сомножителей р и q значение функции определить очень трудно и, если сделать открытыми числа е и n, а число d держать в секрете, то нахождение числа M из C сводится к трудной задаче извлечения корня степени е из числа C по модулю m. Это и означает, что предложенная система может быть использована как система открытого шифрования, когда преобразование зашифрования открыто, а преобразование расшифрования держится в секрете. В этом случае открытым ключом является пара (е, n), а закрытым - (d, n).

Напомним, что по теореме Эйлера числа M и n =pq должны быть взаимно простыми. Именно в этом предположении была показана справедливость преобразований зашифрования - расшифрования. Но оказывается, что вероятность этого близка к единице при больших значениях р и q. Действительно, число чисел M, не взаимно простых с n, равно , а их доля в интервале [0,1] близка к нулю в силу соотношения

при больших значениях р и q.

Для полноты картины можно отметить, что есть небольшая вероятность того, что шифрование числа M возведением в степень е по модулю n не изменяет открытый текст M. Так, в [16] показано, что для каждого значения е существует, по крайней мере, девять значений M таких, что . Так как е взаимно просто c , то е является нечетным числом, и поэтому два сравнения и имеют три решения. x=0, 1, -1. Комбинируя их в условиях китайской теоремы об остатках, получаем искомые 9 сообщений M.

Например, для n=4759=2773 это: 0, 1, 2772, 2537, 2303, 235, 2538, 471, 236.

В криптосистеме RSA вместо функции Эйлера можно рассмотреть функцию Кармайкла (Carmichael) - , определяемую для произвольного целого числа следующим образом:

Значение функции Эйлера совпадает с порядком мультипликативной группы целых чисел по модулю n, а значение функции Кармайкла совпадает с экспонентой этой группы.

В теореме Кармайкла, обобщающей теорему Эйлера, утверждается, что для любого целого числа M, взаимно простого с числом n, верно сравнение .

Далее в приведенных рассуждениях можно заменить на . При n = pq имеем = Н. О.К. [p-1, q-1] = /нод (p-1, q-1), где в знаменателе стоит наибольший общий делитель чисел (p-1) и (q-1), который больше 2 в силу четности p-1 и q-1.

Описанная блочная криптосистема может использоваться и как обычная криптосистема с секретным ключом. Так, в [10] было предложено в качестве n выбирать большое простое число р. Оно может быть и несекретным (в соответствии с правилом Керкхоффcа), так как возможно его нахождение по размерам блоков шифртекста. В этом случае числа e и d являются секретными ключами . Это так называемая криптосистема Полига-Хеллмана (Pohllg-Hellman).

Стойкость этой криптосистемы зависит от сложности вычисления дискретных логарифмов в конечном поле GF(р), так как при атаке с известным открытым текстом криптоаналитик решает задачу нахождения числа , где C и M - шифрованный и открытый тексты соответственно.

При реализации системы RSA применяется китайская теорема об остатках, позволяющая сводить вычисление по большому модулю n=pq к вычислениям по меньшим модулям р и q. Покажем это на примере расшифрования, когда вычисляется . Введем обозначения , . Разделив d на (p-1) и (q-i) с остатком получим d = k(p-l)+ r =J(q-l)+s или r = d mod (р-1), s = d mod(q-1). По теореме Эйлера находим

Для восстановления M из вычисленных таким образом чисел а и b найдем и, 0<u<p, из условия . Тогда, как показано в [28], м находится одним из двух способов.

Легко видеть, что сложность операции расшифрования составляет ^3 операций.

Стойкость системы RSA можно оценить сверху сложностью разложения большого числа n на множители р и q с последующим определением и d. Именно потребности криптографии дали толчок в развитии методов факторизации целых чисел. Обзор по этим методам можно найти в [82]. Именно они влияют существенным образом на выбор ключевых параметров р и q.

В работе [46] можно найти доказательство того факта, что если для системы RSA удалось найти такое число , что для всех M взаимно простых с модулем n, тогда это дает возможность разложить число n на множители. Изложенный там алгоритм является примером так называемого вероятностного алгоритма (probabilistic algorithm), которые используются в криптографии.

То, что определить открытый текст в системе RSA можно без разложения числа n на множители, показывает следующий метод итерации преобразования зашифрования, предложенный в [30]. В этом методе криптоаналитик пытается найти целое число j, такое, что

, где - шифртекст, полученный из M на ключе (n, e).

Если такое число j найдено, то M получается следующим образом

,

так как справедливо соотношение .

В [30] приводится пример для p = 983, q = 563, е = 49, М = 123456.

Тогда , , , (число j делит порядок числа е по модулю ). В примере j = 10.

В работе [30] приведенная идея бесключевого чтения была обобщена, и криптоаналитик старается найти многочлен р(е) вида р(е) = еф(е), такой, что . Тогда открытый текст M находится вычислением

.

Некоторые последние результаты по труднорешаемым задачам

Задача факторизации

Решето числового поля(NFS), May 2005 RSA200 (665 бит).

Метод эллиптических кривых (ECM), April 2005 (220 битовый делитель).

Формула года Y, когда будет факторизовано целое число из D десятичных знаков приведено в трудах CRYPTO`00 и имеет вид

Y = 1928,6 + 13,24 D.