Я записал в блокноте: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576.
Теперь мы с Катей погрузились в расчёты и начали выписывать, чему равны эти числа по модулю 13. Хорошо, что папа был не против того, чтобы мы пользовались калькулятором. Получился такой ряд: 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1, 2, 4, 8, 3, 6, 12, 11, 9. В общем-то сразу была видна закономерность. А отец спросил:
— Катерина, ты можешь сказать, чему будет равно 2 в степени 21 по модулю 13?
— Пять?
— Верно. Как вы видите, тут имеется явная закономерность — степени двойки вразнобой пробегают все числа от 1 до 12 при вычислении их остатка по модулю 13, потом всё повторяется. Этот период и эта последовательность будут повторяться до бесконечности. И это очень важное свойство, ради которого мы всё это рассмотрели. Давайте запишем такое уравнение:
2X = 11 (mod 13)
Отец написал его на листке и продемонстрировал нам. Неизвестное стояло в степени двойки, и я как-то сразу затруднился, поскольку в школе мы подобного ещё не проходили. Судя по виду Кати, она тоже не знала, как его решать. Отец же продолжил:
— Надо найти наименьшее число X, при подстановке которого в это уравнение оно становится правильным. Очевидно, что в данном случае это число 7. Но как решается это уравнение? Проблема в том, что решить его мы можем только способом перебора или очень сложного алгоритма, называющегося «дискретным логарифмированием». А теперь подумаем, что будет, если мы возьмём не модуль 13, а какое-нибудь другое число, состоящее из нескольких тысяч цифр. Теоретически такое уравнение решить можно, но на практике для этого потребуется слишком много времени. Очень много. Больше, чем есть у кого бы то ни было.
Нам с Катей пришлось поверить отцу на слово, поскольку у нас не было никакой возможности проверить это утверждение. Но, судя по предыдущему упражнению, его слова были похожи на правду. Я, к примеру, решил записанное им уравнение только перебором.
Тем временем отец продолжил:
— Теперь давайте рассмотрим такую схему передачи информации. Вы хотите обменяться друг с другом секретным ключом, но сделать это надо по открытому каналу, потому что встретиться тайно нет возможности. Поэтому вы пользуетесь следующей схемой…
Отец обратился к Кате:
— Ты, Катерина, должна выбрать какое-нибудь простое число. Не слишком большое, чтобы было просто считать — скажем, из второго десятка. Это будет модуль, и назовём его 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. Даже если бы я не знал их, то смог бы подобрать, перебрав варианты. Так что в качестве начального условия нужны именно огромные числа.
Пока мы изучали эту новую и интересную тему, не заметили, как наступил вечер. Мы вернулись в дом, и тётя Катя поворчала на отца, что он заставляет детей пропускать обед, рассказывая «всякую пустоту». Тогда мы уж поужинали, и напоследок отец дал нам задание:
— До завтра придумайте аналогичный алгоритм передачи секретного ключа, основанный на другом методе. Это может быть любой метод. Главное в нём — невозможность быстро и легко выполнить обратную операцию. Вот в том, что мы рассмотрели, сложно от значения вернуться к показателю степени. Но это не обязательно может быть операция возведения в степень в кольце.
Мы пообещали что-нибудь придумать, и на этом наше занятие закончилось.
Из дневника Кирилла:
13 июля. Как интересно. Папа научил нас обмениваться секретным ключом по открытому каналу, не сообщая сам ключ. Способ достаточно лёгкий, но какой головой надо обладать, чтобы придумать его? Суть в том, что прямую операцию сделать легко, а обратную практически невозможно.
Интересно, какую ещё можно придумать операцию? Мне на ум приходит смешивание. Ведь смешать что-нибудь просто, а вот разделить потом назад совсем не просто. Надо подумать.
На следующее утро отец разбудил меня как-то слишком рано. Я чувствовал себя невыспавшимся, глаза слипались, в голове был какой-то туман. Через полчаса мы уже выдвинулись. Я сел на велосипед, и отец повесил мне на спину рюкзачок. По его словам, в нём были всякие съестные припасы и инструменты. У него за спиной висело ружьё, а по бокам были набитые чем-то сумки.
Мы доехали до Кати, а она уже ждала нас с велосипедом. Папа перед тем, как разбудить меня, сигнализировал ей, чтобы была готова к нашему приезду. Ей ничего не досталось из снаряжения, и она ехала свободно, а я, честно говоря, немного устал с рюкзаком. Но потом я привык, как будто бы открылось второе дыхание.
Мы направились на восток по дороге, бывшей продолжением поворота к школе. Судя по карте, которую я изучил ранее, мы ехали к Кермиси и Пензенской области. Только тут отец объявил цель нашей поездки:
— Едем в Муханские овраги. Вчера вечером я сделал преобразование плана, наложил его на карту и получил ту точку, которую мы ищем. Сегодня мы должны попасть в эту местность и как бы разметить её.
Примерно через двадцать минут после того, как мы проехали наши берёзки, мы доехали до дубовой рощи. Хорошо, что отец заранее загрузил нужные карты к себе в смартфон, так что дальше мы просто поехали по построенному маршруту. Отец сказал, что двадцать пять лет назад, когда он бывал здесь на каникулах, местность выглядела иначе — было несколько дорог, поля ещё не заросли лесом, поэтому он немного путается. Но всё-таки мы выехали на место, которое он искал. Оказалось, что это неприметный въезд в дубовую рощу.
Мы долгое время ехали в сумраке. Лес здесь был древним, с деревьев свисали какие-то лианоподобные растения. На душе было неспокойно, но папа беззаботно крутил педали. Внезапно мы выехали на огромных размеров поляну, освещённую ярким солнцем. Со всех сторон ее окружал такой же лес.
Отец остановился и осмотрелся. Потом он отвёз велосипед в тенёк, снял с себя все сумки и ружьё. Мы последовали его примеру. Отец сказал, что именно в этом месте надо искать. Он достал из кармана листок бумаги и показал нам — на нём было с десяток пар чисел. Как я понял, это были координаты, которые надо было найти на местности и как-то отметить.
Мы выпили чаю из термоса, отец достал из сумки белые колышки, и мы приступили к работе. Отец шёл по навигатору и искал точки. Все точки отличались друг от друга цифрами в самом последнем знаке, и на местности это обозначало разницу в несколько метров. При этом каждая пара чисел на земле превращалась в трехметровый эллипс. Мы это сразу поняли, как только хотели установить один колышек.
Папа попробовал ставить колышки в каждой точке из своего списка. При обозначении первой точки он разработал целую методику, чтобы разметить колышками на земле эллипс. Но на это ушёл примерно час времени и все колышки. Так что мы вернулись к велосипедам.