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

Мы видим, что зашифрованное значение буквы под номером х(в стандартном алфавите) является буквой, стоящей на позиции х+ 3 (также в стандартном алфавите). Поэтому необходимо найти преобразование, которое каждому числу ставит в соответствие число, сдвинутое на три единицы, и взять результат по модулю 26.

Заметим, что 3 является ключом нашего шифра. Таким образом, наша функция записывается как

C(х)= (х+ 3) (mod 26),

где х— изначальное значение, а С( х) — зашифрованное значение. Теперь достаточно подставить вместо буквы ее числовое значение и применить трансформацию.

Возьмем в качестве примера слово PLAY и зашифруем его.

Буква Рстоит на позиции 15, С(15) = 15 + 3 18 (mod 26), а число 18 соответствует букве S.

Буква Lстоит на позиции 11, С(11) = 11 + 3 14 (mod 26), а число 14 соответствует букве О.

Буква Астоит на позиции 0, С(0) = 0 + 3 3 (mod 26), а число 3 соответствует букве D.

Буква Yстоит на позиции 24, С (24) = 24 + 3 = 27 1 (mod 26), а число 1 соответствует букве В.

Таким образом, слово PLAY, зашифрованное с ключом 3, превратится в слово SODB.

В общем случае, если хозначает позицию буквы, которую мы хотим зашифровать (0 для А, 1 для В, и т. д.), позиция зашифрованной буквы [обозначаемая С( х)] выражается формулой

С(х)= (х+ k) (mod n),

где n— длина алфавита (26 в английском алфавите), a k— ключ, используемый в данном шифре.

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

С -1 (х)= (х— k) (mod n).

В случае сообщения SODB, зашифрованного шифром Цезаря с ключом 3 с применением английского алфавита, то есть k = 3 и n = 26, мы получим:

С -1 (х)= (х— 3) (mod 26).

Применим эту формулу следующим образом:

Для S: х = 18, С -1(18) = 18 — 3 15 (mod 26), что соответствует букве Р.

Для О: х = 14, С -1(14) = 14 — 3 11 (mod 26), что соответствует букве L.

Для D: х = 3, С -1(3) = 3–3 0 (mod 26), что соответствует букве А.

Для В: x = 1, С -1(1) = 1–3 = —2 + 26 24 (mod 26), что соответствует букве Y.

Сообщение SODB, зашифрованное шифром Цезаря с ключом 3, соответствует, как мы уже знаем, оригинальному тексту PLAY.

В заключении нашего первого знакомства с математикой криптографии мы рассмотрим новое преобразование, известное как аффинный шифр, частным случаемкоторого является шифр Цезаря. Оно определяется следующим образом:

С (a,Ь)(x)= (а∙ х + b) (mod n),

где аи b— два целых числа, меньших, чем число ( n) букв в алфавите. Наибольший общий делитель (НОД) чисел аи nдолжен быть равен 1 [НОД ( а, n) = 1], потому что иначе, как мы увидим позже, получится несколько возможностей для шифрования одной и той же буквы. Ключ шифра определяется парой ( а, Ь). Шифр Цезаря с ключом 3 является, следовательно, аффинным шифром со значениями

а= 1 и b= 3.

Обобщенный аффинный шифр имеет более высокий уровень безопасности, чем обычный шифр Цезаря. Почему? Как мы видели, ключом аффинного шифра является пара чисел ( а, b). Если сообщение написано с использованием алфавита из 26 букв и зашифровано с помощью аффинного шифра, то и а, и bмогут принимать любые значения от 0 до 25. Таким образом, в этой системе шифрования с алфавитом из 26 букв возможное количество ключей составит 25 х 25 = 625. Заметим, что количество ключей для алфавита из nбукв в nраз больше, чем в шифре Цезаря.

Это значительное улучшение, но аффинный шифр все еще возможно расшифровать методом перебора всех возможных вариантов.

* * *

НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ (НОД)

Наибольший общий делитель двух чисел может быть найден с помощью алгоритма Евклида. Этот алгоритм заключается в делении одного числа на другое, а затем проведении последовательных делений предыдущего делителя на новый остаток. Процесс заканчивается, когда остаток равен 0. Делитель последней операции деления и будет наибольшим общим делителем данных чисел.

Например, найдем НОД (48,30).

Разделим 48 на 30, получим остаток 18 и частное 1.

Разделим 30 на 18, получим остаток 12 и частное 1.

Разделим 18 на 12, получим остаток 6 и частное 1.

Разделим 12 на 6, получим остаток 0 и частное 2.

Мы закончили алгоритм.

НОД (48,30) = 6.

Если НОД( а, n) = 1, мы говорим, что аи nвзаимно просты.

Соотношение Везу, имеющее большое значение в криптографии, устанавливает следующий факт: для двух целых чисел аи n, больших нуля, существуют целые числа kи q, такие что НОД( а, n) = kа+ nq.

При каких условиях сообщение, зашифрованное аффинным шифром, может расшифровать предполагаемый получатель или шпион? Мы ответим на этот вопрос, используя простой пример шифра для алфавита из шести букв:

Текст будет зашифрован с помощью аффинного шифра C(x)= 2x+ 1 (mod 6).

Буква Азашифрована по формуле С(0) = 2 х 0 + 1 1 (mod 6), что соответствует букве В.

Буква Взашифрована по формуле C(1) = 2 x 1 + 1 3 (mod 6), что соответствует букве D.

Буква Сзашифрована по формуле С(2) = 2 х 2 + 1 5 (mod 6), что соответствует букве F.

Буква Dзашифрована по формуле С(3) = 2 х З + 1 = 7 1 (mod 6), что соответствует букве В.

Буква Езашифрована по формуле С(4) = 2 х 4 + 1 = 9 3 (mod 6), что соответствует букве D.

Буква Fзашифрована по формуле С(5) = 2 х 5 + 1 = 11 5 (mod 6), что соответствует букве F.

Предлагаемый аффинный шифр преобразует сообщения АВС и DEF в одно и то же BDF, поэтому исходное сообщение теряется. Что же случилось?

Если мы работаем с шифром, выраженным формулой С (а, b)(х)= (а∙ х+ b) (mod n), мы можем расшифровать сообщение однозначно, только когда НОД ( а, n) = 1. В нашем примере НОД (2, 6) = 2 и, следовательно, не удовлетворяет этому условию.

Математическая операция расшифровки эквивалентна нахождению неизвестного хпри данном значении упо модулю n.