Математики, шпионы и хакеры. Кодирование и криптография - [10]

Шрифт
Интервал

Вот один из примеров такого обобщенного шифра подстановки:



Строка (1) — алфавит открытого сообщения. Строка (2) — шифроалфавит.


Первые шесть букв шифроалфавита дают подсказку к выбранному порядку букв: он соответствует порядку букв на клавиатуре в стандарте QWERTY. Чтобы зашифровать известное высказывание Цезаря VENI VIDI VICI («Пришел, увидел, победил») шифром QWERTY, для каждой буквы алфавита открытого сообщения мы найдем соответствующую в шифроалфавите.



Мы получим следующее зашифрованное послание:

CTFO CORO СОЕО

Существует очень простой способ для генерации почти неисчерпаемого количества легко запоминающихся шифров для шифрования этим методом. Достаточно выбрать любое ключевое слово (это может быть даже фраза), поместить его в начале шифроалфавита и, начиная с последней буквы ключевого слова, завершить ряд буквами стандартного алфавита, следующими в обычном порядке, исключив лишь повторяющиеся буквы. Возьмем в качестве примера ключевую фразу JANUARY CIPHER («январский шифр»). Сначала мы избавимся от пробела и одинаковых букв, получив ключевое слово JNUYCIPHE. В результате наш шифроалфавит будет выглядеть так:



Сообщение VENI VIDI VICI теперь будет зашифровано как ХСМЕ XEYE XEUE. Такая система генерации шифров легко обновляется и почти исключает ошибки со стороны отправителя и получателя. В нашем примере было бы достаточно менять ключевое слово каждый месяц — JANUARY CIPHER (январский шифр), FEBRUARY CIPHER (февральский шифр), MARCH CIPHER (мартовский шифр) и т. д. — то есть после изначального выбора шифра стороны могут обойтись без дополнительных соглашений.

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

* * *

ШИФРОВАНИЕ СЛОВА БОЖЬЕГО

Средневековые криптоаналитики считали, что в Ветхом Завете тоже использовались шифры, и они не ошиблись. Существует несколько фрагментов из священных текстов, которые зашифрованы с помощью шифра подстановки, называемого атбаш. Этот шифр состоит в замене каждой буквы (n) другой буквой, которая находится в алфавите на таком же расстоянии от конца алфавита, как оригинальная буква — от начала. Например, в латинском алфавите буква А заменяется на Z, буква В — на Y и т. д. В оригинальном Ветхом Завете использовались буквы еврейского алфавита. Так, в книге пророка Иеремии (25:26) слово «Бабель» (Вавилон) зашифровано как «Шешах».



Еврейская Библия начала XVIII в.


Частотный криптоанализ

Коран состоит из 114 глав, каждая из которых соответствует одному из откровений, полученных пророком Мухаммедом. Эти откровения были записаны во время жизни пророка различными его спутниками и позднее собраны воедино по решению первого халифа Абу Бакра. Умар и Усман, второй и третий халифы соответственно, завершили проект. Фрагментарный характер оригинальных писаний привел к рождению области богословия, посвященной точной датировке различных откровений.

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



Рукопись Корана. XIV в.


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

Даже если Аль-Кинди не был первым, его имя, безусловно, занимает важное место в истории криптоанализа.

До недавнего времени очень мало было известно о новаторской роли Аль-Кинди.

В1987 г. в одном из архивов Стамбула была обнаружена копия его трактата «Манускрипт о дешифровке криптографических сообщений». Он содержит краткое изложение революционного метода:

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

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


Еще от автора Жуан Гомес
Когда прямые искривляются. Неевклидовы геометрии

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


Рекомендуем почитать
Квантовый оптоэлектронный генератор

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


Флатландия. Сферландия

Произведения Э. Эбботта и Д. Бюргера едины по своей тематике. Авторы в увлекательной форме с неизменным юмором вводят читателя в русло важных геометрических идей, таких, как размерность, связность, кривизна, демонстрируя абстрактные объекты в различных «житейских» ситуациях. Книга дополнена научно-популярными статьями о четвертом измерении. Ее с интересом и пользой прочтут все любители занимательной математики.


Стратегии решения математических задач

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


Вначале была аксиома. Гильберт. Основания математики

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


Симпсоны и их математические секреты

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


Истина и красота: Всемирная история симметрии

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