Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 9.2.3 Методы ускорения операции сложения Вверх: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках Назад: 9.2.1 Представление чисел   Содержание   Предметный указатель

9.2.2 Ускоренное вычисление

Традиционное выполнение операции $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ выглядит как последовательное выполнение умножения $ P=A*B$ (что приводит к размерности $ P$, равной $ 2n$) и модульной редукции $ P\mskip-\medmuskip\mkern5mu \mathbin{\rm modulo}\penalty900 \mkern5mu\mskip-\medmuskip N$. Однако, этот процесс не следует считать ни быстрым, ни экономичным и лучше прибегнуть к выполнению операции методом "цифра-за-цифрой": сначала вычисляется $ P=A*B[i]$ (где размерность $ P$ равна $ n+1$), а затем $ P\mskip-\medmuskip\mkern5mu \mathbin{\rm modulo}\penalty900 \mkern5mu\mskip-\medmuskip N$. Процесс организуется по всем цифрам $ B[i]$. Рассмотрим несколько возможных алгоритмов для этого метода. На рис. 1 приведен псевдокод алгоритма модулярного умножения, предложенного в [HDVC].

Рис. 1. Алгоритм модулярного умножения $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$, использующий операции умножения/деления (алгоритм 1)
\begin{figure}\par\centerline{\it Алгоритм 1}\par\bigskip\centerline{\vbox{\tt ... ...$); \symbol{''7B}\textrm{$\widehat P$~--- результат}\symbol{''7D}}}}\end{figure}

И хотя авторы признаются, что это не самый эффективный алгоритм из-за наличия в нем операций $ \widehat P\mskip-\medmuskip\mkern5mu \mathbin{\rm DIV}\penalty900 \mkern5mu\mskip-\medmuskip \widehat N$, $ \widehat Q*\widehat N$ и $ \widehat P-\widehat Q*\widehat N$, тем не менее при аппаратной реализации за счет введения небольшой заранее вычисленной таблицы (так как частное $ \widehat Q$ принимает значения только 0, 1, 2 и 3) быстродействие данного алгоритма может быть повышено. Действительно, скорость одного RSA-шифрования при использовании такого алгоритма для 512-битовой экспоненты составляет 17 Кбитов/сек, однако платой за это служат размеры схемы, которые соответствуют размерам карманного калькулятора -- $ 13{,}9\times6{,}4$ см, что не позволяет использовать данный метод для интеллектуальных карточек. Есть несколько разновидностей подобного алгоритма, каждая из которых удобна для программной реализации. Однако для $ n$-разрядных параллельных процессоров лучше свести операцию модулярного умножения к чередованию операций сложения/вычитания/сдвига. Это приведет к большей асимптотической эффективности алгоритма, что "$ \ldots$ можно интуитивно объяснить тем, что умножение выполнить труднее, чем сложение и для достаточно больших $ n$ любое фиксированное число $ n$-разрядных сложений требует меньше времени, чем $ n$-разрядное умножение, независимо от того, какой из (известных) алгоритмов применяется" [АХУ, стр. 79-80].

Опишем несколько схем реализации такого процесса [ORSPT].

Рис. 2. Алгоритм модулярного умножения $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ (алгоритм 2)
\begin{figure}\par\centerline{\it Алгоритм 2}\par\bigskip\centerline{\vbox{\tt ... ...}write($S$); \symbol{''7B}\textrm{$S$~--- результат}\symbol{''7D}}}}\end{figure}

Достоинства алгоритма 2 в том, что $ P$ и $ S$ положительны, однако текущий результат $ S$ может требовать два последовательных сложения на 1 бит множителя.

Рис. 3. Алгоритм модулярного умножения $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ (алгоритм 3)
\begin{figure}\par\centerline{\it Алгоритм 3}\par\bigskip\centerline{\vbox{\tt ... ...}write($P$); \symbol{''7B}\textrm{$P$~--- результат}\symbol{''7D}}}}\end{figure}

Достоинства алгоритма 3 в том, что требуются только два слагаемых, но, как и в алгоритме 2, необходимы два последовательных сложения на 1 бит множителя.

Рис. 4. Алгоритм модулярного умножения $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ (алгоритм 4)
\begin{figure}\par\centerline{\it Алгоритм 4}\par\bigskip\centerline{\vbox{\tt ... ...}write($P$); \symbol{''7B}\textrm{$P$~--- результат}\symbol{''7D}}}}\end{figure}

Скорость вычислений по алгоритму 4 выше чем у алгоритмов 2, 3, однако требуется дополнительная память для хранения $ P+N$, $ P-N$, $ P-2N$.

Существует еще несколько способов повышения быстродействия рабочих алгоритмов вычисления $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$. Так, в [ORSPT] даны два из них. Один заключается во введении в алгоритм асимметричных временных фаз. Например, в алгоритме 2 во время формирования очередного текущего результата $ S$, в случае, если $ S<0$, выполняется $ S\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=S+P$; а если $ S>0$, то $ S\,\rlap{\raisebox{3.5pt}{\rm .}}\raisebox{1.1pt}{\rm .}\mspace{-4mu}=S+2P-2N$. Время выполнения каждой из ветвей алгоритма в таком случае будет неодинаково, что требует асинхронного управления. Другой способ заключается в использовании на каждом шаге не одного бита $ B[i]$, а сразу двух разрядов множителя $ B$. За счет этого вдвое сокращается число временных периодов, хотя требуется две последовательные операции сложения в каждом периоде. Техника этого алгоритма, который известен под названием Modified Booth's Algorithm (MBA) изложена в [ORSPT]. Следует отметить еще один немаловажный момент -- во всех приведенных выше алгоритмах выполняется сравнение вида $ S>N$ или $ P<0$ или $ 2*P>N$. Однако, не следует забывать, что мы имеем дело с числами большой размерности, и на такое сравнение уйдет достаточно много времени. В то же время для некоторых алгоритмов в [Se] показано, что для сравнения при выполнении модульной редукции достаточно 10 старших битов операндов. А в [Bak] для сравнения $ P$ и $ N$ используются лишь 3 старших бита $ N$ и 6 старших битов $ P$.

Алгоритм, который предложил Бейкер в [Bak], и который является, в сущности, модификацией алгоритма 3, -- один из наиболее удачных алгоритмов для быстрого вычисления $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$, что обусловлено эффективной реализацией сравнения многоразрядных чисел и применением сложения CSAs.

Поскольку операция $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ носит фундаментальный арифметический характер и вряд ли в ближайшее время найдется какое-то принципиально новое решение, резко увеличивающее быстродействие подобных операций, то при условии удачной реализации алгоритма Бейкера в технические решения на хорошем технологическом уровне, такая СБИС будет вполне конкурентоспособна на рынке аналогов, по крайней мере с точки зрения пространственно-временных характеристик. Временная сложность алгоритма и количество логических элементов, необходимых для его реализации, оцениваются как $ O(n)$.

Выбор какого-то конкретного из описанных алгоритмов для реализации его в интеллектуальных карточках зависит от многих факторов. В частности, должны учитываться: наличие асинхронного устройства управления, установленные временные критерии, уровень технологической базы, стоимостные ограничения и др.


$ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$-алгоритм B [Bak]

Пусть $ A$, $ B$ и $ N$ -- три $ n$-битовых положительных двоичных числа, где $ n$ достаточно большое и $ A,B<N$. Пусть $ P$ представлено как двоичное частичное произведение в избыточной форме с явным представлением сохраняемого переноса (CARRY-SAVE REDUNDANT FORM). Операнд $ P$ состоит из 2 компонент: суммы $ P_s$ и переноса $ P_c$. Для каждой из компонент ($ P_s$ и $ P_c$) необходимо $ n+3$ бита. Вычисление $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ требует повторения сложения $ B[i]*A$ и $ P$, $ i\in[1,\ldots,n]$ одновременно с вычитанием $ N$ (или $ 2*N$) из $ P$ или сложением $ N$ (или $ 2*N$) и $ P$, где $ P$ ограничено абсолютным значением $ N$ в конце каждой итерации. Выбор одной из ветвей алгоритма B осуществляется на основе операции сравнения, для которой используются 3 старших бита $ N$, называемых $ N\!\_short$ и 6 старших, образованных в каждой итерации, битов P, называемых $ P\!\_short$. На рис. 5 показаны размерности операндов, а на рис. 6 -- псевдокод алгоритма B.

Рис. 5. Размерности $ N\!\_short$, $ P\!\_short$ и $ N$, $ P$ для алгоритма B
\begin{figure}\bigskip\centerline{\vbox{ \hbox{\phantom{\vrule width.4pt height1... ...6.2pt height11.5pt depth-11.1pt}\hbox to17pt{\hss$1$\hss}}}}\bigskip\end{figure}

Рис. 6. Алгоритм модулярного умножения $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ -- алгоритм B
\begin{figure}\par\centerline{\it Алгоритм B}\par\bigskip\centerline{\vbox{\tt ... ...$); \symbol{''7B}\textrm{$\widehat P$~--- результат}\symbol{''7D}}}}\end{figure}


Алгоритм $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ -- алгоритм P

Ниже описывается оригинальный алгоритм выполнения операции модулярного умножения.

Операнды многократной точности для данного алгоритма представляются в виде одномерного массива целых чисел (см. рис. 7). Для знака можно зарезервировать элемент с нулевым индексом. Размер элемента обсуждался в п. 9.2.1, а особенности представления чисел при организации взаимодействия алгоритма с другими рабочими программами, при организации ввода-вывода и т. д. рассматриваются, например, в [Hu]. Нижеописанный алгоритм является, по существу, модификацией алгоритма 1 за счет введения некоторых оригинальных приемов. В алгоритме использован известный вычислительный метод "разделяй и властвуй" и реализован способ вычисления "цифра-за-цифрой". Прямое умножение не следует делать по нескольким причинам: во-первых, произведение $ A*B$ требует в два раза больше памяти, чем при методе "цифра-за-цифрой"; во-вторых, умножение двух многоразрядных чисел труднее организовать, чем умножение числа многократной точности на число однократной точности. Так, в [BW] приводятся расчеты на супер-ЭВМ "CRAY-2" для 100-разрядных десятичных чисел: модулярное умножение методом "цифра-за-цифрой" выполняется примерно на 10% быстрее, чем прямое умножение и следующая за ним модульная редукция.

Рис. 7. Размерности $ N\!\_short$, $ P\!\_short$ и $ \widehat N$, $ \widehat P$ для алгоритма P
\begin{figure}\bigskip\centerline{\vbox{ \hbox{\phantom{\vrule width.4pt height1... ...box to54.4pt{\ $2$\hss}\hskip4pt\hbox to54.4pt{\hss$1$\ }}}}\bigskip\end{figure}

Рис. 8. Алгоритм модулярного умножения $ A*B\mskip -\medmuskip \mkern 5mu\mathbin {\rm modulo}\penalty 900\mkern 5mu\mskip -\medmuskip N$ -- алгоритм P
\begin{figure}\par\centerline{\it Алгоритм P}\par\bigskip\centerline{\vbox{\tt ... ...$); \symbol{''7B}\textrm{$\widehat P$~--- результат}\symbol{''7D}}}}\end{figure}

Алгоритм P приведен на рис. 8, на рис. 9 представлен псевдокод процедуры ADDK.

Рис. 9. Алгоритм вычисления $ \widehat P+k*\widehat N$ (процедура ADDK)
\begin{figure}\par\centerline{\it Алгоритм 5}\par\bigskip\centerline{\vbox{\tt ... ...$); \symbol{''7B}\textrm{$\widehat P$~--- результат}\symbol{''7D}}}}\end{figure}

Так как $ \widehat B[i]\in[0,2^{\lambda/2}-1]$, то проверку "if $ \widehat B[i]\neq0$" в алгоритме P можно не вводить потому, что вероятность того, что $ \widehat B[i]$ будет равняться 0 достаточно мала, если значение $ \lambda$ не слишком мало. Ошибка затем все равно будет алгоритмом обнаружена. Проверка "if $ p\_short-k*n\_short>n\_short\mskip-\medmuskip\mkern5mu \mathbin{\rm DIV}\penalty900 \mkern5mu\mskip-\medmuskip 2$" позволяет представлять $ k$ числом однократной точности и работать с наименьшими абсолютными остатками в каждой итерации. Значение операнда $ \widehat P$ на каждом шаге итерации должно быть ограничено величиной  $ \widehat N$.

Теорема 1.  Пусть $ \widehat P_i$ -- частичное произведение $ \widehat P$ в конце $ i$-ой итерации (т. е. в конце $ i$-ого цикла FOR алгоритма P). Тогда для любого $ i$, $ i=1\dots n$ $ \qopname\relax o{abs}\left(\widehat P_i\right)<\widehat N$, $ r^{m-1}\leqslant\widehat N\leqslant r^m$.

В алгоритме P используется известный метод, когда для получения частного от деления двух многоразрядных чисел, используются только старшие цифры этих чисел (см., например, алгоритм D в [Кнут, стр. 291-295]). Чем больше основание системы счисления $ r$, тем ниже вероятность того, что пробное частное ($ k$) от деления первых цифр больших чисел не будет соответствовать действительному частному.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 9.2.3 Методы ускорения операции сложения Вверх: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках Назад: 9.2.1 Представление чисел   Содержание   Предметный указатель

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100