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

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

ОГЛАВЛЕНИЕ

Следующая >>

но фиксируется количество знаков чисел, над которыми совершают­
ся действия, например, 1024 битов для алгоритмов RSA и DSA^ и 200
битов для алгоритмов, основанных на эллиптических кривых. Это
приводит к возможности выбора различных программ из библио­
теки «арифметика многократной точности». В результате вопросы
динамического распределения памяти снимаются и можно сосредо­
точиться на ускорении процесса.
Целые числа в компьютере представляются в так называемом
«малословном» формате, т. е. если большое целое число х хранится в
компьютере в виде набора XQ^XI^ ,.. ^Хп^ то XQ — наименьшее знача-
щее слово, а, х^ — наибольшее. Например, в 32-разрядных машинах
64-битовое число х хранится в виде двух 32-битовых слов: [j^o^^i]?
г д е X = XI

11.5.1. Сложение
Большинство современных процессоров имеют специальный при­
знак переноса, учитываюш;ий добавочное слагаемое к следуюш,ему
разряду при побитовом сложении. Кроме того, существуют специ­
альные функции, обычно называемые чем-то вроде addc, которые
складывают два целых числа с учетом признака переноса. Так, ес­
ли мы хотим сложить два 64-битовых числа х = xi - 1?^ + жо и
у — У\- 2^^ -f уо? нам нужно вычислить:
г = ж + 2/ = 2 2 • 2^^ + ;^i • 2^^ + Z^.
^
Глава 11. Реализация операций

Значения Zi определяются следующим образом:

zO <- add хО,уО
zl <- addc х1,у1
z2 <- addc 0,0

Заметим, что значение Z2 не превышает 1 и ;г может оказаться
65-битовым числом. Описанная техника сложения двух 64-битовых
целых чисел может быть без труда обобш;ена на сложение чисел лю­
бой фиксированной длины. Е^ можно использовать и при вычитании.

11.5.2. Умножение в столбик
Теперь обратимся к следуюш;ей простейшей арифметической опе­
рации, идуш;ей после сложения и вычитания, а именно, к умноже­
нию. Заметим, что при умножении двух 32-битовых чисел получится
64-битовое, и, естественно, большинство современных процессоров
оснап1;ено операцией, осуш;ествляюш;ей это действие.
Wi - W2 = {Высший^ Низший) = {H{wi • W2)^L{wi • W2))»

При стандартном умножении в столбик мы получаем что-то вроде
таких вычислений:


X У1_ Уо_
Н{хо • Уо) Цхо ' Уо)
Цхо • Ух)
Н{хо -yi)
H{xi • уо) L{xi • Уо)
Я(ж1-у1) L{xi'yi)
Затем все четыре строки складываются и получается искомый от­
вет Z = X -у. При этом, естественно, необходимо следить за перено­
сами разрядов. На псевдокоде процесс умножения выглядит следу­
ющим образом.

(zl,zO)<-mul хО,уО
(z3,z2)<-mul х1,у1
(h,l) <-mul х1,уО
zl <-add zl,l
z2 <-addc z2,h
11.5. Арифметика многократной точности 297

z3 <-addc z3,0
(h,l) <-mul xO,yl
zl <-add zl,l
z2 <-addc z2,h
z3 <-addc z3,0


Если n обозначает битовый размер целых чисел, над которыми про­
изводятся действия, то описанный выше способ перемножения тре­
бует 0(р?) операций над битами, а сложение и вычитание — 0{п).
Возникает естественный вопрос: можно ли умножить числа быстрее,
чем за 0{ri^) операций?

11.5.3. У м н о ж е н и е К а р а ц у б ы
Один из методов ускорения умножения носит название умножения
Карацубы. Предположим, нам нужно перемножить два п-битовых
числа ж и у. Запишем их в виде
х - а ; о + 2^/2:г1, у - Уо + 2^/2yi,
где О ^ жо,Ж1,уо7У1 < 2"^/^. Умножение происходит с помощью вы­
числений:
A = XQ' УО,
В = {x^^xi) • (yo + yi),
С = xi -уь
Ответ получается в результате преобразований:
С2^ + (Б - А - С)2^/2 + А = ;^iyi2^ + {хт + xoyi)2^/2 + хоуо =
= {xo + 2^/^xi)'{yo + 2^/^yi)=X'y,
Легко заметить, что при этом было использовано три умножения
и два сложения (п/2)-битовых чисел, и три операции сложения-
вычитания над п-битовыми числами. Обозначив через М{п) коли­
чество операций, необходимых для умножения п-битовых чисел, а
через А{п) — А^ЛЯ ИХ сложения или вычитания, получим следующее
соотношение:
М{п) = ЗМ(п/2) + 2А(п/2) + ЗА(п).
Используя аппроксимацию А{п) ^ п, замечаем, что
М{п) ^ ЗМ(п/2) + 4п.
Глава 11. Реализация операций

Если умножение n/2-битовых чисел происходит по той же схеме,
то решая полученное рекуррентное соотношение, найдем, что при
п -^ оо
М{п) ^ 9 п 1 ^ ^ 9п^'^^.
Итак, у нас есть алгоритм с асимптотической сложностью 0(п^'^^).
Умножение Карацубы выполняется заметно быстрее, чем умноже­
ние в столбик, если умножаются числа, количество знаков в кото­
рых насчитывает несколько сотен. Однако можно умножать еш;е
быстрее. Сложность наиболее эффективного из известных методов
оценивается как
O(nlnnlnnlnn).
Но ни этот последний метод, ни умножение Карацубы не исполь­
зуются в криптографических приложениях. Причины станут ясны
после обсуждения деления.

11.5.4. Д е л е н и е
После знакомства с умножением перейдем к самой сложной арифме­
тической операции — делению. Оно необходимо, в частности, д^ля
определения остатков от деления двух целых чисел — основной за­
дачи арифметики остатков, а значит и RSA.
Итак, для данных двух целых х иу чисел мы хотим найти такие
^ и г, что X = qy -\- г^ причем, как обычно, О ^ г < у. Напомним,
что такое деление называется делением с остатком или евклидовым
делением.
Представим делимые числа в малословном формате
Х== {хо,..,,Хп) и у= (уо,-..,Угг),

где основание разложения равно Ь = 2^, и обозначим через t « v
сдвиг целого числа t влево на v слов, т.е. результат умножения t
на Ь^. При этих соглашениях алгоритм на псевдокоде выглядит так:

г=х;
/* Тривиальный случаи */
if (t>n)
{ q=0; return; }
q=0; s=0;
/* Нормализуем делитель */
while (y[t]<b/2)
{ y=y*2; r=r*2; s++; }
if (r[n+l3!=0) { n=n+l; }
11.5. Арифметика многократной точности 299^

/* Получаем частное */
while (r>=(y«(n-t)))
{ q[n-t]=q[n-t]+l;
r=r-(y«n-t);
}
/* Разбираемся с остатком •/
for (i=n; i>=t+l; i — )
{ if (r[i]==v[t])
{ q[i-t-l]=b-l; }
else
{ д[1-г-1]=целая_часть( (x[i]*b+r[i-l] )/y[t] ); }


if (t!=0) { rhsjn = y[t]*b+y[t-l] ; }
else { rhsjn =y[t]*b; }
rhs=q[i-t-l] •rhsjn;


if (i!=l) { Ihs = x[i]*b*b+r[i-l]*b+r[i-2]; }
else { Ihs = x[i]*b*b+r[i-l]*b; }


while (rhs>lhs)
{ q[i-t-l]=q[i-t-l]-l;
rhs=rhs-rhs-m;
}
r=r-(q[i-t-l]*y)«(i-t-l);
if (r<0)
{ r=r+(y«i-t-l);
q[i-t-l]=q[i-t-l]-l;
}
}
/* Перенормировка */
for (i=0; i<s; i++) { r=r/2; }

Как видите, это очень сложная операция. Поэтому ее следует
избегать по мере возможности.

11.5.5. Арифметика Монтгомери
Поскольку деление больших целых чисел — операция сложная, все
наши криптографические действия будут идти очень медленно, если
мы будем использовать стандартный метод деления, представлен­
ный в предыдущем параграфе. Напомним, что практически все кри-
Глава 11. Реализация операций

птосистемы с открытым ключом работают с арифметикой остат­
ков. Поэтому нам хотелось бы уметь вычислять остатки от деления,
не прибегая к дорогостоящей операции деления. На первый взгляд
это кажется невозможным, но если прибегнуть к специальной ариф­
метике Монтгомери, то все окажется не так страшно.
Эта арифметика работает с альтернативным представлением це­
лых чисел — представлением Монтгомери. Обозначим через b сте­
пень двойки, показатель которой — длина слов в нашем компьюте­
ре, т.е. b = 2^^ или 6 = 2^^. Выберем целое число Д, удовлетворяю­
щее неравенству R = Ь^ > N. Теперь вместо числа х будем хранить
в памяти компьютера величину х • R (mod N) в малословном форма­
те. Значение х • R (mod N) называется представлением Монтгомери
числа X (modiV).
Сложение двух целых чисел в этом представлении осуществля­
ется просто. Нам даны х • R (modN) и у • R (modA^), а нам нужно
вычислить Z • R mod iV, где z = х + у. Представим нужное вычи­
сление на псевдокоде:

zR = xR + yR
if (zR>=N) { zR-=N; }

Для прояснения его работы разберем пример.
7V = 1073 741827, Ь = Д = 2^^ = 4 294 967 296.
Запишем числа 1, 2 и 3 в представлении Монтгомери:
1 1 • R (mod N) = 1073 741815,
2 2 . R (mod N) = 1073 741803,
3 3 • R (modiV) = 1073741791.
Теперь мы можем проверить работу сложения, поскольку в стан­
дартном представлении результат нам известен: 1 + 2 = 3. В пред­
ставлении Монтгомери это действие отражается следуюпщм образом:
1073 741815 + 1073 741803 = 1073 741791 (modiV).
Посмотрим, как происходит умножение в арифметике Монтго­
мери. Если просто перемножить два элемента в представлении Монт­
гомери, то получим:
(xR) • (yR) = xyR^ (modiV).
Но нам нужно вычислить xyR (modiV). Следовательно, нам придет­
ся еще разделить результат стандартного умножения на R. Посколь­
ку i? — степень двойки, мы надеемся, что этот процесс окажется
11,5, Арифметика многократной точности 301

не очень сложным. Пусть, в общей ситуации, нам нужно вычислить
Z = y/R (modTV). Сделаем это с помощью редукции Монтгомери.
Сначала вычисляется целое число q = 1/N (modi?), которое мож­
но найти не делением, а с помощью двоичного алгоритма Евклида.
Затем осуществляем шаги, записанные на псевдокоде на следующей
странице.

u=(-y*q)7oR;
z=(y+u*N)/R;
if (z>=N) { z-=N; }

Заметим, что редукция по модулю i?, которая происходит в первой
строке алгоритма, является легкой операцией: мы вычисляем про­
изведение традиционным способом, а редукцию осуществляем про­
стым обрезанием результата^. Действительно, ведь R — степень
числа Ь. Деление на i?, происходящее во второй строке, тоже вполне
доступно: поскольку y + u-N = О (modi?), мы просто сдвигаем наше
представление числа на t слов вправо (потому что R = Ь^).
В качестве примера опять возьмем
7V = 1073 741827 и ft = i? = 2^^ = 4 294 967 296.
Вычислим произведение 2 • 3 с помощью арифметики Монтгомери.
Напомним, что
2 2 • R (mod N) = 1073 741803,
3 3 • i? (mod N) = 1073 741791.
Прибегая к стандартному алгоритму умножения, получаем
w = X'y = l 152921446624789 173 = 2 • 3 • i?^
Теперь нам нужно перевести значение w в представление Монтго­
мери. Находим
w = 1152 921446 624 789 173,
q = (l/N) (modi?) = 1789569 707,
u = -w-q (mod i?) = 3 221225 241,
z = {w + U' N)/R = 1073 741755.
Таким образом, результатом произведения х иу в арифметике Монт­
гомери служит число
1073 741755.
^Обратите внимание, что 123456 (mod 100) = 56. — Прим. перев.
Глава 11. Реализация операций

Можно убедиться в корректности ответа, подсчитав,

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

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

ОГЛАВЛЕНИЕ

Следующая >>