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

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

ОГЛАВЛЕНИЕ

Следующая >>

6 • R (mod TV) - 1073 741 755.
Итак, мы увидели, что арифметика Монтгомери позволяет нам скла­
дывать и умножать остатки от деления на АГ, не привлекая дорого-
стояш;ую операцию деления.
Описанный метод редукции Монтгомери использует два полных
умножения. Поэтому умножая два числа в арифметике Монтгоме­
ри, мы затратим три умножения. Если сомножители насчитывают
по 1024 бит, то результат будет состоять из 2048 знаков. Нам бы
хотелось чуть сэкономить и мы можем сделать это.
Предположим, у задан в малословном формате
У= (2/0,2/b.--,y2t-2,y2t-l).

Тогда наилучший способ осуш;ествления редукции Монтгомери за­
ключается в том, что используется заранее вычисленная величина
N' = -l/N (modb),
которая определяется сравнительно легко. Делаем следуюш;ее:

z=y;
for (i=0; i < t ; i++)
{ u=(zi*N07ob;
z+=u*N*b;
}
z/=R;
i f (z>=N) { z-=N; }

Заметим, что ввиду редукции по модулю b в первой строке цикла,
мы можем выполнить начальное умножение, используя алгоритм
умножения слов. Второй шаг цикла требует сдвига на одно слово
(умножение на Ь) и одного умножения слова на большое целое чис­
ло. Следовательно, мы сокраш;аем число больших промежуточных
результатов в редукции Монтгомери.
Можно также чередовать умножение с редукцией, ограничива­
ясь одним проходом цикла и получая
Z = XY/R (modAT).
Так что если X = xR и?
= = yR^ то
Z = {xy)R (modiV).
1L6, Арифметика в конечных полях 303

Эта процедура называется умножением Монтгомери и позволяет
вычислять произведения в арифметике Монтгомери, не прибегая
к большим целыми числам. Перемежающаяся версия представлена
«программой»

Z=0;
for (i=0; i < t ; i++)
{ u=((zO+Xi*YO)*NOy.b;
Z=(Z+Xi*Y+u*N)/b;
}
if (Z>=N) { Z-=N; }

Хотя сложность умножения Монтгомери оценивается как 0(р?)^ в
отличие от 0{'п}'^^) — сложности умножения Карацубы, — предпо­
чтительнее использовать арифметику Монтгомери, поскольку она
более эффективна в арифметике остатков.


11.6. Арифметика в конечных полях
Кроме полей вычетов по простому модулю р в криптографии ис­
пользуются поля четной характеристики. Такие поля встречаются,
например, в алгоритме Rijndael и в некоторых системах, основан­
ных на эллиптических кривых. В Rijndael поле настолько мало, что
можно использовать поисковые таблицы или специальные микросхе­
мы для реализации основных арифметических действий, поэтому в
этом параграфе мы будем разбираться с полями над F2 большой сте­
пени, такими, которые, например, используются в эллиптических
кривых. Кроме того, нас будут интересовать только программные
реализации операций. На аппаратных средствах операции в полях
характеристики 2 могут реализовываться с помощью так называе­
мых оптимальных нормальных базисов, но мы не будем здесь этого
касаться.
Напомним, что для задания конечного поля характеристики 2
мы выбираем неприводимый многочлен f{x) с коэффициентами из
F2 степени п и рассматриваем факторкольцо:


т.е. работаем с двоичными многочленами по модулю f{x). Элемен­
ты такого поля обычно представляются строкой бит, изображаю­
щей двоичный многочлен. Например, строка битов
101010111
Глава 11, Реализацуя операций

представляет многочлен


Сложение и вычитание элементов поля ?2^ осуществляется простым
поразрядным сложением битов строки по модулю 2. Поэтому труд­
ность могут представлять только действия умножения и деления.
Оказывается, деление, хотя и более медленная операция, чем умно­
жение, описывается проще. Так что начнем с него. Чтобы вычи­
слить а/^, где а, y G F2n, сначала находят /3˜^, после чего ищут
S
произведение аф˜^. Таким образом, деление сводится к умножению
и вычислению обратного элемента. Один из способов обращения эле­
мента состоит в применении теоремы Лагранжа, которая говорит,
что для любого /3 7^ О
/32"-1 = 1.
Следовательно,
^ • ^2"-2 = 1, т. е. Г' = / 9 ' " - ' = ^2(2-^-1).
Второй способ вычисления /0˜^ связан с двоичным алгоритмом Ев­
клида. Берем многочлен / , определяющий поле, Ь, представляющий
элемент /3, и применяем следующую версию двоичного алгоритма
Евклида, где Isb (b) — наименьший значащий бит строки b (други­
ми словами, коэффициент при х^).

a=f;
В=0;
D=l;
/ * По крайней мере один из а и Ъ теперь имеет свободный член
на каждом проходе цикла.
*/
while (а != 0) do
{ while (lsb(a)=0)
{ а=а»1;
i f (lsb(B)!=0) { B=B˜f; }
B=B»1; }
}
while (lsb(b)=0)
{ b=b»l;
i f (lsb(D)!=0) { D=D˜f; }
D=D»1;

/* Сейчас как a так и b имеют свободный член */
11.6. Арифметика в конечных полях 305

if (deg(a)>=deg(b))
{ a=(a-b); 6=6-^0; }
else
{ b=(a-b); D=D-B; }
}
вывести D;

Обратимся к операции умножения. В отличие от целых чисел
по модулю ЛГ, где мы применяли специальные методы арифмети­
ки Монтгомери, в полях характеристики 2 существует возможность
выбора многочлена f{x)^ обладающего «хорошими свойствами». Лю­
бой неприводимый многочлен степени п можно использовать для
построения конечного поля ?2-^ • Так что нам нужно лишь взять наи­
более удобный.
Почти всегда многочлен f{x) выбирают среди трехчленов
f{x)=x'' + x^ Л-1
или пятичленов
f{x) = а;^ + х^^ + х^^ + х^' + 1.
Замечено, что для всех полей, степень которых не превышает 10 000,
всегда можно подобрать трехчлен или пятичлен, сильно облегчаю­
щий операцию умножения. В таблице 11.1, размещенной в конце этой
главы, приводится список всех значений п, лежащих между 2 и 500,
с примерами трехчленов или пятичленов, определяющих поле ?2п.
Во всех случаях, где можно подобрать трехчлен, мы его вписыва­
ем в таблицу. В противном случае представляем соответствующий
пятичлен.
Теперь, чтобы перемножить элементы а и /5, мы сначала перем­
ножаем представляющие их многочлены и получаем многочлен 7(^)7
степень которого не превышает 2п — 2. После этого нам необходимо
вычислить остаток от деления 7(^) на многочлен f{x).
Покажем, как это делать, если f{x) — трехчлен, оставив случай
пятичлена в качестве упражнения. Записываем
j{x) =^i{x)x'' + jo{x),
где deg 71(^)5 deg7o(^) ^ n — 1. Тогда
7(ж) (mod/(a:)) = 7о(ж) + (x^ + 1)71 (^).
Правую часть этого уравнения можно вычислить с помощью поби­
товых операций:
^ = 70 ©71© (71 <fc)-
Глава 11. Реализация операций

Степень многочлена 5 не может превышать п — \-\-к. Повторим эту
процедуру, представив 8 в виде
8{х) =5х{х)х'' + 6Q{X),
гдedegJo(^) ^ п —1 и deg5i(a;) ^ А —1. Значит 7(^) (mod/(x)) равен
;
битовой строке, полученной с помощью формулы:


Степень У — max(n — 1,2fc — 1). Поэтому если наш трехчлен f{x) вы­
бран так, что к < п/2, то действия, описанные в следующем абзаце,
завершат деление с остатком.
Пусть д — многочлен степени 2п — 2, который нам нужно при­
вести по модулю / (т.е. найти остаток от деления ^ на / ) , причем
оба многочлена представлены строками битов. Тогда делаем такие
шаги:

gl=g»n;
gO=g[n-1..0];
g=g0^gr(gl«k);
gl=g»n;
gO=g[n-1..0];
g=g0^gr(gl«k);

Для завершения рассказа об умножении элементов поля F2n нам
осталось объяснить, как реализовать умножение двоичных много­
членов степени ^ п — 1.
Здесь тоже можно применить наивный алгоритм умножения. До­
вольно часто для умножения многочленов, степень которых меньше
восьми (они представляются одним байтом), применяются поиско­
вые таблицы, т. е. что-то вроде таблицы умножения, а многочлены
большей степени умножаются в столбик, как в школьном алгорит­
ме. Сложность такого умножения описывается функцией 0(71^)^ где
п — степень перемножаемых многочленов.
Предположим, что у нас есть таблица умножения всех двоичных
многочленов степени < 8. Тогда степень произведений будет мень­
ше 15. Функцию, сопоставляющую паре 8-битовых многочленов а
и Ь их произведение, обозначим через Mult_Tab(a,b). Приведем ал­
горитм умножения общих п-битовых многочленов, обозначив через
у » 8 сдвиг строки вправо на 8 бит.

z=0; i =0;
while (х!=0)
11.6, Арифметика в конечных полях 307

{ и=у; j=0;
while (u!=0)
{ w=Mult_Tab(x&255,u&255);
w=w«(8*(i+j)) ;
ans=ans"w;
u=u»8; j=j+l;
}
x=x»8; i=i+l;
}
Как и при умножении целых чисел, здесь применима техника
«разделяй и властвуй», основанная на умножении Карацубы. Ее слож­
ность будет оцениваться как 0(п^'^^). Допустим, нам нужно перем­
ножить два многочлена
а = ао + x'^/'^ai и 6 = Ьо + x'^/'^bi,
где ао, ai, Ьо, bi — многочлены степени меньшей чем п/2. Поступа­
ем следующим образом:
А = ао -Ьо,
В = («о + ai) • (fto + bi),
С = ai - bi.
Произведение a • b получается по формуле:
Cx^' + iB-A- С)х'''^ + Л = aibix"" + (aibo + aobi)a:^/^ + аоЬо =
- (ao + x'^/'^ai) . (6o + x'^'Hi) = a-b.
Умножая ao на bo и т. д., мы вновь применим умножение Карацу­
бы рекуррентным образом. И как только сведем умножение к вы­
числению произведений многочленов степени 7 и ниже, воспользу­
емся таблицей умножения. В отличие от случая целых чисел, здесь
умножение Карацубы эффективнее алгоритма умножения в столбик
даже р,ля вычисления произведения многочленов достаточно малой
степени п ^ 100.
Следует отметить, что возведение в квадрат многочленов над
полем характеристики 2 вообще практически ничего не стоит. Пусть
дан многочлен
а = ао + aix + а2Х^ + asx^,
где а{ равно О или 1. Его квадрат получается простым «прорежива­
нием» коэффициентов:
а = ао -\- aix^ Ч- а2х'^ + а^х^.
Глава 11. Реализация операций

Происходит это благодаря формуле, справедливой над любым полем
характеристики 2: {А + В)'^ = А? -\- В^. Таким образом, возведение
в квадрат над полем характеристики 2 — очень быстрая операция
в сравнении с общим умножением.

К р а т к о е с о д е р ж а н и е главы

- Возведение в степень в арифметике остатков или в любой дру­
гой конечной абелевой группе можно осуш;ествить с помош;ью
метода двоичного потенцирования. Часто оконный метод ока­
зывается более эффективным, а для эллиптических кривых
можно применять знаковое потенцирование.
- Алгоритм RSA можно оптимизировать. В качестве открытой
экспоненты нужно выбирать число не только малое, но и обла-
даюш;ее наименьшим весом Хемминга. В процедуре расшифро­
вания нужно использовать информацию о разложении модуля
алгоритма N на простые сомножители и китайскую теорему
об остатках.
- В процедуре проверки подписи алгоритма DSA суш;ествует ме­
тод одновременного возведения в степень, который оказыва­
ется эффективнее способа, при котором каждая из степеней
вычисляется отдельно, а потом перемножаются результаты.
- Основные действия в арифметике остатков реализуются с по-

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

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

ОГЛАВЛЕНИЕ

Следующая >>