Код плюс аддитивное шифрование

Независимо от того, сколько кодовых групп содержится в коде, при наличии достаточного количества сообщений криптоаналитик рано или поздно выявит повторяющиеся кодовые группы, даже если одним и тем же словам и фразам открытого текста сопоставлены несколько альтернативных кодовых групп. К тому же, если кодовая книга попала в руки противника, дешифрование всех сообщений становится тривиальным. Для преодоления этих слабостей сами кодовые группы обычно шифруют. Стандартным способом шифрования является сложение кодовых групп с аддитивной гаммой с использованием модульного сложения, то есть сложения без переноса. И хотя мы уже упоминали об этом раньше, давайте вспомним, как это делается, и рассмотрим пример. Допустим, у нас есть кодовая группа 6394, а гамма для сложения с ней равна 2798. Выпишем цифры кодовой группы и подпишем знаки гаммы непосредственно под ними; теперь сложим без переноса цифры, стоящие в одном столбце - например, при сложении последних цифр кода и гаммы (4 и 8) записывается сумма 2, а не 12. Иначе говоря, складывается цифра за цифрой, по модулю 10. Итак, имеем:

Кодовая группа 6394

Гамма 2798

Сумма 8082,

и шифрованный текст равен 8082. Для других кодовых групп гамма будет другой, так как на практике она либо не повторяется вовсе, либо, если и повторяется, то только через очень большое число знаков. Поскольку при зашифровании гамма складывается с кодовыми группами, получателю, чтобы получить кодовые группы и расшифровать сообщение, необходимо вычесть гамму из шифрованного текста цифра за цифрой, по модулю 10. Итак:

Шифрованный текст 8082

Гамма 2798

Кодовая группа 6394.

Очевидно, что теперь кодовые группы замаскированы, и стойкость системы значительно повысилась при условии, что гамма не повторяется достаточно долго. Предметом значительного интереса математиков и криптографов являются вопросы выработки последовательностей цифр, которые не повторяются в течение многих тысяч знаков. Более подробно мы поговорим об этом в главе 8. Здесь же для иллюстрации рассмотрим простой метод, который порождает последовательность, повторяющуюся через 60 цифр.

Пример 6.2

Построить последовательность цифр, начиная с цифр 3 и 7, в которой каждая следующая цифра получается сложением двух предыдущих по модулю 10.

Решение

Последовательность начинается с цифр

3 7,

поэтому следующая цифра равна (3+7)=10, что дает 0(mod 10); четвертая цифра будет равна (7+0)=7; пятая цифра равна (0+7)=7. Продолжая вычисления таким образом, получаем последовательность следующего вида:

3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4

9 3 2 5 7 2 9 1 0 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0...

Эта последовательность начинает повторяться после 60 цифр, на что указывают три последние подчеркнутые цифры, совпадающие с тремя первыми. Так как каждая цифра является суммой двух предыдущих по модулю 10, то такая гамма начинает повторяться, как только в ней встретятся 2 цифры, которые уже появлялись в этой последовательности в том же порядке. Отсюда следует, что никакая последовательность модуля 10, полученная таким образом, не может иметь период больше 100, поскольку существует только 100 различных пар цифр модуля 10. Последовательность из приведенного примера, имеющая период 60, в действительности имеет самый длинный период из возможных. Если бы мы положили обе первые цифры равными нулю, то получили бы последовательность из одних нулей. Такая последовательность, будучи использованной в качестве гаммы, оставила бы кодовые группы без изменения.

Хотя последовательность знаков гаммы из примера 6.2 является самой длинной из возможных для данного простого метода, она, к сожалению, имеет некоторые числовые свойства, делающие ее непривлекательной с криптографической точки зрения. Во-первых, что особенно плохо, в ней две трети цифр - нечетные, и только одна треть - четные, а желательно иметь примерно поровну и тех, и других. Это происходит потому, что данная последовательность построена по очень простому четно-нечетному шаблону, что сразу бросается в глаза, а именно:

нечет нечет чет нечет нечет чет ...

Другое свойство состоит в том, что в ней регулярно, через каждые 15 позиций, встречаются сдвоенные знаки (77, 99, 33 и 11). Данная конкретная последовательность очень хорошо известна и представляет собой частный случай последовательности, которая, пожалуй, является самой интенсивно изучаемой последовательностью в математике. В своей обычной форме она начинается с 0 и 1 в качестве первых двух знаков и вычисляется далее, как и в приведенном примере, только без приведения по модулю 10, то есть применяется обычное сложение. Начало последовательности выглядит так:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597...

Элементы последовательности возрастают с потрясающей скоростью (выражаясь математическим языком, они растут "экспоненциально"). Каждый следующий элемент, начиная с 5-го, более чем в полтора раза превосходит предыдущий, и, например, сотый элемент последовательности записывается с помощью 21 цифры. Если привести все эти числа по модулю 10, то есть оставить от каждого только по младшей цифре, то получим

0 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7...,

то есть ту же самую последовательность из нашего примера, начиная с 48-й позиции. Эта последовательность, начинающаяся с цифр 0 1 1..., называется последовательностью Фибоначчи. Впервые в математический обиход ее ввел Леонардо из Пизы, известный также под именем Фибоначчи. Произошло это в тринадцатом столетии. Более подробно об этой знаменитой последовательности можно прочитать в приложении M5.

Задача 6.1

1. Получите цифровую гамму по модулю 10, как описано выше, взяв в качестве двух первых знаков цифры 0 и 2. Каков будет период, и почему эта гамма будет отвергнута криптографом?

2. Каков будет период гаммы, если начать с 1 и 3 в качестве двух первых знаков?

Последовательность чисел Фибоначчи - простейшая из принадлежащих к классу последовательностей, которые могут быть использованы при генерации гаммы для криптографического использования. Хотя ответ на вопрос, является ли та или иная последовательность "хорошей" гаммой (т.е. все ли возможные значения встречаются в ней с одинаковой частотой), может быть получен лишь с использованием методов высшей математики (см. [1.2, 1.3]). Довольно очевидное обобщение последовательности чисел Фибоначчи получается, если вычислять каждый следующий элемент последовательности как сумму (по модулю 10) трех предыдущих ее элементов. Так можно получить последовательности с большей длиной цикла, например:

Пример 6.3

Начиная с 0, 1, 1, построить последовательность, каждый раз складывая между собой (по модулю 10) три предыдущих числа.

Решение

Последовательность начинается с цифр 0 1 1 2 4 7 3 4 4 1... и повторяется через 124 шага. Частоты встречаемости отдельных цифр несколько неравновероятны: хотелось бы, чтобы каждая цифра встречалась 12 или 13 раз, однако цифра 3 встречается только 6 раз, а цифры 4 и 9 - по 18 раз. Проверить эти факты предоставляем читателю.

Если выбрать в качестве начала другие тройки цифр, можно получить циклы и покороче: 0,1,2 дает цикл длины 62, а 0,5,0 будет очень неудачным выбором, так как длина цикла в этом случае всего лишь 2.

Этим методом можно получать гамму любого модуля. Например, начиная с 0,1,1, при приведении по модулям 2, 3, 5 и 7 получаем последовательности с длинами циклов, соответственно, 4, 13, 31 и 48. Хотя эти факты и представляет интерес с число математической точки зрения, но на практике криптографы, как правило, используют в качестве модулей числа 2, 10 и 100.

Если ту же самую последовательность вычислить по модулю 100, то она начинается с чисел

00 01 01 02 04 07 13 24 44 81 49 74 ...,

и оказывается, что ее период равен 1240.

Можно модифицировать последовательность чисел Фибоначчи, чтобы немного сгладить соотношение четных и нечетных знаков, слегка улучшив ее криптографические свойства. Скромный шаг в этом направлении иллюстрирует

Пример 6.4

Постройте 20 элементов последовательности чисел Фибоначчи по модулю 100, начиная с чисел 13 и 21 в качестве двух первых элементов, а затем поменяйте местами вторую и третью цифры в каждой четырехзначной группе цифр, получив в результате 20 двузначных элементов последовательности знаков гаммы.

Решение

Первые 20 значений последовательности чисел Фибоначчи по модулю 100, начиная с 13 и 21, выглядят так:

13 21 34 55 89 44 33 77 10 87 97 84 81 65 46 11 57 68 25 93.

Меняя местами вторую и третью цифры в каждой группе из четырех цифр, получим результирующую гамму:

12 31 35 45 84 94 37 37 18 07 98 74 86 15 41 61 56 78 29 53.

Отклонение в отношении нечет:чет теперь сократилось (с 2:1 до примерно 7:5), и поэтому качество гаммы улучшилось, хотя оно нас по‑прежнему не удовлетворяет.

Задача 6.2

Буквы алфавита представляются с помощью двузначного цифрового кода следующим образом:

A=17, B=20, C=23,..., Z=92,

то есть каждое следующее значение на 3 больше предыдущего. Сообщение зашифровано с использованием этого кода и аддитивной гаммы (12 31 35...), полученной в предыдущем примере. Сложение осуществляется позначно, без переносов. Результирующий шифрованный текст выгладит так:

86 69 42 19 60 35 08 13 76 48 23 02 50 91.

Расшифруйте сообщение.