Математики, шпионы и хакеры

Алгоритм 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⁷  = 4 782969  15 (mod 33).

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

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

15³  = 3375  9 (mod 33).

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

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

204²³⁵  34 (mod 391).

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

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

Потенциальный шпион располагает значениями n и е

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

Приемлемая конфиденциальность

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

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

PGP использует классическое симметричное шифрование, что и обеспечивает ей большую скорость на домашних компьютерах, но она шифрует ключи по асимметричному алгоритму RSA.

Циммерман объяснил причины этой меры в открытом письме, которое заслуживает быть процитированным здесь, по крайней мере, частично из-за пророческого описания того, как мы живем, работаем и общаемся два десятилетия спустя.