f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5, f6 = 8…., f12 = 144….
Первые два числа в этой последовательности заданы и равны единице, то есть f1 = 1, f2 = 1, а каждое последующее число равно сумме двух предыдущих чисел. Например, f6 = f5 + f4 (или 8 = 5 + 3). Счет можно продолжить. Так, например, двенадцатое число Фибоначчи равно f12 = 144.
Числами Фибоначчи можно описать как корзинку подсолнуха, так и расположение спиральных рукавов Галактики.
Отметим, что в своем труде Леонардо Фибоначчи, который по делам торговли не раз оказывался в арабском Алжире, рассмотрел впервые в европейской математике арабскую систему счисления. Привычная нам десятичная позиционная система, которую все мы изучаем в школе, в свое время стала крупнейшим прорывом в математике. Не будь ее, нам пришлось бы до сих пор пользоваться римской нотацией, столь неудобной при вычислениях.
Плавно перейдем к другой задаче по кодированию и передаче информации, где также возникают вездесущие числа Фибоначчи. Но предварим ее небольшим двойным линейным кроссвордом.
По верхнему ряду рисунков кроссворд разгадывается следующим образом: «парк, окно, сок», по нижнему ряду – «пар, кок, носок».
Как видим, сообщение «паркокносок» можно прочесть двумя способами. В данном случае информацию, состоящую из одиннадцати букв, вы легко дешифровали, используя подсказки-картинки. Но у криптоаналитика подсказок, как правило, нет.
Рассмотрим аналогичную задачу{9}, связанную с передачей информации, также состоящей из одиннадцати символов, но не сопровождающейся дополнительными подсказками.
Вот ее условие. Некоторый алфавит состоит из шести букв, которые для передачи по телеграфу кодируются одним или двумя знаками следующим образом:
•, –, • •, –, • –, – •.
При передаче некоего слова не сделали промежутков, отделяющих букву от буквы, так что получилась сплошная цепочка точек и тире, состоящая из одиннадцати знаков.
Сколькими способами можно прочесть переданное слово?
Сделаем задачу более наглядной. Предположим, что вам передали следующее слово:
• • – • – • – •
Попробуйте для начала разобраться с этим частным случаем.
Задача полностью аналогична той, которую вы разгадывали в линейном кроссворде. Но там вы отделяли друг от друга слова, а здесь придется отделить закодированные буквы в слове. Известно, что при передаче телеграмм или радиограмм применяется азбука Морзе, в которой, например, буква А всегда кодируется двумя знаками • –, тогда как буква Е – это одна точка •, а буква Т – просто тире – . Таким образом, получив сообщение из двух знаков • – (в котором преднамеренно пропущен пробел), вы можете его декодировать либо как букву А, либо как две буквы ЕТ.
Теперь попробуйте применить подобный подход для слова из одиннадцати знаков. Не забудьте, что наш этюд называется «Числа Фибоначчи»!
Попробуйте сделать это самостоятельно, потратьте на задачу час, два, три… Столько, сколько вам понадобится. Но не забегайте вперед, чтобы просто прочитать ответ. Задача не так сложна: при ее решении вам не придется воспользоваться ни одной математической формулой!
Подсказка: ответ задачи – двенадцатое число Фибоначчи.
Решим эту задачу подробно – шаг за шагом. Итак, слово длиной в одиннадцать знаков уже задано. Предположим, что сначала нам дана последовательность из 1 знака, затем из 2, 3…., 11 знаков. Каждый знак, как вы помните, – это либо точка, либо тире.
Первый шаг. Вначале имеем слово длиной в один знак: *, где * обозначает либо точку, либо тире.
Очевидно, слово у нас прочитается единственным образом. Когда конкретное сообщение из одного знака у вас перед глазами, то вы увидите либо • либо –.
Второй шаг. Теперь задано слово длиной уже в два знака: **.
(*)(*), (**) – два способа декодирования. Других комбинаций попросту нет. Здесь круглыми скобками выделены отдельные буквы (однозначные либо двузначные) в полученном нами слове.
Третий шаг. Имеем слово длиной в три знака: ***.
(*)(*)(*), (*)(**), (**)(*) – уже три способа декодирования (будем располагать последовательность из букв в лексикографическом[2] порядке их длины). Как мы помним, буквы из трех знаков (***) по условию нашей задачи не существует.
Четвертый шаг. Имеем слово длиной в четыре знака: ****.
(*)(*)(*)(*), (*)(*)(**), (*)(**)(*), (**)(*)(*), (**)(**) – вот так сюрприз! У нас теперь не четыре, как можно было бы ожидать, а целых пять способов декодирования.
Пятый шаг. Имеем слово длиной в пять знаков: *****.
(*)(*)(*)(*)(*), (*)(*)(*)(**), (*)(*)(**)(*), (*)(**)(*)(*), (**)(*)(*)(*), (*)(**)(**), (**)(*)(**), (**)(**)(*) – восемь вариантов декодирования.
Можно продолжать в том же духе. Но попытаемся угадать закономерность, возникающую в ходе решения задачи.
Выпишем количество способов декодирования, полученных на каждом нашем шаге.
Первый шаг – 1 способ.
Второй шаг – 2 способа.
Третий шаг – 3 способа.
Четвертый шаг – 5 способов.
Пятый шаг – 8 способов.
И т. д…
Теперь хорошо видно, что справа у нас стоят числа Фибоначчи:
f2 = 1, f3 = 2, f4 = 3, f5 = 5, f6 = 8….
Так как при решении задачи на первом шаге мы получили второе число Фибоначчи f2 = 1, на втором шаге – третье число f3 = 2, то, следовательно, правильным ответом будет двенадцатое число Фибоначчи f12 = 144, так как полученное слово состоит из одиннадцати знаков.
Какая элегантная и красивая задача! И вполне по силам любому. Надеюсь, вы получили море удовольствия при ее самостоятельном решении и не подглядывали в ответ.
Этюд V Суеверный писец
Широко использовалась тайнопись и на Руси. Переписчики древних текстов (как правило, монахи) обычно в конце рукописи зашифровывали свое имя. «Употребление тайнописи вызывается здесь традицией «смирения», ради которого пишущий, хотя и желает оставить по себе память, находит нескромным назвать себя открыто»{10}. Возможно, такая скрытность была вызвана боязнью дурного глаза{11}.
В начале рукописи, найденной в Вологде и относящейся к 1643 году, писец сделал следующую приписку, в которой зашифровал свое имя:
Этот вид тайнописи назывался «мудрая литорея» и основывался на замене буквы соответствующим ей числом в кириллической системе счисления.
Дело в том, что вплоть до начала XVIII века на Руси достаточно было поставить знак «титло» над буквой, чтобы превратить ее в число. Например, первая буква кириллицы «аз» () превращалась в единицу (), третья[3] буква «веди» () – в два () и т. д. С одиннадцатой буквы «и», числовое значение которой равнялось десяти (), начинался отсчет десятков. Сотни обозначались с буквы «рцы» () и т. д.
Затем полученная с помощью литореи числовая последовательность преобразовывалась посредством простых арифметических действий.
По сути, литорея – шифр простой замены, который не составляет труда дешифровать.
Попробуем угадать имя суеверного (или скромного) писца. Десять «и» в конце имени при сложении дадут сто, что соответствует букве «рцы» (). Таким образом, получили окончание имени «оръ». А что с первой буквой имени? Имеем пять букв «рцы», то есть пять раз по сто, или пятьсот. Переберем последовательно буквы кириллицы: «рцы» – 100, «слово» () – 200, «твердо» () – 300, «ук» () – 400, «ферт» () – 500. Следовательно, первая буква в имени «Ф». Здесь нетрудно уже и догадаться, что писца звали Федор.
Этюд VI Шифр Бэкона
В своем труде «О достоинстве и преумножении наук»[4]{12}, написанном на латыни, английский философ, историк и политик Фрэнсис Бэкон (1561–1626) размышляет в числе прочего об искусстве шифрования: «Существует довольно много видов шифра: простые шифры; шифры, смешанные со знаками, ничего не обозначающими; шифры, изображающие по две буквы в одном знаке; шифры круговые; шифры с ключом; шифры словесные и т. д. Шифры должны обладать тремя достоинствами: они должны быть удобными, не требующими многих усилий для их написания; они должны быть надежны и ни в коем случае не быть доступны дешифровке; и, наконец, если это возможно, они не должны вызывать подозрения. Ведь если письма попадут в руки тех, кто обладает властью над тем, кто пишет это письмо, или над тем, кому оно адресовано, то, несмотря на надежность шифра и невозможность его прочесть, может начаться расследование соответствующего дела, если только шифр не будет таким, что не вызовет никакого подозрения или же ничего не даст при его исследовании».
Обратим особое внимание на третье условие: шифры «не должны вызывать подозрения». Это редкое требование к шифрам; Бэкон думает также и о сокрытии факта самого существования секретного сообщения. Ведь бессмысленный текст типа «ffff uuu gg e» в перехваченном письме дает основания заподозрить, что здесь применен некий шифр. А теперь попробуйте понять, что не так со следующей фразой, первоначально написанной на латыни{13}, к которой как раз и применен шифр, не вызывающий подозрения:
Вы заметили что-нибудь необычное в шрифте этой фразы? Нет? А ведь при ее наборе использовалось два похожих, но тем не менее различных шрифта! К тому же фраза самая обычная. Шифры «не должны вызывать подозрения». Это принцип стеганографии[5]: даже перехватив послание, вы ничего странного в нем не заметите, даже не будете подозревать, что здесь что-то не так.
Другое дело, если бы факт существования шифра не скрывался так тщательно, тогда вышеприведенная фраза была бы более наглядной:
MaNeRE te VOlo DOnec Venero
Как видим, все дело в двух различных шрифтах. Вот что пишет по этому поводу сам Бэкон: «Нужно иметь два алфавита[6]: один – состоящий из обычных букв, другой – из букв, не имеющих никакого значения, и отправить одно в другом сразу два письма: одно – содержащее секретные сведения, другое – имеющее достаточно правдоподобное для пишущего содержание, которое, однако, не должно навлечь на него никакой опасности».
Заметим, что выделенное большими жирными буквами слово NREVODOV не имеет никакого смысла, зашифровано совсем другое сообщение! NREVODOV всего лишь состоит «из букв, не имеющих никакого значения».
Теперь, когда шифр стал явным, может быть, вы сможете дешифровать его? Для облегчения задачи приведем аналогичным образом зашифрованную фразу на русском языке:
Я хочУ, чтОбЫ ты оСТаВалСя на месте, пока я не приду.
Как видим, здесь выделенных букв УОЫСТВС даже меньше, чем в оригинальном варианте. Да и стоят они на других местах…
Еще одна подсказка: количество букв в дешифруемом слове как в латинском, так и русском варианте текста совпадает и равно четырем. В латинском тексте в четырех словах есть выделенные буквы, а в русском – только в трех. Так что общего в двух приведенных примерах?
Попробуем разбить фразы на составные части следующим способом:
MaNeR || E te VO || lo DOn || ec Ven || [ero].
(Я хочУ, || чтОбЫ || ты оСТ || аВалС || [я на месте, пока я не приду]).
Лишь теперь, после разбиения фразы на пятерки букв, мы видим, что дешифруемое слово состоит ровно из четырех букв. Места расположения выделенных букв в пятерках не совпадают, так как русское слово не является калькой с латинского и пишется иначе. В квадратные скобки заключен лишний текст, который не использовался при шифровании; при дешифровке он легко будет отброшен как ненужный.
Этот шифр Бэкон изобрел «еще в ранней юности», в семнадцать лет. В шестьдесят он писал: «Даже сейчас, как нам кажется, это изобретение не потеряло своего значения и не заслуживает забвения. Ибо оно представляет собой высшую ступень совершенства шифра, давая возможность выражать всё через всё (omnia per omnia). Единственным условием при этом оказывается то, что внутреннее письмо должно быть в пять раз меньше внешнего; никаких других условий или ограничений не существует».
Вы уже догадались, в чем дело, или пора в качестве очередной подсказки дать ответ?
Итак, секретное послание, состоящее из одного слова, – это fuge (лат. «беги»).
Как же это слово возникло из фразы, по какому алгоритму? Рассмотрим все по порядку:
MaNeR соответствует при дешифровке f;
EteVO – u;
loDOn – g;
ecVen – e;
ero – ничему не соответствует, так как в этом остатке фразы слишком мало букв.
Улавливаете закономерность? Вспомним, что мы используем два шрифта для данного шифра. Заменим все обычные буквы фразы на цифру 0, а ВЫДЕЛЕННЫЕ – на 1. Получаем, что
f = 00101, u = 10011, g = 00110, e = 00100,
или в русскоязычном варианте:
б = 00001, е = 00101, г = 00011, и = 01001.
Если первой букве классического латинского алфавита[7] А поставить в двоичной системе счисления (в которой всего две цифры: 0 и 1!) в соответствие число 0 (или, используя пять символов, 00000), то второй латинской букве B (в русском языке Б) будет соответствовать 00001, третьей букве C (В) – 00010, четвертой букве D (Г) – 00011, пятой букве E (Д) – 00100, шестой букве F (Е) – 00101, седьмой букве G (Ё) – 00110…., десятой букве K (И) – 01001…., двадцатой букве V[8] (Т) – 10011.
У математиков бытует шутка, что на свете существует 10 типов людей: те, кто понимает двоичную систему счисления, и те, кто не понимает[9]. Надеюсь, что в предыдущем абзаце вы прекрасно разобрались.
Заметим, что внешнее письмо может быть написано на одном языке, а внутреннее – на другом. Так, если вышеприведенную фразу на латыни записать как:
ManeRe tE vOlo dONeC veNero,
то, зная, что тайное послание записано на русском языке, в результате дешифровки получаем «беги».
Конечно, Бэкон ничего не знал о двоичной системе счисления, которая была полностью разработана в европейской математике в трудах Г. В. Лейбница[10] несколько позже. Он просто заметил, что на каждую букву достаточно пяти символов (где каждый символ – это либо буква а, либо b или, как у нас в этюде, равнозначные им цифровые символы 0 и 1), чтобы полностью заменить весь латинский алфавит различными сочетаниями этих знаков: «Перестановки из двух букв[11] по пяти дадут нам тридцать два различных сочетания, что более чем достаточно для замещения двадцати четырех букв, из которых состоит наш алфавит».
Последовательность из символов 0 и 1 (или, если угодно, из «двух букв» a и b, как в сочинении Бэкона) является двоичной последовательностью, без которой теперь немыслима работа ни одного компьютера. Бэкон словно предчувствовал большое будущее такого способа передачи информации: «…это изобретение приводит нас к чрезвычайно важным выводам. Ведь из него вытекает способ, благодаря которому с помощью любых объектов, доступных зрению или слуху, мы можем выражать и передавать на любое расстояние наши мысли, если только эти объекты способны выражать хотя бы два различия. Такими средствами могут быть: звук колоколов или рога, пламя, звуки пушечных выстрелов и т. п.». Со временем человечество усовершенствует способы передачи информации: телеграф, радио, интернет… А на тот момент хватало и звона колокола.
В своем труде лорд Бэкон пишет и о том, что «…учение о дешифровке ‹…› это, конечно, очень трудное дело, требующее в то же время большой изобретательности; это искусство (точно так же как и искусство шифра) используется в секретных государственных делах. Но если проявить достаточно ловкости и предосторожности, то можно было бы сделать это искусство бесполезным, хотя, судя по нынешнему положению дел, оно приносит немалую пользу».
Заметим, что шифр Бэкона не уникален: примерно в то же время в Париже этот метод включил в свою книгу (вышедшую в 1586 году) французский дипломат Виженер. Бэкон опубликовал свое описание позже, но заявил дату создания шифра более раннюю, чем Виженер.
Ниже приведен в качестве примера шифровки отрывок из первого письма древнеримского политика и философа, блестящего оратора Марка Туллия Цицерона проконсулу Публию Корнелию Лентулу Спинтеру. (В своей работе Бэкон дает текст письма, для удобства чтения, на более поздней латыни, в которой буквы V и U уже разделились; но в тексте все равно кое-где вместо U написано V. Например, во втором предложении явно написано vt quoniam tu вместо ut quoniam tu.)
Отрывок из письма Цицерона с внутренним скрытым посланием воинов Спарты, зашифрованным методом Ф. Бэкона
Письмо является внешним текстом, в котором спрятан другой, внутренний. Применяя полученные знания, попытайтесь его дешифровать. Руководствуйтесь тем, что буквы алфавита одного шрифта объединяют какие-нибудь общие черты: наличие или отсутствие засечек, ширина, общая округлость букв и т. п.
В рассмотренном выше примере различие между шрифтами было явно выделенным. Естественно, будучи одним из высших сановников королевства, лорд-канцлер Англии, барон Веруламский и виконт Сент-Олбанский разработал для своего метода шифрования такие шрифты, чтобы при чтении текста разнородность букв не бросалась в глаза. Но – Praemonitus praemunitus («Предупрежден – значит вооружен») – вы, несомненно, заметите тонкие различия.