Криптографические приключения. Таинственные шифры и математические задачи - Роман Душкин

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

Тем временем отец продолжил:

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

Отец обратился к Кате:

— Ты, Катерина, должна выбрать какое-нибудь простое число. Не слишком большое, чтобы было просто считать — скажем, из второго десятка. Это будет модуль, и назовём его p. Потом для этого модуля надо подобрать другое простое число, которое должно обладать рассмотренным нами свойством: его степени, начиная от нулевой, перебирают все остатки от деления на выбранный модуль. К слову, такое число называется первообразным корнем, и мы будем обозначать его g. Ты помнишь, какие числа называются простыми?

Катя кивнула:

— Это такие числа, которые делятся нацело только сами на себя и на единицу.

Отец продолжил:

— И потом ты должна выбрать какую-нибудь степень, в которую ты будешь возводить первообразный корень g. Это будет твой секретный ключ, и мы назовём его a. Как только ты всё это выбрала, ты должна переслать Кириллу по рации три числа: p, g и A = ga mod p. Заметь, ты пересылаешь не свой секретный ключ, а значение первообразного корня в этой степени по выбранному модулю. Это очень важно. Давай выберем все эти числа и посмотрим, что получится.

Катя записала в своём блокноте:

p = 17

g = 5

a = 7

Папа быстро что-то набросал у себя и сказал, что выбранные числа p и g подходят, поэтому можно двигаться дальше. Он дал Кате листок бумаги и попросил записать на нём три числа, которые она должна передать мне. Катя что-то долго рассчитывала, потом написала:

p = 17

g = 5

A = 10

Папа достал свой смартфон и проверил Катины вычисления. Она всё сделала правильно. Тогда он взял у неё листок и передал его мне, сказав:

— Кирилл, теперь ты должен выбрать свой секретный ключ b и проделать ту же операцию, получив остаток B = gb mod p. Это полученное число B ты передашь назад Катерине. Выбирай, записывай у себя в блокноте и на листочке и передай своей напарнице.

Я записал:

b = 14

B = 15

Все расчеты я проделал тоже при помощи планшета, так как вычислить 514 вручную было уже очень сложно, а тем более — посчитать после этого остаток от деления на 17. Отец перепроверил меня и продолжил:

— Теперь смотрите: волшебство. У Кирилла есть числа p, g, A, b и B. У Катерины есть числа p, g, a, A и B. Каждый из вас может создать секретный ключ. У вас обоих он будет одинаковым, но никто из вас не передавал его друг другу. Как это сделать? Кирилл считает K = Ab mod p, а Катерина считает K = Bamod p. Давайте-ка проделаем это.

Мы с Катей принялись считать. У меня получилось: 1014 mod 17 = 8. У Кати вышло: 157 mod 17 = 8. Всё сошлось. Отец торжествующе заявил:

— А теперь обратите внимание, что числа 8 нет на том листочке, который вы передавали друг другу. Так вы получили одинаковый секретный ключ, не передавая его в явном виде по открытому каналу. Ну не красота ли?

Катя засомневалась:

— Мне кажется, что число 8 слишком маленькое, чтобы быть ключом.

Но это нисколько не смутило отца. Он возразил:

— Во-первых, его необходимо перевести в двоичную систему, и это уже будет 01000 в пятибитном коде. Во-вторых, я уже сказал, что для этих целей используются числа огромных размеров — состоящие из нескольких тысяч цифр. А так-то узнать ваши секретные ключи a и b можно — это будет 7 и 14. Даже если бы я не знал их, то смог бы подобрать, перебрав варианты. Так что в качестве начального условия нужны именно огромные числа.

Пока мы изучали эту новую и интересную тему, не заметили, как наступил вечер. Мы вернулись в дом, и тётя Катя поворчала на отца, что он заставляет детей пропускать обед, рассказывая «всякую пустоту». Тогда мы уж поужинали, и напоследок отец дал нам задание:

— До завтра придумайте аналогичный алгоритм передачи секретного ключа, основанный на другом методе. Это может быть любой метод. Главное в нём — невозможность быстро и легко выполнить обратную операцию. Вот в том, что мы рассмотрели, сложно от значения вернуться к показателю степени. Но это не обязательно может быть операция возведения в степень в кольце.

Мы пообещали что-нибудь придумать, и на этом наше занятие закончилось.

Из дневника Кирилла:

На следующее утро отец разбудил меня как-то слишком рано. Я чувствовал себя невыспавшимся, глаза слипались, в голове был какой-то туман. Через полчаса мы уже выдвинулись. Я сел на велосипед, и отец повесил мне на спину рюкзачок. По его словам, в нём были всякие съестные припасы и инструменты. У него за спиной висело ружьё, а по бокам были набитые чем-то сумки.

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

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

— Едем в Муханские овраги. Вчера вечером я сделал преобразование плана, наложил его на карту и получил ту точку, которую мы ищем. Сегодня мы должны попасть в эту местность и как бы разметить её.

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