Теория и практика защиты программ

Алгоритм A*B modulo N - алгоритм выполнения операции модулярного умножения


Операнды многократной точности для данного алгоритма представляются в виде одномерного массива целых чисел. Для знака можно зарезервировать элемент с нулевым индексом. Особенности представления чисел при организации взаимодействия алгоритма с другими рабочими программами, при организации ввода-вывода и т.д. рассматриваются, например, в работе [Hu]. В алгоритме использован известный вычислительный метод «разделяй и властвуй» и реализован способ вычисления «цифра-за-цифрой». Прямое умножение не следует делать по нескольким причинам: во-первых, произведение A*B

требует в два раза больше памяти, чем при методе «цифра-за-цифрой»; во-вторых, умножение двух многоразрядных чисел труднее организовать, чем умножение числа многократной точности на число однократной точности. Так, в работе [BW] приводятся расчеты на супер-ЭВМ «CRAY-2» для 100-разрядных десятичных чисел: модулярное умножение методом «цифра-за-цифрой» выполняется примерно на 10% быстрее, чем прямое умножение и следующая за ним модульная редукция. Алгоритм модулярного умножения (алгоритм P) приведен на рис.2.2, а на рис.2.1 представлен псевдокод процедуры ADDK.

Алгоритм ADDK

carry:=0;

for i:=1 to m do

begin

t:=P[i]+k*N[i]+carry;

P[i]:=t

mod r;

carry:=t div r;

end;

P[m+1]:=carry;

write(P); {P - результат}



Рис.2.1. Псевдокод алгоритма вычисления P+k*N

(процедура ADDK)

Так как B[i]Î[0,...,2l/2-1], то проверку «if B[i]<>0» в алгоритме P можно не вводить потому, что вероятность того, что B[i] будет равняться 0 пренебрежимо мала, если значение l

не достаточно мало. Ошибка затем все равно будет алгоритмом обнаружена. Проверка

«if p_short-k*n_short>n_short DIV 2»

позволяет представлять k числом однократной точности и работать с наименьшими абсолютными остатками в каждой итерации. Значение операнда Pi на каждом шаге итерации должно быть ограничено величиной N.

Теорема 2.1.

Пусть Pi - частичное произведение P в конце i-той итерации (т.е.
в конце i-того цикла FOR алгоритма P). Тогда для любого i (i=[1,...,n]) abs(Pi)<N, rm-1£N£rm.

Доказательство.

Доказательство теоремы проведем методом индукции.

Если k=abs(p_short) DIV n_short, где DIV - целочисленное деление, то

p_short=(k+d)*n_short,                                                   (2.1.6)

где k - целое, 0£k<r-1 и 0£d<1.

Проверка «if p_short-k*n_short> n_short DIV 2» есть ни что иное, как проверка

d>0.5                                                                               (2.1.7)

На i-том шаге алгоритм вычисляет:

P'=Pi-1*r+A*B[i]                                                                                                                                                                                                                                                                                                                                                                                                                  (2.1.8)

Алгоритм P

m_shifts:=0;

while n[m_shifts]=0 do

begin

shift_left(N and A);

m_shifts:=m_shifts+1;

end;

m:=m_shifts;

reset(P);

n_short:=N[m];

for i:=n downto 1 do

begin

shift_left(P); {сдвиг на 1 элемент влево или умножение P*r}

if b<>0 then

addk(A*B[i],{to}P);

let p_short represent the 2 high assimilated digits of P;

k:=abs(p_short) div n_short;

if p_short-k*n_short>n_short div 2 then k:=k+1;

if k>0 then

begin

if p_short<0 then

addk(k*N,{to} P)

else

addk(-k*N,{to} P);

end;

end;{for}

right shift P, N by m_shifts;

if P<0 then

P:=P+N;

write(P); {P - результат}

Рис. 2.2. Псевдокод алгоритма модулярного умножения A*B modulo N

Возможны два варианта:

Вариант 1. Если k=0, т.е. n_short>abs(p_short) (см. алгоритм), то суммирование при помощи процедуры ADDK не производится и утверждение теоремы выполняется, т.е.


abs(Pi)<N.

Вариант 2. Если k>0, т.е.

n_short<abs(p_short)                                                      (2.1.9)

Здесь также возможны два варианта:

Вариант A:

p_short<0                                                                                                                                                                                                                                                                                                                                                                                                                                              (2.1.10)

Из (2.1.9) и (2.1.10) следует P'<-N и так как Pi=-P'+k*N

(см. алгоритм), то согласно (2.1.7)

Pi=d*N,                            если d£0.5                               (2.1.11)

и так как Pi=-P'+(k+1)*N, то

Pi=-(1-d)*N,                                                                                                                                                                                          если d>0.5                                                                                                                                                                                                                            (2.1.12)

Вариант B:

p_short>0                                                                        (2.1.13)

Из (2.1.9) и (2.1.13) следует P'>N и так как Pi=P'-k*N, то согласно (2.1.7)

Pi=-d*N,                           если d£0.5                               (2.1.14)

и так как Pi=P'-(k+1)*N, то

Pi=(1-d)*N,                      если d>0.5                               (2.1.15)

Во всех случаях (2.1.11), (2.1.12), (2.1.14) и (2.1.15), так как 0£d<1, то abs(Pi)<N.

Теорема доказана n.

Примечание. Для чего нужна проверка (2.1.7)

«if p_short-k*n_short>n_short DIV 2» ?

Пусть в конце каждой итерации P



принимает максимально возможное значение Pi-1=N-1, а N, A и B[i] заведомо тоже велики: N=rn+1-1, A=rn+1-2, B[i]=r-1. Тогда на i-том шаге согласно (2.1.8):

Pi'=(rn+1-2)*r+(rn+1-2)*(r-1)=2*rn+2-rn+1-4*r+2                  (2.1.16)

                             (2.1.17)

При достаточно большом m, если не введена проверка (2.1.6), то k<2*r-1, по условию же 0<k<r-1. И из (2.1.16) и (2.1.17) видно, что P

придется представлять m+2 разрядами (что определяется слагаемым 2*rn+2), по условию же m+1. Если же ввести проверку (2.1.7), то даже при d=0,5 т.е.

Pi-1=(N-1)/2 и с учетом того, что если неравенство (2.1.7) выполняется, то Pi

меняет знак на противоположный (сравн. (2.1.11), (2.1.12), (2.1.14) и (2.1.15)), из (2.1.6) и (2.1.7) получим, что 0£k<(1/2)*r-1, что удовлетворяет наложенному на k

условию, и для представление P

достаточно m+1 разряда.

В алгоритме P

используется также известный метод, когда для получения частного от деления двух многоразрядных чисел, используются только старшие цифры этих чисел (см., например, алгоритм D

в работе [Кн, стр.291-295]). Чем больше основание системы счисления r, тем меньше вероятность того, что пробное частное k от деления первых цифр больших чисел не будет соответствовать действительному частному.

Методы доказательства правильности программ могут быть применены при разработке ПО при существенных ограничениях на размеры и сложность создаваемых программ. И в частных случаях они могут оказаться более эффективными, чем другие известные методы анализа программ, которые исследуются в следующих разделах данной работы.

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY


Содержание раздела