— Верно! А асимметричное?
Тут уже в разговор вступила Катя:
— Ну, видимо, когда ключи у сторон разные?
— Да. Но как такое возможно?
Мы переглянулись и пожали плечами. Наверняка это опять было связано с какой-нибудь сложной математикой, про которую нам в школе ещё не рассказывали — примерно так, как это было с протоколом Диффи — Хеллмана.
Папа не стал ждать наших ответов и продолжил:
— Представьте, что было бы, если бы мы могли зашифровывать текст одним ключом, а расшифровывать его надо было бы другим. Как можно воспользоваться такой технологией? Не забудьте о проблеме распространения ключей.
Я уже знал ответ:
— Такой проблемы не было бы. Мы могли бы разместить ключ для шифрования хотя бы на доске объявлений, к которой есть доступ у любого. И любой человек смог бы этим ключом зашифровать текст, но никто, даже он сам, уже не мог бы его расшифровать. Но имея тайный ключ для расшифровки, мы могли бы расшифровывать сообщения, отправляемые нам.
Отец ответил:
— Всё верно. Ключ для всех называется «открытым», и при помощи него можно только зашифровывать. Расшифровать текст уже не получится. Ключ для расшифровки называется «закрытым», и он должен храниться в секрете. Это можно пояснить при помощи замка и ключа.
Папа быстро нарисовал картинку, на которой были шкафчик, амбарный замок и ключ от него.
— Вот шкафчик открыт. В него любой может положить письмо и закрыть замком, просто защёлкнув его. Всё, теперь шкафчик открыть нельзя. Замок — это открытый ключ. Он используется для шифрования, то есть сокрытия информации. Теперь, чтобы открыть замок, нужен ключик, то есть закрытый ключ. Он есть только у владельца шкафчика. Всё просто.
Он посмотрел на нас и спросил, всё ли понятно. Мы в ответ синхронно кивнули. Тогда он продолжил:
— Давайте подумаем, что может служить таким замком и ключиком в криптографии. Помните, что вся современная криптография основана на математике. Давайте найдём что-то математическое, что позволяет просто запирать замочек, но не позволяет отпирать. Подумайте, дайте поработать своей интуиции…
Но у нас с Катей ничего не получалось. Мы сделали пару предположений, но папа все их отверг. Тогда он продолжил сам:
— Возьмём простые числа. Помните, что это такое? Простым называется число, у которого нет целых делителей, кроме единицы и его самого. Ряд простых чисел начинается так: 2, 3, 5, 7, 11, 13 и так далее. Пока не доказано, что ряд простых чисел бесконечен, но и не опровергнуто. При этом нет формулы, при помощи которой можно было бы получить простое число по его номеру. Другими словами, ряд целых чисел необходимо вычислить и запомнить. Третья проблема — нет и эффективного алгоритма для построения ряда простых чисел. Есть, например, алгоритм под названием «решето Эратосфена». Надо взять бесконечный ряд натуральных чисел, начинающийся с 2, и вычёркнуть все числа, которые делятся на 2. Потом вычеркнуть все числа, которые делятся на 3, потом на 5, потом на 7 и так далее до бесконечности. Как вы понимаете, для бесконечности этот алгоритм не вполне эффективен. Но если нужно найти все простые числа, не превышающие заданного, то этот алгоритм работает довольно быстро. Особенно если использовать эффективные критерии делимости.
Мы с Катей переглянулись, так как было всё ещё неясно, при чем тут принципы асимметричного шифрования. Я сказал:
— Всё это хорошо и понятно. Расскажи нам про асимметричное шифрование.
Отец тяжело вздохнул и начал с другой стороны:
— Ну ладно. Давайте так. Возьмём два очень больших простых числа. Пусть в каждом из них будет по тысяче цифр. Перемножить эти два числа проще простого, так? Но просто ли по произведению найти эти два числа?
Эта задача была мне известна, поэтому я сказал:
— Нет, это очень сложная задача. Теперь я понял — ты говоришь про разложение числа на простые множители. В общем виде эта задача не имеет эффективного решения.
Катя с подозрением посмотрела на меня, а отец продолжил:
— Да, ты абсолютно прав. Если взять огромное число, а наше произведение состоит приблизительно из двух тысяч цифр, то разложить его на простые множители практически невозможно. Не существует эффективных алгоритмов для того, чтобы сделать это. Даже если мы знаем, что число представляет собой произведение двух простых чисел, то чтобы найти их, понадобится астрономическое число операций. И чем больше число, которое надо разложить на простые множители, тем больше операций нужно для этого, и количество операций растёт экспоненциально. А теперь ответьте мне: что в рассмотренном математическом формализме — замок, а что — ключ от него? Другими словами, чем мы будем шифровать, а чем расшифровывать?
Я задумался, а Катя ответила сразу же:
— Очевидно, произведение будет замком, то есть будет использоваться для шифрования. А вот его разложение на множители будет ключом — именно эту информацию надо хранить в тайне.
— Почему?
— Ну потому, что мы только что обсудили, что для того, чтобы получить произведение двух простых чисел, их надо просто перемножить. А для того чтобы разложить большое число на два простых, надо очень сильно постараться. Другими словами, то, что сделать просто, должно быть общедоступно. А вот то, что сделать практически невозможно, надо объявить тайной.
Отец сказал, что Катя полностью права. Затем он продолжил свои объяснения:
— На самом деле не всё так просто. В качестве открытых и закрытых ключей в алгоритме, про который я хочу вам рассказать, используются иные значения. Но они вычисляются на основе пары простых чисел. Давайте посмотрим…