Pull to refresh

Алгоритм Энигмы

Information Security *Cryptography *
Sandbox
        В данном сообществе я нашел много статей про известную шифровальную машинку «Enigma», но нигде из них не описывался подробный алгоритм ее работы. Наверняка многие скажут, что это не нуждается в афишировании, — я же надеюсь, что кому-нибудь да будет полезно об этом узнать. С чего все началось? Во времена Первой мировой войны большой популярностью пользовался шифр Playfair. Его суть заключалась в том, что буквы латинского алфавита записывались в квадрат 5х5, после чего буквы исходного алфавита разбивались по парам. Далее, используя квадрат в качестве ключа, эти биграммы заменяли на другие по определенному алгоритму. Преимущество данного шифра было в том, что он не требовал дополнительных устройств, и, как правило, к тому моменту, когда сообщение расшифровывали, оно уже теряло актуальность. Еще одним способом тайнописи был шифратор Джефферсона.

image


        Сие устройство состояло из определенного количества дисков, нанизанных на единую ось (обычно, дисков было 36). Каждый из них делился на 26 частей, каждая из которых обозначало букву. Буквы на дисках были расставлены в случайном порядке. Оператор путем вращения дисков набирал нужное сообщение, а затем переписывал другую строчку. Человек, принявший данное сообщение, должен был обладать точно таким же устройством с точно такой же расстановкой букв. И тот и другой способы были относительно неплохими для тех времен, но учитывая, что человечество вступило уже в XX век, возникла необходимость механизации процесса шифрования. В 1920 году голландский изобретатель Александр Кох изобрел первую роторную шифровальную машинку. Затем, на нее получили патент немецкие изобретатели, которые усовершенствовали ее и выпустили в производство, под названием «Enigma» (от греч. – загадка). Таким образом, эта машинка приобреталась многими фирмами, которые желали сохранить в тайне свои переписки. В этом и состояла вся гениальность Энигмы – все знали алгоритм шифрования, но никто не мог подобрать нужный ключ, так как число возможных комбинаций превосходило 15 квадриллионов. Если хотите узнать, каким образом Энигму взламывали, советую прочитать книгу Саймона Сингха «Книга шифров». Подытоживая все вышесказанное, хочу сказать, что шифр Энигмы являлся некой смесью шифратора Джефферсона и шифра Цезаря.

        Итак, приступим к изучению алгоритма. На данном сайте имеется очень неплохой симулятор, который в доступной и наглядной форме показывает весь процесс целиком и полностью. Давайте же разберем принцип работы трехроторной Энигмы. В ней имелось три отсека для помещения трех роторов и дополнительный отсек для размещения рефлектора. Всего за время Второй мировой войны было изготовлено восемь роторов и четыре рефлектора, но одновременно могло использоваться ровно столько, на сколько была рассчитана машина. Каждый ротор имел 26 сечений, что соответствовало отдельной букве алфавита, а так же 26 контактов для взаимодействия с соседними роторами. Как только оператор нажимал на нужную букву, — замыкалась электрическая цепь, в результате чего появлялась шифрованная буква. Замыкание цепи происходило за счет рефлектора.

image


       На рисунке представлена иллюстрация нажатия клавиши «А» с последующей дешифрацией в букву «G». После ввода буквы крайний правый ротор перемещался вперед, меняя тем самым ключ. Так каким же образом одна букву заменялась на другую? Как я уже говорил, для Энигмы было разработано восемь различных роторов. Внутри каждого из них было установлено 26 различных коммутаций. Здесь представлена подробная спецификация на каждый из них. Например, если на вход первого ротора поступала буква «N», то на выходе должна быть только «W» и никакая другая буква больше. Попади это буква на второй ротор, она бы уже преобразовалась в «T» и т.д. То есть, каждый ротор выполнял четко поставленную задачу в плане коммуникации. А какую же роль играли кольца? Рассмотрим следующий пример. Установим роторы III, II и I, а порядок колец «C», «U» и «Q».

image


        Нажмем на клавишу «A». Крайний правый ротор повернется вперед на один шаг, то есть, буква «Q» перейдет в «R». Ротор посередине также повернется вперед на букву «V», но об этом я расскажу чуть позже. Итак, наша буква «А» начинает путешествие с первого отсека, в котором установлен ротор I и на котором выставлена уже буква «R». Уже перед тем как попасть на первый ротор буква претерпевает свое первое преобразование, а именно: сложение с буквой «R» по модулю 26. Фактически, это шифр Цезаря. Если пронумеровать все буквы от 0 до 25, то буква «А» будет как раз таки нулевой. Значит, результатом сложения будет буква «R». Далее, мы с вами знаем, что в первом отсеке ротор I, а в его конструкции заложено, что буква «R» всегда переходит в «U». Теперь на очереди второй отсек с ротором II. Опять, перед попаданием на второй ротор, теперь уже буква «U» меняется по несколько иному алгоритму: к ней прибавляется разница значений последующего ротора и предыдущего. Поясню. На втором роторе ожидает нас буква «V», а на предыдущем, — «R», их разница равна четырем буквам, и именно они прибавляются к нашей букве «U». Поэтому, на второй ротор поступает буква «Y». Далее по таблице находим, что во втором роторе букве «Y» соответствует «O». Далее опять смотрим разницу букв «C» и «V», — она равна семи. Значит, букву «O» сдвигаем на семь позиций и получаем «V». В роторе III «V» переходит в «M». Перед тем как попасть на рефлектор, из нашей буквы вычитается буква «C», преображая ее в букву «K». Далее происходит отражение. Если вы заметите, то в каждом роторе образуются большие циклические группы, например: (A – E – L – T – P – H – Q – X – R – U), а в рефлекторе они разбиты по парам: (A — Y)(B — R)(C — U) и т.д. Это сделано для того, чтобы потом это возможно было расшифровать. Предположим, что установлен рефлектор B, в котором «K» заменяется на «N» (и наоборот). Половина пути пройдена. Теперь мы опять прибавляем значение буквы «С», получив тем самым букву «P». Здесь наоборот, в строке третьего ротора находим «P» и смотрим, в при нажатии какой буквы она бы появилась. Это буква «H». Преобразование в третьем роторе закончено. Теперь из этой буквы вычитается разница букв «C» и «V», то есть семь. Получаем букву «A». Во втором роторе она переходит саму в себя, поэтому оставляем ее без изменений. Далее, вычитаем разницу букв «V» и «R», то есть четверку и получаем букву «W». В первом роторе её обратно преобразование отображается в букву «N». Остается только вычесть из нее букву «R» и получим искомую букву «W». Как видите, алгоритм работы машинки оказался не таким сложным каким казался. Для усовершенствования шифра немцы внедрили коммутационную панель, которая позволяла попарно менять местами буквы. Если мы соединим буквы «Q» и «W», то при вводе той же «A» мы получили бы «Q», так как по факту должна быть «W», но она заменена буквой «Q». Вот прилагаемая схема действия.
image
        Осталось лишь рассказать про смещения роторов относительно друг друга. Правый ротор поворачивался всегда при нажатии клавиши на один шаг. Например, для ротора I эта позиция равна букве «R». Именно поэтому в нашем примере второй ротор повернулся: первый ротор прошел через букву «R». Далее, пройдя через определенную позицию, правый ротор приводил в движение левый на один шаг. В более усовершенствованных моделях левый ротор прокручивался два, а то и три раза.

        В завершение скажу, что здесь собраны некоторые материалы по взлому Энигмы, которые могут быть полезны. Надеюсь, что данная статья кому-нибудь пригодится.
Tags:
Hubs:
Total votes 58: ↑51 and ↓7 +44
Views 113K
Comments Comments 13