«Энигма» и шифры многоалфавитной замены

Атака на шифр «Энигмы»

Говоря о проекте создания «Энигмы» (лат. «загадка»), нельзя не вспомнить, пожалуй, первую из книг по истории криптографии [1], где описаны устройство и работа знаменитой немецкой машины. С сожалением приходится отметить, что в разных источниках «Энигма» описывается по-разному. Касается это числа символов алфавита и числа дисков, наличия или отсутствия сепараторов и штекерного коммутатора. Иногда приходится слышать и читать о якобы разработанных методах вскрытия шифров «Энигмы». Однако все сообщающие о них почему-то хранят глубокомысленное молчание о деталях таких операций. Конечно, при небольшом числе шифровальных дисков и фиксированной распайке их контактов вскрытие возможно, если... диски не перемещаются в процессе шифрования и над ними не производится иных манипуляций. Вместе с тем вполне надежный и простой шифр RC4 Рона Ривеста уж очень напоминает однодисковую «Энигму», на сей раз с заменяемыми в процессе шифрования дисками (см. далее). Так что слухи скорее всего сильно преувеличены.

В комплект применявшейся немцами в начале Второй мировой войны трехдисковой «Энигмы» [2, с. 88—93] входило пять шифровальных дисков, из которых одновременно использовались три. Для их поворота служили два разделявших диски вращающихся сепаратора. Каждый из них получал вращение от одного из смежных с ним шифрующих дисков и после полного оборота перемещал другой из сцепленных с ним смежных дисков. Все шифрующие диски содержали по 26 букв латинского алфавита. Клавиатура подключалась через штекерный коммутатор. Неподвижный рефлектор обеспечивал обратное прохождение токовой посылки, соответствующей шифруемому символу. Наличие рефлектора упрощало конструкцию «Энигмы», но не влияло на стойкость шифра. Результат зашифровывания или расшифровывания считывался визуально с панели индикаторов. Для взлома шифра «Энигмы» применялся частотный анализ триграмм и индекс совпадения IC, предложенный Фридманом в 1920 г.

Формально этот индекс определяется следующим способом:

В этом выражении k — число символов в алфавите; n — длина строки символов алфавита; n[i] — среднее число символов с номером i в строке длины n.

Для полностью случайного текста n[i]=n/k, i=1..k и, следовательно, IC=1/k, т.е. IC=0,038 при k=26. Если же брать только «осмысленные» тексты, то для немецкого и английского языков IC=0,065.

Краткое описание «Энигмы» и технологии взлома ее шифра можно найти в [1, с. 88—93]. Там же фактически приведена и оценка вычислительных затрат для случая, когда противник имеет неограниченный доступ к оборудованию, что и соответствовало действительности (полный комплект оборудования «Энигмы» англичане в свое время сняли с умышленно затопленных на мелководье немецких подводных лодок).

Атака на шифр «Энигмы» строится следующим образом.

1. Перебором находятся использованные для шифрования диски и их взаимное расположение. Критерий перебора - максимальное значение индекса совпадения. Трудоемкость перебора - 60?26³ операций расшифровывания (5?4?3=60 - количество выборов трех дисков из пяти, для каждого из которых существует 26 начальных положений - по числу символов алфавита). На этом этапе не учитываются ни положение штекеров в коммутационной панели, ни угловые положения сепараторов. В силу этого угловые положения дисков считаются не вызывающими доверия.
2. Опять же с помощью перебора находится положение первого из сепараторов и первого из шифрующих дисков. Критерий перебора все тот же - максимальное значение индекса совпадения. Трудоемкость - 26⁴ операций расшифровывания (три диска и один сепаратор). Поскольку положение второго сепаратора здесь не учитывается, то угловые положения второго и третьего шифрующих дисков доверия не вызывают, а результатом будут начальные угловые положения первого из дисков и первого сепаратора (а также комплект и порядок следования дисков с этапа 1).
3. Перебором положения второго сепаратора, а также второго и третьего шифрующих дисков по максимуму индекса совпадения находится начальное угловое положение дисков и сепараторов. Трудоемкость этой операции - 26³ расшифровываний. Положение штекеров все еще остается неопределенным. Общая трудоемкость подбора положения сепараторов и дисков составляет 60?26³+26⁴+26³ расшифровываний.
4. Для найденного положения дисков и сепараторов определяется положение штекеров до получения осмысленного текста. Делается это на основе анализа триграмм.

   4.1. Начальным перебором выбирается положение трех штекеров, соответствующее максимальной частоте следования триграмм, что требует 26?25?24 расшифровываний. После чего эти штекеры устанавливаются в свои гнезда.

   4.2. Далее аналогичный перебор делается для оставшихся 23 гнезд и штекеров, и снова эти штекеры устанавливаются в свои гнезда. На это требуется 23?22?21 расшифровываний.

   4.3. То же самое повторяется для 20, 17, 14, 11, 8, 5 каждый раз остающихся гнезд и штекеров, требуя 20?19?18, 17?16?15, 14?13?12, 11?10?9, 8?7?6 и 5?4?3 расшифровываний соответственно.

   4.4. Определить положение оставшихся двух штекеров уже не представляет проблемы и может быть сделано не более чем за два расшифровывания (а практически за одно).

Трудоемкость определения положения штекеров на коммутационной панели требует не более 26?25?24+ +23?22?21+20?19?18+...+5?4?3+2, т.е. 40 718 расшифровываний. А для полного взлома «Энигмы» потребуется перебрать 60.26³+26⁴+26³+26?25?24+23?22?21+...+5?4?3+2 вариантов, что составляет примерно 2²¹ пробных расшифровываний. По нынешним временам это, конечно, немного. Для сравнения: алгоритм шифрования известного архиватора PKZIP Роджера Шлафлы имеет временную сложность около 2²⁷, а его вскрытие на обычном персональном компьютере занимает всего лишь несколько часов [3, с. 443—444].

При неизвестной распайке контактов шифрующих дисков взлом «Энигмы» резко усложняется. Действительно (см. приведенное далее утверждение), уже на первом этапе число проб расшифровывания вместо 60?26³ сразу возрастает до 25!?(25!-1)?(25!-2)?26³, т.е. более чем в 2²³⁰ раза. При таких условиях «Энигма», пожалуй, не взламываема и на современных вычислителях.

Кстати, для взлома небезызвестного DES требуется всего 2⁵⁶ переборов, а вот об успешном вскрытии тройного DES (2¹⁶⁸ переборов), использованного для шифрования архивов заслуженным строителем пирамид (финансовых, разумеется) Сергеем Пантелеймоновичем Мавроди (математиком, между прочим), известно только одно: что его (Мавроди, а не тройной DES, конечно) вроде бы посадили непонятно за какое мошенничество, в то время как не менее знаменитые деятели все еще на свободе.

Между тем принявшие взамен DES новый стандарт AES (со 128-, 192- и 256-битовыми ключами) специалисты NIST (Национальный институт стандартов и технологий США), считают, что 2¹²⁸ переборов уже гарантируют практическую невзламываемость шифра (стандарт AES-128), а вот российские чиновники от медицины требуют, чтобы для засекречивания медицинских данных использовался стандарт AES-256 (2²⁵⁶ переборов).

Выбор же этак с полсотни шифрующих дисков из 255! возможных для 256-символьного алфавита (255! а не 256! получается из-за того, что для одного и того же диска возможно 256 различных положений; доказательство этого утверждения приводится далее) поставит в затруднение и современных криптоаналитиков (даже если не вводить сепараторы). А что будет, если эти диски из комплекта, включающего их 255! штук, еще и заменять в процессе шифрования?

Остается заметить, что вполне современный потоковый шифр RC4 Рона Ривеста (одного из авторов RSA) оперирует с 256!?256² (примерно 2¹⁷⁰⁰) внутренними состояниями. Столько же требуется и пробных расшифровок для его вскрытия (если, конечно, кто-то не изобретет более эффективного метода). С другой стороны, RC4 можно рассматривать и как однодисковую «Энигму» (без сепараторов и коммутационной панели, с единственным шифровальным диском, поворачиваемым и заменяемым по фиксированной процедуре). Этот пример показывает, что возможности электронной реализации «Энигмы» далеко еще не исчерпаны...

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

Листинг.
function LogFact2 (N : integer) : integer;
(*********************************)
(* Двоичный логарифм  факториала *)
(* (ф-ла Стирлинга и округление) *)
(*********************************)
begin
LogFact2 := Round(((N+0.5)*Ln(N)-N+Ln(Pi)/2)/
Ln(2)+0.5);
Exit
end; (* LogFact2 *)

Утверждение. Число k различных шифровальных дисков «Энигмы» с n-символьным алфавитом рассчитывается по формуле: k=(n-1)!

Действительно, для n=1,2,3 формула верна. Пусть формула верна и для некоторого m. Тогда диск (m+1)-символьной «Энигмы» может быть получен размещением символа с номером m+1 между символами диска m-символьной «Энигмы», что для каждого такого диска можно сделать ровно m способами (по числу промежутков между m+1 символами). А так как по предположению индукции различных дисков у m-символьной «Энигмы» точно (m-1)!, то и разных дисков у (m+1)-символьной «Энигмы» будет m?(m-1)!=m!, что и доказывает утверждение.

Шифры многоалфавитной замены

В основе шифра многоалфавитной замены лежит понятие алфавита, под которым имеется в виду конечное вполне упорядоченное множество A из n попарно различных элементов a[0], a[1], ..., a[n-1], называемых также символами алфавита. Не ограничивая общности, символами алфавита можно считать просто набор чисел 0..n-1. Располагая эти n чисел произвольным образом, можно получить n! (n-факториал) различных алфавитов A[i]=a[i,0]..a[i,n-1], i=0..n-1. При этом естественно алфавиты A[i], A[j] считать различающимися, если найдется хотя бы один такой номер k: 0шkшn-1, что a[i,k]<>a[j,k].

Располагая какими-либо m: 0шmшn!-1 алфавитами A[i], i=0..m-1, можно построить шифр многоалфавитной (при m>1) замены:

c[k]=a[k mod m, p[k]], k=0,1, ... 	(1),

где p[0], p[1], ... — символы открытого текста (Plain Text), а c[0], c[1], ... — соответствующие им символы зашифрованного текста (Cipher Text).

Обращением преобразования (1) служит ему подобное (2), отличающееся от (1) лишь смыслом входящих в него элементов:

p[k]=b[k mod m, c[k]], k=0,1,... 	(2)

В данном случае b[i,j] — элементы инверсного алфавита B[i]=b[i,0]..b[i,n-1] по отношению к A[i]=a[i,0]..a[i,n-1]], который в таком случае является прямым для алфавита B[i]=b[i,0]..b[i,n-1].

Связь между прямым A[i] инверсным (обратным ему) B[i] алфавитами выражается простым соотношением:

b[i,a[i,j]]=j, j=0..n-1 	(3)

Из соотношения (3), истинность которого проверяется непосредственно (можно индукцией по числу элементов алфавита), следует, что если алфавит B[i] является инверсным для алфавита A[i], то алфавит A[i] будет инверсным для B[i]. И ничего странного здесь нет, так как это обычное отношение между прямой и обратной функциями, частными видами которых являются алфавиты.

Главная проблема при использовании шифров многоалфавитной замены связана с хранением множества самих алфавитов. Пожалуй, самое удачное решение здесь было предложено Эдвардом Хеберном (ставшим впоследствии знаменитым из-за своей роли во Второй мировой войне) в 1917 г. в прообразе электромеханического шифратора «Энигма». Промышленный образец «Энигмы» был создан чуть позднее берлинским инженером Артуром Кирхом (или Артуром Шербиусом — по другим источникам).

Однако выпущенные тогда «Энигмы» не нашли спроса, а производившая их небольшая фирма в конце концов разорилась. Положение изменилось лишь в 1930-е годы с возрождением германского милитаризма. В 1939 г. массовое производство «Энигм» было развернуто в оккупированной Польше.

Промышленный образец «Энигмы» состоял из четырех вращающихся на одной оси шифровальных дисков, которые можно было менять местами (хотя использовалось это крайне редко) с 25 символами усеченного латинского алфавита (обычно с отождествленными буквами I, J и U, V, подобно тому как в русском алфавите часто отождествляют буквы Е, Ё и, несколько реже, И и Й).

Перед началом работы диски устанавливались в определенное четырехбуквенным ключом положение, а после зашифровывания очередного символа входной диск поворачивался на 1/25 (по числу символов) полного (360?) оборота, осуществляя смену текущего алфавита. После зашифровывания первых 25 символов на тот же угол поворачивался следующий за ним диск, точь-в-точь как в механическом счетчике электроэнергии. Число различных взаимных положений дисков и, следовательно, общее число m реализованных в «Энигме» алфавитов составляло 25⁴, что было весьма внушительным для столь простого устройства. Раскрытие сообщений короче указанного (390 625) или несмысловых без знания других деталей устройства при этом представляло неразрешимую задачу.

На боковых сторонах размещались по 25 (опять же по числу символов) соприкасающихся у смежных дисков контактов, соединенных попарно с контактами на противоположной стороне. Внешние контакты крайних дисков использовались для ввода шифруемого и вывода зашифрованного символов. Каждый символ при проходе через «Энигму» претерпевал четыре (по числу дисков) замены.

Для расшифровки сообщений диски устанавливались в соответствии с кодовым словом, а вход и выход «Энигмы» переключались.

Главным секретом «Энигмы» была распайка контактов, знание которой позволяло вскрывать и короткие смысловые шифровки обычным в таких случаях методом подбора ключей. В погоне за этим секретом англичане устроили настоящую охоту на немецкие подводные лодки, преднамеренно затапливая их на мелководье, чтобы снять установленные на них «Энигмы». По иронии судьбы соединение контактов используемых немцами «Энигм» в точности соответствовало промышленному образцу выпуска аж 1917 г., во что англичане просто отказывались верить, явно переоценив своего противника.

В связи с этим на память приходит еще один эпизод, на этот раз связанный с Вернером Гейзенбергом — одним из создателей квантовой механики и видным членом национал-социалистической партии Германии. При его аресте теперь уже американцы не задумываясь высадили дверь, между прочим незапертую. Дверь просто открывалась в другую сторону.

Однако конструкторская мысль не стояла на месте, и к концу войны немцы располагали «Энигмами» сначала с пятью, а потом и с шестью шифровальными дисками, вращение которых стало нерегулярным. Шифры таких усовершенствованных «Энигм» были уже невскрываемыми.

Советская разведка также проявляла интерес к «Энигмам», лицемерно восхищаясь успехами англичан по взлому ее шифров. Умели ли в СССР читать ее шифровки, неизвестно. Скорее всего захваченные «Энигмы» использовались для совершенствования советской шифровальной техники. И курьезом истории остается факт чтения немцами шифров Ставки Верховного главнокомандующего в конце войны, когда исход последней был уже предопределен.

О построении электронной модели «Энигмы» и ее исходные тексты см. в полной версии статьи на «Мир ПК-диске».