Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография

Гарднер призвал читателей попробовать расшифровать сообщение, используя предоставленную информацию, и даже дал подсказку: для решения необходимо разложить число Nна простые множители ри q. Более того, Гарднер назначил приз в размере $100 (приличная сумма на тот момент) тому, кто первым получит правильный ответ. Каждый, кто захочет побольше узнать о шифре, писал Гарднер, может обратиться к создателям шифра — Рону Ривесту, Ади Шамиру и Лену Адлеману из Лаборатории информации Массачусетского технологического института.

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

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

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

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

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

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

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

• Согласно теореме Эйлера, если НОД ( n, а) = 1, то а ф(n) 1 (mod 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, е) для шифрования сообщения Мс помощью функции М= m e(mod n).Получив сообщение, Джеймс вычисляет M d= (m e) d(mod n),а это выражение эквивалентно M d= (m e) 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 1 (mod 20).

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

9 7 = 4 782969 15 (mod 33).

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

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