Книга шифров

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

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

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

Считается, что данная система асимметричной криптографии, известная как RSA, является одним из видов шифрования с открытым ключом. Чтобы понять, насколько надежна RSA, мы можем проверить ее с точки зрения Евы и попробовать прочесть сообщение, посланное Алисой Бобу. Для того чтобы зашифровать сообщение для Боба, Алиса должна отыскать его открытый ключ. Для создания своего открытого ключа Боб берет выбранные им самим простые числа, рB и qB , и перемножает их, получая NB. Он хранит рB и qB в секрете, ибо они составляют его секретный ключ для дешифровывания, но при этом публикует NV , которое равно 408 508 091. Так что Алиса подставляет открытый ключ Боба NB в общую одностороннюю функцию шифрования, а затем зашифровывает свое сообщение ему. Когда приходит зашифрованное сообщение, Боб может обратить функцию и расшифровать его, используя значения pв и qB, которые составляют его секретный ключ. Между тем Ева сумела во время передачи сообщения перехватить его. Ее единственная надежда расшифровать сообщение — обратить одностороннюю функцию, а это возможно только в том случае, если она знает рB и qB. Боб держит рv и qv в секрете, но, как и всем остальным, Еве известно N B, равное 408 508 091. Далее Ева пытается найти значения рB и qB путем подбора чисел, которые при перемножении дают 408 508 091 — процесс, известный как разложение на множители.