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

Легран начал с предположения, что оригинальный текст был написан на английском языке. В английских текстах наиболее часто встречается буква «е». Далее, в порядке уменьшения частоты, идут остальные буквы: а, о, 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 = 2²

•5

63 = З² •7

1050 = 2•3•5²•7.

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

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

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

3, 7, 31,127, 8191,131071, 524287, 2147483647.

В настоящее время известно чуть более 40 простых чисел Мерсенна. Самым большим из них является гигантское число: 2^43112609—1, найденное в 2008 г. Для сравнения, примерное число элементарных частиц во Вселенной меньше, чем 2³⁰⁰.

Простые числа Ферма — это простые числа вида F_n = 2²ⁿ + 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.