"Таємничі сторінки. Цікава криптографія "

Книга Івана Єфішова "Таємничі сторінки. Цікава криптографія "побудована як набір етюдів, у кожному з яких розбираються закономірності, пов'язані зі знаками і символами, що допомагають кодувати або декодувати ті чи інші повідомлення. Ця книга увійшла в лонг-ліст премії науково-популярної літератури «Просвітитель» 2017 року. Підбиття підсумків премії відбудеться 16 листопада; зі списком книг і авторів, які увійшли в шорт-лист премії, можна ознайомитися тут.

Етюд IV Числа Фібоначчі

Американський письменник Ден Браун (р. 1964) у своєму «Коді да Вінчі» використовував для декодування інформації числа Фібоначчі. Коротко нагадаємо канву подій, пов'язаних з цими загадковими числами.

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

13-3-2-21-1-1-8-5 На вид ідола родич! О міна зла!

Що за міна зла? Та ще родич якогось ідола... Що стосується чисел - якщо їх розташувати за зростанням (1, 1, 2, 3, 5, 8, 13, 21), то ми отримаємо перші вісім чисел нескінченного ряду Фібоначчі. Втім, передамо тепер слово головному герою роману, професору Гарвардського університету Роберту Ленгдону: "Спотворений ряд Фібоначчі - це ключ. Числа є натяком на те, як слід розшифровувати іншу частину послання. Соньєр спеціально порушив послідовність, натякаючи на те, що такий же підхід можна застосувати і до тексту ".

Таким чином, Жак Соньєр залишив натяк, що написане ним - криптограма! Тобто, переставивши літери в посланні, ми отримаємо інший сенс записки. Перший рядок записки зі спотвореннями (адже ряд Фібоначчі теж спотворений) дає «Ліодардо да Вінчі!», другий декодується як «Мона Ліза!». Сенс записки тепер більш-менш ясний: вона залишена куратором Лувру, де і зберігається знаменита картина:

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

Але чому Жак Соньєр вибрав для коду доступу саме числа Фібоначчі? Ось як це пояснює сам Ден Браун на сторінках роману: "Якщо перетворити послідовність Фібоначчі на простий набір з десяти цифр, вона стає практично невпізнанною. Запам'ятати легко, а на перший погляд цифри здаються обраними навмання. Геніальний, приголомшливий цифровий код, який Соньєр ніколи б не забув ".

Розгляньмо історію цього «геніального, приголомшливого цифрового коду». Звідки взялися ці цифри?

Збіг! Їх відкрив теж Леонардо, і теж італієць, але, на жаль, не знаменитий да Вінчі, а якийсь купець Леонардо Фібоначчі (1170-1250). У своїй першій математичній праці «Книга Абаки» (Liber Abaci, 1202 рік) він розглянув завдання про розмноження кроликів. У результаті з'явилися чудові числа, пізніше названі ім'ям Фібоначчі:

1 = 1, ₂ = 1, ₃ = 2, ₄ = 3, ₅ = 5, ₆ = 8, ... , ₁₂ = 144, ...

Перші два числа у цій послідовності вказані і дорівнюють одиниці, тобто ₁ = 1, ₂ = 1, а кожне наступне число дорівнює сумі двох попередніх чисел. Наприклад, ₆ = ₅ + ₄ (або 8 = 5 + 3). Рахунок можна продовжити. Так, наприклад, дванадцяте число Фібоначчі дорівнює ₁₂ = 144.

Числами Фібоначчі можна описати як кошик соняшника, так і розташування спіральних рукавів Галактики.

Зазначимо, що у своїй праці Леонардо Фібоначчі, який у справах торгівлі не раз опинявся в арабському Алжирі, розглянув вперше в європейській математиці арабську систему обчислення. Звична нам десяткова позиційна система, яку всі ми вивчаємо в школі, свого часу стала найбільшим проривом у математиці. Не будь її, нам довелося б досі користуватися римською нотацією, настільки незручною при обчисленнях.

Плавно перейдемо до іншого завдання з кодування і передачі інформації, де також виникають всюдисущі числа Фібоначчі. Але передваримо її невеликим подвійним лінійним кросвордом.

По верхньому ряду малюнків кросворд розгадується наступним чином: «парк, вікно, сік», по нижньому ряду - «пар, кік, шкарпетка».

Як бачимо, повідомлення «паркокносок» можна прочитати двома способами. У даному випадку інформацію, що складається з одинадцяти літер, ви легко дешифрували, використовуючи підказки-картинки. Але у криптоаналітика підказок, як правило, немає.

Розгляньмо подібне завдання [11], пов'язане з передачею інформації, яка також складається з одинадцяти символів, але не супроводжується додатковими підказками.

Ось її умова. Деякий алфавіт складається з шести букв, які для передачі по телеграфу кодуються одним або двома знаками наступним чином:

• , —, • •, — —, • —, — •.

При передачі якогось слова не зробили проміжків, що відокремлюють букву від букви, так що вийшов суцільний ланцюжок точок і тире, що складається з одинадцяти знаків.

Скількома способами можна прочитати передане слово?

Зробимо завдання більш наочним. Припустімо, що вам передали таке слово:

• • — — • — — — • — •

Спробуйте для початку розібратися з цим приватним випадком.

Завдання повністю аналогічне тій, яку ви розгадували в лінійному кросворді. Але там ви відділяли одне від одного слова, а тут доведеться відокремити закодовані букви в слові. Відомо, що при передачі телеграм або радіограм застосовується абетка Морзе, в якій, наприклад, буква А завжди кодується двома знаками • -, тоді як буква Е - це одна точка •, а буква Т - просто тире -. Таким чином, отримавши повідомлення з двох знаків • - (в якому навмисно пропущений пробіл), ви можете його декодувати або як букву А, або як дві літери ЕТ.

Тепер спробуйте застосувати подібний підхід для слова з одинадцяти знаків. Не забудьте, що наш етюд називається «Числа Фібоначчі»!

Спробуйте зробити це самостійно, витратьте на завдання годину, дві, три... Стільки, скільки вам знадобиться. Але не забігайте вперед, щоб просто прочитати відповідь. Завдання не так складне: при її вирішенні вам не доведеться скористатися жодною математичною формулою!

Підказка: відповідь завдання - дванадцята кількість Фібоначчі.

Вирішимо це завдання детально - крок за кроком. Отже, слово довжиною в одинадцять знаків вже задано. Припустимо, що спочатку нам дана послідовність з 1 знака, потім з 2, 3,..., 11 знаків. Кожен знак, як ви пам'ятаєте, - це або точка, або тире.

Перший крок. Спочатку маємо слово довжиною в один знак: *, де * означає або точку, або тире.

Очевидно, слово у нас прочитається єдиним чином. Коли конкретне повідомлення з одного знака у вас перед очима, то ви побачите або • або -.

Другий крок. Тепер вказано слово довжиною вже в два знаки: **.

(*) (*), (* *) - два способи декодування. Інших комбінацій просто немає. Тут є круглими дужками окремі літери (однозначні або двозначні) в отриманому нами слові.

Третій крок. Маємо слово довжиною в три знаки: ***.

(*) (*) (*), (*) (* *), (* *) - вже три способи декодування (будемо мати послідовність з літер в лексико-графічному порядку їх довжини - спочатку будемо намагатися виписувати слова, які починаються з літер, що мають найменшу довжину, тобто складаються з одного знака (*); а слова, що містять літери з подвійних знаків (* *), будемо намагатися виписувати після перших. Інакше кажучи, слово (*) (*) (* *) будемо писати перед словом (*) (* *), оскільки одиночних знаків зліва у першого слова більше, ніж у другого). Як ми пам'ятаємо, букви з трьох знаків (* * *) за умовою нашого завдання не існує.

Четвертий крок. Маємо слово довжиною в чотири знаки: ****.

(*) (*) (*) (*), (*) (*) (* *), (* *) (*), (* *) (*) (*), (* *) (* *) - ось так сюрприз! У нас тепер не чотири, як можна було б очікувати, а цілих п'ять способів декодування.

П'ятий крок. Маємо слово довжиною в п'ять знаків: *****.

(*) (*) (*) (*) (*), (*) (*) (* *), (*) (*) (*) (*), (*), (* *) (*) (*), (* *) (*) (*), (* *) (*)) - вісім варіантів декодування.

Можна продовжувати в тому ж дусі. Але спробуємо вгадати закономірність, що виникає в ході вирішення завдання.

Випишемо кількість способів декодування, отриманих на кожному нашому кроці.

Перший крок - 1 спосіб.

Другий крок - 2 способи.

Третій крок - 3 способи.

Четвертий крок - 5 способів.

П'ятий крок - 8 способів.

І т. д...

Тепер добре видно, що праворуч у нас стоять числа Фібоначчі: ₂ = 1, ₃ = 2, ₄ = 3, ₅ = 5, ₆ = 8, ... Оскільки при вирішенні завдання на першому кроці ми отримали друге число Фібоначчі ₂ = 1, на другому кроці - третє число ₃ = 2, то, отже, правильною відповіддю буде дванадцяте число Фібоначчі ₁₂ = 144, оскільки отримане слово складається з одинадцяти знаків.

Яке елегантне і гарне завдання! І цілком під силу будь-кому. Сподіваюся, ви отримали море задоволення при її самостійному рішенні і не підглядали у відповідь.

Детальніше читайте: . Таємничі сторінки. Цікава криптографія/Іван Єфішов. - М.: Манн, Іванов і Фербер, 2016. - 240 с.