Математики, шпионы и хакеры. Кодирование и криптография - Гомес Жуан - Страница 29
- Предыдущая
- 29/30
- Следующая
pa + qb = 1.
Работая по модулю n, возьмем НОД (а, n) = 1, тогда обязательно существуют целые числа р и q, такие что pa + qn = 1. Так как n — модуль, то qn = 0, следовательно, существует такое р, что pa = 1, то есть существует число, обратное числу а по модулю n, а именно р.
Элементы, имеющие обратный элемент по модулю n, являются натуральными числами, которые меньше, чем n, и удовлетворяют условию НОД (а, n) = 1. Количество таких чисел называется функцией Эйлера и обозначается как ф(n).
Если число n представлено в виде произведения степеней простых чисел следующим образом
Например, если n = 1600 = 26∙52, то
Более того, в случае, если 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 = 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
1km (mod n) = m (mod n).Это и есть нужный нам результат.
2. Если НОД (m,n)
1 и n = р∙q, тот содержит или только множитель р, или только q, или оба одновременно.Пусть m содержит только множитель р. Тогда, во-первых, m кратно р, то есть существует целое число r, такое, что m = rр. Поэтому mde
0 (mod р) или mde = m (mod р), другими словами, существует значение А, такое, что:mde — m = Ар. (1)
Во-вторых, мы имеем:
(me)d = med = mk ф(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).Подставим это в предыдущее выражение.
(me)d = med = mk ф(n)+1 = m k ф(n)∙m = (mф(n))k∙m = (m(q-1))k(p-1)∙m
1k (р-1)∙m m (mod q).Откуда мы заключаем, что существует значение В, такое что:
mde — m = Вq. (2)
Из (1) и (2) следует, что разность (mde — m) делится на n = рq, поэтому
mde — m
0 (mod n).Аналогично это доказывается для случая, когда m содержит только множитель q.
В случае, когда m кратно и р, и q одновременно, результат тривиален. Следовательно,
(mе)d
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/30
- Следующая