Математики, шпионы и хакеры. Кодирование и криптография
Шрифт:
Первые восемь простых чисел Мерсенна выглядят так:
3, 7, 31,127, 8191,131071, 524287, 2147483647.
В настоящее время известно чуть более 40 простых чисел Мерсенна. Самым большим из них является гигантское число: 243112609—1, найденное в 2008 г. Для сравнения, примерное число элементарных частиц во Вселенной меньше, чем 2300.
Простые числа Ферма — это простые числа вида Fn = 22n + 1, где n — натуральное число.
В настоящее время известно пять простых чисел Ферма: 3 (n = 0), 5 (n = 1), 17 (n = 2), 257 (n = 3)
Простые числа Ферма носят имя прославленного французского юриста и математика Пьера де Ферма (1601–1665), который их открыл. Он сделал также другие важные открытия в теории простых чисел. Классической является малая теорема Ферма, которая утверждает: «Если р — простое число, и целое а не делится на р, тоар a (mod р).»
Этот результат имеет большое значение для современной криптографии, как мы сейчас увидим.
От Эйлера к 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 = 26•52, то
Более того, в случае, если n — простое число,
Итак, подведем итог самым важным фактам.
1. ф(n) называется функцией Эйлера и обозначает количество натуральных чисел, меньших n и взаимно простых с ним.
2. Если n = рq, где р и q простые числа, то
a(n) = (p — 1)(q — 1).
3. Из малой теоремы Ферма мы знаем, что если а — целое число, большее нуля, и р — простое число, то а р
4. Если НОД (а, n) = 1, тогда имеем аф(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. Используя это и формулу Эйлера, получим: