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

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

ОГЛАВЛЕНИЕ

Следующая >>

Метод, с помощью которого достигается такал экономия опера­
ций носит специальное название: метод двоичного потенцирования.
Работает он, поочередно считывал знаки двоичного представления
показателя, начинал с младшего разряда. Чтобы увидеть, как это
происходит, запишем на псевдокоде алгоритм двоичного потенци­
рования, вычисляющего у = х^ (modn), где гг, у, d и п — большие
целые числа, представленные с помощью средств языков С или Java.
^Вес Хемминга числа равен количеству единиц в его двоичном представлении.
Прим. перев.
11.2. Алгоритмы возведете в степень

y=i;
while ( d o O )
{ i f ((dy.2)!=0)
{ у=(у*х)У.п;
d=d-l;
}
d/=2;
x=(x*x)'/,n;
}

Этот метод имеет много разных названий. Некоторые авторы
называют его алгоритмом квадратов и умноэ/сений^ поскольку он
действительно осуществляется с помощью этих операций. Другие
именуют его алгоритмом индийского потенцирования. Тот, что мы
привели на псевдокоде, иногда величают алгоритмом потенциро­
вания справа-налево^ поскольку он перебирает знаки показателя,
начиная от самого младшего, т. е. стоящего справа.
Можно реализовать этот метод и с помощью вызова рекурсив­
ной функции. Приведенная ниже программа, написанная на языке
Haskell^ реализует двоичное потенцирование по модулю т. Для вы­
числения а^ (mod т) используется процедура bin^pow а m п, опре­
деляемая следующим образом:

bin_pow : : I n t -> I n t -> I n t -> I n t
bin_pow a m n
I n == 0 =1
I n 'mod' 2 == 0 = bin>.pow ((a*a) 'mod' m) m (n ' d i v ' 2)
I otherwise = (a*t) 'mod' m
где t = bin_pow ((a*a) 'mod' m) m ((n-1) ' d i v ' 2)

В большинстве случаев возведение в квадрат осуществляется бы­
стрее, чем общее умножение. Следовательно, чтобы еще больше со­
кратить время вычислений, стоит попытаться уменьшить количе­
ство общих умножений. Это можно сделать, применяя технику окон,
которая использует заранее вычисленные значения.
Чтобы лучше понять этот новый метод, вновь обратимся к стан­
дартному двоичному потенцированию. Но на этот раз вместо ва­
рианта справа-налево^ мы начнем со старшего разряда показате­
ля, осуществляя вариант слева-направо двоичного потенцирования.
Предположим, что мы находим у = х^ (modn), и введем обозначе-
290 Глава 11. Реализация операций

ПИЯ А^ля двоичного представления показателя:
t

i=o
где di G {0,1}. Алгоритм слева-направо двоичного потенцирования
выполняется следующим образом:


y=i;
for ( i = t ; i>=0; i ˜ )
{ У = (y*y)7.n;
if (d[i]==l)
{ у = (у*х)У.п; } }

Здесь обрабатывается один бит показателя за каждый проход
цикла. При этом число возведений в квадрат равно t, а ожидаемое
число общих умножений — t/2,
В оконном методе за один раз учитывается w знаков показателя.
Сначала заполняется таблица заранее вычисленных значений
Хг = х^ (mod п) для г = О,..., 2^ — 1.
Потом показатель представляется в виде

t/w


г=0
где di € { 0 , 1 , . . . ,2*" — 1}. Реализация оконного метода выглядит
так:

y=i;
for (i=t/w; i>=0; i ˜ )
{ for (j=0; j<w; j++)
{ У = (y*y)'/.n; }
j=d[i];
У = (y*x[j])7.n; }

Проследим за действиями алгоритма с шириной окна го = 3 на
примере вычисления у = х^^^ (modn). Разложим показатель по сте­
пеням 2^:
215 = 3 • 2^ + 2 • 2^ + 7.
11.2. Алгоритмы возведения в степень

Тогда


у = у.Х^ = Х^, у = у.х'^= х'^^, у = у-Х^= Ж^^^.
В оконном методе по-прежнему требуется t возведений в квадрат,
но число общих умножений уменьшается в среднем до t/w. Можно
добиться еще больших успехов, если применить метод скользящего
окна, в котором показатель представляется в виде




где di G {1,3, 5, • • • 2^ — 1}, а ei^i — Ci ^ w. Выбирая лишь нечетные
значения р^ля коэффициентов d^, и меняя ширину окна, мы дости­
гаем экономии памяти на хранение заранее найденных значений и
увеличиваем эффективность вычислений. Считая, что уже опреде­
лены степени х[г] = х'^ р,ля г = 1, 3, 5, . . . , 2^ — 1, представим метод
скользящего окна на псевдокоде:

y=i;
for ( i = l ; i>=0; i ˜ )
{ for (j=0; j < e [ i + l ] - e [ i ] ; j++)
{ У = (y*y)7.n; }
j=d[i];
У = (y*xCj])7.n;
}
for (j=0; j < e [ 0 ] ; j++)
{ у = (у*у)У.п; }

Тут число возведений во вторую степень по-прежнему остается рав­
ным t, а число общих умножений сокращается в среднем до I до
t/{w 4- 1). В нашем примере вычисления у = х^^^ (modn) происхо­
дит следующее:
215 = 3 • 2^ + 2^ + 7;

y=h У = У' = х'\ У = у''= х''\
у = у,х^ = Х^, у = У'Х = Х^^, у = У'х'^ = х'^^^.
Обратите внимание на то, что все описанные нами оконные ме­
тоды применимы для возведения в степень в любой абелевой группе,
а не только в кольце вычетов. Следовательно, их можно использо­
вать для вычисления а^ в конечном поле или [d]P на эллиптической
Глава 11, Реализация операций

кривой, хотя в последнем случае происходит умножение точки на
число.
В случае эллиптических кривых легко вычисляются обратные
элементы, т. е. по данной точке Р достаточно просто можно опре­
делить точку —Р. Это позволяет разработать знаковые двоичный и
оконный методы. Ограничимся рассказом о знаковом оконном ме­
тоде. Сначала вычисляют
Pi = \i]P для г = 1,3,5,... 2^-^ - 1,
т. е. лишь половину значений, требуемых р^ля скользящего оконного
метода, или четверть необходимых данных в стандартном оконном
методе. Теперь представляем показатель в виде


i=0
где di G {±1, ± 3 , . . . , ±(2^"^ — 1)}. Знаковый оконный метод вычи­
сления степеней на эллиптических кривых представлен следующим
алгоритмом на псевдокоде:

Q=0;
for ( i = l ; i>=0; i ˜ )
{ for (j=0; j < e [ i + l ] - e [ i ] ; j++)
{ Q = [2] Q; }
j=d[i];
if (j>0) { Q = Q + P [ j ] ; }
else { Q = Q - P[-j]; }
}
for (j=0; j < e [ 0 ] ; j++)
{ Q = [2] Q; }



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

11.3Л. Шифрование (проверка подписи) в RSA
Как уже было отмечено в предыдущих главах, часто применяются
достаточно небольшие открытые (шифрующие) экспоненты, напри­
мер, Е — 3^ 17 или 65 537. Причина, по которой выбираются такие
значения, состоит в том, что эти числа имеют небольшой вес Хем-
минга, фактически наименьший из возможных для открытых RSA-
ключей, а именно, 2. Поэтому двоичный метод или любой другой
разумный алгоритм потенцирования будет использовать лишь одно
общее умножение и к возведений в квадрат, где к — число двоичных
знаков открытой экспоненты. Например,
М^ = М^' М, М^^ = М^^'М = (((М2)2)2)2 . М.

11.3.2, Распхифровывание (подписывание) в RSA
В случае расшифрования или подписывания сообщения в алгоритме
RSA показатель вычисляемой степени будет общим 1000-битовым
числом. Следовательно, нам нужен какой-нибудь путь сокращения
числа операций. К счастью, мы знаем секретный ключ,а значит и
разложение модуля алгоритма на множители: N = pq. При расши­
фровывании сообщения приходится вычислить
т^-С^ (modAT).
Для ускорения процесса сначала найдем т по модулям р и q:
тпр = С^ (modp) = С^ (modp-i) (modp),
rriq = С^ (modq) = С^ (^odq-i) (jnodg).
Поскольку p и q — числа порядка 2^^^, на эти действия потребует­
ся два потенцирования с показателем в 512 знаков по модулю 512-
битового числа. Это существенно быстрее, чем одно потенцирова­
ние с 1024-битовым показателем по модулю числа с 1024 двоичными
знаками.
Теперь предстоит восстановить т по тПр и т ^ , что можно сде­
лать с помощью китайской теоремы об остатках. Вычисляем
t = р"^ (mod^) и храним его вместе с секретным ключом, а со­
общение т восстанавливается по схеме:
и = {тпд — mp)t (mod^),
т = гпр + up.
Как раз ^1,ля ускорения вычислений и надо хранить р и q вместе
с секретным ключом, как было замечено в главе 7, хотя с точки
зрения математики в этом нет никакой необходимости.
Глава 11. Реализация операций

11.4. Потенцирование в DSA
Напомним, что при проверке подлинности подписи в алгоритме DSA
нам необходимо вычислить
R = G^Y^.
Это можно сделать, поочередно возводя в степень сначала G, по­
том У, а затем перемножая полученные значения. Однако зачастую
проще возводить в степень эти элементы одновременно. Существу­
ет множество методов, реализующих эту идею, которые используют
различные варианты оконной техники или что-либо похожее. Но все
они по сути эксплуатируют один трюк, называемый приемом Ша-
мира.
Сначала заполняется поисковая таблица
Gi = G'^Y'\
где г = (ioih) — двоичное представление числа г = 0,1,2,3. За­
тем заполняется массив показателей, исходя из данных А и В. Его
размерность — 2 х t, где t — максимум из числа знаков А и В. Стро­
ки массива — двоичное представление показателей А и В. Через Ij
(j = 1, . . . , t) обозначаются числа, чье двоичное представление зада­
ется столбцами этого массива. Наконец, параметру г присваивают
единичное значение и вычисляют
г = г^ - Gj. р,ля j от 1 до t.
В качестве примера найдем г = G^^Y'^. В этом случае t = 4.
Сначала мы вычисляем
Go = 1^ Gi = G^ G2 = Y^ Gs = G • Y.
Поскольку в двоичной системе счисления числа 11 и 7 имеют вид
^10116^ и '111Ь', массив показателей будет таким:




Отсюда находим Iji
/1 = 1, /2 = 2, 7з = 3, /4 = 3.
Таким образом, четыре шага алгоритма выглядят следующим обра­
зом:
г = Gi = G,
11.5. Арифметика многократной точности

r^r^.Gs = {G^- Y^) . (G • У) - G^ • У ^
г = г^^Оз = {G^^ ' Y^). (G • У) = G^^ • F ^
Заметим, что уловку, аналогичную приему Шамира, в случае эл­
липтических кривых можно разработать, используя знаковое пред­
ставление показателя. Мы не станем объяснять здесь модификацию
метода для кривых, а оставим это пытливым читателям как воз­
можность для приложения своих способностей.


I 1.5. Арифметика многократной точности
Здесь объясняется, как осуществляются арифметические действия
в кольце вычетов по 1024-значным модулям. Мы покажем, как эти
действия реализуются на современных процессорах и почему наив­
ные алгоритмы заменяются специализированной техникой, предло­
женной Монтгомери.
В криптографических приложениях арифметики остатков обыч­

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

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

ОГЛАВЛЕНИЕ

Следующая >>