Методы и задачи криптографической защиты информации. Мартынов А.И. - 86 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

Арифметика вычетов очень похожа на обычную арифметику: она
коммутативна, ассоциативна и дистрибутивна. Кроме того, приведение каждого
промежуточного результата по модулю n дает тот же результат, как и
выполнение всего вычисления с последующим приведением конечного
результата по модулю n.
(a + b) mod n == ((a mod n) + (b mod n)) mod n
(a - b) mod n == ((a mod n) - (b mod n)) mod n
(a * b) mod n == ((a mod n) * (b mod n)) mod n
(a * (b+c)) mod n == (((a*b) mod n) + ((a*c) mod n)) mod n
Вычисление mod n часто используется в криптографии, так как
вычисление дискретных логарифмов и квадратных корней mod n может быть
нелегкой проблемой. Арифметика вычетов, к тому же, легче реализуется на
компьютерах, поскольку она ограничивает диапазон промежуточных значений
и результата. Для k-битовых вычетов n, промежуточные результаты любого
сложения, вычитание или умножения будут не длиннее, чем 2
k
бит.
Поэтому в арифметике вычетов мы можем выполнить возведение в
степень без огромных промежуточных результатов. Вычисление степени
некоторого числа по модулю другого числа, a x mod n, представляет собой
просто последовательность умножений и делений, но существуют приемы,
ускоряющие это действие. Один из таких приемов стремится минимизировать
количество умножений по модулю, другой - оптимизировать отдельные
умножения по модулю. Так как операции дистрибутивны, быстрее выполнить
возведение в степень как поток последовательных умножений, каждый раз
получая вычеты. Сейчас вы не чувствуете разницы, но она будет заметна при
умножении 200-битовых чисел.
Например, если вы хотите вычислить a 8 mod n, не выполняйте наивно
семь умножений и одно приведение по модулю:
(a * a * a * a * a * a * a * a) mod n.
Вместо этого выполните три меньших умножения и три меньших
приведения по модулю:
((a
2
mod n)
2
mod n)
2
mod n
.
Точно также,
a
16
mod n =(((a
2
mod n)
2
mod n)
2
mod n)
2
mod n.
Вычисление a
x
, где x не является степенью 2, ненамного труднее.
Двоичная запись представляет x в виде суммы степеней двойки: 25 – это
бинарное 11001, поэтому 25 = 2
4
+ 2
3
+ 2
0
. Поэтому:

Страницы