Високопродуктивна реалізація протоколів захисту інформації на базі операцій медулярної арифметики

РАЗДЕЛ 2.
Ускорение выполнения модулярного умножения чисел
большой разрядности при фиксированном модуле
Операция модулярного умножения является базовой для большинства протоколов
защиты информации в сетях. При этом целесообразно рассматривать два различных
варианта ее использования: для выполнения отдельного умножения и как составной
части модулярного экспонен­цирования.
2.1. Основные обозначения и модель оценки эффективности
алгоритмов модулярного умножения
При описании и анализе обработки чисел большой разрядности на k-разрядном
процессоре обычно используется представление целых чисел по основанию b, где b
– количество чисел, представимых k–разрядным двоичным кодом: b = 2k . При этом
n-разрядное число А представляется в виде А={as-1,…,a1,a0}, 0Ј aj < b,
"jО{0,…,s-1}:
Для анализа операций модулярной арифметики и корректного выполнения следующих
ниже преобразований важное значение имеют следующие основные свойства
модулярной арифметики [39]:
Если , то
Если , то ,
только если А и М – взаимно-простые.
Базовой операцией модулярной арифметики, используемой в алгоритмах защиты
информации является модулярное умножение, то есть вычисление R=AЧB mod M.
Полагается, что результат R, множитель A, множимое B и модуль M представляют
собой n-разрядные двоичные числа, причем, старший разряд модуля равен единице:
2n-1 Ј M < 2n , а сомножители меньше модуля: Aоперация модулярного умножения выполняется на k-разрядном процессоре общего
назначения (микропроцессоре или микроконтроллере). Соответственно, каждое из
чисел, участвующих в операции модулярного умножения может быть представлено в
виде s=n/k –разрядных слов:
где aj, bj, mj – k-разрядные слова, jО{0,…,s-1}.
В отличие от классического алгоритма [22] модулярного умножения, современные
алгоритмы [52] не используют операции деления, которая неэффективно реализуется
на процессорах общего назначения. Исходя из этого, в качестве критерия оценки
производительности программной реализации алгоритмов модулярного умножения
обычно рассматривается суммарное время выполнения операций умножения и
сложения: основных операций современных алгоритмов модулярного умножения [15].
Полагается, что результатом команды умножения двух k-разрядных чисел является
2Чk-разрядное произведение. Если обозначить через qm – коли­чество требуемых
команд умножения (время выполнения каждой такой команды полагается равным tm),
а через qa – количество команд сложения (при этом ta – время выполнения каждой
такой команды), то в качестве оценки времени выполнения модулярного умножения
над n-разрядными числами можно с приемлемой для сравнительного анализа
точностью считать . Если полагать, что времена выполнения команд умножения и
сложения на процессоре соотносятся как w = tmul/ta , то время выполнения
модулярного умножения может быть представлено в следующем виде: .
Постоянство модуля М позволяет упростить выполнение модулярной редукции в
процессе умножения за счет использования результатов пред­вычислений. Такие
предвычисления зависят только от значения модуля М, а поэтому выполняются
однократно при изменении модуля. Результаты предвычислений сохраняются в
табличной памяти и используются много­кратно при каждом выполнении модулярного
умножения.
При реализации модулярного умножения, часть вычислительных ре­сур­сов
используется на выполнение собственно умножения, а другая часть – на нахождение
остатка. В различных алгоритмах модулярного умно­жения удельный вес затрат на
эти две процедуры различен. В таблице 1 приведено количество операции умножения
и деления слов, используе­мое в наиболее известных алгоритмах модулярного
умножения для вычисле­ния произведения АЧВ и выполнения модулярной редукции
[3].
Модулярная редукция С = X mod M, X=KЧM+C, где K-априори неизвестное m-разрядное
целое число, а Х- заданное (m+n)-разрядное число, предусматривает циклическое
выполнение последовательности операций сравнения и вычитания, для q, которое
меняется от m до 0:
1. q:=m;
2. сравнения X с 2qЧM: если X<2qЧM, переход на п.3.
3. вычитание X:=X-2qЧM;
4. q:=q-1, если qі0, возврат на п.2.
При этом сравнение X с 2qЧM выполняется, начиная со старших разрядов до первого
разряда, в котором сравниваемые коды отличны. Очевидно, что при больших
разрядностях чисел, время сравнения существенно меньше времени вычитания, так,
что среднее время выполнения операции модульной редукции, в основном,
определяется длительностью реализации m операций вычитания: mЧtc., tc – время
выполнения операции типа суммирование-вычитание.
Очевидно, что возможности уменьшения числа операций для вычисления произведения
АЧВ за счет предвычислений при постоянном модуле весьма ограничены, поскольку
сам модуль непосредственно не используется в таких вычислениях. Поэтому,
основным резервом повышения скорости программной реализации модулярного
умножения является использование предвычислений для снижения вычислительной
сложности модулярной редукции.
Основным источником повышения производительности является использование
следующего преобразования:
X mod M = = ((X' mod M) + (Xўў mod M)) mod M
Если , то число Хў образовано р его младшими, а Хўў - (n+m-p) старшими
разрядами Х: , так, что Х=Хў+Хўў. Если pЈn-1, то Xў mod M = Xў, в силу того,
что Xўравномерно распределено в интервале от 0 до M, то среднее значение (Xўў mod M)a
= Ma/2=2n-1 = 2n-2+2n-3. Если p=n-1, Xўa= 2n-2 и, следовательно, среднее
значение Xў+(Xўў mod M) составляет Xўa+(Xўўmod M)a = 2n-1+2n-3. Вероятность
того, что Xў+(Xўў mod M) > M примерно равна 0.25. Если p=n-2 эта