Криптовойна 1933-1945

Newmanry

В Newmanry были реализованы машинные решения для статистического подхода к криптоанализу кода, формальное название подразделения Statistical section. Здесь была разработана теория, позволившая создать машины Heath Robinson и Colossus.

Подразделение известно по имени Макса Ньюмана, он возглавил его после поступления в Блетчли-Парк в 1943 году, сделав к тому времени блестящую академическую карьеру. Более раннему вступлению на этот путь мешало немецкое гражданство его отца. Ньюман прекрасно сочетал математические способности с инженерным видением задач, поэтому ему удалось собрать в одну команду таких математиков, как Гуд, Миши и Татт, физика-электронщика Уилл-Уильямса и инженеров Аллена Кумбса и Томми Флоуэрса. Их совместными усилиями за фантастически короткий срок, в военное время удалось сконструировать, изготовить и запустить в эксплуатацию криптоаналитическую машину Colossus. По мирным представлениям на это потребовались бы годы.

По окончании войны Ньюман принял участие в создании первого британского компьютера Manchester Mark 1и успешно продолжил математические исследования.

Женщины в Блетчли-Парке

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

На женщин возложили монотонную, но, тем не менее, важную работу, которая требовала большой концентрации внимания. Они занимали множество разных вспомогательных должностей – от администраторов, составителей картотеки и диспетчеров до специалистов по взлому кодов. Для работы с машинами Bombe была привлечена группа женщин из Королевской военно-морской службы (Wrens). Женщины принадлежали самым разным слоям общества – одни окончили колледж, другие – университеты, а третьи пришли прямо из школы. Среди них были и представительницы высшего, они стали первыми из добровольцев Блетчли-Парка. Независимо от происхождения, все женщины искали работу, которая позволила им бы внести свой вклад.

Единственным исключением оказалась упомянутая выше Джоан Кларк, выпускница Кембриджского университет, ее Гордон Уэлчман пригласил присоединиться к Hut 6 в начале 1940 года. Но по прибытии в Блетчли-Парк произошла встреча с Аланом Тьюрингом и тот переманил ее к себе в Hut 8. Кларк лучше других освоила работу методом Banburismus и еще другим – Yoxallmus, предложенный Лесли Йоксоллом. Ее связывали сложные отношения с Тьюрингом, они то объявляли о помолвке, то отменяли, весной 1941 года все же обручились, но в итоге расторгли помолвку. Тем не менее Кларк и Тьюринг продолжали дружить и переписывались во время поездки Тьюринга в Соединенные Штаты зимой 1942–1943 годов.

Глава 2. Криптология от Ренессанса до первых шифромашин

О криптологии

Криптология – наука о скрытой информации. Сам термин происходит от греческих слов крипто (скрытый) и логос (учение), то есть буквально означает «учение о скрытом». Исторически криптология представляла собой область практических знаний и умений, связанных с созданием и взломом шифров, и до середины XX века оставалась практической дисциплиной, а не полноценной наукой.

Причина в том, что у нее отсутствовали два ключевых признака любой науки: определенный предмет исследования и формализованные методы. До появления современных математических и вычислительных подходов криптологи опирались главным образом на эмпирические методы, интуицию и личный опыт, создавая интеллектуальные продукты для шифрования и дешифрования.

Современное англоязычное определение точнее отражает природу криптологии: «Cryptology is the practice of creating and studying methods and protocols to secure communication» – «криптология – это практика создания и изучения методов и протоколов, обеспечивающих безопасность коммуникаций». Подчеркивается именно практическая направленность, а не только абстрактная теория.

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

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

Стремление обезопасить передачу сообщений возникло, по-видимому, буквально «на следующий день» после изобретения письменности. Как только появилась возможность фиксировать мысль на материальном носителе, возникла и необходимость скрывать ее от посторонних. Однако сам термин cryptology закрепился в английском языке лишь в XVII веке, а в профессиональный оборот вошел значительно позже – в 1940-е годы, благодаря Уильям Фридман, которого справедливо называют отцом американской криптологии. С ним нам еще предстоит встретиться на страницах этой книги.

Именно Фридман предложил четкое разделение криптологии на две смежные области – криптографию и криптоанализ. В повседневной речи их нередко объединяют общим словом «криптография», но различие между ними принципиально.

Криптографы превращают открытые, осмысленные данные в шифрованные – создают алгоритмы и протоколы, которые делают сообщение недоступным для постороннего.

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

Любопытно, что термин cryptograph относительно молод. Впервые его использовал Эдгар Аллан По в рассказе Золотой жук. Уже тогда художественная литература уловила притягательность шифров как интеллектуального вызова.

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

Термин cryptanalysis моложе и носит вполне академическое происхождение. Его ввел тот же Фридман в своей работе Elements of Cryptanalysis (1923). Под криптоанализом понимается совокупность методов, направленных на взлом криптографических систем и получение доступа к содержимому зашифрованных сообщений.

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

Поэтому на практике криптографию и криптоанализ рассматривают как две стороны одной медали – и вместе они образуют то, что мы называем криптологией.

Четыре основных термина:

• Открытый текст (Plaintext) – незашифрованный исходный текст, доступный для прочтения.

• Шифрованный текст (Ciphertext) – измененный по ключу открытый текст, читаемый только с использованием ключа.

• Шифрование (Encryption) – процесс преобразования открытого текста в шифрованный с использованием с ключа или криптографического алгоритма

• Дешифрование (Decryption) – процесс обратный шифрованию.

Первые попытки защиты информации, заключенной в письменных сообщениях, предпринимались более 5 тысяч лет назад вместе с появлением письменности. С тех пор криптология развивалась, но медленно, ее взрывной рост начался в конце XIX – начале XX века вместе с появлением технологий связи, допускающих перехват сообщений, сначала телеграфа и позже радио. В древности, когда зашифрованный текст татуировали на головах посланников, выдавливали палочкой на глине, писали на папирусе или каких-то иных носителях, сообщение защищалось еще и физически. Прежде, чем расшифровать, его требовалось каким-то образом заполучить, но с появлением радио физическая защищенность сообщений свелась к нулю и открылись неограниченные возможности перехвата сообщений, передаваемых азбукой Морзе или телеграфным кодом.

Что можно почитать в качестве популярного введения в историю криптологии? Среди массы повторяющих друг друга популярных книг выделятся несколько, упомянем только те, которые доступны с сети. Особое место занимают труды Дэвида Кана, признанного знатока криптологии и разведки. За свою долгую жизнь он написал более дюжины книг, в которых в большей степени отразил событийную сторону истории, а не содержательную, тем не менее, их можно назвать своего рода антологией. Его первая сенсационная книга «Взломщики кодов» (The Codebreakers), вышедшая в 1967 году, содержит хронику криптологии от появления письменности до WWII. В рукописи книга содержала информацию об Агентстве национальной безопасности (АНБ) и о других спецслужбах США, естественно они активно препятствовали ее публикации, поэтому после длительных препирательств Кан и издательство согласились удалить из книги главы, относящиеся к АНБ и его английскому аналогу Центру правительственной связи (GCHQ), однако сохранена глава, посвященная криптоаналитике в СССР. «Взломщики кодов» переведены на русский, книга имеется в свободном доступе. Позже Кан выпустил книгу «Захват Enigma» (Seizing Enigma), в которой красочно, но далеко не вполне достоверно описал события, приключения и подвиги, связанные с погоней британских спецслужб за этой машиной. В 2004 году на русском был издан ее явно пиратский перевод на русский под названием «Погоня за Энигмой».

В 2007 году на русском была издана «Книга шифров: Тайная история шифров и их расшифровки» британского популяризатора науки Саймона Сингха. В книге излагается история шифрования от времен Древней Греции до современной математической криптографии, большая глава посвящена Enigma, с точки зрения описания ее устройства это лучшее, что мне встретилось. По «Книге Шифров» снят пятисерийный фильм для The Science of Secrecy, он вышел на британском научно-популярном Channel 4. Эти книги стоит прочесть для вхождения в контекст, а для развлечения можно порекомендовать роман Цзя Мая «Расшифровка», переведенный с китайского, он посвящен особенности работе гениального криптаналитика.

Источниками информации могут быть относительно недавно созданные музеи, среди них, конечно же самый известный – Музей криптографии в Блетчли-Парке, в месте, ставшем национальной гордостью Великобритании. На втором месте Национальный музей криптографии США, созданный АНБ, где наиболее заметная часть экспозиции посвящена деятельности криптологов во время Второй мировой войны. В Польше создан Центр шифров Enigma. Несколько лет назад и в Москве открылся, прямо скажем, замечательный Музей криптографии. Он разместился на «намоленном месте», ранее принадлежавшем РПЦ, потом там размещалась «Марфинская шарашка», описанная А. И. Солженицыным «В круге первом» и Л. З. Копелевым в воспоминаниях «Утоли моя печали». Здесь есть обширная общеисторическая часть и разделы о прошлом прилегающего к музею НИИ Автоматики. В отличие от иных отечественных экспозиций, например, «Атом» на ВДНХ и других, этот музей ни в малейшей степени не идеологизирован.

Во всех перечисленных книгах приоритет отдан шифромашине Enigma, но нет ни слова про другую шифровальную машину Lorenz, нет и рассказа о тех, кто обеспечил взлом и какими средствами. О взломе кода Lorenz есть фильме «Действительно секретная немецкая шифромашина. Дешифровщики, забытые герои Блетчли-Парка». (Germany's Real Secret Code Machine – Code-Breakers: Bletchley Park's Lost Heroes), выпущенном в 2011 году на BBC Two. И уж совсем мало материалов о шведских и японских критомашинах.

Замена и перестановка, два метода шифрования

Почти разнообразие эмпирических приемов традиционной криптографии, использующей алфавитную письменность, в конечном счете сводится всего к двум – к более распространенному методу замены символов и к менее популярному методу перестановки символов. Замена или перестановка и ничего более, к тому же основная идея каждого из них тривиально проста. В первом случае в открытом тексте символы того алфавита, на котором он написан, заменяются символами из другого алфавита, составленного из тех же символов, но иначе упорядоченных. Во втором случае шифрование сводится к перестановке местами символов внутри открытого текста. Помимо алфавитных есть шифры для языков с иероглифической письменностью, таких как японский и китайский, есть стеганография и еще некоторые экзотические шифры. Известны и другие подходы к шифрованию, не связанные с заменой и перестановкой. Они не связаны с содержанием этой книги, поэтому вот лишь названия некоторых: «Миланский ключ», Номенклатор, Великий Шифр Россиньоля, Книжный шифр. За каждым шифром кроется увлекательная история, они хорошо и подробно описаны.

Алгоритмы шифрования заменой и перестановкой относятся к симметричным (symmetric-key algorithm), где и шифрование, и дешифрование выполняется одним и тем же ключом. Впрочем, иного прежде и не мыслилось, неологизм «симметричное шифрование» возник как реакция на появление современного асимметричного шифрования, для противопоставления старого новому. Невольно вспоминается господин Журден из «Мещанина во дворянстве» Мольера, открывший для себя: «Честное слово, я и не подозревал, что вот уже более сорока лет говорю прозой. Большое вам спасибо, что сказали». Такие термины лингвисты называют ретронимами, они служат для обозначения чего-то старого, ранее известного от нового схожего. Общий ключ симметричного алгоритма должен сохраняться в тайне обеими сторонами. Ключ шифрования выбирается сторонами до начала обмена сообщениями.

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

Однако для полноты картины все же следует упомянуть и о методе перестановки. Шифрование им напоминает перетасовку карт, но не случайную, а следуя заданному правилу – ключу. В процессе шифрования перестановкой в открытом тексте единичные символы, а возможно и пары или тройки по заданному ключу меняются местами. Шифрование перестановкой не слишком популярно, но его первое применение можно обнаружить в простейших устройствах, созданных в IV веке до н. э. полководцем Энеем Тактиком, в них шифрование осуществлялось прошивкой шнурком диска или линейки с отверстиями, эти инструменты вошли в историю под его именем диска Энея или линейки Энея.

Из древности известны примеры шифрования перестановкой – анаграммы. Анаграмма, по-гречески «перестановка букв». Известны анаграммы Галилея и Ньютона, которыми великие ученые шифровали свои открытия. Возможны шифры двух вариантов – с простой или со сложной перестановкой. Простую перестановку еще называют маршрутной, потому что в процессе шифрования символы открытого текста записывают не последовательно, а разбрасываются по прямоугольной матрице в заданном порядке, называемом маршрутом, маршрут – это ключ, получатель, обладая им, можно пройти по матрице тем же маршрутом, что и отправитель и восстановить открытый текст. Сложная перестановка предполагает какой-то более изощренный метод маршрутизации. Из сложных наибольшую известность получил шифр Rail fence cipher, названный так, потому что маршрут напоминает ограждение из продольных брусьев, какими огораживают пастбища.

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

Еще одно приспособление для упрощения перестановки называют поворотной решеткой, его придумал в 1550 году итальянский математик Джероламо Кардано. Эта решетка многократно описана в популярных книгах для юношества, например, у Перельмана и Гарднера. В моем детстве их вырезали из бумаги в клеточку и использовали в качестве развлечения при переписке с одноклассниками на скучных уроках.

Метод замены гораздо популярнее перестановки. Знакомый всем тривиальный пример шифрования заменой описан в знаменитом рассказе «Пляшущие человечки» Конана Дойла, здесь ключ есть ничто иное, как правило, по которому осуществляется подстановка символов из одного алфавита или символами другого алфавита.

Шифрования заменой отличается двумя фундаментальными свойствами, которые сохраняются вне зависимости от конкретной реализации, будь то тривиальной ручной или сложной машинный:

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

Симметричность ключа. Симметрию понимают как правило попарного соответствия, сохраняющееся при преобразовании текст в обоих направлениях – от открытого к зашифрованному и в обратном. Симметрия способствовала успеху криптомашин, сама криптомашина является ключом, поэтому одна и та же машина может быть использована как при передаче сообщений, так и при приеме. В приложении к криптомашинам используется термин скремблирование. Скремблер (от scramble – шифровать, перемешивать) – это устройство или алгоритм, выполняющие обратимое преобразование. Обратимый процесс скремблирования позволяет восстановить исходное сообщение, применив обратный алгоритм.

Моноалфавитные шифры

Шифры замены делятся на два класса – на моноалфавитные и на полиалфавитные. В простых моноалфавитных шифрах каждому символу открытого текста ставится в соответствие всего один единственный фиксированный символ из другого, иначе упорядоченного алфавита, поэтому, независимо от того, где и сколько раз некий символ встречается в открытом тексте, в зашифрованном тексте ему будет соответствовать всегда один и тот же заменяющий его символ. Существует несколько алгоритмов для выбора заменяющего символа из шифрующего алфавита. Например, аддитивный шифр Цезаря, в нем ключом дистанция, отделяющая заменяющий символ от исходного. В латинском алфавите она в пределах от 1 до 26 и сохраняется постоянной для всех букв открытого текста. Позиция замещающего символа определяется суммированием. Название пошло от Светония, в «Жизни двенадцати цезарей» он написал, что Гай Юлий Цезарь использовал этот шифр для военных сообщений. Во времена Цезаря шифр был безопасен, если учесть, что большинство его врагов были неграмотны.

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

Наши современники широко узнали о многоалфавитном шифре Атбаш из книги Дэна Брауна «Код да Винчи» и фильму по ней. Его название происходит от четырех букв алфавита древнееврейского языка – первой, последней, второй и предпоследней, то есть Алеф, Тау, Бет и Шин. Скорее всего Атбаш был изобретен иудейской сектой повстанцев ессеев, разрабатывавших методы тайнописи. Однако есть и иные мнения относительно происхождение Атбаша, не связанные с ессеями. Независимо от того, кто прав, его в IV веке унаследовала христианская секта гностиков, далее они передали его катарам, христианскому движению, распространившемуся в западной Европе в XII и XIII веках, затем Атбаш перенял орден Тамплиеров. Атбаш использовался почти 2000 лет, с 500 года до н. э. до того, как орден Тамплиеров перестал существовать в XIV веке.

В средние века появились более надежные полиалфвитные шифры, не знавшие об этом и продолжавшие пользоваться старыми, поплатились за свою отсталость. В конце XVI века Марию Стюарт казнили после расшифровки ее переписки с Энтони Бабингтоном, главой заговора против королевы Англии Елизаветы I. Но есть и более поздние примеры. По мнению Дэвида Кана в 1915 году российская армия перешла на шифр Цезаря 17 июня 1916 года, сочтя другие шифры слишком сложными в использовании. Противникам не составило труда расшифровать такие сообщения. И совсем свежий пример, в 2006 году отличился босс сицилийской мафии Бернардо Провенцано, его поймали взломав его «малявы», написанные с использованием шифра Цезаря.

Известен древнерусский многоалфавитный шифр замены, существовавший со времени монгольского нашествия. Он увлекательно описан в романе Анатолия Рыбакова «Кортик». «Литорея – это тайнопись, употреблявшаяся в древнерусской литературе. Литорея была двух родов: простая и мудрая. Простая называлась еще тарабарской грамотой, отсюда и «тарабарщина». Это простой шифр. Буквы алфавита пишут в два ряда: верхние буквы употребляют вместо нижних, нижние – вместо верхних. Мудрая литорея – более сложный шифр. Весь алфавит разбивался на три группы, по десяти букв в каждой. Первый десяток букв обозначался точками. Например, «а» – одна точка, «б» – две точки и так далее. Второй десяток обозначался черточками. Например: «л» – одна черточка, «м» – две черточки и так далее. И, наконец, третий десяток обозначался кружками. Например, «х» – один кружок, «ц» – два кружка… Значки эти писались столбиками».

Полиалфвитные шифры

Переход от простых моноалфавитных шифров к более сложным полиалфавитным оказался на удивление долгим, он затянулся примерно на тысячу лет. Приоритет на изобретение полиалфавитного шифра принадлежит арабским мудрецам, удивительным людям, им удавалось сочетать занятие разными науками с административной деятельностью на самых высоких постах. Первым был аль-Фарахиди, живший в VII веке. Его соображения о криптографии развил аль-Кинди (IX век), автор трактатов по метафизике, логике, этике, математике, криптографии, астрологии, медицине, метеорологии, оптике, музыке. В Западной Европе он был известен под латинизированным именем Alkindus. До нас дошли списки его труда «О дешифровке криптографических сообщений». Интеллектуальным наследником аль-Кинди в области криптографии стал аль-Дурайхим (XIV век) он описал восемь систем шифрования в книге «Цели ясных глав и разгадка шифров». Завершает цепочку мудрецов аль-Калькашанди (XIV век), опубликовавший исследование шифров замены и перестановки, и дал первое описание полиалфавитного шифра, в котором каждой букве открытого текста присваивается более одной замены.

Эпоха Возрождения (XV–XVI века), ставшая переломной для истории не только Европы, но и в конечном счете для всего цивилизованного мира, совпала с закатом арабской науки и культуры. Естественно, что в этих условиях и прогресс в области криптографии сместился с Востока на Запад, началось бурное развитие полиалфавитных шифров подстановки и некоторых других. Но не только арабские корни, европейский путь криптографии начинается с труда Роджера Бэкона «Послание о тайных действиях искусства и природы и ничтожестве магии», он датирован раньше, 1267 годом. Книга Роджера Бэкона оставалась единственной в своем роде до тех пор, пока через полтораста лет не возникли новые центры криптографии в Венеции и в Ватикане. Здесь были сделаны очередные шаги к дальнейшему развитию шифров замены.