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

Например, сообщение TRILL будет разбито на биграммы следующим образом:

TR IL LX.

А слово TOY — так:

ТО YX.

Разбив текст на биграммы, мы можем начать шифрование, обращая внимание на следующие условия:

а) две буквы биграммы расположены в одной и той же строке;

б) две буквы биграммы расположены в одном и том же столбце;

в) ни одно из вышеперечисленных.

В случае (а) буквы биграммы заменяются буквами, расположенными справа от каждой из них («следующими» в таблице в естественном порядке). Таким образом, пара JE будет зашифрована как AS:

В случае (б) буквы биграммы заменяются буквами, которые находятся следом ниже по таблице. Например, биграмма ЕТ будет зашифрована, как FY, a TY — как YE:

В случае (с), чтобы зашифровать первую букву биграммы, мы смотрим на ее строку, пока не дойдем до столбца, содержащего вторую букву. Результат расположен на пересечении этой строки и этого столбца. Чтобы зашифровать вторую букву, мы смотрим на ее строку, пока не дойдем до столбца, содержащего первую букву.

Результат опять расположен на пересечении этой строки и этого столбца.

Например, в биграмме СО буква С будет заменена буквой G, а буква О — буквой I или К.

Чтобы зашифровать сообщение TEA («чай») с помощью ключевого слова JAMES, мы сделаем следующее.

• Разобьем слово на биграммы: ТЕ АХ.

• Букву Т заменим буквой Y.

• Букву Е — F.

• Букву А — М.

• Букву X — W.

Мы получим зашифрованное сообщение YFMW.

Криптограмма «Золотого жука»

Уильям Легран, главный герой рассказа Эдгара Аллана По «Золотой жук» (1843), определяет, где зарыт клад с сокровищами, расшифровав криптограмму, написанную на куске пергамента. Легран использовал статистический метод, основанный на частоте, с которой буквы алфавита встречаются в английских текстах. Зашифрованное послание выглядело следующим образом:

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

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

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

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

Такое свойство превращает эту операцию в очень полезный инструмент для систем шифрования, основанных на асимметричных ключах, как, например, 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.

В частности, если НОД (a, b) = 1, это соотношение гарантирует существование целых чисел р и q, таких что