Криптоанализ — наука о методах расшифровки зашифрованной информации без предназначенного для такой расшифровки ключа

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

К сожалению, криптоаналитические достижения Калкашанди арабами были вскоре забыты. Иначе невозможно объяснить исторический курьез, имевший место спустя почти 300 лет. Судите сами. В 1600 г. марокканский султан направил в Англию посольство, глава которого вскоре отослал на родину сообщение, зашифрованное без всяческих затей — шифром простой замены. Письмо это каким-то образом попало в руки одного араба, который, судя по оставленной им записке, потратил 15 лет на то, чтобы понять смысл написанного. Пятнадцать лет! Подобную задачу Калкашанди решил бы за несколько часов.

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

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

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

Интересно, что в то время, когда простые люди шифрование считали колдовством и ведьмачеством, основные работы в области криптографии и криптоанализа выполнялись в лоне католической церкви. Так, в XIV веке на свет появляется книга сотрудника папской канцелярии Чикко Симонетти, где он подробно описывает шифры замены, в которых, для выравнивания частоты встречаемости букв в шифртексте, гласным буквам ставится в соответствие не один знак, а несколько. Здесь же впервые встречается описание так называемого «лозунгового» шифра, который в различных модификациях будет применяться и несколько веков спустя. Правило замены букв в нем определяется следующим образом: под алфавитом пишется ключевая фраза — лозунг, а затем буквы, которые в лозунге не встречаются.

Почти век спустя появляется книга «Трактат о шифрах», автор которой, Габриэль де Лавинд, секретарь папы Клементия XII, дает описание нового типа шифра, предполагающего замену букв несколькими символами, количество которых пропорционально встречаемости букв в открытом тексте. Имена, должности, географические названия рекомендуется заменять специальными знаками. Это был самый ранний образец номенклатора — гибридной системы шифрования, которой в последующие 450 лет суждено было распространиться по всей Европе.

В 1466 году опять-таки в папскую канцелярию представляется трактат о шифрах архитектора и философа Леона Альберти, где предлагается способ маскировки сообщения в некотором безобидном вспомогательном тексте. Здесь же Альберти предлагает свой собственный шифр с нескромным названием «шифр королей». По сути, Альберти придумал многоалфавитную замену — новый вид шифрования, используемый в большинстве современных шифрсистем.

По идее Альберти, первую букву сообщения следовало заменять по одному признаку (алфавиту замены), например, a = p, b = m, c = f,..., вторую — по второму, например, a = l, b = t, c = a,..., третью — по третьему, например, a = f, b = x, c = p,... и так далее. Порядок шифралфавитов устанавливался в соответствии с известным ключом. Многоалфавитные шифры явились большим шагом вперед, но на практике не использовались в течение более четырех столетий. Почему? Да потому, что многоалфавитная замена по сравнению с номенклатором отнимала слишком много времени, а «незначительная» ошибка при письме, например, пропуск буквы, приводила к таким искажениям, что получателю сообщения было не суждено расшифровать его даже при наличии верного ключа. Несколькими годами позже, значительно опередив свое время, Альберти изобрел код с перешифровкой, который стал широко применяться в странах Европы лишь 400 лет спустя.

В России, хотя тайнопись использовалась уже в XII–XIII веках, официальной датой появления криптографической службы считается 1549 год (царствование Ивана IV), а именно образование «посольского приказа», при котором имелось «цифирное отделение». Шифры использовались такие же, как на западе — значковые, замены, перестановки. Петр I позднее полностью реорганизовал криптографическую службу, создав Посольскую канцелярию. В это время появляются специальные коды для шифрования — «цифирные азбуки».

В начале XVI века Маттео Арженти, криптограф папской канцелярии, изобрел код, согласно которому могут заменяться не только буквы, но и слоги, слова, даже целые фразы. Где-то в это же время появляется и числовой код.

Следующим этапом развития криптографии можно считать 1563 год, когда в своей книге «О тайной переписке» итальянский естествоиспытатель Джованни Порта описал биграммный шифр, в котором осуществляется замена не одной буквы, а пары букв. В своей книге Порта приводит примеры списков вероятных слов из различных областей знания, существенно предвосхитив то, что впоследствии криптологи назовут «методом вероятного слова». Примерно в то же время французский посол в Риме Блез Виженер, познакомившись с трудами по криптографии, пишет книгу «Трактат о шифрах» (1585 г.), в которой он предлагает в качестве ключа применять открытый или шифрованный текст и высказывает мысль о том, что «все вещи в мире представляют собой шифр. Вся природа является просто шифром и секретным письмом». Позднее эту мысль повторят и Блез Паскаль, и отец кибернетики Норберт Винер.

Эра «черных кабинетов»

XVII век вошел в историю криптоанализа как эра «черных кабинетов». В это время в различных странах начали появляться первые службы дешифровки корреспонденции. В Англии Оливер Кромвель создает «Интеллидженс сервис», в состав которой входит подразделение по дешифровке. Не отстает и Франция. Там дешифровальное отделение было создано при Людовике XIV по предложению кардинала Ришелье. Его возглавил Антуан Россиньоль — автор дипломатического шифра, представляющего собой слогово-словарный код на 600 компонентов. Этот шифр французская армия будет использовать более ста лет. Известно, что даже Наполеон во время своих походов использовал шифры, являющиеся упрощенными вариантами шифра Россиньоля.

Не менее известен и «шифр Ришелье» — при его использовании текст сообщения разбивается на отрезки, буквы которых переставляются в определенном порядке.

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

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

Репутацией же самого лучшего «черного кабинета» по праву пользовался венский. Ежедневно в семь утра туда привозили почту, которая должна была утром доставляться иностранным посольствам в Вене. Письма вскрывали, растапливая сургучные печати, отмечали порядок страниц и передавали помощнику директора. Наиболее важные документы переписывались. Для экономии времени длинные письма читались вслух и записывались одновременно несколькими стенографистами. После копирования письма укладывались обратно в конверты, опечатывались поддельными печатями и уже к половине десятого утра возвращались на почту.

От черной магии к чистой математике

В XVII—XVIII веках становится все более понятно, что защита информации — не столько искусство сочинения и отгадывания изощренных шифров, сколько точная наука. Все заметнее переход криптографии из области черной магии в область чистой математики. Мы почти ничего не знаем о том, занимались ли ведущие математики того времени проблемами шифрования и дешифрования, но есть данные, что некоторые из них владели криптографией. Среди них Блез Паскаль, сделавший ряд открытий в области комбинаторики и создавший метод индуктивного доказательства; Исаак Ньютон и Готфрид Лейбниц, разработавшие дифференциальное и интегральное исчисление. Знаменитый английский философ Френсис Бэкон предложил идею двоичного кодирования. Леонард Эйлер вел обширные исследования по перечислению и построению латинских квадратов, т. е. шифров многоалфавитной замены.

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

Новые условия требуют новых идей

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

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

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

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

Благодаря работам Кергоффса, во всех ведущих государствах мира уже в 80-х годах XIX века криптографию признают наукой и в обязательном порядке начинают преподавать в военных академиях. Для шифрования применяются коды с перешифровкой. Создаются и все шире используются механические шифровальные устройства. Однако в основе систем тех лет, как и в методах оценки их криптостойкости, математические принципы использовались недостаточно полно. Несмотря на это, революционные открытия в математике того времени сформировали фундамент для дальнейшего развития и усложнения систем шифрования и дешифрования. Зародившиеся тогда формальные языки и аксиоматические методы легли в основу тайнописи следующего века.

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

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

Война и радиосвязь полностью преобразили криптографию. Шифрованный текст, переданный по радио, был доступен каждому, кто имел в своем распоряжении несложный приемник. И даже если этот текст нельзя было расшифровать сразу, — его можно использовать при анализе последующих сообщений. В этот период получили развитие методы дешифрования, основанные на парах открытых и шифрованных текстов; на нескольких шифровках, созданных с помощью одного ключа; на переборе вероятных ключей. Именно эти методы применялись англичанами для чтения секретной переписки немцев во время Первой мировой войны. Несмотря на то, что неоценимую помощь английским криптоаналитикам оказали водолазы, добывавшие кодовые книги с затонувших немецких подлодок, основой их работы был скрупулезный анализ перехваченных текстов. Находкой для криптографов было использование в качестве лозунгов пословиц, поговорок, патриотических призывов, а также стереотипные выражения, которые так любили употреблять в своих посланиях немецкие дипломаты. Если бы они только знали, как много информации дала взломщикам их кодов одна только фраза «Имею честь сообщить Вашему Превосходительству, что...»!

Все чаще использовались вероятностно-статистические методы, основанные на частоте появления знаков, биграмм, триграмм и т. д. И все же, методы работы криптоаналитиков оставались «человеческими» до 1917 года, до того момента, когда Гильберт Вернам предложил новый способ шифрования.

Год 1917 — революция в шифровании

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

Все понимали, что такая защита чересчур слаба, но, не сумев придумать ничего другого, пользовались ей до тех самых пор, пока Вернам не предложил использовать для кодирования сообщений особенности телетайпного кода, в котором кодируемый знак выражается в виде пяти элементов. Каждый из этих элементов символизирует наличие («плюс») или отсутствие («минус») электрического тока в линии связи. Например, букве «А» соответствует комбинация «+ – – – –». Подготовленное к отправке сообщение набивается на перфоленте: отверстие соответствует «плюсу» кода, его отсутствие — «минусу». В процессе передачи металлические щупы телетайпа проходят через отверстия, замыкая цепь, и посылают импульсы тока («+»). Там, где отверстия нет, и бумага не позволяет щупам замкнуть цепь, импульс не передается («–»).

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

Дальнейшее усовершенствование метода, предложенного Вернамом, принадлежит будущему начальнику связи войск США Джозефу Моборну, объединившему хаотичность «гаммы», на которую опирался Вернам в своей системе «автоматического шифрования», с используемым в то время в войсках правилом «одноразового шифрблокнота». Идея Моборна заключалась в том, что каждая случайная «гамма» должна использоваться один, и только один раз. При этом для шифрования каждого знака всех текстов, которые уже переданы или будут переданы в обозримом будущем, должен применяться абсолютно новый и не поддающийся предсказанию знак «гаммы».

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

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

Интересно, что Советский Союз производил шифрмашины обоих названных типов.

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

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

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

Однако в обмен на абсолютную стойкость метод этот требует чересчур больших вычислений, что не всегда оправданно. Иногда достаточно обеспечить криптостойкость на некоторое время (помните доктрину Россиньоля?). Как говорил Остап Бендер: «Мне не нужна вечная игла для примуса, я не собираюсь жить вечно».

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

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

Над этими и многими другими проблемами работает современная криптография, новейшая история которой началась в 1978 г. с суммы в 100 долларов и числа

«968613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154». (129-значное число)

Авторы пообещали премию в сто долларов тому, кто первым расшифрует RSA-шифрованную фразу

«968613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154».

Алгоритм RSA (Rivast, Shamir и Adelman, 1977 год) предполагает, что посланное закодированное сообщение может быть прочитано адресатом и только им.

Это было сделано только через 17 лет. Для того чтобы расшифровать фразу The magic words are squeamish ossifrage, команде из 600 человек потребовалось 220 дней работы и 1600 компьютеров, связанных через интернет. Я подозреваю, что затраты несколько превысили размер премии.