О дисковом шифраторе «Энигма» («Загадка») написано много, и вряд ли есть смысл пересказывать изве-стное. Отмечу лишь, что простота конструкции, высокая надежность работы и достаточная стойкость шифра принесли этому электромеханическому шифратору времен Второй мировой войны вполне заслуженную славу.
По конструкции «Энигма» относится к дисковым шифраторам, отличительная особенность которых — наличие вращающихся на одной оси шифрующих дисков. В первых, наиболее массовых образцах «Энигмы» использовались три сцепленных между собой шифровальных диска, совершавших в процессе работы регулярное движение, подобно счетчикам электроэнергии старых конструкций.
Работа над совершенствованием «Энигмы» не прекращалась в течение всей войны, и в конце ее Германия располагала «Энигмами» с уже шестью не связанными между собой шифровальными дисками, движение которых стало хаотичным.
Стойкость шифра последних оказалась не по зубам даже первым в мире электронным вычислителям Colossus («Колосс»), построенным в Англии под руководством Алана Тьюринга.
Справедливости ради замечу, что сначала такой стойкости шифра достигли все же японцы в шифраторе Purple («Пурпур»). Но этот шифратор на шаговых искателях телефонного типа был не столь надежен в работе и не получил широкого распространения.
К сожалению, описание последних образцов «Энигмы» до сих пор не опубликовано, скорее всего по соображениям секретности.
Известно лишь, что электромеханические конструкции «Энигмы» дожили до 60-х годов прошлого столетия или даже дольше, пока не были окончательно вытеснены электронными, несущими свою службу и поныне. И это независимо от заявлений компетентных в своей некомпетентности представителей одноименных органов.
По разным данным, алфавит «Энигмы» содержал 25 или 26 латинских букв. Однако в программной реализации число символов алфавита удобнее считать равным 256, по числу различных значений байта.
Число же дисков обозначим просто n, хотя в приводимых далее программах n=11.
Каждому из шифровальных дисков в электронной реализации соответствует своя, не изменяемая в процессе работы таблица перестановок Tab[i]=Tab[i][j],j=0..255,i=0..n-1 чисел 0..255, склеенная в кольцо. Пусть положение текущего начала каждой таблицы определяется с помощью указателя Ptr[i],i=0..n-1, причем 0<=Ptr[i]
С учетом указанных обозначений шаг зашифровывания символа M для «Энигмы» с регулярным движением шифровальных дисков запишется следующим образом.
1. Полагаем i=0;
Правда, чтобы предотвратить атаку измерением времени исполнения кода, приходится несколько усложнить алгоритм, что и сделано в программе, приведенной в листинге 1. Однако суть его работы от того не изменяется.
Хаотическое движение шифровальных дисков будем моделировать следующим образом.
1. Полагаем i=0;
Этот алгоритм еще проще. Именно в таком виде он и реализован в программе, приведенной в листинге 2.
Вся нерегулярность здесь моделируется строкой 4.1, которую можно записать и как-нибудь иначе, например ввести зависимость от результата зашифровывания или от зашифровываемого символа подобно тому, как это сделано в программе, приведенной в листинге 3. Однако это не приносит сколько-нибудь ощутимых преимуществ.
Обратимость описанных шифрующих преобразований не вызывает сомнений и сводится к смене порядка использования таблиц подстановок Tab[i],i=0..n-1 на противоположный и замене таких таблиц инверсными им InvTab[i],i=0..n-1 с использованием соотношения InvTab[i,Tab[i,j]]=j,j=0..255,i=0..n-1.
Поскольку операция замены по таблицам перестановок ассоциативна, но не коммутативна, то процесс зашифровывания можно построить и на управлении порядком прохождения символов через систему таблиц. Одна из реализаций этой идеи представлена в программе листинга 4. Правда, она соответствует «Энигме» с переставляемыми, а не с вращающимися шифрующими дисками. Однако ничто не мешает скомбинировать такой механизм с одним из рассмотренных ранее. Но мы не будем этого делать, а только укажем, что «Энигма» подобной конструкции вполне может существовать и в электромеханическом варианте.
Очень важный вопрос связан с инициализацией таблиц перестановок Tab[i],i=0..n-1 и указателей Ptr[i],i=0..n-1 к ним. В данном случае применен алгоритм, частично позаимствованный из описания шифра RC4 Рона Ривеста. Сначала таблицу Tab[0]=Tab[0,i],i=[0..255] заполняем линейным образом Tab[0,i]=i, i=0..255. Затем ее элементы переставляем в соответствии со значением ключа, циклически повторяя по мере необходимости короткий ключ. Этот процесс точно соответствует процедуре разворачивания ключа RC41. Далее выполняем отсутствующий в RC4 процесс рандомизации таблицы Tab[0], осуществляемый следующим образом.
1. Полагаем i=0;
Каждая из последующих десяти таблиц Tab[i],i=1..n получается применением описанной процедуры к предыдущей таблице.
Начальные значения указателей Ptr[i],i=0..n-1 вычисляются следующим образом.
1. Полагаем i=0;
Здесь за неимением лучшего опять-таки использованы идеи шифра RC4.
В действительности, опираясь на идеи этого шифра, можно пойти дальше, если заметить, что постоянство распайки контактов «Энигмы» влечет регулярную в классических или нерегулярную в усовершенствованных образцах цикличность замен.
Вместе с тем ничто не мешает нарушить такую цикличность, введя прямую модификацию таблиц электронного аналога, подобно шифру RC4. Правда, последнее соответ-ствует реально неосуществимой перераспайке дисков «Энигмы» непосредственно в ходе шифрования, и для обозначения шифра придется использовать иное название. Но это уже другая песня.
Результатом работы каждой из программ являются три строки, содержащие исходный текст, результат его зашифровывания и восстановленный расшифровыванием текст соответственно. Вывод данных осуществляется через вызовы BIOS.
Программы написаны на входном языке компилятора Turbo Pascal версии 3.01A.
Листинги описанных в статье программ вы можете найти на «Мир ПК-диске».
1 А. В. Аграновский, Р. А. Хади. Практическая криптография: алгоритмы и их программирование. М.: СОЛОН-Пресс, 2002. 256 с.
2. В цикле со счетчиком i вычисляем n раз:
2.1. M=Tab[i,M];
2.2. i=i+1;
2.3. Конец цикла i;
3. Полагаем k=1;
4. В цикле со счетчиком i вычисляем n раз:
4.1. Ptr[i]=(Ptr[I]+k) mod 256;
4.2. Если k=0, уходим на 4.5;
4.3. Если Ptr[i]=0, уходим на 4.5;
4.4. Полагаем k=0;
4.5. i=i+1;
4.6. Конец цикла i.
2. В цикле со счетчиком i вычисляем n раз:
2.1. M=Tab[i,M];
2.2. i=i+1;
2.3. Конец цикла i;
3. Полагаем k=1;
4. В цикле со счетчиком i вычисляем n раз:
4.1. Ptr[i]=(Ptr[i]*i+1) mod 256;
4.2. i=i+1;
4.3. Конец цикла i.
2. В цикле со счетчиком i вычисляем 256 раз:
2.1. j=(Tab[0,i]+Tab[0,Tab[0,i]) mod 256;
2.2. Меняем местами элементы Tab[0,i] и Tab[0,j];
2.3. i=i+1;
2.4. Конец цикла i.
2. В цикле со счетчиком i вычисляем n раз:
2.1. Ptr[i]=(Tab[i,0]+Tab[I,Tab[I,0]]) mod 256 или Ptr[i]=(Tab[i,0]+Tab[I,Tab[I,0]]) mod n (для программы из листинга 4);
2.2. i=i+1;
2.3. Конец цикла i.
