В порядке букв — жизнь и смерь

  Дата публикации: 20 Май 2013 l автор:

Шифровка для Одиссея

Тайные послания люди отправляли друг другу уже в глубокой древности. Одним из первых о способах тайной переписки упоминает Геродот — согласно его «Истории», именно засекречивание письма решило исход войны Афин с персидским царем Ксерксом в V веке до н.э. (противостояние греческих полисов и государства персов Геродот рассматривал как столкновение свободного мира и тоталитарной империи, основанной на подавлении и рабстве).

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

Геродот говорит: «Опасность была очень велика, и Демарат выбрал единственно возможный способ успешно доставить свое послание. Он соскоблил воск с двух дощечек для письма, написал свое сообщение прямо на дереве, затем снова покрыл дощечки воском — чистые они не вызывали подозрений у персидских солдат, и гонец с письмом смог беспрепятственно достичь Эллады».

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

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

Есть в «Истории» Геродота еще один похожий случай — письмо грека Хистаеса к тирану Милета Аристагору, побуждающее к восстанию против персидского царя Дария I. Чтобы послание не обнаружили враги, Хистаес нанес его текст на бритую голову вестника, которого отправил в путь лишь после того, как тайные письмена скрылись под отросшими волосами. По прибытии на место вестник обрил голову вновь и так предстал перед получателем корреспонденции. Что ж, ход событий в те далекие времена был вполне неспешным и позволял прибегать к таким долговременным методикам засекречивания связи.

И Демарат, и Хистаес сохраняли содержание своей переписки с родиной в тайне, пряча от посторонних глаз самое письмо. Этот способ называется стеганографией (от греческих слов steganos — «покрытый» и graphein — «писать»). Он широко применялся во всем мире в течение тысячелетий. Невидимые до поры чернила (например, симпатические — проступающие на поверхности бумаги или ткани только после ее специальной обработки) — классический метод стеганографии.

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

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

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

Кесарю — кесарево

Криптография знает два способа шифрования: замещение и перемещение. В последнем случае все буквы исходного «обычного» текста просто меняют места в соответствии с определенным порядком; при замещении же каждая буква текста передается каким-то другим знаком (обычно знаками шифра служат буквы того же алфавита, которым написан шифруемый текст) по заранее построенной системе соответствий.

Шифрование перемещением было хорошо известно в античном мире: именно на этом принципе работала первая военная шифровальная машина в истории человечества — скитале. Скитале — это особый набор для написания шифровок, применявшийся в античной Греции, в частности, в Спарте. Скитале состоит из двух одинаковых деревянных брусков-многогранников (один из них находится у отправителя, другой у получателя) и кожаного ремня. Отправитель навивал ремень на брусок и писал текст сообщения. Когда ремень снимали с бруска, прочесть на нем можно было только бессмысленную последовательность букв. Гонец нес ремень получателю на бедрах, подпоясавшись им так, чтобы сторона, покрытая буквами, была обращена к телу («для страховки» спартанцы прибегали и к стеганографии), а тот навивал ремень на брусок и читал шифровку.

Упоминания замещающего шифра содержатся в «Галльской войне» Цезаря. Шифр, который применял Цезарь, предполагает замену каждой буквы текста буквой, отстоящей от нее на три позиции вперед в латинском алфавите. Разумеется, «шаг» шифра Кесаря (так его называют) может быть каким угодно. Но для того чтобы прочесть шифровку, нужно знать не только алгоритм, но и — главное — ключ. Мало знать, что буквы «сдвинуты» — чтобы читать текст, нужно знать, на сколько позиций они сдвинуты, то есть иметь ключ к шифру. Именно он составляет главный секрет лиц, состоящих в тайной переписке и шифрующих свои письма, и сохранение его тайны обеспечивает тайну переписки.

Шифр Кесаря, впрочем, не назовешь очень надежным. Если ключом служит число от одного до двадцати или тридцати с небольшим, то подобрать ключ будет нетрудно: достаточно перебрать два-три десятка вариантов. Надежнее устанавливать соответствия между буквами обычного и «шифровочного» алфавитов в произвольном порядке. А от необходимости (связанной с риском) хранить или запоминать таблицу побуквенных соответствий избавляет ключевое слово. Оно может быть любым. Ключом может служить и словосочетание, и целая фраза. Например, если мы возьмем в качестве ключа имя ЮЛИЙЦЕЗАРЬ, то первые 10 букв алфавита заменяются соответственно на буквы слова-ключа (только из ключа, конечно, следует выбросить повторы букв), а для остальных букв алфавита, начиная с 11-й, нужно подставить то, что осталось в алфавите после изъятия букв, входящих в слово-ключ. Вот так:

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

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

Начало большого криптоанализа

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

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

Имя того человека, который первым догадался применить этот закон для дешифровки, история не сохранила. Наиболее раннее из известных описаний дешифровки с применением частотного анализа датировано IX веком и принадлежит перу Абу Юсуфа Якуба ибн-Исхака ибн-Ас-Сабаха ибн-Умран ибн-Исмалила Аль Кинди, одного из крупнейших ученых арабского мира (Аль Кинди написал 209 книг по разным отраслям знания и разным искусствам: медицине, лингвистике, математике, музыке, астрономии, философии). Вот что он писал: «Есть способ прочесть зашифрованное послание, написанное на известном тебе языке. Нужно найти нешифрованный текст на этом языке, размером на страницу или около того, пересчитать все буквы в нем и увидеть, сколько раз встречается каждая из букв. Букву, что встречается чаще всех, назови «первая», ту, что на втором месте по частоте, — «вторая» и так далее, пока не назовешь все буквы алфавита. Затем возьми шифрованный текст и посчитай все его знаки. Так же выбери тот, что встречается чаще других, «второй», «третий» и так далее. «Первый» знак служит для замены «первой буквы», второй — для второй буквы и т.д.»

Вот так — элегантно и просто — был повержен «абсолютный шифр»…

Король умер? Да здравствует король!

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

Чтобы зашифровать таким шифром слово ЗАПИСКА, мы для первой буквы возьмем замену из первого шифроалфавита — Ю, для второй — из второго — Г, для третьей снова из первого — Ё, для четвертой — снова из второго — Д и так до конца слова. В итоге получится ЮГЁДРЦФ. Примечательно то, что первая буква А в шифруемом слове обозначена в шифровке одним знаком (Г), а вторая А — другим (Ф). Решающее преимущество шифра Альберти и состоит в том, что одна буква исходного текста обозначается в шифровке не одним, а несколькими разными знаками, а один знак шифровки соотносится не с одной буквой алфавита, а сразу с несколькими, что делает шифровку неуязвимой для частотного анализа!

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

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

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

Осторожно! За дело берется машина

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

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

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

И Бэббидж попытался. Рассуждал он приблизительно так. Сила шифра Виженера в том, что каждая буква сообщения в шифровке передается не одним знаком, а несколькими разными. Но их число очевидно не больше числа букв в слове-ключе (а вернее — если текст достаточно протяжен — равно ему). Каждая буква слова-ключа обозначает строку в таблице Виженера, из которой берется замена данной букве текста. Также и каждое слово может иметь конечный набор вариантов шифрованной записи. Так, в сообщении, зашифрованном с помощью ключевого слова KING, английский определенный артикль THE может быть передан сочетаниями DPR, BUK, GNO и ZRM — в зависимости от того, под какую букву слова-ключа попадает первая буква артикля.

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

После этого все уже было просто. Зная, что первая буква слова ключа задает шифровочный алфавит для 1-й, 6-й, 11-й, 16-й и т.д. буквы сообщения, вторая буква ключа — для 2-й, 7-й, 12-й, 17-й и т.д., Бэббидж применил к каждой из пяти последовательностей старый добрый частотный анализ и установил, какая строка таблицы Виженера служит шифровочным алфавитом для каждой из последовательностей. То есть взломал «абсолютный» многоалфавитный шифр Виженера.

Сделал он это, скорее всего, в 1854 году — вскоре после обмена письмами с Туэйтсом. Но ученый мир об успехе Бэббиджа узнал только в XX веке, когда исследователи принялись разбирать его обширные архивы — ученый так и не опубликовал своей революционной технологии. Пока его находка лежала под спудом, шифр Виженера успел преодолеть другой человек — отставной офицер прусской армии Фридрих Вильгельм Казиски. В 1863 году Казиски опубликовал печатную работу, содержащую алгоритм проникновения в шифр Виженера, и с тех пор этот алгоритм известен как «тест Казиски», а имя Бэббиджа в связи с преодолением «порога Виженера» вспоминают нечасто.

Почему Бэббидж не опубликовал своего открытия? К сожалению, это было одним из свойств его натуры — бросать незавершенными значительные и многообещающие начинания. Так случилось и с вычислительной машиной, послужившей прообразом компьютера (в машине Чарлза Бэббиджа были «хранилище» (аналог компьютерной памяти) и «мельница» (аналог процессора), которая позволяла машине принимать решения и пользоваться инструкциями, эквивалентными командам ЕСЛИ, ТО и ЦИКЛ, применяющимся в программировании сегодня), создание которой Бэббидж забросил после многих лет работы.

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

Автор: В. Генералов

Источник: http://planetatain.ru/

Рекламный блок

Прокомментировать

Вы должны быть авторизованы для комментирования.