Литмир - Электронная Библиотека

pa + qb = 1.

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

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

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

Математики, шпионы и хакеры. Кодирование и криптография - _130.jpg

Математики, шпионы и хакеры. Кодирование и криптография - _131.jpg

Например, если n = 1600 = 26∙52, то

Математики, шпионы и хакеры. Кодирование и криптография - _132.jpg

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

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

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

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

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

3. Из малой теоремы Ферма мы знаем, что если а — целое число, большее нуля, и р — простое число, то а р  

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_38
 a (mod р), что эквивалентно ар — 1
Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_40
 1 (mod р).

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

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_39
 1 (mod n).

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

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

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

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

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

Алгоритм подразумевает, что исходное сообщение m может быть получено как m = Md = (me)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. Используя это и формулу Эйлера, получим:

(me)d = med = m kф(n)+1= m kф(n)∙m = (m ф(n))k∙m 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_28
1km (mod n) = m (mod n).

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

2. Если НОД (m,n)

Математики, шпионы и хакеры. Кодирование и криптография - n.jpg_0
 1 и n = рq, тот содержит или только множитель р, или только q, или оба одновременно.

Пусть m содержит только множитель р. Тогда, во-первых, m кратно р, то есть существует целое число r, такое, что m =. Поэтому mde 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_29
0 (mod р) или mde = m (mod р), другими словами, существует значение А, такое, что:

mde m = Ар. (1)

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

(me)d = med = mk ф(n)+1 = m k ф(n)m = (mф(n))km = (m(q-1))k(p-1)m.

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

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_30
1 (mod q).

Подставим это в предыдущее выражение.

(me)d = med = mk ф(n)+1 = m k ф(n)∙m = (mф(n))km = (m(q-1))k(p-1)m

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_31
 1k (р-1)m 
Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_32
m (mod q).

Откуда мы заключаем, что существует значение В, такое что:

mde m = Вq. (2)

Из (1) и (2) следует, что разность (mdem) делится на n = рq, поэтому

mde m 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_33
0 (mod n).

Аналогично это доказывается для случая, когда m содержит только множитель q.

В случае, когда m кратно и р, и q одновременно, результат тривиален. Следовательно,

(mе)d 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_34
 m (mod n).

Таким образом, мы продемонстрировали математическую основу алгоритма RSA.

Список литературы

Fernandez, S., Classical Cryptography. Sigma Review No. 24, April 2004.

Garfunkel, S., Mathematics in Daily Life, Madrid, COMAP, Addison-Wesley, UAM, 1998.

Gomez, J., From the Teaching to the Practice of Mathematics Barcelona, Paidos, 2002.

Kahn, D., The Codebreakers: The Story of Secret Writing, New York, Scribner, 1996.

Издание на русском языке: Кан Д. Взломщики кодов. — М.: Центрполиграф, 2000.

Singh, S., The Secret Codes, Madrid, Editorial Debate, 2000.

Tocci, R., Digital Systems: Principles and Applications, Prentice Hall, 2003.

Издание на русском языке: Тончи Р. Цифровые системы. Теория и практика. — М.: Вильямс, 2004.

* * *

Научно-популярное издание

Выходит в свет отдельными томами с 2014 года

Мир математики

Том 2

Жуан Гомес

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

Кодирование и криптография.

РОССИЯ

Издатель, учредитель, редакция:

ООО «Де Агостини», Россия

Юридический адрес: Россия, 105066,

г. Москва, ул. Александра Лукьянова, д. 3, стр. 1

Письма читателей по данному адресу не принимаются.

29
{"b":"247091","o":1}