<< Предыдущая

стр. 47
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

мош;ью представления Монтгомери. Это позволяет избежать
дорогостоящей операции деления, заменяя ее простым сдви­
гом разрядов. Правда, эффективность здесь достигается бла­
годаря нестандартному представлению чисел.
- Операции в полях характеристики 2 также эффективно реа­
лизованы. В этом случае редукция по модулю неприводимого
многочлена f{x) может быть упроп1;ена выбором специального
трехчлена или пятичлена. Обращение элементов поля на прак­
тике осуществляется с помощью адаптированного варианта
двоичного алгоритма Евклида. Однако вычисление обратно­
го элемента происходит как правило в 3-10 раз медленнее, чем
умножение.

Дополнительная литература
Стандартная ссылка на описание алгоритмов, разобранных в этой
главе — второй том книги Кнута. Более легкое введение в них мож­
но найти в книге Бэча и Шаллита, а алгоритмы, не вошедшие в наш
11.6. Арифметика в конечных полях 309

учебник, представлены у Коэна. Первая глава произведения Коэна
дает много полезных сведений по разработке стандартного кальку­
лятора, в то время как книга Бэча и Шаллита содержит обширную
библиографию и соответствующие комментарии.
Е. Bach and S. Shallit. Algorithmic Number Theory, Volume 1: Efficient
Algorithms. MIT Press, 1996.
H. Cohen. A Course in Computational Algebraic Number Theory. Springer-
Verlag, 1993.
D. Knuth. The Art of Computing Programming, Volume 2: Seminumer-
ical Algorithms. Addison-Wesley, 1975.

Контрольные вопросы
11.1.1. Чему равны максимальное и среднее количество умножений
в основном алгоритме двоичного потенцирования?
11.1.2. Почему наименьший возможный вес Хемминга шифрующей
экспоненты алгоритма RSA равен 2?

11.1.3. Что мешает применять алгоритм знакового потенцирования
в системе RSA?

11.1.4. Почему умножение Карацубы редко используется в системе
RSA?

11.1.5. Что такое представление Монтгомери и почему его активно
используют в алгоритмах типа RSA?

11.1.6. Почему в полях характеристики 2 предпочтительнее исполь­
зовать аналог умножения Карацубы, а не Монтгомери?

Лабораторные работы
11.2.1. (Предполагается знакомство с языком С или Java.) Сравни­
те алгоритм двоичного потенцирования с тем, что приведен
ниже:
y=i;
while ( d o O )
{ i f ((d&l)!=0)
{ у=(у*х)У.п; }
d»=l;
x=(x*x)7.n;
}
Глава 11. Реализация операций

Почему этот алгоритм более эффективен? Можете ли Вы
придумать еще более хороший метод?

11.2.2. Разработайте процедуры, осуществляющие сложение, умно­
жение и деление в полях характеристики 2. Ваши алгоритмы
должны работать с полями, чья степень над полем F2 может
быть любой, вплоть до 500.

11.2.3. Напишите программы, умножаюпще точки эллиптической кри­
вой, определенной либо над полем характеристики 2, либо
над полем вычетов по модулю простого числа, предполагая,
что элементы полей представляются битовыми строками дли­
ною около 190 знаков. Примеры полей и кривых можно найти
в одном из многочисленных криптографических стандартов,
доступных в Интернет.

Упралснения
11.3.1. Предположим, что умножение /с-битовых элементов кольца
вычетов требует к'^ операций. Что быстрее: два возведения
в степень 512-разрядного числа с 512-разрядным показателем
или одно потенцирование 1024-битового числа с показателем
в 1024 бита? Заключите из ответа, что метод расшифрования
или генерирования подписи в RSA^ опирающийся на китай­
скую теорему об остатках, более эффективен.

11.3.2. Предположим, что для ускорения процесса расшифрования
(генерирования подписи) в RSA применяется китайская тео­
рема об остатках, т. е. сначала производят вычисления
Шр = С^ (modp-1) ( m o d p ) ,
^ ^ ^ ^ r f (mod 9-1) ( n i o d ^ ) ,

a потом находят ттг, исходя из гпр и rriq. Допустим, что атаку­
ющий сумел заставить эту программу вычислять гПр непра­
вильно, не вмешиваясь в процесс вычисления rriq^ т. е. послед­
нее значение найдено верно. Покажите, что в этом случае
атакующий может раскрыть секретный ключ.

11.3.3. Докажите, что две версии редукции Монтгомери, предста­
вленные на псевдокоде в тексте главы, действительно при­
водят к ожидаемому результату. Покажите, что перемежа­
ющаяся версия умножения тоже работает корректно.
11.6. Арифметика в конечных полях 31 I

11.3.4. Покажите, что шифрование и расшифровывание в алгоритме
RSA можно реализовать за 0{п^) операций, где п — битовая
длина модуля N алгоритма.

11.3.5. Покажите, что шифрование в системе Эль-Гамаль требует
2\пр умножений по модулю р. Выведите отсюда, что его би­
товая сложность равна 0((1пр)^).

11.3.6. Решив рекуррентные соотношения, приведенные в тексте,
покажите, что сложность умножения Карацубы действитель­
но равна 0(п^'^^).

11.3.7. Умножение Карацубы многочленов основано на разбиении
многочленов на две половины. Разработайте вариант тако­
го умножения, при котором многочлены разбиваются на три
части.

Таблица 11.1. Неприводимые трехчлены и пятичлены
п п
к/к1,к2,кз к/к1,к2,кг \
п к/к1,к2,кз
4
2 1 1 1
3
1 1
5 2 6 7
8 7,3,2 1
9 10 3
12
11 2 13 4,3,1
3
1
14 5 15 16 5,3,1
5,2,1
18 19
17 3 3
22
21 2 1
20 3
24 8,3,2 25 3
23 5
5,2,1
27 28 1
26 4,3,1
1
29 2 30 31 3
32 7,3,2 34
10 7
33
6,4,1
35 2 37
36 9
4
38 6,5,1 39 40 5,4,3
42
41 3 7 43 6,4,3
44 5 45 46 1
4,3,1
49
47 5 48 11,5,1 9
50 4,3,2 52
51 6,3,1 3
54
53 6,2,1 55
9 7
4
56 7,4,2 57 58 19
59 7,4,2 1 5,2,1
60 61
64 11,2,1
62 29 1
63
67
65 32 66 3 5,2,1
I 68 33 37,34,33 I
6,5,2
69 70
Глава 11. Реализация операций

Продоллсение таб. 11.1.

1 74'^^ 72 73
35 42 [
36,35,33
75 76
35 35,34,32 38,33,32
78 79
77 41,37,32 40,36,32
38,33,32
82
81 35
80 43,35,32
45,39,32
84 35 85
83 35,34,32
39,33,32
87 88
86 45,35,32
46,34,32
49,39,32
90 91
38
89 35,34,32 41,33,32
94
92 93 43,33,32
35,34,32
37,33,32
96 33
97
95 57,38,32
41,33,32
37
99 100
98 42,33,32
63,35,32
72
102 37 103
101 40,34,32
105 37
104 106 73,33,32
43,33,32
108 33 109
107 34,33,32
54,33,32
111 112
49
110 33 73,51,32
114 115
113 53,33,32
69,33,32
37,33,32
117 33
118
116 78,33,32
48,33,32
121
120
119 38 35,34,32
41,35,32
124 37
122 123 42,33,32
39,34,32
126 49 127 63
125 79,33,32
129 46 130
128 61,33,32
55,33,32
132 133
131 44,33,32 46,33,32
43,33,32
134 135
57 136
39,33,32 35,33,32
138 139
137 35 57,33,32 38,33,32
141 142
140 45 85,35,32 71,33,32
144 52
145
143 59,33,32
36,33,32
147
71 49 148
146 61,33,32
150 53 39
151

<< Предыдущая

стр. 47
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>