Англия.
http://www.bratishka.ru/archiv/2013/01/2013_1_10.php
Весной 1939 г., когда английская сторона случайно получила доступ к немецким правительственным секретам. В находящимся севернее Лондона местечке Блетчли в дешифровальном центре при 'Правительственной школе кодов и шифров' был раскрыт секрет 'Энигмы', электронной шифровальной машинки, используемой Верховным командованием Вермахта, центральными аппаратами СС, СД и полицией для шифровки секретнейших данных, передаваемых по радио. Ежедневно немецкой стороной велось до двух тысяч таких переговоров, причем немецкое командование было уверено в невозможности их дешифровки. Работа 'Центра' находилась под непосредственным контролем У.Черчилля, структура и оборудование его непрерывно совершенствовалась, персонал находился на казарменном положении и составлял несколько тысяч высококвалифицированных специалистов .
Взломщик кода шифратора "Энигма" Алан Тюринг (Alan Turing), покончивший с собой после обвинения в непристойном поведении в соответствии с законом против гомосексуализма, может быть посмертно помилован.
Тюринга, который умер от отравления цианидом в возрасте 41 года в 1954 году после того, как его подвергли "химической кастрации".
Данное заявление свидетельствует об изменении позиции правительства, которое в прошлом году отказало в помиловании 49000 ныне мертвых гомосексуалистов, осужденных в соответствии с поправкой Лабушера от 1885 года. Среди осужденных был Оскар Уайлд.
Ахмад заявил пэрам: "Сам Тюринг считал, что гомосексуализм будет объявлен легальным королевской комиссией. На самом деле, гомосексуализм, за который его осудили, исключил из Блетчли-парке (там в годы Второй мировой войны размещалась правительственная школа кодов и шифров - прим. перев.). Леди Трампингтон заявила пэрам: "Тот корпус, где я работала, занимался военно-морскими шифрами Германии. Мне лишь раз довелось готовить документ для Алана Тюринга, и поэтому я не могу утверждать, что знала его. Однако я уверена в том, что если бы не его работа, мы проиграли бы войну из-за голода".
Тюринг взламывал немецкие шифры при помощи своей машины "Бомба", которая помогла дешифровщикам расшифровывать немецкие коды шифратора "Энигма". Его коллега Томми Флауэрс (Tommy Flowers) создал компьютер Colossus. Ахмад назвал Тюринга "одним из отцов, если не главным отцом кибернетики".
Робин Гэнди (Robin Gandy), единственного аспиранта Тюринга. Гэнди стал близким другом Тюринга и исполнителем его воли.
Шарки заявил: "Как всем должно быть хорошо известно, он был осужден в 1952 году за непристойное поведение, и его приговорили к химической кастрации. Спустя два года Тюринг совершил самоубийство. Правительство знает, что Тюринг был героем и великим человеком. Оно признает факт жестокого с ним обращения. Видимо, оно осознало, с каким уважением к нему относятся в нашей стране и во всем мире".
Польша.
"Энигма" использовалась в Германии с 1928 года, весь период после прихода к власти Гитлера и годы Второй мровой войны. В Шифровальтном бюро Варшавы в 1932 году начались работы над раскрытием тайны "Энигмы".
Возглавлял группу молодой польский математик Мариан Ршевский, выпускник математичекого факультета университета в Познани.Группа имела в своем распоряжении устаревшую коммерческую шифровальную машину, купленную в Германии. Конечно, эта модель была очень далека от современных для той поры немецких военных шифровальных машин и принесла мало пользы. Поэтому главным моментом в работе ученых для решения задачи "Энигмы" было применение математики (теории групп и теории перестановок).
В январе 1933 года было теоретически воссоздано устройство машины, что позволило позже создать её реальную модель; были разработаны также методы восстановления ключей к шифрам на основе перехваченных сообщений.
Позднее, в 1939 году, материалы по "Энигме" были переданы во Францию и Англию. Англичане продолжили работы, раскрыв усовершенствования, которые были внесены в конструкцию последних немецких машин, и систему кодов, используемую Германией. В этой работе, выполнявшейся большой группой ученых в местечке Блетчли в 70км от Лондона, учавствовал знаменитый математик Алан Тьюринг, широко известный как автор воображаемой "машины Тьюринга".
Работа сохранялась в глубокой тайне, и немцы даже не подозревали, что все их секретные сообщения становятся известны антигитлеровской коалиции. Многие историки, изучающие Вторую мировую войну, убеждены, что это значительно ускорило пдение фашистской Германии и сохранило тысячи жизней. История "Энигмы" держалась в глубокой тайне и после окончания войны; она была опубликована только 30 лет спустя, по истечении срока давности военны секретов.
Воистину, во второй половине ХХ века произошла подлинная революция в криптографии. В современной схеме кодирования с открытым ключом ни кодировочная машина, ни ключ шифрования не являются секретными! То есть для шифрования сообщения вообще не нужно знать никаких секретов (секретный ключ нужен только для дешифровки), и шифр практически нельзя взломать.
Принцип работы "Энигмы" сводится к замене символов вводимого текста по таблице соответствия. Для увеличения количества возможных вариантов в "Энигме" такая замена производилась несколько раз. Роль шифрующего узла при этом играла комбинация специальных дисков - роторов, каждый из которых представлял 26 букв латинского алфавита.
Сообщения, обрабатываемые в рамках проекта M4, были зашифрованы при помощи четырёхроторной машины, сообщает CNET News. В Германии в то время считали, что такую защиту невозможно взломать при всём желании, поскольку теоретически она предполагала 2∙10 145 вариантов кодирования. И действительно, после перехвата союзники так и не смогли прочесть эти сообщения.
Атака на шифр "Энигмы"
Говоря о проекте создания "Энигмы" (лат. "загадка"), нельзя не вспомнить, пожалуй, первую из книг по истории криптографии [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]. Там же фактически приведена и оценка вычислительных затрат для случая, когда противник имеет неограниченный доступ к оборудованию, что и соответствовало действительности (полный комплект оборудования "Энигмы" англичане в свое время сняли с умышленно затопленных на мелководье немецких подводных лодок).
Атака на шифр "Энигмы" строится следующим образом.
Перебором находятся использованные для шифрования диски и их взаимное расположение. Критерий перебора - максимальное значение индекса совпадения. Трудоемкость перебора - 60?263 операций расшифровывания (5?4?3=60 - количество выборов трех дисков из пяти, для каждого из которых существует 26 начальных положений - по числу символов алфавита). На этом этапе не учитываются ни положение штекеров в коммутационной панели, ни угловые положения сепараторов. В силу этого угловые положения дисков считаются не вызывающими доверия.
Опять же с помощью перебора находится положение первого из сепараторов и первого из шифрующих дисков. Критерий перебора все тот же - максимальное значение индекса совпадения. Трудоемкость - 264 операций расшифровывания (три диска и один сепаратор). Поскольку положение второго сепаратора здесь не учитывается, то угловые положения второго и третьего шифрующих дисков доверия не вызывают, а результатом будут начальные угловые положения первого из дисков и первого сепаратора (а также комплект и порядок следования дисков с этапа 1).
Перебором положения второго сепаратора, а также второго и третьего шифрующих дисков по максимуму индекса совпадения находится начальное угловое положение дисков и сепараторов. Трудоемкость этой операции - 263 расшифровываний. Положение штекеров все еще остается неопределенным. Общая трудоемкость подбора положения сепараторов и дисков составляет 60?263+264+263 расшифровываний.
Для найденного положения дисков и сепараторов определяется положение штекеров до получения осмысленного текста. Делается это на основе анализа триграмм.
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.263+264+263+26?25?24+23?22?21+...+5?4?3+2 вариантов, что составляет примерно 221 пробных расшифровываний. По нынешним временам это, конечно, немного. Для сравнения: алгоритм шифрования известного архиватора PKZIP Роджера Шлафлы имеет временную сложность около 227, а его вскрытие на обычном персональном компьютере занимает всего лишь несколько часов [3, с. 443-444].
При неизвестной распайке контактов шифрующих дисков взлом "Энигмы" резко усложняется. Действительно (см. приведенное далее утверждение), уже на первом этапе число проб расшифровывания вместо 60?263 сразу возрастает до 25!?(25!-1)?(25!-2)?263, т.е. более чем в 2230 раза. При таких условиях "Энигма", пожалуй, не взламываема и на современных вычислителях.
Главная проблема при использовании шифров многоалфавитной замены связана с хранением множества самих алфавитов. Пожалуй, самое удачное решение здесь было предложено Эдвардом Хеберном (ставшим впоследствии знаменитым из-за своей роли во Второй мировой войне) в 1917 г. в прообразе электромеханического шифратора "Энигма". Промышленный образец "Энигмы" был создан чуть позднее берлинским инженером Артуром Кирхом (или Артуром Шербиусом - по другим источникам).
Однако выпущенные тогда "Энигмы" не нашли спроса, а производившая их небольшая фирма в конце концов разорилась. Положение изменилось лишь в 1930-е годы с возрождением германского милитаризма. В 1939 г. массовое производство "Энигм" было развернуто в оккупированной Польше.
Промышленный образец "Энигмы" состоял из четырех вращающихся на одной оси шифровальных дисков, которые можно было менять местами (хотя использовалось это крайне редко) с 25 символами усеченного латинского алфавита (обычно с отождествленными буквами I, J и U, V, подобно тому как в русском алфавите часто отождествляют буквы Е, Ё и, несколько реже, И и Й).
Перед началом работы диски устанавливались в определенное четырехбуквенным ключом положение, а после зашифровывания очередного символа входной диск поворачивался на 1/25 (по числу символов) полного (360?) оборота, осуществляя смену текущего алфавита. После зашифровывания первых 25 символов на тот же угол поворачивался следующий за ним диск, точь-в-точь как в механическом счетчике электроэнергии. Число различных взаимных положений дисков и, следовательно, общее число m реализованных в "Энигме" алфавитов составляло 254, что было весьма внушительным для столь простого устройства. Раскрытие сообщений короче указанного (390 625) или несмысловых без знания других деталей устройства при этом представляло неразрешимую задачу.
На боковых сторонах размещались по 25 (опять же по числу символов) соприкасающихся у смежных дисков контактов, соединенных попарно с контактами на противоположной стороне. Внешние контакты крайних дисков использовались для ввода шифруемого и вывода зашифрованного символов. Каждый символ при проходе через "Энигму" претерпевал четыре (по числу дисков) замены.
Для расшифровки сообщений диски устанавливались в соответствии с кодовым словом, а вход и выход "Энигмы" переключались.
Главным секретом "Энигмы" была распайка контактов, знание которой позволяло вскрывать и короткие смысловые шифровки обычным в таких случаях методом подбора ключей. В погоне за этим секретом англичане устроили настоящую охоту на немецкие подводные лодки, преднамеренно затапливая их на мелководье, чтобы снять установленные на них "Энигмы". По иронии судьбы соединение контактов используемых немцами "Энигм" в точности соответствовало промышленному образцу выпуска аж 1917 г., во что англичане просто отказывались верить, явно переоценив своего противника.