В криптографии и криптоанализе часто бывает необходимо сложить две последовательности чисел или же вычесть одну из другой. Такое сложение и вычитание производится, как правило, не с помощью обычных арифметических действий, а с помощью операций, называемых модульной арифметикой. В модульной арифметике сложение, вычитание выполняется относительно некоторого фиксированного числа, которое называется модуль. Типичными значениями модулей, используемые в криптографии, являются 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