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

Легран начал с предположения, что оригинальный текст был написан на английском языке. В английских текстах наиболее часто встречается буква «е». Далее, в порядке уменьшения частоты, идут остальные буквы: а, о, i, d, h, n, r, s, t, u, y, c, f, g, 1, m, w, b, k, p, q, x, z.

Герой рассказа строит по криптограмме таблицу, в первой строке которой расположены символы зашифрованного сообщения, а во второй — частота их появления.

Таким образом, символ «8» скорее всего соответствует букве «е». Затем он ищет повторяющиеся тройки символов, заменившие также довольно распространенное слово «the», что позволяет ему расшифровать символы «;», «,», «4» и «8».

Группа символов «; (88», теперь, когда он знает, что она соответствует «t (ее», позволяет ему определить отсутствующую букву. Это может быть только «r», учитывая, что tree — «дерево» — наиболее вероятное слово в словаре. Наконец, благодаря подобным хитроумным криптографическим допущениям и большому терпению, он получает следующую таблицу с частично расшифрованным алфавитом:

Этого достаточно, чтобы расшифровать сообщение:

«Хорошее стекло в трактире епископа на чёртовом стуле двадцать один градус и тринадцать минут север-северо-восток главный сук седьмая ветвь восточная сторона стреляй из левого глаза мертвой головы прямая от дерева через выстрел на пятнадцать футов».

Настоящая математика не оказывает влияния на войну. Никому еще не удалось обнаружить ни одну военную задачу, которой бы служила теория чисел.

Годфри Харолд Харди, «Апология математика» (1940)

Для расшифровки сообщения важно, чтобы шифр был обратим. Как мы уже видели в случае аффинного шифра, это можно гарантировать, лишь используя простое число в качестве модуля. Более того, произведение простых чисел является практически необратимой функцией, то есть после выполнения умножения разложить произведение на исходные множители является очень трудоемкой задачей.

Такое свойство превращает эту операцию в очень полезный инструмент для систем шифрования, основанных на асимметричных ключах, как, например, RSA-алгоритм, который, в свою очередь, является основой криптографии с открытым ключом. Далее мы более подробно расскажем о связи простых чисел с криптографией и о формальной математической основе алгоритма RSA.

Простые числа и «другая» теорема Ферма

Простые числа — это подмножество натуральных чисел, больших единицы, которые делятся только на единицу и на само себя. Основная теорема арифметики утверждает, что любое натуральное число, большее единицы, всегда можно представить в виде произведения степеней простых чисел, и это представление (факторизация) является единственным. Например:

20 = 22∙5

63 = З2 ∙7

1050 = 2∙3∙52∙7.

Все простые числа, кроме числа 2, нечетные. Единственные два последовательных простых числа — это 2 и 3. Нечетные последовательные простые числа — т. е. пары простых чисел, отличающихся на 2 (например, 17 и 19), — называются простыми числами-близнецами. Простые числа Мерсенна и числа Ферма также представляют особый интерес.

Простое число называется числом Мерсенна, если при добавлении единицы получается степень двойки. Например, 7 — число Мерсенна, так как 7 + 1 = 8 = 23.

Первые восемь простых чисел Мерсенна выглядят так:

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) и 65537 (n = 4).

Простые числа Ферма носят имя прославленного французского юриста и математика Пьера де Ферма (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 — простое число, то для любого значения а выполняется НОД (а, 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, или оба одновременно.