Научная литература
booksshare.net -> Добавить материал -> Физика -> Аветисян Р.Д. -> "Теоретические основы информатики" -> 35

Теоретические основы информатики - Аветисян Р.Д.

Аветисян Р.Д., Аветисян Д.О. Теоретические основы информатики — Телеком , 2003. — 170 c.
Скачать (прямая ссылка): teoriticheskieosnoviinformatiki2003.pdf
Предыдущая << 1 .. 29 30 31 32 33 34 < 35 > 36 37 38 39 40 41 .. 64 >> Следующая


T = tf[$2...tfk, (4.36) то число т определяется по формуле

т = [F*(?{3'), ),..., F(,f*)], (4.37)

где

F*(,f') = 2?l"2, (4.37a)

если t\ = 2 и P1 г 3, и

F*(,f') = F(r,?l ) = (,,-1)-,}5'-1 (4.376)

во всех остальных случаях.

Но следует иметь в виду, что т - это лишь верхняя граница для чисел g(D), т.е. это число, для которого при произвольном выборе чисел end имеет место

g(D) т. (4.38)

При случайном же выборе чисел ей d, какими бы большими они ни были, вполне может оказаться, что число g(E) = g(D), характеризующее в данном случае фактическую криптостойкость системы RSA1 окажется недопустимо маленьким. В рассматриваемом смысле при выборе чисел ей d необходимо заботиться, чтобы достаточно большими оказа-

89

ГЛАВА 5 лись не сами эти числа, а соответствующие им числа g(E), которыми, собственно, и определяется необходимое число операций, необходимых для определения секретного ключа расшифрования. Опасность же того, что эти числа могут оказаться недопустимо малыми даже при чрезвычайно больших значениях е и d, вполне реальна, поскольку при случайном выборе чисел q и р недопустимо малым может оказаться даже число т - верхний предел значений g(E). Бытующую же практику случайного выбора простых чисел q и р, с одной стороны, и чисел е и d - с другой, никак нельзя признать приемлемой с точки зрения обеспечения приемлемого уровня криптостойкости. Одно лишь очевидно, что, если числа е и d оказываются большими соответствующих им элементов EuD, т.е., когда числа и к2 в формулах (4.33) и (4.34) оказываются большими нуля, то это приводит лишь к ухудшению скоростных показателей системы, ни на йоту не увеличивая фактическую криптостойкость системы.

Пример 4.3. Пусть числа q и р выбраны равными соответственно q = 1601 и р = 4801, т.е. N = 7686401. При этом F(N) = 7680000, а число T(C(N)) определим по формуле (4.31), т.е.

T = [1600, 4800] = 4800 = 26 • 3 • 52.

Число различных вариантов выбора числа E при этом равно F(T) = = 1280 = 28 • 5. Пользуясь формулой (4.37), можно определить верхнюю границу числа g(E), т.е. число т

т = [24, 2, 22 • 5] = 80.

Это означает, что при любом выборе чисел е и d для рассекречивания данной системы потребуется не более 80 операций. При случайном же выборе числа е необходимое число операций для рассекречивания системы может оказаться значительно меньшим. В табл. 4.2 для рассматриваемого случая приведены некоторые конкретные значения числа E и соответствующие им значения g(E).

Таблица 4.2

E 799 1343 1921 929 497
№ 2 4 5 10 20

Из приведенных в табл. 4.2 численных данных легко убедиться, что при заданной паре чисел q и р случайный выбор числа е чреват опасностью существенного уменьшения криптостойкости системы RSA. Обратим внимание, что фактическая криптостойкость системы определяется числом g(E) и она не изменится, если вместо числа E выбрать в качестве е произвольное другое число, определяемое по формуле (4.33).

90 О НАДЕЖНОСТИ СИСТЕМЫ RSA. ШИФРУЕМЫЕ И НЕШИФРУЕМЫЕ СООБЩЕНИЯ

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

Xemoa(N) = X, (4.39)

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

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

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

е=\+к- [F(q), F(p)], (4.40)

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

Для элементов кольца C(N), которые взаимно просты с числом N, условие (4.39) эквивалентно условию

Xf-1Hiod(ZV) = 1, (4.41)

поскольку относительно операции умножения по модулю N эти элементы образуют группу Gi(N) с единичным элементом, равным E= 1. Очевидно, число элементов этой группы равно F(N): Среди остальных элементов кольца C(N) не могут оказаться элементы, удовлетворяющие условию (4.41), так как они распределены по двум другим группам, единичные элементы которых отличны от E =1. При заданной паре
Предыдущая << 1 .. 29 30 31 32 33 34 < 35 > 36 37 38 39 40 41 .. 64 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed