Правильный ответ был получен лишь через 17 лет. Он стал результатом сотрудничества более чем 600 человек. Ключами оказались р = 32769132993266 709549961988190834461413177642967992942539798288533 и q = 3490529510847650949147849619903898133417764638493387843990820577, а зашифрованная фраза звучала так: «Волшебные слова — это брезгливый ягнятник».

Алгоритм, представленный Гарднером, известен как RSA — буквенная аббревиатура от фамилий Rivest (Ривест), Shamir (Шамир) и Adleman (Адлеман). Это первое практическое применение придуманной Диффи системы шифрования с открытым ключом, которая повсеместно используется и по сей день. Надежность ее практически гарантирована, потому что процесс расшифровки является невероятно сложным, почти невозможным делом. Далее мы рассмотрим основы этой системы в упрощенной форме.

Подробнее об алгоритме RSA

Алгоритм RSA основан на некоторых свойствах простых чисел, о которых заинтересованный читатель может подробнее прочитать в Приложении. Мы ограничимся здесь изложением простых фактов, лежащих в основе алгоритма.

• Количество натуральных чисел, меньших n и взаимно простых с n, называется функцией Эйлера и обозначается как ф(n).

• Если n = p•q, где р и q — простые числа, то ф(n) = (р — 1)(q — 1).

• Из малой теоремы Ферма мы знаем, что если а — целое число, большее нуля, и р — простое число, то ар-1

• Согласно теореме Эйлера, если НОД (n, а) = 1, то аф(n)

Как уже упоминалось, система шифрования называется «с открытым ключом», потому что ключ шифрования доступен любому отправителю, желающему передавать сообщения. Каждый получатель имеет свой открытый ключ. Сообщения всегда передаются в виде цифр, будь то ASCII-коды или какая-либо другая система.

Сначала Джеймс вычисляет значение n путем умножения двух простых чисел р и q (n = pq) и выбирает значение е так, чтобы НОД (ф(n), е) = 1. Напомним, что ф(n) = (р — 1)(q — 1). Данные, которые являются открытыми, — это значение n и значение е (ни при каких обстоятельствах нельзя выдавать значения р и q). Пара (n, е) является открытым ключом системы, а значения р и q называются RSА-числами. Затем Джеймс вычисляет единственное значение d по модулю ф(n), которое удовлетворяет условию d•е = 1, то естьd является обратным элементом к числу е по модулю ф(n). Мы знаем, что обратный элемент существует, потому что НОД (ф(n), е) = 1. Это число d является закрытым ключом системы. Со своей стороны, Питер использует открытый ключ (n, е) для шифрования сообщения М с помощью функции М = me (mod n). Получив сообщение, Джеймс вычисляет Md = (me)d (mod n), а это выражение эквивалентно Md = (me)d = m (mod n), что свидетельствует о возможности расшифровать сообщение.

Теперь мы применим эту процедуру к конкретным числовым значениям.

Если р = 3 и q = 11, получим n = 33. Тогда ф(33) = (3–1)•(11—1) = 20.

Джеймс выбирает е, не имеющее общего делителя с 20, например, е = 7. Открытый ключ Джеймса (33,7).

• Джеймс также вычислил закрытый ключ d, который является обратным элементом к числу 7 по модулю 20, а именно число d = 3, так как 7•3 

• Питер, имея открытый ключ, хочет отправить нам сообщение «9». Чтобы зашифровать это сообщение, он использует открытый ключ Джеймса и вычисляет:

97  = 4 782969 

Зашифрованное сообщение имеет вид «15». Питер посылает его нам.

Джеймс получает сообщение «15» и расшифровывает его следующим образом:

153  = 3375 

Сообщение расшифровано правильно.

Если мы выбираем большие простые числа р, q, то вычисления в алгоритме RSA становятся такими сложными, что нам придется использовать компьютер. Например, если р = 23 и q = 17, то n = 391. Открытым ключом при выбранном е = 3 будет пара (391,3). Тогда d = 235. Для простого сообщения «34» операция расшифровки будет выглядеть так:

204235 

Обратите внимание на степень числа и представьте себе гигантское количество расчетов, необходимых для нахождения этого решения.

Почему мы можем доверять алгоритму RSA

Потенциальный шпион располагает значениями n и е, потому что они являются открытыми. Чтобы расшифровать сообщение, ему нужно также значение d, т. е. закрытый ключ. Как мы показали в предыдущем примере, значение d получается из n и е. Чем же обусловлена безопасность? Напомним, что для построениям/ необходимо знать ф(n) = (р — 1)(q — 1), в частности, р и q. Для этого «достаточно» разложить n на простые множители р и q. Проблема для шпиона заключается в том, что разложение большого числа на простые множители является медленным и трудоемким процессом. Если n достаточно большое (состоящее более чем из 100 цифр), не существует известных способов нахождения р и q за разумное количество времени. В настоящее время простые числа, используемые для шифрования чрезвычайно конфиденциальных сообщений, состоят более чем из 200 цифр.

Алгоритм RSA требует много машинного времени и очень мощных процессоров.

До 1980-х гг. только правительства, армия и крупные предприятия имели достаточно мощные компьютеры для работы с RSA. В результате у них была фактически монополия на эффективное шифрование. Летом 1991 г. Филипп Циммерман, американский физик и борец за сохранение конфиденциальности, предложил бесплатную систему шифрования PGP (Pretty Good Privacy — «достаточно хорошая степень конфиденциальности»), алгоритм которой мог работать на домашних компьютерах.