Курс "Защита информации", кафедра радиотехники, Московский физико-технический институт (МФТИ)

2010: Главная Экзамен Лекции Семинары Проекты Эссе | Преподаватели Литература | Архив: 2009 2008-fall 2008 2007 2006 2005 2004 2003 | English
HTML-версия эссе "History of cryptography Enigma", Ozerov, 2003, сгенерированная из pdf/rtf.
Конвертация не вcегда корректна. Смотрите исходный pdf.
Озеров В В 911 гр Введение.
В двадцатых годах прошлого века для автоматизации процесса шифрования были изобретены различные механические шифровальные устройства. Большинство из них -американская машина SIGABA (М-134), английская TYPEX, немецкая ENIGMA, японская PURPLE были роторными машинами. основе конструкции большинства таких машин лежала концепция ротора - механического колеса, используемого для выполнения подстановки. Роторная машина состоит из клавиатуры и набора связанных между собой роторов. Принцип работы таких машин основан на много алфавитной замене символов исходного текста по длинному ключу согласно версии шифра Вижинера. Остановимся подробнее на этом шифре.
Рис 1. Немецкая шифровальная роторная машина Enigma.
Система шифрования Вижинера
Система Вижинера впервые была опубликована в 1586 г. и является одной из старейших и наиболее известных многоалфавитных систем. Свое название она получила по имени французского дипломата XVI века Блеза Вижинера, который развивал и совершенствовал криптографические системы.
Система Вижинера подобна такой системе шифрования Цезаря, у которой ключ подстановки меняется от буквы к букве. Этот шифр многоалфавитной замены можно описать таблицей шифрования, называемой таблицей (квадратом) Вижинера. На рисунках ниже показаны таблицы Вижинера для русского и английского алфавитов соответственно.
Таблица Вижинера используется для зашифрования и расшифрования. Таблица имеет два входа:
• верхнюю строку подчеркнутых символов, используемую для считывания очередной буквы исходного открытого текста;
• крайний левый столбец ключа.
Последовательность ключей обычно получают из числовых значений букв ключевого слова.
При шифровании исходного сообщения его выписывают в строку, а под ним записывают ключевое слово (или фразу). Если ключ оказался короче сообщения, то его циклически повторяют. В процессе шифрования находят в верхней строке таблицы очередную букву исходного текста и в левом столбце очередное значение ключа. Очередная буква шифртекста находится на пересечении столбца, определяемого шифруемой буквой, и строки, определяемой числовым значением ключа.
Пусть ключевая последовательность имеет длину r, тогда ключ r-алфавитной подстановки есть r-строка
Система шифрования Вижинера преобразует открытый текст
шифртекстс помощью ключасогласно
правилу
Таблица Вижинера для русского алфавита
Таблица Вижинера для английского алфавита
Рассмотрим пример получения шифр текста с помощью таблицы Вижинера. Пусть в качестве ключа выбрано слово АМБРОЗИЯ. Необходимо зашифровать сообщение ПРИЛЕТАЮ СЕДЬМОГО.
Выпишем исходное сообщение в строку и запишем под ним ключевое слово с повторением. В третью строку будем выписывать буквы шифр текста, определяемые из таблицы Вижинера.
Принцип действия роторной машины.
В 20-х годах XX века были изобретены электромеханические устройства шифрования, автоматизирующие процесс шифрования. Принцип работы таких машин основан на многоалфавитной замене символов исходного текста по длинному ключу согласно версии шифра Вижинера. Большинство из них - американская машина SIGABA (М-134), английская TYPEX, немецкая ENIGMA, японская PURPLE были роторными машинами.
Главной деталью роторной машины является ротор (или колесо) с проволочными перемычками внутри. Ротор имеет форму диска (размером с хоккейную шайбу). На каждой стороне диска расположены равномерно по окружности m электрических контактов, где m - число знаков алфавита (в случае латинского алфавита m = 26). Каждый контакт на передней стороне диска соединен с одним из контактов на задней стороне, как показано на рисунке. В результате электрический сигнал, представляющий знак, будет переставлен в соответствии с тем, как он проходит через ротор от передней стороны к задней. Например, ротор можно закоммутировать проволочными перемычками для подстановки G вместо A, U вместо В, L вместо С и т.д.
Банк роторов
При повороте ротора из одного положения в другое подстановка, которую он осуществляет в приходящем сигнале, будет изменяться. В общем случае эту подстановку можно записать в виде
где  - подстановка, реализуемая ротором в его начальном положении; С - циклический сдвиг на одну позицию; C j - циклический сдвиг на j позиций.
Например, если начальная подстановка ротора  (А) = G и ротор сдвигается на три позиции (j = 3), то открытый текст D будет против того контакта ротора, который используется
Схема формирования подстановки при сдвиге ротора (j =3)
для представления открытого текста А, а шифрованный текст J окажется против того контакта ротора, который используется для представления шифрованного текста G, и результирующая подстановка Т(D) = G при j = 3. Алгебраически это записывается в виде
Роторы можно объединить в банк роторов таким образом, чтобы выходные контакты одного ротора касались входных контактов следующего ротора. При этом электрический импульс от нажатой клавиши с буквой исходного текста, входящий с одного конца банка роторов, будет переставляться каждым из роторов, до тех пор, пока не покинет банк.
Математически работу банка роторов можно описать в виде
Такой банк может реализовывать большое число подстановок, соответствующих различным комбинациям положений роторов. Для получения сильной криптографической системы расположение роторов должно меняться при переходе от знака к знаку сообщения.
Роторная машина состоит из банка роторов и механизма для изменения положения роторов с каждым зашифрованным знаком, объединенного с устройствами ввода и вывода, такими как устройство считывания с перфоленты и печатающее устройство.
Простейшее из возможных движений ротора - это движение по принципу одометра; оно использовалось в немецкой машине Enigma во время второй мировой войны. При шифровании одного знака правое крайнее колесо поворачивается на одну позицию. Когда это (и любое другое) колесо переместится на m позиций и совершит полный оборот, колесо, расположенное слева от него, передвинется на одну позицию, и процесс будет повторяться. Этот процесс проведет банк роторов сквозь все его возможные положения, прежде чем цикл повторится. Поскольку все роторы перемещаются с разными скоростями, период n-роторной машины составляет 26n (при m = 26).
Для закона движения ротора желательны следующие характеристики:
• период должен быть большим;
• после шифрования каждого знака все роторы или большая их часть должны повернуться друг относительно друга.
Движение по принципу одометра оптимально в смысле первого требования, но совершенно неудовлетворительно в отношении второго требования. Улучшение движения по принципу одометра можно получить, если поворачивать каждый ротор более чем на одну позицию. Если смещения каждого ротора не имеют общих множителей с объемом алфавита m, то период останется максимальным.
Другое решение заключается в ограничении числа допустимых остановочных мест для каждого ротора за счет введения внешнего фиксирующего кольца, на котором
определенным способом зафиксированы места остановок. При использовании латинского алфавита можно заставить машины поворачиваться и останавливаться следующим образом. Первому колесу разрешается останавливаться в каждой из 26 позиций, второму колесу - только в 25 позициях, третьему колесу - только в 23 позициях, и так далее до шестого колеса, которому разрешается останавливаться только в 17 позициях. Период такой роторной машины теперь составляет 101 млн, а не 266309 млн, как в случае движения по принципу одометра. Потеря в длине периода с успехом окупается полученной сложностью движения роторов. Теперь второе требование удовлетворяется довольно хорошо, поскольку каждое из колес перемещается после шифрования каждого знака и многие колеса могут двигаться друг относительно друга.
Роторная машина может быть настроена по ключу изменением любых ее переменных:
•роторов;
•порядка расположения роторов;
•числа мест остановки на колесо;
•характера движения и т.д.
Поскольку перекоммутировать роторы трудно, то обычно на практике машины обеспечивали комплектом роторов, в котором находилось больше роторов, чем можно одновременно поместить в машину. Первичная настройка по ключу производилась выбором роторов, составляющих комплект. Вторичная настройка по ключу производилась выбором порядка расположения роторов в машине и установкой параметров, управляющих движением машины. С целью затруднения расшифрования шифртекстов противником роторы ежедневно переставляли местами или заменяли. Большая часть ключа определяла начальные положения роторов (2б3=17576 возможных установок) и конкретные перестановки на коммутационной доске, с помощью которой осуществлялась начальная перестановка исходного текста до его шифрования (26!= 41026 возможностей).
Роторные машины были самыми важными криптографическими устройствами во время второй мировой войны и доминировали по крайней мере до конца 50-х годов.
Рассмотрим подробнее одну из них, немецкую Enimgу.
Шифромальная система Enigma.
Шифровальное устройство Enigma использовалось немцами во Второй Мировой войне. Фотография устройства приводится ниже.
Enigma была изобретена в начале 1900-х в Германии Артуром Шербиусом (Arthur Scherbius) и использовалась во второй мировой войне, в частности на подводных лодках для связи с штабом. Enigma имела батарею, позволяющую ей при работе не зависеть от внешних источников энергии, клавиатуру, набор светящихся индикаторов для каждой буквы и набор роторов. Процесс перекоммутации контактов на противоположных сторонах ротора был довольно трудоемким. Фактически приходилось соединять каждую пару отдельно, причем высока была вероятность ошибиться, что привело бы к невозможности расшифровки и отправки шифрограмм, понятных для принимающей
стороны. Поэтому к Enigme, как правило, прилагался набор сменных надлежащим
образом скоммутированных роторов. Обычно общее число роторов составляло 5-7 штук.
Смена ключа производилась сменой роторов.
Каждый ротор Enigmы содержал 52 контакта (2 x число букв латинского алфавита).
Внутреннее устройство ротора схематически показано на рисунке. На рисунке видно, что
провода соединяют контакты не по порядку, например 1 верхний контакт соединен с 15-м
нижним.
Enigma имела 3 таких ротора работающих вместе (4 в конце войны). Последний ротор соединялся с так называемым рефлектором (или отражающим ротором), назначение которого было - заставить роторы обработать каждую букву дважды (это увеличивало период шифра и соответственно безопасную длину сообщений). Половина из 52 контактов каждого ротора была соединена с клавиатурой и батареей, другая половина - с индикаторами. Каждая кнопка клавиатуры замыкала электрическую цепь и загорался индикатор. Какой именно индикатор загорится зависело от положения роторов и от рефлектора.
Для шифрования или расшифрования немецкий шифровальщик должен был установить роторы в начальное положение - задать ключ. Шифрование выполняялось следующим образом. Шифровальщик вводил с клавиатуры буквы исходного текста и смотрел какая индикатор с какой буквой загорится, после чего следовало изменить положение роторов. Так как роторы вращались после каждой буквы, одна и та же буква могла быть зашифрована по-разному. Буква Z использовалась для пробелов, все числа писались словами. Это повышало надежность передачи и сокращало размер необходимого алфавита.
Несмотря на сложность конструкции и алгоритма, Enigma было взломана в ходе войны. Сначала группа польских криптоаналитиков взломала шифр Enigmы и поделилась принципом вскрытия с англичанами. В ходе войны немцы неоднократно модифицировали Enigmу но англичане продолжали анализ новых версий шифров и успешно вскрывали. Несколько роторных машинок были захвачены на подводных лодках.
Список литературы:
1)   Брюс Шнайер "Прикладная криптография"
2)   A. Hodges, Alan Turing "The Enigma of Intelligance, Simon and Schuster"
3)   В. Kahn "Seizing the Enigma" Internet:
4)   http://www.balakovo.san.ru/~mishin/oreilly/tcpip/puis/ch06_03.htm
5)   http://ophil.riva.gomel.by/people/Dennis-M-Richie/crypt.html


Page last update: Fri Jun 10 10:11:25 2005 MSD.
Website last update:
Rambler's Top100 Рейтинг@Mail.ru