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

Этот результат имеет большое значение для современной криптографии, как мы сейчас увидим.

От Эйлера к RSA

Еще один важный результат в модульной арифметике известен как соотношение Везу. Это утверждение гласит, что если аи b— целые положительные числа, тогда уравнение НОД ( a, b) = к эквивалентно существованию двух целых чисел р, q, таких что:

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 2, то

Более того, в случае, если 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 р), другими словами, существует значение А, такое, что: