134
R1, R2 и R3. Неподвижный отражатель обозначается U (по-немецки он назывался Umkehrwalze). На этой упрощенной диаграмме колесо ввода, источник питания, клавиатура и лампочки не показаны. При нажатии на одну из букв на клавиатуре замыкается контакт, и ток от батареи проходит через колеса R1, R2 и R3. Проходя через отражатель, ток "возвращается обратно", и после повторного прохождения через колеса R3, R2 и R1 зажигает лампу, которая подсвечивает букву шифрованного текста.
Путь, который проходит ток, налагает на шифр два серьезных ограничения:
(1)никакая буква при шифровании не может перейти в себя;
(2)пары букв открытого - шифрованного текстов симметричны ("взаимно-обратны"), то есть если буква A при шифровании переходит в K, то при той же установке колес буква K при шифровании перейдет в A.
Шифрование с использованием контактных колес
Чтобы понять, как осуществлялось шифрование в шифрмашине "Энигма", нужно разобраться, что происходит, когда ток от клавиатуры проходит через контактное колесо. С каждой стороны колеса имеются 26 контактных точек. Провода в случайном порядке соединяют пары точек на противоположных сторонах; поэтому ток, поступающий, например, на контакт A, должен появиться на каком-то из 26 контактов с противоположной стороны. Не зная внутренней распайки колеса, нельзя предсказать точку выхода. Предположим, что это будет Y. Если теперь повернуть колесо, то проводник, соединяющий контакты A и Y, сдвинется на одну позицию с каждой стороны, и теперь ток пойдет из B в Z. Аналогично, если до поворота колеса контакт B был соединен с M, а контакт C был соединен с A, то после поворота контакты C и D окажутся соединены, соответственно, с N и B. Это показано на рис. 9.2*) .
Когда колесо повернется 26 раз, то проводники снова займут свои исходные положения, и контакты A, B и C опять окажутся соединены, соответственно, с Y, M и A.
Если нам известна внутренняя распайка проводов колеса, то мы знаем, как именно в 1-м угловом положении колеса будет зашифрована каждая из букв A, B, C, ..., Z. Следовательно, мы сможем определить, как будет зашифрована любая из букв в каждом угловом положении колеса. Например, если нам нужно узнать, во что перейдет буква K в 6-м угловом положении этого колеса, мы будем рассуждать следующим образом.
*) Подпись под рисунком 9.2: Рис. 9.2. Положение 1. A->Y |
B->M |
C->A |
|
Положение |
2. B->Z |
C->N |
D->B |
135
Проводник, точка входа которого в 6-м угловом положении расположена напротив буквы K, в 1-м угловом положении был повернут так, что его точка входа располагалась напротив буквы F, стоящей в алфавите на 5 позиций ранее K. Если в 1-м угловом положении буква F переходит, например, в P, то в 6-м угловом положении буква K переходит в букву, стоящую в алфавите через 5 позиций после P, то есть в U. Короче говоря,
Если в 1-м угловом положении F переходит в P, то в 6-м угловом положении K переходит в U.
Шифрование, осуществляемое любым колесом, можно полностью описать с помощью перечисления переходов каждой буквы в 1-м угловом положении колеса, так как отсюда можно найти переходы всех букв во 2-м угловом положении, затем в 3-ем, и т.д. 1-е угловое положение вовсе не является особенным. С таким же успехом можно использовать алфавит шифрования (то есть алфавит простой замены) для любого углового положения колеса.
Так, например, зная, как будут зашифрованы в 1-м угловом положении первые 6 букв алфавита, можно начать составлять таблицу 9.1.
Таблица 9.1
Буквы |
|
|
Угловые положения |
|
|
|
||
1 |
2 |
3 |
4 |
5 |
6 |
. . . |
|
|
|
|
|
|
|
|
|
|
|
A |
Y |
. |
. |
. |
. |
. |
. |
|
B |
M |
Z |
. |
. |
. |
. |
. |
|
C |
A |
N |
A |
. |
. |
. |
. |
|
D |
T |
B |
O |
B |
. |
. |
. |
|
E |
F |
U |
C |
P |
C |
. |
. |
|
F |
R |
G |
V |
D |
Q |
D |
. |
|
|
|
|
|
|
|
|
|
|
"Точки" в этой таблице обозначают места, по которым мы пока не располагаем достаточной информацией о шифрованных эквивалентах букв. Как только станут известны шифрованные эквиваленты всех 26 букв в 1-м угловом положении, вся таблица зашифрования размера 26 26 окажется заполнена целиком.
Отметим важное свойство данной таблицы зашифрования: каждая ее диагональ, параллельная главной (идущей из левого верхнего угла в правый нижний угол), содержит полный алфавит, записанный в обычном порядке, начиная с буквы в столбце 1.
С другой стороны, если нам известно, куда переходит буква A (или любая другая буква) при всех 26 угловых положениях колеса, то мы точно так же можем вычислить переходы всех букв для любого углового
136
положения. Например, предположим, что нам нужно узнать, во что перейдет буква N в 11-м угловом положении. Проводник, точка входа которого в 11-м угловом положении расположена напротив буквы N, располагался напротив буквы A на 13 шагов раньше, так как буква N стоит в алфавите на 13 позиций после A. Так как 11-13=-2, а угловое положение под номером -2 - то же самое, что и угловое положение под номером 26-2, то есть 24. Посмотрим, в какую букву переходит буква A в 24-м угловом положении. Если это будет, скажем, G, то буква N в 11-м угловом положении переходит в букву, стоящую в алфавите на 13 позиций дальше G, то есть в букву T.
Читатель, хорошо знакомый с матрицами, сразу заметит, что, по сути, мы получили представление шифра, реализуемого колесом, в виде матрицы размера 26 26. В первом столбце матрицы записан полный алфавит, зашифрованный в 1-м угловом положении колеса, а в первой строке - буквы, получающиеся при зашифровании буквы A в каждом из 26 угловых положений колеса.
Эту матрицу можно полностью восстановить либо по ее первой строке, либо по ее первому столбцу, используя "диагональное свойство", о котором говорилось выше. Важная криптографическая особенность этой матрицы заключается в следующем: любой столбец содержит все 26 букв алфавита, поскольку при одном и том же угловом положении колеса две разные буквы не могут перейти в одну и ту же букву; а строки могут содержать повторения одной или нескольких букв, так как одна и та же буква при разных угловых положениях колеса вполне может при шифровании перейти в одинаковые буквы. На самом деле для колеса с 26 контактами (или с любым четным их числом) в каждой строке должна повториться по крайней мере одна буква. В 6-буквенном примере, который мы рассматривали выше, такие повторения уже есть: например, C переходит в A в 1-м и 3-м угловых положениях. Если число контактов нечетное, то строчки могут и не содержать никаких повторений. С криптографической точки зрения, чем меньше повторений букв в строке, тем лучше. (Объяснение этих фактов и другие подробности см. в приложении M14.)
Шифрование в "Энигме"
Мы только что видели, как происходит шифрование буквы в одиночном контактном колесе. В шифрмашине "Энигма" ток поступает от буквы на клавиатуре и проходит через колесо ввода, а затем через три колеса R1, R2 и R3. После этого ток, проходя через отражатель U, возвращается через те же три колеса, но в обратном порядке: R3, R2 и R1, и наконец, снова поступает на колесо ввода и зажигает лампочку, обозначающую букву шифрованного текста. Таким образом, буква исходного открытого текста при преобразовании в букву шифрованного текста подвергается 9
137
преобразованиям. В действительности, как мы увидим ниже, в большинстве военных версий "Энигмы" было еще 2 преобразования, и таким образом, всего их было 11.
Если бы колеса были неподвижны, то "Энигма" просто была бы довольно сложным способом построения шифра простой замены. Однако колеса в ней движутся. При нажатии на букву клавиатуры крайнее правое колесо, R1, немедленно поворачивается на одно положение, и затем ток проходит через машину. После зашифрования 26 очередных букв колесо R1 возвращается в исходное положение. Если бы за это время колеса R2 и R3 не сдвинулись, то "Энигма" была бы эквивалентна 26 шифрам простой замены. Однако колесо R2 за это время обязательно сдвинется. Кольцо с выемкой на колесе R1 движется вместе с ним, и, таким образом, в процессе шифрования 26 букв в какой-то момент времени V-образная выемка оказывается прямо перед рычагом, установленным в глубине машины напротив колеса R1. Рычаг входит в зацепление с V-образной выемкой, это приводит в движение рычаг напротив колеса R2, который проворачивает это колесо на одно положение. Поскольку колесо R2 сдвинулось, то алфавиты шифрования теперь отличаются от тех, которые использовались 26 шагов тому назад. Таким образом, при шифровании каждых 26 букв колесо R2 сдвигается по крайней мере один раз. В действительности оно движется немного чаще, поскольку на нем тоже есть кольцо с выемкой, и когда его собственная выемка оказывается напротив рычага колеса R2, то на одно положение сдвигается третье колесо, R3. В этот момент само колесо R2 также поворачивается. Как следствие, все три колеса возвращаются в свои исходные положения только после зашифрования
26 25 26=16900
букв. Таким образом, шифрмашина "Энигма" представляет собой автоматический способ последовательного применения 16900 шифров простой замены. Допустим, кольцо с выемкой на колесе R1 установлено так, что его выемка проворачивает колесо R2, когда в окошке колеса R1 видно букву Z, и точно так же установлено кольцо с выемкой на колесе R2. Тогда последовательные угловые положения всех трех колес, начиная с положения A, Y, Y (читая слева направо), будут следующие:
A Y Y
A Y Z
A Z A
B A B.
Изобилие алфавитов замены обеспечивает высокую стойкость системы,
138
но это еще не предел, так как еще до того, как будут зашифрованы 16900 букв, все три контактных колеса можно снять и вновь смонтировать на общей оси в другом порядке. На первой шифрмашине "Энигма" в комплекте, поставляемом вместе с машиной, было только три колеса, и их можно было установить шестью разными способами. Поэтому число возможных алфавитов простой замены было
6 16900=101400.
Фактически же исходным для колеса R2 может быть любое из 26 угловых положений, включая Z, хотя во время обычной работы машины оно и не может попасть в положение Z, если только R1 до этого также не находилось в положении Z. Поэтому всего существует 6 26 26 26=105456 возможных исходных угловых положений и алфавитов простой замены.
Даже если в распоряжении криптоаналитика имеется подобная шифрмашина "Энигма", то перед ним стоит задача опробования всех 105456 возможных начальных установок колес для каждого сообщения. Очевидно, решить такую задачу в докомпьютерную эпоху было непосильным делом. Если же криптоаналитик не имеет в своем распоряжении такой машины, и он не имеет данных о внутренней распайке трех колес и отражателя, то ему придется опробовать гораздо большее число вариантов, так как число возможных вариантов распайки каждого колеса равно
25! (т.е. 25 24 23 22 ... 2 1)
а это число превосходит
1025.
Для трех таких колес число возможных вариантов распайки будет больше, чем
1075.
Более того, криптоаналитику неизвестна внутренняя распайка отражателя, и это увеличивает число вариантов еще более чем в
1012
раз (расчет этого числа см. в приложении M15). Следовательно, для дешифрования сообщений, зашифрованных на машине "Энигма" с неизвестной распайкой криптоаналитику пришлось бы перебрать более