Читать «Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография» онлайн - страница 64

pa + qb = k.

В частности, если НОД (a, b) = 1, это соотношение гарантирует существование целых чисел р и q, таких что

pa + qb = 1.

Работая по модулю n, возьмем НОД (а, n) = 1, тогда обязательно существуют целые числа р и q, такие что pa + qn = 1. Так как n — модуль, то qn = 0, следовательно, существует такое р, что pa = 1, то есть существует число, обратное числу а по модулю n, а именно р.

Элементы, имеющие обратный элемент по модулю n, являются натуральными числами, которые меньше, чем n, и удовлетворяют условию НОД (а, n) = 1. Количество таких чисел называется функцией Эйлера и обозначается как ф(n).

Если число n представлено в виде произведения степеней простых чисел следующим образом 

Например, если n = 1600 = 2^6∙5², то

Более того, в случае, если n — простое число, то для любого значения а выполняется НОД (а, n) = 1, и, следовательно, любое число а будет иметь обратное по модулю n, значит ф(n) = n — 1.

Итак, подведем итог самым важным фактам.

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

2. Если n = рq, где р и q простые числа, то

a(n) = (p — 1)(q — 1).

3. Из малой теоремы Ферма мы знаем, что если а — целое число, большее нуля, и р — простое число, то а ^р   a (mod р), что эквивалентно а^{р — 1}  1 (mod р).

4. Если НОД (а, n) = 1, тогда имеем а^ф(n)  1 (mod n).

Почему работает RSA-алгоритм?

Математические факты, изложенные выше, лежат в основе алгоритма шифрования RSA.

RSA-алгоритм зашифровывает численное представление m некоторого сообщения с помощью двух простых чисел р и q. Возьмем n = pq. Обозначим за е любое значение, такое что НОД (е, ф(n)) = 1, и пусть d будет обратный элемент числа е по модулю ф(n). [Мы знаем, что он существует, так как НОД (е, ф(n)) = 1]. Тогда:

d∙е = 1 по модулю ф(n).

Зашифрованное послание М шифруется следующим образом: М = m^е (mod n).

Алгоритм подразумевает, что исходное сообщение m может быть получено как m = M^d = (m^e)^d (mod n). Проверка этого уравнения как раз и демонстрирует работу алгоритма RSA. Мы воспользуемся теоремой Ферма и функцией Эйлера.

Рассмотрим два случая.

1. Если (m, n) = 1, то с функцией Эйлера имеем: m^ф(n) 1 (mod n).

Начнем с того, что d∙е = 1 по модулю ф(n) эквивалентно соотношению е∙d — 1 = 0 (mod ф(n)) то есть существует целое значение k, такое, что е∙d — 1 = k∙ф(n) или е∙d = k∙ф(n) + 1. Используя это и формулу Эйлера, получим:

(m^e)^d = m^ed = m ^kф(n)+1= m ^kф(n)∙m = (m ^ф(n))^k∙m  1^km (mod n) = m (mod n).

Это и есть нужный нам результат.

2. Если НОД (m,n) 1 и n = р∙q, тот содержит или только множитель р, или только q, или оба одновременно.

Пусть m содержит только множитель р. Тогда, во-первых, m кратно р, то есть существует целое число r, такое, что m = rр. Поэтому m^de  0 (mod р) или m^de = m (mod р), другими словами, существует значение А, такое, что:

m^de — m = Ар. (1)

Во-вторых, мы имеем:

(m^e)^d = m^ed = m^{k ф(n)+1} = m ^{k ф(n)}∙m = (m^ф(n))^k∙m = (m^(q-1))^k(p-1)∙m.

Так как НОД (m, n) = р, НОД (m, q) = 1, то по теореме Ферма m^(q-1)  1 (mod q).