Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
91
ГЛАВА 5 чисел q и р значение периода T(C(N)) можно определить по формуле (4.31). Можно показать, что при заданном значении е число нешиф-руемых сообщений группы Gt(N), т.е. число элементов этой группы, удовлетворяющих условию (4.41), можно определить по формуле
щ(е- \) = ytl(e~l)yp(e-l), (4.42) где числа yq(e - 1) и ур(е - 1) определены как
yq(e-\) = (q-\,e-\), (4.43)
ур(е-\) = (р-\,е-\). (4.43а)
Когда число N является произведением двух простых чисел q и р, все N - 1 ненулевых элемента кольца C(N) распределяются по трем группам. Это группа Gt(N), включающая F(N) взаимно простых с N элементов кольца, группа Gq(N), включающая р - 1 элементов кольца C(N), кратных числу q, и группа Gp(N), включающая q - 1 элементов кольца C(N), кратных числу р. Естественно, что среди элементов групп G11(N) и Gp(N) не могут оказаться элементы, которые являются решением уравнения (4.41), так как единичные элементы этих групп отличны от элемента E = 1. В то же время условие (4.41) является достаточным, но не необходимым для того, чтобы очередной элемент оказался нешифруемым. Действительно, ведь для того, чтобы очередной элемент Показался нешифруемым, необходимо, чтобы имело место
Xе = Xmod (N). (4.44)
Чтобы это условие имело место, необходимо и достаточно, чтобы имело место
X''-1 = ?mod(/V), (4.45)
где под E подразумевается единичный элемент той группы, которой принадлежит элемент X. В случае, когда речь шла об элементах группы Gt(N), единичный элемент оказался равным единице и вместо уравнения (4.45) мы имели дело с уравнением (4.41). В общем же случае следует учесть конкретные значения единичных элементов. Так, можно показать, что число элементов группы Gq(N), удовлетворяющих уравнению (4.45), равно у (е - 1). Аналогично, число элементов группы Gp(N), удовлетворяющих условию (4.45), равно ур(е - 1).
Таким образом, при заданных значениях е и N, из N - 1 ненулевых элементов кольца C(N)
V(e - 1) = vt(e - 1) + yq(e - 1) + ур(е - 1) (4.46)
элементы окажутся нешифруемыми.
Пример 4.4. Пусть в качестве простых чисел q и р выбраны числа, соответственно, q = 151 и р = 251. Тогда число N получится равным N = 37901, а числа элементов в группах, соответственно, Gt(N), Gq(N)
92 Таблица 4 J
е 1 11 13 17 19 23 29 31
12 100 12 4 12 4 4 300
V(e-1) 20 120 20 8 20 8 8 340
е 37 41 43 49 77 121 151 173
vx(e~\) 12 100 12 12 4 300 7500 4
20 120 20 20 8 340 7700 8
е 193 211 251 751
VX(e-\) 12 300 12500 37500
V(e-\) 20 340 12800 37900
и Gp(N) окажутся равными F(N) = (q - 1) ¦ (р - 1) = 37500 = 22 • 3 • 55, р - 1 = 250 = 2 • 53, q - 1 = 150 = 2-3-52. Значение периода кольца сообщений C(N) при этом определяется как
T = [q - I, р - I] = [150, 250] = 750 = 2 • 3 ¦ 53.
Число функционально различных вариантов выбора числа е, т.е. число различных E равно
F(T) = 200 = 23 ¦ 52.
Порядок каждого из этих чисел Е, т.е. каждое число типа g(E) является делителем числа т, определяемого по формуле
т = [F(2\ FO), F(53)] = 100 = 22- 52.
Это означает, что при любом выборе числа е для рассекречивания системы потребуется не более 100 операций. При случайном же выборе числа е число g(E) - характеристика фактической криптостойкости системы - может оказаться значительно меньшим числа т= 100.
Пусть в качестве е выбрано число е = 1301, взаимно простое с числом F(N) = 37500. Число е - 1 при этом окажется равным е - 1 = 1300 = = 22 • 52 • 13, т.е.
yq(e - 1) = (2 • 53, 22 • 52 • 13) = 50 = 2 • 52,
ур(е - 1) = (2 • 3 • 52, 22 ¦ 52 • 13) = 50 =2 • 52.
Подставляя эти значения в формулы (4.42) и (4.46), получим числа
v^e- 1) = 2500,
V(e - 1) = 2500 + 50 + 50 = 2600.
Таким образом, при принятых конкретных значениях q = 151, р = 251
93
ГЛАВА 4 me = 1301 из общего числа N- 1 = 37900 ненулевых элементов кольца сообщений V(e - 1) = 2600 элементов окажуется нешифруемыми, т.е., в среднем каждое из 15-ти сообщений окажется нешифруемым. Естественно, что такое положение дел не может устраивать пользователей.
В заключение приведем значения и|(<? - 1) и V(e - 1) при некоторых других вариантах выбора числа е (см. табл. 4.3):
ЛИТЕРАТУРА К ГЛАВЕ 4
1. Аветисян Д.О. Проблемы информационного поиска: (Эффективность, автоматическое кодирование, поисковые стратегии). - M.: Финансы и статистика, 1981. -208 е., ил.
2. Аветисян Д.О. Статистические методы при решении прикладных задач документального поиска. Автореф. дис. д-ра техн. наук. - Новосибирск, 1975.
3. Аршинов М.Н., Садовский Л.Е. Коды и математика - M.: Наука, 1983.- (Б-чка "Квант"; Вып. 30).
4. Аснис ИJl., Федоренко С.В., Шабунов К Б. Краткий обзор криптосистем с открытым
ключом // Защита информации "Конфидент". - 1994. - № 2.
5. Герасименко В.А. Защита информации в автоматизированных системах обработки данных. В 2-х кн.: Кн. I и 2. - Энергоатомиздат, 1994.
6. Лебедев А.Н. Криптография "с открытым ключом" и возможности ее практического
применения // Защита информации. - 1952. - Вып. 2.
7. Мельников Ю.Н. Электронная цифровая подпись. Возможность защиты // Защита информации "Конфидеит". - 1995. - № 6/4.
