Энигма в контексте истории криптографии и развития шифровальных роторных машин
Содержание:
1. Краткая история криптографии
2. Роторные шифровальные машины и первые образцы Энигмы
3. Энигма и ее значение в эпоху Второй Мировой Войны
4. Внутреннее устройство и принцип работы Энигмы
5. Расшифровка кода Энигмы
1. Краткая история криптографии
1.1 Основные положения и принципы криптографии
Криптография — наука о создании и расшифровке сообщений, значение которых в той или иной степени засекречено от лиц, пытающихся перехватить их. Сообщение, которое необходимо переслать, называется открытым текстом (plaintext), в то время как непосредственно пересылаемое сообщение — зашифрованный текст (ciphertext). Основная задача шифровальной системы — обеспечить невозможность или в крайней степени затруднить расшифровку пересылаемого сообщения без знания ключа — специального алгоритма кодирования сообщения. Получатель же сообщения без труда может раскодировать его, используя этот ключ.
1.2 Зарождение криптографии
Криптография в том или ином виде существовала на протяжении всей истории становления человеческой цивилизации. Доказательством этому факту служат найденные зашифрованные сообщения, которые использовались в древнем Египте, Китае или Индии примерно три тысячи лет до н.э. Множество примеров существования закодированных сообщений можно обнаружить в литературе давно минувших дней. Так, например, Гомер в своей «Илиаде» пишет про зашифрованное послание, переданное королем Проитосом, жаждущим убить молодого Беллерофонтеса.
Однако детали многих древних шифровальных систем не смогли сохраниться до наших времен. Квадрат Полибия — одна из первых таких систем, структура которой смогла не затеряться в истории человечества. Она была разработана греческим историком Полибием во втором веке до н.э. и представляла собой квадрат 5×5, в каждую клетку которого была вписана буква алфавита. В итоге, передавая сообщение, каждую его букву можно было бы представить с помощью квадрата Полибия, ведь каждой букве соответствовали две цифры — номер ряда и номер столбца. Зашифрованное сообщение состояло как раз из множества пар таких цифр. Однако же главным достоинством данного метода шифрования была отнюдь не его комплексность и надежность. Очевидным преимуществом выше описанного метода кодирования сообщения являлась его простота в передаче сообщений на большие расстояния. Алфавит сокращался до вида, удобного для коммуникации с помощью, к примеру, факелов: от одного до пяти в каждой руке (в соответствии с номером строки и столбца данной буквы). В дальнейшем из схожих принципов и целей были разработаны уже известные в современности азбука Морзе и семафоры, уже не говоря о ASCII и Unicode (современное цифровое шифрование).
Квадрат Полибия
Одним же из самых известных методов шифрования является знаменитый шифр Цезаря. Опираясь на работы древних римских историков, можно сделать вывод, что сам Юлий Цезарь использовал шифр, подразумевающий сдвиг алфавита на определенное число — ключ данного шифра — и сопоставление буквам открытого сообщения букв, полученных при сдвиге, учитывая их новый порядковый номер в полученном алфавите. Отсюда данный метод шифрования и получил свое имя. Изначально алфавит сдвигался на 3 символа, таким образом A становилось D, B — E и так далее. Если же буква занимала одну из трех последних позиций, то перестановка циклически продолжалась через начало алфавита. X переходило в A, Y — в B, а Z — в С. С течением времени популярность данного метода кодировки не угасла, ведь даже сегодня он повсеместно используется на различных интернет ресурсах и также в популярной культуре. К примеру, пользователи интернета могут активировать мод, который называется ROT13, который кодирует весь контент интернет браузера с помощью шифра Цезаря со сдвигом на 13 символов. Также, отсылку на шифр можно заметить в произведении Артура Кларка »2001», где HAL — имя компьютера, является шифром Цезаря со сдвигом 1 и открытым сообщением IBM. За простотой этого шифра кроется простота в декодировке. Для текстов на английском существует всего 25 возможных шифров, поэтому для его взлома потребуется перебрать лишь 25 возможных вариантов текста, пока он не предстанет в читаемом виде. Более безопасная схема зашифровки сообщения подразумевает замену каждой буквы исходного открытого сообщения на любую другую, но без привязки к определенному расстоянию между буквами. Ключом такого шифра, в свою очередь, является таблица соответствия между буквами. Такая схема кодировки сообщения называется подстановочным шифром. Также, в 15-м веке в арабской криптографической энциклопедии впервые были упомянуты шифры, в которых разные закодированные символы могут соответствовать одному и тому же символу открытого текста. Шифры, где каждому символу открытого текста соответствует единственный символ зашифрованного называются моноалфавитными, если же больше одного — полиалфавитными.
Одна из возможных тактик при взломе моноалфавитных шифров — подсчет частоты использования символов в зашифрованном тексте и последующее сопоставление этих частот частотам символов латинского или любого другого алфавита. Такой метод называется частотным анализом. При прямом же переборе мы сталкиваемся с тем, что нужно перебрать огромное число возможных вариантов. Так, для моноалфавитных подстановочных шифров мы можем представить A 26-ю вариантами, B — 25-ю, C — 24-мя и так далее. В итоге получается 26! (262524…321) возможных кодировок, что почти невозможно перебрать даже с учетом мощностей современного оборудования.
2. Роторные шифровальные машины и первые образцы Энигмы
2.1 Основные принципы работы роторных машин
Как было сказано ранее, подстановочные шифры не так-то легко взломать без знания ключа. Поэтому использование таких шифров приобрело поразительную актуальность к началу 20-ого века. Для автоматизации процесса шифрования были разработаны специальные механические устройства — электрические роторные машины, которые позволяли использовать шифровальные алгоритмы намного более сложные, чем шифры, сделанные вручную. Выше упомянутые устройства стали прорывом в сфере криптографии и прослужили человечеству в авангарде шифровального искусства на протяжении многих лет. Аналогично изобретению Ньютоном и Лейбницом деференциально-интегрального счисления, идея о концепции использования роторных машин в криптографии пришла в голову нескольким изобретателям одновременно и независимо друг от друга. На данный момент изобретателями роторной шифровальной машины считаются два голландских офицера флота — Тео А. ван Хенгель (1875 — 1939) и Р.П. С. Спенглер (1875 — 1955). Датируется это, без всякого преувеличения великое, изобретение 1915-м годом. Эти электро-механические машины использовали систему подвижных роторов для зашифровки сообщения, используя полиалфавитный шифр подмены. Роторная машина с виду очень напоминает пишущую машинку c интерфейсом, позволяющем вводить сообщения, используя набор клавиш с буквами латинского алфавита (или любого другого). В самом простом виде данная машина, при нажатии на клавишу, воспроизводит определенный символ, в зависимости от внутренней конструкции самой машины. Всего таких символов, как и клавиш, 26 — на каждую букву алфавита. При базовой конструкции (без роторов) каждая клавиша ведет только к одному символу на дисплее, который загорается при каждом нажатии кнопки, к нему подведенной с помощью провода. Таким образом в данной конфигурации машина использует простой шифр подмены. Однако если во внутреннюю конструкцию роторной машины добавить непосредственно ротор со своей внутренней структурой проводов, то ситуация кардинально изменится. При каждом нажатии клавиши ротор будет вращаться с помощью механизма и при следующем нажатии этой же клавиши символ зашифруется уже по другому, так как подводка проводов от кнопки к дисплею изменится внутри машины. Для примера, если нажать на клавиатуре AA, то устройство воспроизведет LD, так как ротор повернулся и поменял внутреннюю проводку. Внутреннее расположение проводов должно оставаться в секрете, чтобы избежать скорого взлома данного шифровального алгоритма. Однако даже знание внутренней топологии не отменяет комплексности воспроизведения механизма шифровки сообщения с помощью роторной машины. Для дешифровки зашифрованного послания необходима машина с аналогичным ротором на принимающей стороне. В этой же конфигурации мы уже имеем дело с более сложным и продвинутым полиалфавитным шифром подмены.
Защиту от дешифровки можно с легкостью улучшить на порядок путем простого добавления роторов, выходы которых будут соединены со входами соседних роторов. У каждого ротора свое расположение проводов, что делает анализ данной конфигурации еще более сложной задачей. Также немаловажным фактором является скорость с которой вращаются роторы — она должна быть разной. Каждый ротор обеспечивает 26 подстановок. Таким образом, при шифровании одного и того же символа, мы снова сможем получить аналогичную последовательность вывода на дисплей после нажатия на ту же самую кнопку через 26 нажатий (после полного прокручивания ротора).Для увеличения периода этого повтора можно использовать несколько роторов, соединенных последовательно. Когда один из них совершает полный оборот, следующий ротор начинает вращаться и передвигается на одно деление. Это увеличивает период повтора до 676-ти, а далее до 26^n, где n — количество роторов, установленных внутри машины последовательно.
2.1 Первые прототипы Энигмы
Конечно же такого типа машины снискали свою популярность по время мировых войн, когда потребность в передачи зашифрованных сообщений была особенно высока и имела стратегическое значение для противоборствующих сторон конфликта. Во время Первой Мировой Войны роторные шифровальные машины еще не вошли в массовых обиход в силу своей новизны, ведь только в 1917 году Эдвардом Хэпберном был изобретен прототип будущей всемирно известной Энигмы — роторной шифровальной машины, которая обладала симметрией. Это означало, что если сообщение зашифровать дважды (при одинаковых настройках), то в итоге можно получить изначальное открытое сообщение. Массовое же производтво Энигмы началось только в 1923-м году, когда немецкий инженер Артур Шребиус создал промышленный прототип. Огромное количество разных прототипов Энигмы было разработано в следующие 25 лет, учитывая простые машины, выводившие сообщения с помощью систем дисплеев — лампочек, а также и более сложные, выводившие послания на бумагу с помощью пишущих устройств вывода.
Устройство роторной шифровальной машины
Сначала была разработана модель Энигма А — первый массовый прибор с таким названием, который в дальнейшем послужил прототипом для знаменитой Энигма I (Энигма времен второй мировой). Далее были модели B, C и D, отличавшиеся только роторной конфигурацией и общим функционалом, но они все еще выводили сообщения через лампочки — дисплеи. В 1926 году появилась новая модель — Schreibende Enigma. У нее было 4 шифровальных ротора и 28 клавиш для написания сообщений. Положение же роторов регулировалось ручками на корпусе машины. Сама машина печатала сообщения на бумаге.
3.Энигма и ее значение в эпоху Второй Мировой Войны
Во многом технический прогресс и современные компьютерные технологии своим развитием обязаны Второй Мировой Войне. Для получения тактического и стратегического преимущества обе стороны задейтсвовали самые передовые технологии того времени. Так, немецкая сторона конфликта инвестировала огромные суммы в ракетостроение и разработку новых моделей ракетных снарядов, что привело к изобретению ракет V-1 и V-2, столь известных и часто используемых во время войны. В свою очередь США поспособствовали созданию первой атомной бомбы, собрав лучших ученых тех лет в Манхэттэнском проекте. Также огромное количество ресурсов затрачивалось на развитие технологий шифровки и дешифровки сообщений для получения бесценной информации о расположении войск противника, его дислокации и структуре будущих маневров. Так, на авансцене появляется Энигма. Как было описано выше, прототип, использовавшийся во время второй мировой, был основан на ранних версиях Энигмы А и назывался Энигма I. Это была стандартная роторная шифровальная машина: клавиатура с немецкой раскладкой и соответствующее количество лампочек, которые с помощью внутренних соединений сообщались с кнопками, зажигаясь при нажатии последних, тем самым выводя зашифрованный символ. Внутренняя проводка же контролировалась тремя роторами, которые могли занимать 26 позиций каждый. Все роторные позиции также обозначались буквами немецкого алфавита (за исключением ум-ляут). Однако для улучшения безопасности передачи сообщений, немцами было усовершенствовано строение аппарата.
Были добавлены еще два ротора, тем самым шифровальщикам было позволено использовать набор из любых трех роторов из пяти возможных. Для потенциальных взломщиков это означало 60 возможных взаимных расположений роторов. В добавок к этому, на некоторых моделях были имплементированы механизмы, которые изменяли положение соседних роторов, при котором следующий ротор приходил во вращение. Однако самой неприятной деталью для дешифровщиков было другое усовершенствование — передняя панель с разъемами для каждой буквы алфавита — так называемая штекерная плата. Немецкие шифровальщики использовали ее, чтобы менять буквы местами с помощью кабелей. Такие пары букв назывались штекерными парами. Таким образом количество изначальных настроек Энигмы стало на несколько порядков больше. Только различные варианты замены букв с помощью кабелей на штекерной панели подразумевали свыше 2×10^14 вариантов подключений. Плюс к этому 26^3 вариантов расположения самих роторов и 60 способов выбрать 3 ротора из 5-ти. Всего получалось свыше 2×10^20 возможных изначальных установок роторной машины. Даже для нынешних технологий задача перебора всех этих вариантов займет огромное количество времени, уже не говоря о технологиях тех лет — во время второй мировой это было просто-напросто невозможно.
4. Внутреннее устройство и принцип работы Энигмы
Теперь немного о внутренней структуре Энигмы и роторов в частности. Каждый из трех задействованных роторов имел по 26 контактов на левой и правой стенке. Ток, который поступал на левый контакт проходил через внутреннюю систему проводов к правому контакту, в зависимости от структуры проводки самого ротора, которые были разные для разных роторов. Таким образом каждый ротор служил для подмены символов, проще говоря для перестановок. Штекерная плата также служила для перестановок, которые назначались вручную шифровальщиками, в зависимости от инструкций сверху. Каждый ротор поворачивался на одну позицию при нажатии любой клавиши. Таким образом внутренняя топология машины менялась, так как провода от буквы открытого сообщения вели уже к совсем другой букве зашифрованного. После совершения полного оборота левым ротором, при 26-ти нажатиях, средний ротор прокручивается на одну позицию. После полного оборота среднего — правый, в свою очередь, прокручивается так же на одну. Также каждый ротор вращается со своей скоростью: левый — быстрый ротор — каждое нажатие, средний — средний ротор — каждые 26 нажатий, правый — медленный ротор — каждые 26×26.
Внутри Энигмы
На картинке выше можно увидеть, каким образом машина шифрует сообщения. При нажатии на букву А быстрый ротор прокручивается на одну позицию, меняя настройку роторов с JLY на JLZ. После нажатия ток течет по проводу от буквы А через все три ротора. При этом лампочка при букве А отсоединяется от подачи тока, чтобы избежать ее загорания. Пройдя через все роторы, ток течет через отражатель, где он перенаправляется и течет в обратном направлении в соответсвии с внутренней проводкой и наконец доходит до контакта рядом с лампочкой буквы В, тем самым подводя к ней ток. В результате лампочка загорается и мы получаем букву шифрованного сообщения. Таким образом шифротекст буквы А при начальных настройках JLZ — В. С каждым новым нажатием шифр меняется и таким образом мы имеем дело с полиалфавитным шифром замены. Здесь же можно заметить фундаментальную особенность шифра Энигмы — он симметричен. То есть если шифр для буквы А — буква В, то это работает и в другую сторону — В шифруется в А. Ведь схема соединений абсолютна одинакова, отличие лишь в направлении, в котором течет ток от одного контакта до другого. Это означает, что получателю и отправителю послания не нужны два разных ключа. Весь процесс передачи состоял в том, что отправитель настраивал Энигму в соответствии с инструкцией, заданной командованием на определенный день, вводил сообщение в машину, получал шифротекст с помощью лампочек — индикаторов, затем посылал его с помощью азбуки Морзе по радиоканалу. Получатель же в свою очередь переводил текст из Морзе в шифр, затем печатал его на Энигме и наконец получал исходный открытый текст в силу симметрии самой машины. Однако эта симметрия также послужила помощником на пути к взлому кодировки Энигмы.
5. Расшифровка кода Энигмы
Задача взлома Энигмы легла на плечи команды криптографов под кодовым названием «Ultra». Это были выходцы из лучших британских школ кодирования и шифрования, базировавшихся на севере Лондона в Блетчли-парк. Самым известным математиком этой группы был Алан Тьюринг, тот самый создатель машины Тьюринга и ученый, внесший неоценимый вклад в исследование по расшифровке алгоритма шифрования Энигмы. Однако ученые из Блетчли-парк пользовались наработками польских ученых, которые впервые смогли взломать Энигму в 1932 году. Основными слабостями Энигмы были симметричность шифровки и тот факт, что машина не могла шифровать буквы в самих себя. Также, сообщения, передаваемые немецкими войсками, были очень лаконичные и часто содержали в себе повторяющиеся элементы или целые куски посланий. Основной стратегией взлома такого шифра являлась атака на основе открытых текстов — угадывание меньшей части открытого сообщения и последующий процесс нахождения алгоритма шифрования для выявления роторной конфигурации. Такая часть сообщения называется crib. Самым распространенным crib-ом во время войны было сообщение «keine besonderen ereignisse» — нечего докладывать. Определить же местонахождение в тексте известной его части помогал тот факт, что Энигма не шифровала буквы в самих себя, что облегчало использование данной стратегии. Далее нужно было определить роторную конфигурацию. Основная идея здесь — только лишь конечный набор установок Энигмы мог составить пары букв, полученные путем сопоставления шифротекста и crib«a. Все, что нужно было сделать — это перебрать все возможные такие установки, что в целом могло бы быть реализовано, учитываю большую британскую команду ученых. Однако наличие штекерной панели делало взлом Энигмы таким способом практически невозможным в силу огромного количества вариантов взаимных коммутаций букв. Справится с этим препятствием помогло предположение о том, что пары буквы шифротекста и crib«a не зависели от штекерной панели. Чтобы ускорить процесс обнаружения этих закономерностей и перебора всех возможных вариантов конфигураций Энигмы, ученые из Блетчли-парк разработали знаменитый электронный аппарат — Бомбу, что поспособствовало победе, одержанной в этой непростой шифровальной дуэли.
