Секретная жизнь ранних ЭВМ. Как криптография повлияла на появление современных цифровых компьютеров, и почему об этом надолго забыли

МЕНЮ


Главная страница
Поиск
Регистрация на сайте
Помощь проекту
Архив новостей

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


Об истории первых шифровальных машин и устройств для дешифрования, о том, как дешифровальные службы повлияли на развитие ЭВМ и компьютерной лингвистики

В этом году исполнилось 80 лет с момента первого практического применения двоичного компьютера — лампового гиганта Colossus («Колосс»). Его разработали в Блетчли-парке — поместье в центре Англии, где во время Второй мировой войны базировалась британская шифровальная служба GC&CS. Colossus использовали для дешифрования перехваченных немецких сообщений, зашифрованных с помощью шифровальных машин Lorenz SZ-40 и SZ-42. Там же, в Блетчли, знаменитый математик Алан Тьюринг занимался взломом «Энигмы», еще одной немецкой шифровальной машины.

«Колоссы» производились в строжайшей секретности. Большая их часть была уничтожена сразу после войны, два последних экземпляра разобраны в 1960-е, а само их существование было рассекречено только в 1974 году. В этом материале мы расскажем о невидимой руке криптографии и криптоанализа в развитии ЭВМ.

«Искусственная разведка»

Первый этап развития компьютеров и информационных технологий неразрывно связан с криптографией: фундаментальные основы теории информации были независимо разработаны Клодом Шенноном и Владимиром Котельниковым во время работы над решением проблем секретной связи, опыт Алана Тьюринга в Блетчли-парке повлиял на его послевоенную работу в области информатики и искусственного интеллекта, а одними из первых заказчиков вычислительных машин на всех этапах их развития, начиная с электромеханических табуляторов IBM и заканчивая современными квантовыми компьютерами, были шифровальные службы.

До 1970-х годов непосредственно на компьютерах никто ничего не шифровал: они были громоздкими и дорогими, а электромеханические машины были доступными и портативными. Компьютеры использовались для криптоанализа (взлома вражеских шифров и анализа стойкости собственных шифров), тестирования случайных последовательностей чисел1, для частотного анализа текстов на разных языках, а также для аналитики больших объёмов разведданных.

Эта сторона истории ЭВМ во многом остается белым пятном. Достижения ЭВМ в других сферах — например, расчеты по баллистике и термоядерному оружию на американском ENIAC, достаточно быстро стали достоянием общественности и предметом гордости американской науки. А вот публикации о компьютерном криптоанализе могли выдать ценный источник разведывательной информации, поэтому их почти не было. Взлом «Энигмы» был так хорошо скрыт, что и после войны немцы считали, что потери флота после июля 1942 года были связаны с высокоточными американскими радарами. «Никто так и не понял, что криптоанализ, а не радары и системы обнаружения и наводки, раскрыл позиции и цели немецких подлодок2».

Не случайно многие прорывные работы в области искусственного интеллекта написали специалисты, работавшие в области криптографии и криптоанализа в годы Второй мировой войны. Самыми известными из них являются Клод Шеннон и Алан Тьюринг. Можно сказать, что криптоанализ — это вывернутый наизнанку тест Тьюринга. Если тест предполагает поиск сообщений, созданных машиной, среди текстов, написанных человеком, то криптоанализ в первой половине ХХ века заключался в поиске паттернов человеческого языка в псевдослучайном потоке, сгенерированном шифровальной машиной.

Читая тексты 1940–1950-х годов, иногда кажется, что artificial intelligence корректнее перевести не как «искусственный интеллект», а как «искусственная разведка». Ведь первые задачи, которые ставились перед ИИ в рамках проекта DARPA, связаны именно с разведкой: машинный перевод (в первую очередь с русского языка), анализ текстов, выделение паттернов в разведданных, машинное зрение. И сегодня не стоит забывать, что за яркими ширмами ChatGPT, DALL-E и голосовых ассистентов в тени прячутся и другие сферы применения ИИ — распознавание лиц, дата-майнинг в целях деанонимизации, обработка больших данных в криптоанализе и радиоразведке, например при атаке по побочным каналам.

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

С чего всё началось?

Потребность в автоматизации криптоанализа стала логичной реакцией на автоматизацию шифрования. 

Первые использованные на практике шифровальные машины были разработаны в 1910-х годах, а первые патенты появились в 1918–1921 годах. Именно в интербеллум криптография вступила в индустриальную эпоху: процесс шифрования многократно ускорился, стойкость шифров повысилась, а требования к теоретической подготовке шифровальщиков стали ниже. Почти синхронно патенты на шифровальные машины получили пятеро изобретателей: Артур Шербиус из Германии (создатель знаменитой «Энигмы»), Гуго Кох из Голландии (который, судя по последним данным, был плагиатором), Арвид Дамм из Швеции, Эдвард Хеберн и Гилберт Вернам из США. Устройства Шербиуса, Дамма, Коха и Хеберна относятся к одному типу — дисковым шифровальным машинам, хотя в их конструкциях были существенные различия. А вот шифр Вернама стоит особняком — фактически он является первым двоичным шифром и с определенными оговорками можно сказать, что он используется в криптографических алгоритмах до сих пор.

Иллюстрация из патентной заявки Эдварда Хеберна 1921 года. На столе расположены шифровальная машина (справа) и электрическая пишущая машинка (слева). Когда на клавиатуре шифровальной машины набирается сообщение, оно сразу же печатается в зашифрованном виде на пишущей машинке. 

Работа всех этих шифровальных машин была основана на принципе полиалфавитного шифрования, при котором используется несколько моноалфавитных шифров замены. Первый алгоритм для взлома таких шифров независимо друг от друга разработали Чарльз Бэббидж и Фридрих Вильгельм Касиски в 1854 и 1863 годах. Однако сложность реализации метода Бэббиджа — Касиски зависела от периода ключа — того, насколько часто повторяется алфавит замены. Сообщение с коротким (до 8 букв) периодом ключа человек мог взломать за нескольких часов, хотя это было трудно и утомительно. У «Энигмы» период ключа равнялся 17576 буквам. Для того, чтобы взломать такой шифр, нужно было не только усовершенствовать метод Бэббиджа — Касиски, но и ускорить выполнение рутинных операций. И здесь на помощь пришли вычислительные машины, которые могли очень быстро быстро осуществлять монотонные операции по определенному алгоритму и ускорять таким образом работу криптоаналитика. Не случайно именно Бэббидж разработал аналитическую машину — первое программируемое вычислительное устройство, способное циклически выполнять любые арифметические и логические операции по заранее заданной программе и останавливаться по условию (при получении определенного результата). 

Для того, чтобы понять, зачем были созданы первые криптоаналитические вычислительные машины, давайте сначала разберемся, как работали шифровальные машины.

Как эти машины работали? 

Дисковые шифровальные машины (в западной литературе их также называют роторными) основаны на достаточно простой идее. Представим себе, что у нас есть две электрические пишущие машинки. Каждую клавишу на одной машинке мы подключим проводом к другой клавише на второй машинке, а провода перепутаем. При нажатии на букву «А» вторая машинка напечатает, например, букву «Е»3. Это шифр простой замены. Чтобы усложнить его, мы добавим между машинками подвижный элемент — шифровальный диск. При каждом нажатии на клавишу он будет совершать шаг, схема соединения букв друг с другом будет меняться, и машина при шифровании каждый раз будет заменять букву разными символами. Например, последовательность букв «ААААА» превратится в «ЕНВСМ». Если мы добавим несколько дисков подряд и усложним правила, по которым они шагают, можно создать достаточно безопасную систему шифрования.

Иллюстрация из патентной заявки Эдварда Хеберна 1921 года. Внутри диска контакты, соответствующие разным буквам, попарно соединены проводами. При вращении диска способ подключения букв друг к другу меняется.

Иллюстрация аналогичной схемы в патентной заявке Артура Шербиуса (разработчика «Энигмы») 1918 года. 

Автоматизацией взлома дисковых машин первыми занялись сотрудники польского Бюро шифров. Уже в 1932 году математик Мариан Реевский разработал метод взлома «Энигмы», опираясь на теорию групп перестановок. Его задачу упростили разведывательные данные от завербованного французами немца Ганса-Тило Шмидта. Для его автоматизации Реевский и другие сотрудники Бюро в 1934 году собрали устройство под названием «Циклометр», а в 1938-м разработали первую «Криптологическую бомбу». В 1939 году наработки поляков были переданы в британский Блетчли-парк, где была собрана знаменитая «Бомба Тьюринга». Все эти устройства представляли собой специализированные аналоговые компьютеры, состоявшие из нескольких функциональных копий «Энигмы» (36 в случае «Бомбы Тьюринга»), которые на большой скорости перебирали возможные комбинации настроек шифровальной машины. Это был своеобразный «брутфорс» (взлом методом перебора), в котором количество вариантов перебора было сокращено с помощью определенных эвристических методов.

«Бомба» Тьюринга

В это же время перспективы автоматизации криптоанализа оценил и Уильям Фридман, ведущий криптограф AFSA (Army Forces Security Agency, Агентство безопасности вооруженных сил США, предшественник современного Агентства национальной безопасности). В 1934 году Фридман осознает ценность табуляторов (электромеханических вычислительных машин) для криптоанализа и составления новых кодов и добивается аренды таких машин у компании IBM для криптографической службы AFSA. Так он стал пионером в использовании вычислительных машин общего назначения для криптоанализа еще до появления полноценных электронных компьютеров. Главное отличие подхода Фридмана заключалось в том, что он предложил использовать коммерчески доступные машины и разрабатывать для них программы, а не разрабатывать для каждой новой шифровальной машины свое специализированное устройство (например, после каждого обновления «Энигмы» приходилось серьёзно модифицировать «Бомбы»). 

Однако более важную роль в развитии ЭВМ сыграл второй тип шифровальных машин, разработанный Гилбертом Вернамом.

Абсолютная стойкость

Шифр Вернама с механической точки зрения устроен проще, чем дисковые шифровальные машины. Вместо того, чтобы использовать для каждой буквы отдельный провод и «запутывать» их с помощью дисков, перед шифрованием мы можем превратить буквы в двоичную последовательность чисел с помощью кода Бодо — первого в истории техники двоичного способа кодирования информации, разработанного французским телеграфистом Эмилем Бодо в 1870 году. А с двоичным кодом гораздо проще совершать логические и математические операции. С помощью кода Бодо сообщения можно записывать на бумажные перфоленты (отверстиями кодируются единицы, а отсутствием отверстий  —  нули). В современной терминологии код Бодо является пятибитным, то есть каждой букве соответствует комбинация из пяти нулей или единиц.

Первая версия кода Бодо (1870). Впоследствии на ее основе был разработан международный телеграфный код МТК-2, а также различные локальные варианты, в частности советский СТ-35

Пятибитная и восьмибитная перфоленты с нанесенными на них данными

Гилберт Вернам предложил взять две перфоленты и нанести на одну ключ, а на другую открытый (незашифрованный) текст, а затем суммировать их (вместо простого сложения используется сложение по модулю два, также известное как XOR, исключающее или). Поскольку код Бодо представляет собой пятибитную двоичную последовательность, для этой операции достаточно всего пяти электромеханических реле (а позже ламп или транзисторов). Результатом их суммирования и станет зашифрованный текст. Чтобы восстановить открытый текст, достаточно проделать ту же самую операцию  — сложить по модулю два зашифрованный текст и ключ. Причем, так как операция XOR симметрична, шифрование и расшифрование можно выполнять с помощью одной и той же схемы  —  не нужно никакого переключателя  «Зашифрование/Расшифрование».

Иллюстрация принципа работы шифра Вернама

Иллюстрация из патента на реализацию шифра Вернама компании Siemens & Halske (1921). На одной перфоленте записано сообщение (3), на другой — ключ (5). Пять щупов (39 и 40) считывают с них информацию, которая затем суммируется по модулю при помощи реле (20) и отправляется по линии связи.

Еще одним важным плюсом этого метода было то, что, поскольку результат шифрования также был закодирован с помощью кода Бодо, его можно было сразу передавать по телеграфной линии связи. Это был первый пример поточного, или линейного шифрования, в котором процессы ввода сообщения, его зашифрования, передачи по линии связи, расшифрования и вывода могли происходить одновременно. Как это устроено? Для того, чтобы реализовать такую систему безопасной связи, нам нужно два телетайпа, две шифровальные машины и канал связи между ними — провод или радиоканал. Между телетайпами и каналом связи устанавливаются шифровальные машины и, когда мы нажимаем клавишу на одном телетайпе, сигнал проходит через шифровальную машину, зашифровывается, передается по линии связи, попадает в шифровальную машину получателя, расшифровывается и сразу же печатается на втором телетайпе. При правильно настроенных устройствах даже не требуется присутствие шифровальщика со стороны получателя.

В советской традиции такой шифр называется шифром гаммирования (альфа — открытое сообщение, бета — зашифрованное сообщение, гамма — ключ).

XOR ? = ?

XOR ? = ?

XOR ? = ?

Современники Вернама понимали, что несмотря на простоту алгоритма, взломать такой шифр очень сложно. А в 1940-х советский ученый Владимир Котельников и его американский коллега Клод Шеннон независимо друг от друга доказали, что при выполнении определенных правил этот шифр взломать невозможно. Шифр Вернама является аппаратной реализацией шифра одноразовых блокнотов, который обладает абсолютной стойкостью, если:

1. Длина ключа шифрования равна длине сообщения (каждой букве сообщения соответствует один символ ключа).

2. Ключ заготовлен заранее и известен только отправителю и получателю.

3. Ключ используется только один раз.

4. Ключ истинно случаен.

У шифра Вернама было три важных минуса. 

Во-первых, с механической точки зрения нужно было добиться синхронизации двух потоков — перфолент с текстом и ключом. Забегая вперед, скажем, что потребовалось больше двадцати лет, чтобы решить эту проблему — первым серийным устройством такого типа стала советская шифровальная машина М-100, запущенная в производство в 1938 году после почти семи лет отладки и экспериментов; за ней последовали британско-канадская Rockex (1942) и немецкая Siemens T-43 (1943).

Фото шифровальной машины Siemens T-43 с аукциона Bonhams

Во-вторых, требовалось заготовить большой объем ключей и распределить их между абонентами так, чтобы у каждой возможной пары абонентов был свой уникальный ключ, ведь повторное использование одного и того же ключа с разными текстами приводило к его компрометации.

И в-третьих, ключ должен быть истинно случаен, то есть каждый следующий бит ключа никак не должен быть связан с предыдущими. Для создания такой последовательности не подходят никакие алгоритмы — по определению они закономерны, то есть предсказуемы. Истинно случайные последовательности в криптографии можно получить только с помощью физических процессов — броска костей, лото, показателей теплового шума или распада радиоактивных элементов. А что, если в такую последовательность закрадётся закономерность? Например, одна из костей будет изготовлена с дефектом, или кто-то подменит фишки в лото… Такие последовательности нужно особым образом анализировать и контролировать, насколько «качественная» в них случайность.

Для того, чтобы решить эти проблемы, многие производители пошли на компромисс. Вместо истинно случайных последовательностей они решили использовать генераторы псевдослучайных чисел. Благодаря такому генератору вместо того, чтобы заранее заготавливать длинные ключи, отправителю и получателю перед отправкой сообщения достаточно было договориться о стартовых настройках (например, о позициях шифровальных дисков) и запустить свои генераторы, которые производили одинаковую ключевую последовательность. Шифр Вернама с использованием генератора псевдослучайных чисел применяется до сих пор. Если вы сейчас подключены к Wi-Fi роутеру, то ваш трафик скорее всего зашифровывается именно так — случайная последовательность генерируется с помощью алгоритма RC4, а затем суммируется по модулю 2 с теми данными, которыми ваш телефон или компьютер обменивается с роутером.

В любой псевдослучайной последовательности неизбежно найдутся закономерности, но обнаружить их вручную почти нереально. Во второй части статьи мы поговорим о том, как при помощи шестеренок приручить случайность, и почему только программируемый двоичный компьютер мог совладать с немецкой шифровальной машиной Lorenz SZ-40, а также о том, как продолжился симбиоз ЭВМ и криптографии после того, как компьютеры перестали быть тайной за семью замками.

Как приручить случайность

Одними из первых шифровальных машин, которые использовали псевдослучайные последовательности для шифрования телетайпного сигнала, стали немецкие Siemens T-52 и Lorenz SZ-40. T-52 использовался в основном на проводных линиях связи, и сообщений, зашифрованных с его помощью, было перехвачено немного. А вот SZ-40 использовалась верховным командованием немецкой армии для радиосвязи, что позволяло британцам перехватывать все сообщения, зашифрованные этой машиной. SZ-40 производились компанией Lorenz, а SZ — Schl?sselzusatz — означало «шифровальная приставка». Машина подключалась напрямую между телетайпом и радиоточкой и зашифровывала текст в реальном времени. Их было выпущено немного, и все они использовались руководителями государства и высшими чиновниками, в частности во время  переговоров между Гитлером и генералами вермахта, например, с маршалом Роммелем в Северной Африке. Именно для взлома Lorenz SZ-40 был разработан первый двоичный компьютер Colossus.

Lorenz SZ-42 в коллекции музея Блетчли-парка

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

Всего дисков 12. Помните, что каждой букве в телетайпном коде Бодо соответствует пять нулей или единиц? Так вот, в SZ-40 эти пять бит разбиваются на пять потоков, каждый из которых проходит через два диска. Первый бит суммируется с выходами из первого и шестого диска, второй — с выходами второго и седьмого диска, и так далее. Еще два диска нужны, чтобы иногда останавливать вращение части дисков, вызывая таким образом «заикание». Так последовательность получится более случайной.

На этом сложности не заканчиваются. Классические дисковые машины типа «Энигмы» привязаны к количеству букв в алфавите. В латинском алфавите их 26, поэтому на каждом диске «Энигмы» — 26 контактов и 26 зубцов. А вот у SZ-40 у каждого диска своё количество зубцов (возможных положений). У одного 23, у другого 26, и далее — 29, 31, 37, 41, 43, 47, 51, 53, 59, 61… Эти числа — взаимно простые, то есть у них нет общих делителей. Поэтому в теории, позиции у них совпадут только через 16 с лишним квинтиллионов зашифрованных букв (16 033 955 073 056 318 658). По крайней мере, так считали разработчики машины. А по факту, для взлома SZ-40 оказалось достаточно примерно 8000 перехваченных букв.

HQIB PEXE ZMUG

Взломал SZ-40 британский математик Билл Татт, выпускник Кембриджа, как и Тьюринг. Сотрудникам Блетчли-парка крупно повезло: британская радиоразведка передала им настоящее сокровище — два перехваченных сообщения из 4000 тысяч букв, которые начинались с 12 одинаковых букв: HQIB PEXE ZMUG. Немецкий шифровальщик передал по радио длинное сообщение, зашифрованное с помощью SZ-40. Из-за радиопомех сообщение дошло не полностью, процесс расшифрования сбился, и получатель попросил повторить передачу. И здесь шифровальщик совершил фатальную ошибку. Он установил ту же самую стартовую позицию (пресловутые HQIB PEXE ZMUG), то есть оба раза использовался один и тот же ключ. Британцы увидели, что передается такой же зашифрованный текст, но в какой-то момент начинаются расхождения: шифровальщик торопился, совершал опечатки, использовал сокращения. 

Вспомним формулу, которую мы приводили выше:

XOR ? = ?

XOR ? = ?

XOR ? = ?

Если для шифрования использовался один и тот же ключ, разности между двумя открытыми текстами и двумя зашифрованными текстами будут одинаковыми. Благодаря этому в ключе можно найти закономерности, которые многое могут сказать о внутреннем устройстве шифра.

Ни разу не видя машину, у Татта получилось восстановить ее конструкцию исключительно на основе анализа перехваченных сообщений. Только в 1944 году британцам удалось захватить экземпляр обновленной модели устройства SZ-42. Татт был удивлен тем, насколько миниатюрной оказалась эта машина, для взлома которой был построен гигантский «Колосс»… впрочем, здесь мы забегаем вперед.

Татт догадался, что анализировать нужно не сами буквы, а отдельные биты. Ведь по сути, для каждого из пяти бит вырабатывался свой отдельный ключ, причем всего лишь двумя дисками. Для того, чтобы выявить закономерности в их движении, достаточно было выписать нули и единицы только из первого бита каждой пятибитной буквы. Что Татт и сделал на огромном листе бумаги. К своему удивлению он заметил, что почти в каждой строчке прослеживалась одна диагональная линия из нулей — место, где позиция двух шифровальных дисков совпадала. Так Татт узнал количество зубцов у первых двух дисков. Дальнейшая работа стала делом техники.

“Диагональ” Татта

Через две недели кропотливой работы, проанализировав множество текстов, зашифрованных одинаковыми или похожими ключами (немецкие шифровальщики не отличались оригинальностью), Татт полностью восстановил внутреннее устройство машины. Но оказалось, что раз в месяц немцы полностью меняли позиции всех переключателей на всех зубцах дисков. Поэтому работу по поиску этих комбинаций приходилось начинать с начала  —  снова искать сообщения, вероятно, зашифрованные одним ключом, или схожие сообщения, зашифрованные разными ключами. 

В 1942 году задача усложнилась, так как компания Lorenz выпустила новую версию шифровальной машины — Lorenz SZ-42. Для того, чтобы иметь возможность быстро переключаться с анализа текста, зашифрованного той или иной версией машины, и автоматизировать работу, инженеры Томми Флауэрс и Франк Морелл в январе 1943 года приступили к разработке  вычислительной машины «Хит Робинсон» (Heath Robinson), которую завершили уже через полгода.

Heath Robinson: the unsung hero of British eccentricity and innovation |  WIRED UKHeath Robinson: the unsung hero of British eccentricity and innovation |  WIRED UK

Устройство было названо в честь британского карикатуриста Хита Робинсона, который в своих рисунках часто изображал различные переусложненные механизмы для выполнения простейших действий.

Современная реплика «Хита Робинсона»

«Хит Робинсон» сравнивал две перфоленты: на одной было записано перехваченное сообщение, а на другой — заранее заготовленные короткие ключевые последовательности, сгенерированные дисками SZ-40 с разными стартовыми позициями. Перфоленты склеивались в замкнутые петли, и одна из перфолент была длиннее другой ровно на одну букву. За счет этого при каждом новом прогоне через машину «Хит Робинсон» сообщение сдвигалось на одну букву, таким образом перебирались все возможные ключи шифрования. 

Колосс на ламповых ногах

Уже в марте 1943 года, еще до введения «Хита Робинсона» в эксплуатацию, Флауэрс запросил средства на следующий проект — полностью электронную программируемую вычислительную машину. В ней планировалось использовать больше 5000 ламп и 2500 реле, и, по расчетам, она должна была выделять тепла больше, чем восемь электрических обогревателей. Зато она могла обрабатывать до 10 тысяч символов в секунду, анализируя по пять бит каждой буквы параллельно. Сообщение наносилось на перфоленту, а затем прокручивалось на большой скорости (5000 отверстий в секунду). В декабре 1943 года устройство было впервые запущено, а в феврале 1944 были получены первые дешифрованные немецкие сообщения. 

Рассекреченные в 2023 году фотографии «Колосса»

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

Как мы писали выше, после войны большая часть «Колоссов» была уничтожена, однако два последних устройства работали еще на протяжении 15 лет. Их применяли в учебных целях, а также для дешифрования «русской рыбы» — советских шифрующих приставок к телеграфным аппаратам, часть из которых использовали схожий прием генерации псевдослучайной гаммы с помощью шифровальных дисков. «Рыбами» машины такого типа называли из-за «журчащего» звука, передающегося по радио телетайпного трафика. Например, Lorenz SZ-40 британские криптографы называли тунцом (tunny), а Siemens T-43  — акулой-лисицей (thresher). Интересно, что немцы тоже называли свою T-43 рыбой, но другой — рыбой-пилой, S?gefisch. «Русской рыбой» предположительно был трафик, зашифрованный шифровальными машинами М-101, С-308 или С-309, хотя документального подтверждения этому нет.

Помимо «Колосса» и «Хита Робинсона» в Блетчли-парке использовались и другие цифровые вычислительные машины. Например, с помощью табуляторов IBM проводился частотный анализ биграмм и триграмм (сочетаний из двух и трех букв) немецкого языка. Большую роль во взломе как Lorenz SZ-40, так и других шифровальных машин сыграли теория графов и расчеты марковских цепей для немецкого языка.

Холодная война, теплые транзисторы

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

О роли криптоанализа в победе союзников во Второй мировой войне стали говорить в 1970-х годах, когда США и Британия одновременно начали рассекречивать подробности о совместном проекте ULTRA по дешифрованию немецких, итальянских, японских и советских шифров.

Среди рассекреченных материалов были и архивные документы о шифровальных службах Третьего рейха, где использовали электромеханические устройства собственной разработки и американские «машины Холлерита» (табуляторы IBM), а также информация о нереализованных проектах немецкого инженера Конрада Цузе (создателя первого программируемого электромеханического компьютера).

После развала Советского Союза были рассекречены документы о криптоанализе 1950–1990-х годов во многих бывших странах социалистического блока (в частности, ПНР и ГДР). Данные о советских разработках в этой области до сих пор остаются одними из самых закрытых. Об использовании советских ЭВМ известно по косвенным данным — по упоминаниям в польских и немецких архивах Группы координации, которая занималась организацией взаимодействия между криптографическими и радиоразведывательными службами стран Варшавского договора. Среди ЭВМ, которые использовались криптографическими службами соцблока, — советские «Урал-2» и «Булат», польские EMAL-2 (компьютер Польской академии наук), XYZ (первая универсальная ЭВМ в Польше), а также закупленный в Британии Elliott-803. Все они использовались не только для взлома вражеских систем шифрования, но и для контроля стойкости собственных шифров. Так как ЭВМ в 1950–1960-е годы были достаточно редкими, практиковалось разделение машинного времени: для сохранения секретности днем машины могли использоваться для научных целей, а ночью машинный зал занимали «люди в штатском» (так, например, происходило с компьютерами Польской академии наук).

В США в послевоенный период на базе AFSA (Агентство безопасности вооруженных сил) было организовано АНБ — Агентство Национальной Безопасности США. Эта разведывательная служба быстро стала одной из крупнейших в мире; для нее была построена глобальная сеть радиоперехвата и одни из самых мощных вычислительных комплексов для криптоанализа. Именно в этой службе работал Эдвард Сноуден. Как только АНБ было создано, оно сразу стало одним из главных покупателей суперкомпьютеров IBM и Cray. А также вступило в сговор со многими производителями шифровальных устройств, чтобы они разрабатывались с заложенными уязвимостями. АНБ это нужно было для того, чтобы на момент появления этих устройств на рынке у агентства уже был рабочий алгоритм для их взлома. Так, например, произошло с компанией-производителем шифровальных машин Crypto AG, которая с 1950-х годов состояла с АНБ в партнерстве, а в 1970-м была куплена ЦРУ через цепь подставных лиц. После этого сама компания по факту занималась только разработкой hardware, а криптографические алгоритмы разрабатывались сотрудниками АНБ. 

Сеть Фейстеля и сеть сетей

В 1970-х началась эра персональных компьютеров и компьютерных сетей. Небольшие по размеру, но мощные компьютеры одновременно подключались к незащищенным сетям, что сделало целесообразным их использование для шифрования сообщений. Появилось новое поколение шифров — программных, а не аппаратных. Одним из первых в 1971 году стал шифр немецко-американского криптографа Хорста Фейстеля под названием «Люцифер», во второй версии которого Хорст применил принцип, впоследствии получивший известность как сеть Фейстеля. Он лег в основу ранних стандартов шифрования — американского DES и советской «Магмы».

Патент Хорста Фейстеля на первую версию  «Люцифера» и архитектура сети Фейстеля

После 1970-х начался постепенный переход к гражданской криптографии, когда эта наука стала защищать не только государственные тайны, но и персональные секреты (наиболее активной борьба между сторонниками использования криптографии исключительно в интересах государства и теми, кто считал необходимым более широкое ее применение, была на рубеже 1990–2000-х годов). Показательным в этой области является пример протокола открытого обмена ключом. В 1976 году Уитфилд Диффи и Мартин Хеллман при содействии Ральфа Меркля разработали, запатентовали и опубликовали в научной статье протокол открытого обмена ключом (известный как протокол Диффи — Хеллмана). Этот протокол позволяет участникам переписки сформировать общий секретный ключ, обмениваясь данными по незащищенному каналу связи. Однако принцип открытого обмена ключом впервые сформулировали в 1969 году Джеймс Эллис, Клиффорд Кокс и Малкольм Уилльямсон. Будучи сотрудниками британского Центра правительственной связи (GCHQ, английская спецслужба, похожая на АНБ по масштабам и кругу интересов), Эллис и соавторы могли опубликовать свои разработки только в закрытом докладе для Communication-Electronics Security Group. В результате разработка легла на полку и была рассекречена только в 1997 году. 

Протокол Диффи — Хеллмана в различных реализациях до сих пор широко используется в сети, хотя еще в 2015 году злоумышленники, располагающие значительными вычислительными ресурсами (например, некоторые спецслужбы мира), могли взламывать этот протокол. А при появлении полноценного квантового компьютера, который поставит под удар традиционную криптографию с открытым ключом, будет невозможно обеспечить защищенный обмен ключами шифрования, что сделает практически все современные протоколы защищенных коммуникаций в сети интернет небезопасными, в том числе и протокол Диффи — Хеллмана. Поэтому уже сейчас ведутся разработки в области постквантовой криптографии.

Страница из патента, описывающего протокол Диффи-Хеллмана

Сейчас доступность шифрования для защиты онлайн-покупок, банковских операций, передачи паролей, сообщений и звонков кажется чем-то самим собой разумеющимся, но еще в 1990-е годы за разработку средств шифрования можно было получить уголовное дело. Например, самая первая безопасная покупка в интернете произошла 11 августа 1994 года в интернет-магазине NetMarket (первым проданным товаром стал диск Стинга Ten Summoner’s Tales). Для безопасной передачи банковских данных использовалась программа PGP, разработанная Филиппом Циммерманом, который на тот момент был фигурантом уголовного дела по статье о незаконном экспорте военных технологий (стойкая криптография классифицировалась как военная технология, а публикация в сети — как экспорт за границу). Дело было закрыто только после того, как Циммерман опубликовал исходный код своей программы в виде книги, так как запрет на экспорт книг противоречил бы первой поправке в Конституцию США. Последовавшая либерализация законодательства в области криптографии, появление доступных алгоритмов шифрования и их популяризация стали достижением активистов и шифропанков, среди которых были и Циммерман, и Диффи с Хеллманом. 

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

  1.  Случайные последовательности чисел используются в качестве ключей шифрования для  одноразовых блокнотов — системы шифрования, которую невозможно взломать. В такой системе  «случайность» должна удовлетворять строгим математическим требованиям. ??
  2. Target Intelligence Committee. Vol.2. Notes on German high level cryptography and cryptanalysis. Army Security Agency, Washington, D.C., 1946 (declassified 06.01.2009) ??
  3.  Вместо печатающего элемента можно использовать ламповую панель — при нажатии на клавишу на ней будет загораться лампочка, подсвечивающая ту или иную букву. ??

Источники и литература

  1. Carter, Frank. Codebreaking with the Colossus Computer, Report Number 1. Bletchley Park Trust, Bletchley Park, Bletchley, Milton Keynes, UK. 2008
  2. Sale Toney. The Lorenz Cipher and how Bletchley Park broke it. 2001 http://www.codesandciphers.org.uk/lorenz/fish.htm
  3. Michie, Good et al. General Report on Tunny. Forum for the History of Science, Technology and Medicine. 1944
  4. John F. Dooley. History of Cryptography and Cryptanalysis: Codes, Ciphers, and Their Algorithms. Springer, 2018
  5. Breaking Teleprinter Ciphers at Bletchley Park by James A. Reeds, Whitfield Diffie, and J. V. Field
  6. Christensen, C. 2018. Review of Lorenz and comments on the work of William Tutte. Cryptologia 42 (5):445–66. doi:10.1080/01611194.2018.1435216.
  7. Davies, D. W. 1995. The Lorenz Cipher Machine SZ42. Cryptologia 19 (1):39–61. doi:10.1080/0161-119591883755.
  8. Erskine, R. 1988. From the archives Tunny Decrypts. Cryptologia 12 (1):59–61. doi:10.1080/0161-118891862792.
  9. Jan Bury (2012) Polish Cold War Codebreaking of 1959–1989: A Preliminary Assessment, Cryptologia, 36:4, 341-379, DOI: 10.1080/01611194.2012.713804
  10. Edwin Black. IBM and the Holocaust : the strategic alliance between Nazi Germany and America’s most powerful corporation. Washington, D.C. : Dialog Press, 2012.
  11. Marek Czarkowski. Od EMAL-a do… Rozmowa z prof. Romualdem W. Marczy?skim, tw?rc? pierwszych, polskich komputer?w / “Bajtek,” nr 3/89 (39), str. 3
  12. Wroc?awskie Zak?ady Elektroniczne ELWRO. Okres maszyn cyfrowych typu ODRA / “Informatyka,” nr 8-12/1989, str. 26-30
  13. R. Marczynski, «The First Seven Years of Polish Digital Computers» in IEEE Annals of the History of Computing, vol. 2, no. 01, pp. 37-48, 1980
  14. Jackson, John. Hitler’s Codebreakers — German Signals Intelligence in World War 2. BookTower Publishing, Redditch, Worcestershire, UK, 2012
  15. Stephen Budiansky (2001) CODEBREAKING WITH IBM MACHINES IN WORLD WAR II, Cryptologia, 25:4, 241-255, DOI: 10.1080/0161-110191889914
  16.  Alan G. Konheim (2015) The Impetus to Creativity in Technology, Cryptologia, 39:4, 291-314, DOI: 10.1080/01611194.2015.1044816
  17. Nicolas Courtois, J?rg Drobick & Klaus Schmeh (2018) Feistel ciphers in East Germany in the communist era, Cryptologia, 42:5, 427-444, DOI: 10.1080/01611194.2018.1428835
  18. Frode Weierud, Sandy Zabell. (2020) German mathematicians and cryptology in WWII. Cryptologia 44:2, pages 97-171
  19. Corera, G. Intersept: The Secret History of Computers and Spies. Weidenfeld & Nicolson, London, 2015
  20. C. A. Deavours (1977) THE ITHACA CONNECTION: COMPUTER CRYPTOGRAPHY IN THE MAKING, Cryptologia, 1:4, 312-317, DOI: 10.1080/0161-117791833057
  21. Frank Rubin (1978) COMPUTER METHODS FOR DECRYPTING MULTIPLEX CIPHERS, Cryptologia, 2:2, 152-160, DOI: 10.1080/0161-117891852938
  22.  Frank Rubin (1978) COMPUTER METHODS FOR DECRYPTING RANDOM STREAM CIPHERS, Cryptologia, 2:3, 215-231, DOI: 10.1080/0161-117891853027
  23. Caxton C. Foster (1978) CRYPTANALYSIS AND COMPUTERS, Cryptologia, 2:3, 236-237, DOI: 10.1080/0161-117891853045
  24. I. J. Good (1979) EARLY WORK ON COMPUTERS AT BLETCHLEY, Cryptologia, 3:2, 65-77, DOI: 10.1080/0161-117991853855
  25. Ryska R., Herda S. Kryptographische Verfahren in der Datenverarbeitung. Informatik-Fachberishte, 24 (Gesellschaft fur Informatik.) Berlin and New York: Springer-Verlag, 1980.
  26. Chris Christensen & Jared Antrobus (2015) The Story of Mamba: Aligning Messages Against Recovered Additives, Cryptologia, 39:3, 210-243, DOI: 10.1080/01611194.2014.988364
  27. Chris Christensen (2014) The National Cash Register Company Additive Recovery Machine, Cryptologia, 38:2, 152-177, DOI: 10.1080/01611194.2013.797050
  28. Dooley John F. History of Cryptography and Cryptanalysis: Codes, Ciphers, and their Algorithms. Springer, Cham, Switzerland, 2018.
  29. Raul Rojas (2014) Konrad Zuse’s Proposal for a Cipher Machine, Cryptologia, 38:4, 362-369, DOI: 10.1080/01611194.2014.915265
  30. Jan Bury (2017) Lambda: A Cold War Polish line encryptor and the networks it served, Cryptologia, 41:6, 512-533, DOI: 10.1080/01611194.2017.1357983
  31. Colin Burke (1993) AN INTRODUCTION TO AN HISTORIC COMPUTER DOCUMENT THE 1946 PENDERGASS REPORT CRYPTANALYSIS AND THE DIGITAL COMPUTER, Cryptologia, 17:2, 113-123, DOI: 10.1080/0161-119391867809
  32. Jerzy Jaworski (2008) Rejewski-R??ycki-Zygalski Lectures in Computer Science, Cryptologia, 32:4, 348-350, DOI: 10.1080/01611190802253128
  33. Narrative and Report of Proceedings of TICOM Team 6, 11 April — 6th July 1945 /National Archives and Record Administration, College Park (NARA). RG 457, Entry 9037 (Records of the NSA), Box 168.
  34. Final Report of TICOM Team 1. / National Archives and Record Administration, College Park (NARA). RG 457, Entry 9037 (Records of the NSA), Box 168.
  35. Final Report of TICOM Team 3. National Archives and Record Administration, College Park (NARA). RG 457, Entry 9037 (Records of the NSA), Box 168.
  36. Report of TICOM Team 4 visit to Southern Germany and Austria, 14th June – 12th July 1945. National Archives and Record Administration, College Park (NARA). RG 457, Entry 9037 (Records of the NSA), Box 168
  37. IF-167 Final Report on the Visit of TICOM Team 5 to the Schliersee Area 3rd August to 7th October 1945. NSA Freedom of Information Act, September 2010, case #62136A.
  38. Final Report of TICOM Team 2. National Archives and Record Administration, College Park (NARA). RG 457, Entry 9037 (Records of the NSA), Box 168.
  39. Radom?r Dohnal (2017). Wilhelm Tranow: g?nius, kter? louskal britsk? ?ifry a pak zmizel https://www.idnes.cz/xman/styl/wilhelm-tranow-sifry-druha-svetova-valka-b-dienst.A171114_193634_xman-styl_fro 
  40. Target Intelligence Committee. Vol.2. Notes on German high level cryptography and cryptanalysis. Army Security Agency, Washington, D.C., 1946 (declassified 06.01.2009)
  41. Applications of Artificial Intelligence in Cryptography. Federal Office for Information Security, Deutschland, 2024 https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisationen/Informationen-und-Empfehlungen/Kryptografie/KI-in-der-Kryptografie/ki-in-der-kryptografie_node.html 
  42. Lewis, Peter H. Attention Shoppers: Internet Is Open / New York Times, 12.08.1994

Авторы: Музей криптографии, Егор Ефремов


Источник: sysblok.ru

Комментарии: