Математики, шпионы и хакеры. Кодирование и криптография | страница 55

Алгоритм 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, е) для шифрования сообщения М с помощью функции М = 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 

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

9^>7  = 4 782969 

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