М. И. Анохин, Н. П. Варновский, В. М. Сидельников, В. В. Ященко "КРИПТОГРАФИЯ В БАНКОВСКОМ ДЕЛЕ"

Геовикипедия
wiki.web.ru

Поиск

Главная страница

Конференции: Календарь / Материалы

Каталог ссылок

Словарь

Форумы

В помощь студенту

Последние поступления

Геология | Курсы лекций

Обсудить в форуме

Добавить новое сообщение

Вперед: 9.3 Анализ возможностей использования интеллектуальными карточками вспомогательных вычислителей Вверх: 9.2 Алгоритмические проблемы реализации и применения криптографических протоколов на интеллектуальных карточках Назад: 9.2.4 Ускоренное вычисление A^e modulo N Содержание Предметный указатель

9.2.5 Альтернативный подход

Все обсуждавшиеся до сих пор методы ускорения вычислений основывались на следующем очевидном подходе: разрабатывается некоторая криптографическая схема, а затем ищутся эффективные алгоритмы выполнения операций, требуемых для ее реализации. Альтернативный и менее очевидный подход состоит в поиске эффективно вычислимых операций и в построении криптографических схем, использующих эти операции. В литературе имеется пример применения этого подхода, основанный на алгоритмах Монтгомери [Montg].

Опишем сначала алгоритмы Монтгомери [Montg]. Первый алгоритм (рис. 12) вычисляет $AB2^{-l(n)}\bmod n$ , где -- длина числа в битах, нечетно.

Рис. 12

$\begin{figure}\par\centerline{\it Алгоритм $M_n(A,B)$}\par\bigskip\centerline{\v... ... \hbox{\hspace*{0em}if $R<n$\ then return($R$) else return($R-n$)}}}\end{figure}$

Алгоритм (рис. 13) вычисляет $A^p2^{-l(n)(p-1)}\bmod n$ , где опять -- длина в битах и нечетно.

Рис. 13

$\begin{figure}\par\centerline{\it Алгоритм $E_n(A,p)$}\par\bigskip\centerline{\v... ...ox{\hspace*{1em}$e\gets M_n(e,e)$} \hbox{\hspace*{0em}return($z$)}}}\end{figure}$

Возникающие в результате выполнения этих алгоритмов паразитные множители обычно предлагается подавлять с помощью дополнительной операции модулярного умножения. Однако, это снижает выигрыш, полученный от применения ускоренных алгоритмов. В работе [NM'RR] предложена остроумная идея модифицировать вместо этого сами криптографические схемы таким образом, чтобы основными операциями в них стали и(или) . Такие модификации даны для ряда схем, включая криптосистему RSA, схему Диффи-Хеллмана, подпись Эль Гамаля и т.д.

Например, в криптосистеме RSA модификация состоит в вычислении шифртекста в виде $c=E_n(m,e)=m^eN^{e-1}$ , где $N=2^{-l(n)}$ , -- открытый ключ, -- сообщение. Получатель выполняет операцию дешифрования в виде:

$\displaystyle E_n(c,d)=c^dN^{d-1}=(m^eN^{e-1})^dN^{d-1}=m^{ed}N^{ed-1}=m\bmod n,$

где

-- секретный ключ.

В статье [NM'RR] со ссылкой на неопубликованную работу Арази (B. Arazi) приводятся два любопытных замечания. В первом из них, без дальнейших пояснений, указывается, что Арази доказал следующий факт: сложность (в смысле аппаратуры, памяти и времени) операции такая же как и у операции (без приведения по модулю). Во втором замечании более конкретно указывается следующий результат Арази: операция может быть выполнена за цикл, т.е., с той же скоростью, что и обычное умножение.

Предварительный анализ показывает, что стойкость всех модифицированных криптографических схем такая же, как у исходных. Учитывая все сказанное выше, это означает, по существу, возможность реализации криптографических схем с такой же эффективностью, как если бы все операции выполнялись в $\mathbb{Z}$ .

Михаил Анохин

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