227

aббббб+бcб=б0.

Складывая первое уравнение со вторым по модулю 2, получим

aá+ácá=á1,

что противоречит первому уравнению. Поэтому система уравнений несовместна, и ни одного решения степени3 не существует.

М13. Получение псевдослучайных чисел

В типовом приложении, например в таком, где требуются случайные числа, равномерно распределенные в интервале [0,1], целые числа, порождаемые рекуррентой, делятся на значение модуля. Если действовать таким образом в примере 8.4, то 16 приведенных в нем целых чисел необходимо разделить на 17. В результате получатся следующие 16 псевдослучайных значений (получаем два знака после запятой):

0.29, 0.12, 0.59, 0.00, 0.24, 0.94, 0.06, 0.41, 0.47, 0.65, 0.18, 0.76, 0.53, 0.82, 0.71, 0.35.

В задачах реального масштаба для получения менее предсказуемого множества значений модуль надо брать очень большим и, что еще лучше, необходимо использовать несколько линейных рекуррент, комбинируя каким-либо образом снимаемые с них последовательности. Практическое обсуждение этих вопросов, возможные наборы значений для модуля, множителя и приращения, а также полезные компьютерные программы можно найти в главе 7 работы [8.4].

Глава 9

М14. Распайка колёс шифрмашины "Энигма"

Алфавиты простой замены, которые контактное колесо "Энигмы" образует в каждом из 26 своих положений, можно представить в виде матрицы размера 26 26. В первом столбце этой матрицы стоят знаки, в которые перейдут 26 букв алфавита при зашифровании в 1-м угловом положении колеса, во втором столбце - во 2-м угловом положении, и т.д. В силу "диагонального свойства" вся матрица оказывается полностью определена, как только выписан ее первый столбец.

228

Кроме того, в первой строке матрицы содержатся знаки, в которые перейдет буква A при зашифровании в каждом из 26 угловых положений колеса. И снова, благодаря "диагональному свойству", матрица оказывается полностью определенной, как только выписана ее первая строка.

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

Чтобы сделать рассуждения более наглядными, мы вместо букв будем использовать числа. В первом столбце матрицы 26 26 должна содержаться некоторая перестановка чисел (0, 1, 2, ... , 25); обозначим ее через

(a1, a2, ..., a25, a26).

Поскольку это перестановка чисел (0, 1, 2, ... , 25), то отсюда следует, что сумма

a1+a2+...+a25+a26 = 0+1+2+...+24+25 = 325 13(mod 26).

С другой стороны, числа, стоящие в верхней строке данной матрицы, равны (по модулю 26)

(a1, a26+1, a25+2,..., a3+24, a2+25),

и если среди этих 26 чисел не содержится одинаковых, то их сумма также должна при делении на 25 давать в остатке 13. Однако эта сумма равна

(a1+a2+...+a25+a26)+(1+2+...+24+25),

и поскольку (1+2+...+24+25) = 325 13(mod 26), то по модулю 26 получаем:

13+13=26 0(mod 26).

Таким образом, получаем противоречие. Отсюда следует, что в каждой строке матрицы должно содержаться хотя бы одно повторяющееся число.

Таким же образом можно показать, что в любом колесе с четным числом контактных соединений должны быть повторения пар букв

229

открытого-шифрованного текстов. Однако для колес с нечетным числом контактов это не так. Можно привести примеры колес, которые не дают повторений, а именно:

Пример (отсутствие повторений в строках матрицы зашифрования) Рассмотрим 7-контактное колесо, для которого матрица зашифрования имеет 1-й столбец, равный (1, 3, 6, 2, 0, 5, 4). Тогда первая строка будет равна

(1, 4+1, 5+2, 0+3, 2+4, 6+5, 3+6),

то есть, приводя по модулю 7,

(1, 5, 0, 3, 6, 4, 2).

Данное множество не содержит повторений. Поскольку матрица полностью определяется по любой своей строке или столбцу, то ни одна ее строка не содержит повторений.

М15. Число возможных отражателей шифрмашины "Энигма"

В отражателе 26 букв объединены попарно. Первую пару можно выбрать

26 25

2

способами (число способов необходимо делить на 2, так как не важно, какую букву данной пары выбирать первой, а какую второй). Теперь следующую пару можно выбрать

24 23

2

способами, и так далее. Таким образом, разбиение 26 букв на пары можно осуществить

26!

213

способами. Однако, если мы в другом порядке выберем те же самые 13 пар, то получим тот же самый отражатель. И поскольку 13 пар можно переставить 13! способами, то число различных отражателей равно