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

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

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


Таким образом, при заданных числах а и Ь, чтобы максимально усложнить задачу злоумышленника, числа q и р необходимо выбрать такими, чтобы число V/V оказалось близким к числу Ы2, если а =? Ь/4 и

числу Va ¦ b, если а > Л/4 (см. рис. 4.1).

Пример 4.2. Пусть известно (в том числе и злоумышленнику), что числа q Vi р выбираются из игервала чисел, содержащих по 3 десятичных знака. Пользуясь таблицей простых чисел, можно заметить, что числа а и b при этом окажутся равными, соответственно, а = 101 и b = 997. Очевидно, отношение bla = 997/101 больше четырех, т.е. имеет место случай (а) (см. рис. 4.1). Пусть число р принято равным р = = 983 и необходимо выбрать число q такое, чтобы максимально усложнить задачу злоумышленника по вычислению чисел q и р. В табл. 4.1

для различных значении q приведены значения V/v и Aq. Численные значения Aq определены е помощью формул (4.22) или (4.25), в зависимости от того, имеет ли место условие N =S а ¦ b или нет.

Таблица 4.1

q 101 103 211 251 257 313 491 911 967 977
V77 315 318 455 498 503 554 694 946 975 979
А? 214 217 247 250 249 246 21 1 49 22 18
N < ab N > a h

В рассматриваемом примере к линейной зоне (формула (4.22)) относится лишь значение q = 101 и далее, начиная со значения q = 103, начинается параболическая зона (формула (4.25)). В этой зоне с ростом q число Aq сначала растет до достижения значения Aq = Ы4 = 250 (при

этом V/V оказывается равным b/2 = 498), после чего дальнейший рост числа q влечет уменьшение числа Aq, облегчив тем самым задачу потенциальных злоумышленников. Если, к примеру, пользователь стремится выбрать число q как можно большим, надеясь максимально усложнить этим задачу злоумышленника, то это приводит к диаметрально противоположному эффекту: необходимое число испытаний для

87

ГЛАВА 5 злоумышленника может уменьшаться из числа Aq = 250 (при q = 251) до числа Af/ =18 (при q = 977).

Другим объектом прямой атаки (не через числа q и р) со стороны злоумышленника может служить секретный ключ расшифрования -число d. Для анализа возможных угроз его рассекречивания будем рассматривать кольцо сообщений C(N), подразумевая под ним множество классов вычетов по модулю N с определенными на его элементах операциями сложения и умножения по этому модулю. Под периодом кольца T(C(N)) будем понимать минимальное значение числа z > 0, при котором для всех сообщений (всех элементов кольца C(N)) X є C(N) имеет место

= Xmod(/V). (4.29)

Можно показать, что говорить о периоде кольца C(N) можно лишь применительно к случаям, когда в каноническом разложении числа N

N = p?p?...p? (4.30)

все а, (/ = 1, 2, 3, ... , п) равны единице. Во всех остальных случаях среди элементов X є C(N) всегда окажутся такие, для которых формула (4.29) не имеет места ни при каких z > 0. Поскольку в системе RSA число N определяется как произведение двух простых чисел, то можно говорить о периоде кольца C(N), значение которого равно T(C(N)). Можно показать, что в рассматриваемом нами случае число T равно наименьшему общему кратному чисел F(p) = р - 1 и F(q) = ц - 1, т.е.

T(C(N)) = {p-\,q-\\. (4.31)

Введем в рассмотрение понятие кольца степеней C(T), подразумевая под ним множество классов вычетов по модулю T(C(N)) с определенными на нем операциями сложения и умножения по этому модулю. Можно показать, что множество элементов кольца степеней, которые взаимно просты с числом T(C(N)), образует группу относительно операции умножения по этому модулю. Эту группу будем называть группой допустимых степеней, имея в виду то обстоятельство, что числа е и d всегда выбираются такими, чтобы они были взаимно простыми с числом

F(N) = (q- 1)- (р- 1). (4.32)

Отсюда с учетом (4.31) легко сделать вывод, что числа е и d являются взаимно простыми также с числом T(C(N)). Иными словами, элементы группы допустимых степеней характеризуются тем, что числа е и d всегда можно представить как

е = E + к\ ¦ Т, (4.33)

d = D +Ic2-T, (4.34)

где элементы EwD принадлежат этой группе, которую далее

88 обозначим через G1(T)- Из (4.33) и (4.34) следует, что в формулах (4.7) и (4.11), согласно которым в системе RSA осуществляется шифрование и расшифрование конфиденциальных сообщений, числа ей d всегда можно заменить функционально эквивалентными им числами EnD, которые принадлежат группе G1(T) и в общем случае меньше чисел соответственно е и d. В рассматриваемом смысле для злоумышленника вовсе не обязательно найти именно число d, а вполне достаточно найти соответствующее ему число D, которое в общем случае может оказаться существенно меньшим числа d. Заметим также, что элементы E и D группы G1(T) являются обратными друг другу, т.е. имеет место

ED = 1 mod (71. (4.35)

Порядки элементов EnD равны между собой, т.е. g(E) = g(D). Легко заметить, что именно этим порядком и определяется необходимое число операций для рассекречивания числа d - секретного ключа расшифрования. Это обстоятельство необходимо учесть как на этапе выбора чисел q и р, так и особенно на этпе выбора чисел end. Выбор конкретной пары чисел q и р уже предопределяет число т - период группы G1(T). Легко заметить, что именно число«; является верхней границей числа g(D). Можно показать, например, что, если каноническое разложение числа T имеет вид
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 64 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed