Книга шифров .Тайная история шифров и их расшифровки

N важно, поскольку оно представляет собой изменяющийся элемент односторонней функции, благодаря чему каждый человек может выбирать различные значения N, образуя всякий раз различные односторонние функции. Чтобы выбрать свое собственное значение N, Алиса берет два простых числа, р и q перемножает их. Простое число — это число, у которого нет других делителей, кроме самого себя и 1. Например, 7 — это простое число, т. к. оно не делится без остатка ни на какое другое число, кроме 1 и 7. Точно так же и 13 — простое число, т. к. оно тоже не делится без остатка ни на какое другое число, кроме 1 и 13. А вот 8 уже является не простым, а составным числом, поскольку может делиться на 2 и на 4.

Итак, Алиса может выбрать свои простые числа, например, р = 17 159 и q = 10 247. Перемножая эти два числа, она получает 17 159 х 10 247 = 175 828 273. Полученное Алисой N фактически будет ее открытым ключом для зашифровывания, и она может напечатать его на своей визитной карточке, разместить в Интернете или опубликовать в справочнике открытых ключей вместе со значениями N других людей. Если Боб захочет зашифровать сообщение для Алисы, он отыскивает ее значение N (175 828 273), а затем вставляет его в одностороннюю функцию общего вида, которая также известна всем. Теперь у Боба есть односторонняя функция, сшитая с открытым ключом Алисы, поэтому ее можно назвать односторонней функцией Алисы. Чтобы зашифровать сообщение для Алисы, он берет одностороннюю функцию Алисы, вставляет сообщение, выписывает результат и отправляет его Алисе.

В этот момент зашифрованное сообщение становится секретным, поскольку никто не сможет расшифровать его. Сообщение было зашифровано с помощью односторонней функции, поэтому обращение односторонней функции и расшифровка сообщения по определению является исключительно трудным делом. Однако остается вопрос, как же Алиса сумеет его расшифровать? Чтобы прочитать присланные ей сообщения, у Алисы должен быть способ обращения односторонней функции. Ей необходимо иметь доступ к некоторой специальной порции информации, которая и даст ей возможность расшифровать сообщение. К счастью для Алисы, Ривест задумал и создал одностороннюю функцию таким образом, что она является обратимой для каждого, кто знает значения p и q — два простых числа, которые были перемножены для получения N. Хотя Алиса сообщила всем, что у нее N равняется 175 828 273, она не раскрыла значений р и q, поэтому только у нее есть специальная информация, необходимая для расшифровки своих сообщений.

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

Подробности того, как можно использовать р и q для обращения односторонней функции приведены в Приложении J. Имеется, однако, один вопрос, который следует решить не откладывая. Если все знают открытый ключ N, то разве нельзя найти р и q — секретный ключ — и прочесть сообщения Алисы? Как-никак, Nбыло образовано из р и q. В действительности же оказывается, что если N достаточно велико, то из него практически невозможно вычислить р и q, и это, пожалуй, самый превосходный и элегантный аспект в асимметричном шифре RSA.

Алиса образовала N, выбрав pиqзатем перемножив их вместе. Основной момент здесь заключается в том, что это по своей сути односторонняя функция. Чтобы продемонстрировать односторонний характер умножения простых чисел, мы можем взять два простых числа, например, 9419 и 1933, и перемножить их. Используя калькулятор, нам понадобится всего лишь несколько секунд, чтобы получить ответ 18 206 927. Однако, если вместо этого нам дадут число 18 206 927 и попросят найти простые множители (два числа, которые перемножили, чтобы получить 18 206 927), это займет у нас гораздо больше времени. Если вы сомневаетесь в том, насколько трудно находить простые множители, то примите во внимание следующее. Мне понадобилось лишь десять секунд, чтобы образовать число 1 709 023, но у вас с калькулятором в руках, чтобы найти простые множители, это займет добрую часть дня.