Криптографические приключения: таинственные шифры - Страница 43

— Катерина, ты можешь сказать, чему будет равно 2 в степени 21 по модулю 13?

— Пять?

— Верно. Как вы видите, тут имеется явная закономерность — степени двойки вразнобой пробегают все числа от 1 до 12 при вычислении их остатка по модулю 13, потом всё повторяется. Этот период и эта последовательность будут повторяться до бесконечности. И это очень важное свойство, ради которого мы всё это рассмотрели. Давайте запишем такое уравнение:

2 = 11 (mod 13)

Отец написал его на листке и продемонстрировал нам. Неизвестное стояло в степени двойки, и я как-то сразу затруднился, поскольку в школе мы подобного ещё не проходили. Судя по виду Кати, она тоже не знала, как его решать. Отец же продолжил:

— Надо найти наименьшее число X, при подстановке которого в это уравнение оно становится правильным. Очевидно, что в данном случае это число 7. Но как решается это уравнение? Проблема в том, что решить его мы можем только способом перебора или очень сложного алгоритма, называющегося «дискретным логарифмированием». А теперь подумаем, что будет, если мы возьмём не модуль 13, а какое-нибудь другое число, состоящее из нескольких тысяч цифр. Теоретически такое уравнение решить можно, но на практике для этого потребуется слишком много времени. Очень много. Больше, чем есть у кого бы то ни было.

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

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

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

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

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

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

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

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

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

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

p = 17

g = 5

a = 7

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

p = 17

g = 5

A = 10

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

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

Я записал:

b = 14

B = 15

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

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

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

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

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

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

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

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

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