Компьютерная безопасность. Криптографические методы защиты - Петров А.А.
ISBN 5-89818-064-8
Скачать (прямая ссылка):
Необходимо отметить, что RSA критичен также к адаптивной атаке с выбором зашифрованных сообщений. Этот метод основан на гомоморфных свойствах RSA. Другими словами, для любых открытых сообщений Hi1 и т2 и для соответствующих зашифрованных сообщений C1 и C2 выполняется следующее равенство: (In1In2)6= mfmf= C1C2 (mod п).
1.3.4. Методы ускорения вычислений, применяемых в асимметричных алгоритмах
Одной из основных проблем, возникающих при использовании асимметричных алгоритмов, является низкая скорость проведения операций зашифрования/расшифрования. Этот факт особенно характерен для реализаций алгоритмов на устройствах с небольшими вычислительными
60
Общие сведения по классической криптографии
возможностями (реализация ЭЦП на интеллектуальных карточках). Один из выходов - уменьшение размерности параметров системы, но, как показано в разделе 1.3.5, это чревато уменьшением стойкости алгоритма.
Другим решением этой же проблемы является применение эффективных процедур проведения основных видов математических вычислений, используемых в асимметричных алгоритмах шифрования. Причем эффективность в зависимости от ситуации может трактоваться не только как высокая скорость работы, но и как минимальный объем памяти, минимальный программный код и их совокупность. Суть большинства методов ускорения вычислений заключается в том, чтобы свести операции модульного умножения и возведения в степень к выполнению последовательности операций модульного сложения/вычитания.
Алгоритм модульного умножения
Выполнение операции AxB mod п обычным путем, то есть умножение А на В и затем применение модульной редукции, не является ни быстрым и экономичным способом умножения. Данное вычисление гораздо лучше выполнить, используя, например, разложение числа В вида В = Ъп\п + + ЪпЛХп~1 + ... + D1A, + Ь0 и последовательное умножение вида с = Ab; (при этом получаются числа с размерностью n + 1), а затем вычислить mod п. (рис. 1.14).
F=O Q=O
for i from n to 0 do begin: F=2*F+Ab. Q=IF/n| F=F-Q*n
end Рис. 1.14
return ( F ) Алгоритм ускоренного модулярного умножения AXB mod п
По мнению авторов данного алгоритма, он не является одним из самых действенных алгоритмов модулярного умножения. Среди более эффективных следует отметить алгоритм умножения (см. рис. 1.15).
Модульное возведение в степень ABmod п
Проведение операции модульного возведения в степень путем последовательного умножения числа А самого на себя, применяющейся для зашифрования/расшифрования в RSA, требует большого объема памяти
Асимметричные алгоритмы шифрования
61
P = A
P = P-N
(A-N) = P
for i from n to 0 do begin:
P = 2 * P Реализуется сдвигом влево.
if b. = 1 then
begin:
if В < 0 then P = P + A
else P = P + (A-N) end
if P < 0 then P = P + N
else P = P-N Рис. 7.75
end Алгоритм модулярного умножения
return (F) AXB mod n
для хранения полученных чисел и времени. Для решения этой проблемы существует метод последовательного возведения в квадрат, с помощью которого можно добиться, чтобы не возникали числа, большие А2, и при этом существенно возросла скорость возведения в степень. Суть его состоит в следующем:
1. В представляется в двоичном виде:
В = ?х(2!, где X1 = 0 + 1 и k = [log2B] + 1.
i=0
2. Затем вычисляются числа вида (A2 mod п, где i- 0 -г к); данные вычисления требуют к возведений в квадрат.
3. Далее числа A2 mod п последовательно перемножаются с одновременным сведением по mod п; этих операций будет не более k - 1.
Таким образом, получаем не более 2k - 1 операций модулярного умножения с числами, меньшими п. Данный метод разрешается модернизировать за счет сокращения числа ненулевых X1 в битовом представлении В: В = ЪпХп + Iv1A"-1 + ... + hiX + b0, где bn & 0,0 < bj < X, i = 0 + п. Выбор основания X производится в соответствии с представлениями чисел в машине. Так, при употреблении двоичного представления числа используется на 20% меньше памяти, нежели при двоично-десятичном представлении.
Модульная редукция X mod п
Суть метода заключается в вычислении значения г = X mod п (рис. 1.16), для чего предварительно вычисляется ц = [Я2к/п]. Эти числа можно запомнить, если выполняются многократные вычисления с использованием
62
Общие сведения по классической криптографии
данного модуля, при этом X является основанием в разложении числа X; обычно на практике его значение принимается равным разрядности процессора.
Входные значения:
X = X215-1X24"1+ ... +X1A + х0;
n = nK-iAk"1+ •¦• +niX + no Ч-1*°>; [X2k/n] .
q,= [х/Л*-1]
q3= [q2/Xk+1] г = x mod Ak+1 T2 = q3n mod Ak+1
r = r - r
1 2
if r < 0 then r = r + Ak+1
while r> = ndo: r = r-n Рис. 1. 16
return (г) Модульная редукция методом Барето
Несмотря на то что в представленном алгоритме производится большое количество операций деления, все они легко реализуются с помощью правого сдвига по основанию X. При этом необходимо учитывать, что q2 используется для вычисления q3. В связи с этим в q2 используется только k + 1 младших разрядов. .
1.3.5. Практическое применение
Асимметричные алгоритмы используются в основном для решения задачи распределения сеансовых ключей по общедоступным каналам передачи данных. То есть симметричный ключ передается зашифрованным при помощи асимметричного алгоритма шифрования, и дальнейший обмен данными производится с использованием симметричных алгоритмов шифрования. Алгоритмы подобного рода также применяются в процедурах генерации и проверки электронно-цифровой подписи (ЭЦП). Хотя в общем случае эти алгоритмы нужны для зашифрования/расшифрования данных, но для длинных сообщений их использование в связи с низкой скоростью работы оказывается неэффективным. Например, алгоритм RSA в 1000 раз медленнее алгоритма DES.
