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

* * *

На следующее утро я наблюдал, как тётя Надя прогоняла дочек от чана с рыбой, а те хотели устроить рыбную ловлю на удочки. Дядя Руслан собирался снова ехать в Муханские овраги, а дядя Игорь ворчал, что его заставляют чистить всю рыбу. Но все были неумолимы — он просил, он наловил, теперь надо готовить. Так что именно дяде Игорю досталась эта обязанность.

Отец сидел на скамейке и грелся на утреннем солнышке. Я подошёл и спросил:

— Скажи, пап, а что стало с теми людьми, которые напали на нас ночью?

Отец, не открывая глаз, ответил:

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

— Что будем делать?

— Да ничего особенного. Вряд ли кто-то сунется, пока нас тут много. Плохо то, что, когда уедем, могут отомстить, отыгравшись на имуществе. И ничего не поможет. Ну ладно, тут уже ничего не поделаешь. Не переезжать же сюда жить.

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

— Пока все заняты, я хочу рассказать вам ещё несколько интересных вещей. Вспомните предыдущий способ шифрования. Я не говорил вам, что он очень устойчив к взлому, и потому на нём основана большая часть современной криптографии? Но скажите, почему же его очень сложно взломать?

Катя ответила:

— Мне кажется, мы уже говорили на эту тему: похоже, у нас просто нет достаточно эффективных методов разложения числа на простые множители.

— Да, верно. А теперь представьте, что у нас вдруг появится средство для быстрого разложения на простые множители произвольно большого числа. Например, чтобы сегодня найти простые множители числа с двумя тысячами цифр, требуется несколько лет работы сети из сотни компьютеров. Но вдруг появится средство, которое будет давать тот же самый результат за пару минут. Что произойдёт?

Мы задумались. Катя перелистывала свой рабочий блокнот, я вспоминал детали этого криптографического алгоритма, но ничего в голову не приходило. Это странно — ведь в алгоритме RSA разложение на множители не используется напрямую. Открытый ключ — открытая экспонента и произведение двух простых чисел, а закрытый — закрытая экспонента и то же самое произведение. Злоумышленник может получить открытую экспоненту и произведение двух простых чисел, но этого недостаточно, чтобы расшифровать послание. Нужна закрытая экспонента.

Отец смотрел на нас, но ничего не говорил. А мы, откровенно говоря, не знали, что сказать в ответ. Через минут пять отец решил нам помочь:

— Ну что нужно для расшифровки?

Я ответил сразу же:

— Закрытая экспонента.

— А как она вычисляется?

Хм-м. Это обратный элемент для открытой экспоненты по модулю, равному функции Эйлера для произведения двух простых чисел. Я сказал:

— Нам надо уметь вычислять обратный элемент.

Но отец парировал:

— Это очень просто. Это несложная задача. Её можно решить хотя бы перебором. Подумайте. Ты уже сказал про функцию Эйлера. Для чего она нужна?

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

И тут Катя воскликнула:

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

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

Я спросил:

— Погоди-ка. Если ты говоришь, что есть метод быстрого взлома этого алгоритма RSA, но при этом на нем основана вся криптозащита в мире, то не собираешься ли ты нам рассказать страшную тайну, за которую могут и чикнуть?

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

Отец немного поразмыслил, а потом сказал:

— Итак, давайте с самого начала. Кто мне скажет, как при помощи двух простых множителей взломать шифрограмму RSA?

Я, не дожидаясь разрешения, выпалил:

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

Отец похвалил меня, а потом обратился к Кате:

— Катерина, скажи теперь ты, что такое «обратный элемент»?

— Это такое число, которое, если его перемножить с заданным, даст единицу по некоторому модулю.

— Отлично! Никак не думал, что вы сможете так просто оперировать математическими понятиями, которые изучаются на специальных курсах абстрактной алгебры. Теперь давайте поговорим о новой математической модели, про которую я обещал вам рассказать. Она называется «квантовые вычисления».

Я даже выдохнул от таких известий. Дело в том, что я точно знал: в научной лаборатории у отца уже сейчас проходит испытания прототип квантового компьютера. При его разработке использовались те же самые технологии, которые он применял ко мне для создания искусственной памяти. Неужели теперь он посвятит меня в тайну этих методов?

Вместе с тем отец продолжал:

— Вы хорошо знаете, что в информатике и теории информации используется понятие «бит». Это единица количества информации, и один бит представляет собой количество актов выбора между двумя альтернативами. Если у нас есть два различных предмета, то для того, чтобы выбрать между ними, требуется один бит. Если есть четыре предмета, то для выбора одного требуется два бита. Для восьми предметов требуется три бита. Ну и так далее, вы уже должны это прекрасно понимать. Традиционно для представления битов используются две цифры — 0 и 1. Так и выглядит альтернатива между двумя предметами: 0 или 1. Если у нас четыре предмета, то требуется два бита, которые дают четыре варианта: 00, 01, 10 и 11. Вспомнили?