Книга шифров. Тайная история шифров и их расшифровки



страница3/32
Дата24.08.2017
Размер4,62 Mb.
1   2   3   4   5   6   7   8   9   ...   32

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

Объяснение аль-Кинди гораздо проще показать на примере английского алфавита. Прежде всего необходимо взять достаточно большой кусок обычного английского текста, может быть, несколько текстов, чтобы установить частоту появления каждой буквы алфавита. Наиболее часто встречающейся буквой в английском алфавите является буква е, затем идут буквы t, а и т. д. (см. таблицу 1). Затем возьмите интересующий вас зашифрованный текст и подсчитайте частоту появления каждой буквы в нем.

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

Однако не следует безоговорочно применять принцип аль-Кинди для криптоанализа, поскольку в таблице 1 указаны только усредненные частоты появления букв, а они не будут в точности совпадать с частотами появления этих же букв в любом другом тексте. К примеру, краткое сообщение, в котором обсуждается влияние состояния атмосферы на передвижение полосатых четвероногих животных в Африке, «From Zanzibar to Zambia and Zaire, ozone zones make zebras run zany zigzags» не поддалось бы непосредственному применению частотного анализа. Вообще говоря, частота появления букв в коротком тексте значительно отклоняется от стандартной, и если в сообщении меньше ста букв, то его дешифрование окажется очень затруднительным. В то же время в более длинных текстах частота появления оукв будет приближаться к стандартной, хотя это происходит и не всегда.

Таблица 1 Таблица относительной частоты появления букв на основе отрывков, взятых из газет и романов; общее количество знаков в отрывках составляло 100 362 буквы. Таблица была составлена X. Бекером и Ф. Пайпером и впервые опубликована в «Системах шифрования: защита связи»

В 1969 году французский автор Жорж Перек написал 200-страничный роман «Исчезновение» («La Disparition»), в котором не было слов с буквой е. Вдвойне примечательно то, что английскому писателю-романисту и критику Гилберту Адэру удалось перевести «La Disparition» на английский язык, где по-прежнему, как и у Перека, буква е отсутствовала. Как ни удивительно, но перевод Адэра, под названием «А Void», является удобочитаемым (см. Приложение А). Если бы весь этот роман был зашифрован с помощью одноалфавитного шифра замены, то попытка дешифровать его оказалась бы безуспешной из-за полного отсутствия наиболее часто встречающейся буквы в английском алфавите.

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

Криптоанализ зашифрованного текста

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

При виде такого зашифрованного текста любой криптоаналитик немедленно приступит к анализу частоты появления всех букв; его результат приведен в таблице 2. Нет ничего удивительного в том, что частотность букв различна. Вопрос заключается в том, можем ли мы на основе частотности букв установить, какой букве алфавита соответствует каждая из букв зашифрованного текста. Зашифрованный текст сравнительно короткий, поэтому мы не можем непосредственно применять частотный анализ. Было бы наивным предполагать, что наиболее часто встречающаяся в зашифрованном тексте буква О является и наиболее часто встречающейся буквой в английском языке — е или что восьмая по частоте появления в зашифрованном тексте буква Y соответствует восьмой по частоте появления в английском языке букве h. Бездумное применение частотного анализа приведет к появлению тарабарщины. Например, первое слово РС<2 будет расшифровано как аоv.

Таблица 2 Частотный анализ зашифрованного сообщения.

Начнем, однако, с того, что обратим внимание только на три буквы, которые в зашифрованном тексте появляются более тридцати раз: О, X и Р. Естественно предположить, что эти наиболее часто встречающиеся в зашифрованном тексте буквы представляют собой, по всей видимости, наиболее часто встречающиеся буквы английского алфавита, но не обязательно в том же порядке. Другими словами, мы не можем быть уверены, что О = е, X = t и Р = а, но мы можем сделать гипотетическое допущение, что:

О = е, t или а, X = е, t или а, Р = е, t или а.

Чтобы быть уверенным в своих дальнейших действиях и идентифицировать три чаще всего встречающихся буквы: О, X и Р, нам потребуется применить частотный анализ более тонким образом. Вместо простого подсчета частоты появления трех букв, мы можем проанализировать, как часто они появляются рядом с другими буквами. Например, появляется ли буква О перед или после некоторых других букв, или же она стремится стоять рядом только с некоторыми определенными буквами? Ответ на этот вопрос будет убедительно свидетельствовать, является ли буква О гласной или согласной. Если О является гласной, то она должна появляться перед и после большинства других букв, если же она представляет собой согласную, то она будет стремиться избегать соседства со множеством букв. Например, буква е может появиться перед и после практически любой другой буквы, в то время как буква t перед или после букв b, d, g, j, k, m, q и v встречается редко.

В нижеприведенной таблице показано, насколько часто каждая из трех чаще всего встречающихся в зашифрованном тексте букв: О, X и Р появляется перед или после каждой буквы. О, к примеру, появляется перед А в 1 случае, но никогда сразу после нее, поэтому в первой ячейке стоит 1. Буква О соседствует с большинством букв, и существует всего 7 букв, которых она совершенно избегает, что показано семью нулями в ряду О. Буква X общительна в не меньшей степени, так как она тоже стоит рядом с большинством букв и чурается только 8 из них. Однако буква Р гораздо менее дружелюбна. Она приветлива только к нескольким буквам и сторонится 15 из них. Это свидетельствует о том, что О и X являются гласными, а Р представляет собой согласную.

Теперь зададимся вопросом, каким гласным соответствуют О и X. Скорее всего, что они представляют собой е и а — две наиболее часто встречающиеся гласные в английском языке, но будет ли О = е и X = а, или же О = а, а X = е? Интересной особенностью в зашифрованном тексте является то, что сочетание ОО появляется дважды, а XX не попадается ни разу. Так как в открытом английском тексте сочетание букв ее встречается значительно чаще, чем аа, то, по всей видимости, О = е и X = а.

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

Хотя у нас есть пробелы между словами, однако следующий прием сработает и там, где зашифрованный текст был преобразован в непрерывную строку символов. Данный прием позволит нам определить букву h после того, как мы нашли букву е. В английском языке буква h часто стоит перед буквой е (как, например, в the, then, they и т. п.), но очень редко после е. В нижеприведенной таблице показана частота появления буквы О, которая, как мы полагаем, является буквой е, перед и после всех других букв в зашифрованном тексте. На основе этой таблицы можно предположить, что В представляет собой букву h, потому что она появляется перед О в 9 случаях, но никогда не стоит после нее. Никакая другая буква в таблице не имеет такой асимметричной связи с О.

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

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

Теперь мы уже гарантированно определили значение четырех букв: О = е, Х = а, Y = i и В = h и можем приступить к замене отдельных букв в зашифрованном тексте их эквивалентами для открытого текста. При замене я буду придерживаться следующего правила: буквы зашифрованного текста останутся прописными, а подставляемые буквы для открытого текста будут строчными. Это поможет нам отличить те буквы, которые нам еще только предстоит определить, от тех, значение которых мы уже установили.

Этот несложный шаг даст нам возможность определить еще несколько букв, поскольку сейчас мы можем отгадать отдельные слова в зашифрованном тексте. К примеру, самыми часто встречающимися трехбуквенными словами в английском языке являются the и and, и их сравнительно легко найти в тексте: Lhe, которое появляется шесть раз, и aPV, которое появляется пять раз. Следовательно, L, по всей видимости, является буквой t, Р — n, а V — d. Теперь мы можем заменить и эти буквы в зашифрованном тексте, подставив вместо них их действительные значения:

Как только будут определены несколько букв, дальнейший процесс дешифрования пойдет очень быстро. Так, в начале второго предложения стоит слово Сn. В каждом слове есть гласная, поэтому С должна быть гласной. Нам осталось определить только две гласные: u и о; u не подходит, значит, С должна быть буквой о. У нас также есть слово Khe, в котором К может быть либо t, либо s. Но мы уже знаем, что L = t, поэтому совершенно очевидно, что К = s. Установив значения этих двух букв, подставим их в зашифрованный текст, в результате чего получим фразу thoMsand and one niDhts. Здравый смысл подсказывает, что это должно быть thousand and one nights, и, скорее всего, данный отрывок взят из «Тысячи и одной ночи». Отсюда получаем, что M = u, I = f, J = r, D = g, R = I и S = m.

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

Анализируя частично заполненную строку шифралфавита, мы можем завершить криптоанализ. Последовательность VOIDBY в шифралфавите дает возможность предположить, что в качестве ключа криптограф использовал ключевую фразу. Можно догадаться, что ключевой фразой здесь будет A VOID BY GEORGES PEREC, которая, после того как будут убраны пробелы и повторы букв, сократится до AVOIDBYGERSPC. После нее буквы следуют в алфавитном порядке, при этом те из них, которые уже встречались в ключевой фразе, пропускаются. В данном частном случае криптограф расположил ключевую фразу не в начале шифралфавита, а начиная с третьей буквы. Это допустимо, поскольку ключевая фраза начинается с буквы А, криптограф же хочет избежать зашифровывания а как А. Наконец, определив шифралфавит, мы можем полностью дешифровать весь зашифрованный текст, и криптоанализ будет закончен.

[7]

Эпоха Возрождения на Западе



Между 800 и 1200 годами н. э., когда для арабских ученых наступил период выдающихся интеллектуальных достижений, Европа прочно увязла в Темных веках. В то время как аль-Кинди описывал изобретение криптоанализа, европейцы все еще постигали основы криптографии. Единственными в Европе институтами, в которых поощрялось изучение тайнописи, были монастыри, где монахи исследовали Библию в поисках скрытого в ней значения; заманчивость этих поисков была такова, что они продолжаются и по сей день (см. Приложение C).

Средневековые монахи были заинтригованы тем фактом, что в Ветхом Завете имелись явные признаки использования криптографии. В нем, к примеру, встречаются куски текста, зашифрованного с помощью атбаша, — традиционной формы шифра замены в иврите. Принцип зашифровывания здесь следующий: берется буква, определяется, какой она является по счету от начала алфавита, после чего заменяется буквой, которая стоит на том же самом месте, но только считая от конца алфавита. Для английского языка это означает, что а, стоящая в начале алфавита, заменяется буквой Z, стоящей в конце алфавита, b заменяется на Y и так далее. Название атбаш само намекает на замену, которая используется в этом шифре: слово атбаш состоит из первой буквы алфавита иврита; алеф, за которой

следует последняя буква в алфавите тав, далее идет вторая буква, бет, а за ней — вторая буква от конца шин. Примеры атбаша даны в книге пророка Иеремии, глава 25, стих 26 и глава 51 стих 41, где слово «Вавилон» заменено словом «Сесах» («Шешах»); первая буква слова Babel (Вавилон) — бет, вторая буква алфавита иврита, заменяется на шин, вторую букву от конца; второй буквой слова Babel[8] также является бет, и поэтому она тоже заменяется на шин; последняя буква слова Babel — ламед, двенадцатая буква алфавита иврита, и она заменяется на каф, двенадцатую букву от конца алфавита.

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

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

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

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

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

Открытия, сделанные мусульманами в естественных науках и в математике, оказали огромное влияние на возрождение науки в Европе, так что среди завезенных знаний вполне мог оказаться и криптоанализ.

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

И другие дворы Европы также стали приглашать на службу искусных криптоаналитиков, таких как Филибер Бабу, который был криптоаналитиком короля Франции Франциска I. Бабу приобрел репутацию невероятно упорного человека, который способен работать круглые сутки неделями напролет, чтобы раскрыть перехваченное сообщение. К несчастью для Бабу, это дало возможность королю вступить в длительную любовную связь с его женой. К концу шестнадцатого века, с появлением Франсуа Виета, который получал особое удовлетворение от взлома испанских шифров, французы повысили свое мастерство по дешифрованию сообщений. Испанские криптографы, которые выглядели простодушными по сравнению со своими противниками в Европе, не могли поверить, когда узнали, что их сообщения становились известны французам. Испанский король Филипп II даже обратился с прошением в Ватикан, заявив, что единственным объяснением успешности применения криптоанализа Виета является то, что он — «сатана, вступивший в сговор с дьяволом». Филипп убеждал, что Виет должен предстать перед судом кардиналов из-за своих дьявольских дел, но папа, который знал, что его собственные криптоаналитики уже не первый год вскрывали испанские шифры, отверг прошение испанцев. Новость о прошении вскоре стала известна криптоаналитикам различных стран, и испанские криптографы оказались посмешищем всей Европы.

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

Между тем государства, которые получили предупреждение о слабости одноалфавитного шифра замены, стремились создать более стойкий шифр, который смог бы защитить их сообщения от раскрытия криптоаналитиками неприятеля. Одним из простейших приемов повышения стойкости одноалфавитного шифра замены является использование «пустых» знаков — символов или букв, которые не заменяли реальные буквы, а являлись просто пустыми, ничего не обозначающими символами. Например, можно заменить каждую букву открытого текста числами от 1 до 99, из которых 73 ничего не означают и могут случайным образом появляться с разной частотой в зашифрованном тексте. «Пустые» знаки не представляют никакой сложности для получателя, кому предназначено данное сообщение, кто знает, что эти символы не следует принимать во внимание. Однако наличие таких знаков будет сбивать с толку противника, перехватившего сообщение, потому что они усложняют атаку с применением частотного анализа. Ради повышения стойкости криптографы иногда сознательно перед зашифровыванием сообщения писали слова неправильно. Thys haz thi ifekkt off diztaughting thi ballans off fnkwenseas — усложняет криптоаналитику возможность применения частотного анализа. Однако получатель данного сообщения, если он знает ключ, сможет расшифровать его, после чего в его распоряжении окажется неверно написанный, но все же вполне понятный текст.

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

Однако замену можно осуществлять на гораздо более высоком уровне, когда каждое слово представляется другим словом или символом — это и будет код. Например:

Исходное сообщение = убить короля сегодня вечером. Закодированное сообщение = D-Ω-28

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



Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   32


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница