Модульная арифметика

В криптографии и криптоанализе часто бывает необходимо сложить две последовательности чисел или же вычесть одну из другой. Такое сложение и вычитание производится, как правило, не с помощью обычных арифметических действий, а с помощью операций, называемых модульной арифметикой. В модульной арифметике сложение, вычитание выполняется относительно некоторого фиксированного числа, которое называется модуль. Типичными значениями модулей, используемые в криптографии, являются 2, 10 и 26. Какой бы модуль мы ни взяли, все встречающиеся числа заменяются на остатки от деления этих чисел. Если в остатке получается отрицательное число, то к нему прибавляют значение модуля, чтобы остаток стал неотрицательным. Например, если используется модуль 26, то единственно возможные числа лежат в диапазоне от 0 до 25. Так, если прибавить 17 к 19, то результат равен 10, поскольку 17+19 = 36, а 36 при делении на 26 дает остаток 10. Чтобы указать, что используется модуль 26, принята форма записи:

17+19=10(mod26).

Если вычесть 19 из 17, то результат (-2) получается отрицательным, поэтому к нему прибавляется 26, и в итоге получается 24.

При сложении по модулю 26 двух числовых последовательностей сформулированные правила сложения применяются в каждой паре чисел по отдельности, без «переноса» на следующую пару. Аналогично, при вычитании по модулю 26 одной числовой последовательности из другой правила вычитания применяются к каждой паре чисел по отдельности, без «заимствования» из следующей пары.

Пример 1.1

Сложить по модулю 26 последовательности 15 11 23 06 11 и 17 04 14 19 23

 

Решение

11 23 06 11

17 04 14 19 23

32 15 37 25 34

06 15 11 25 08

и в результате 06 15 11 25 08

Если модуль равен 10, то используются числа от 0 до 9; при модуле 2 – только 0 и 1

Арифметика по модулю 2, или, как ее обычно называют, двоичная (бинарная) арифметика, имеет особое значение, поскольку в этом случае сложение и вычитание являются идентичными операциями, т.е всегда дают одинаковый результат, а именно:

0 0 1 1 0 0 1 1

+ 0 1 0 1 - 0 1 0 1

0 1 1 2 0 -1 1 0

0 1 1 0 0 1 1 0 (mod 2) в обоих случаях.

Модульное сложение и вычитание букв

Давайте рассмотрим пример модульного сложения и вычитания применимо к буквам.

Прибавить TODAY к NEVER по модулю 26

Вычесть TODAY из NEVER по модулю 26

Решение

TODAY= 19 14 03 00 24

NEVER= 13 04 21 04 17

Сумма = 32 18 24 04 41 06 18 24 04 15 = GSYEP

 

TODAY= 19 14 03 00 24

NEVER= 13 04 21 04 17

Разность = 06 10 -18 -04 07 06 10 08 22 07 = GKIWH