Математики, шпионы и хакеры. Кодирование и криптография
Шрифт:
Для О: х = 14, С– 1(14) = 14 — 3
Для D: х = 3, С– 1(3) = 3–3
Для В: x = 1, С– 1(1) = 1–3 = —2 + 26
Сообщение SODB, зашифрованное шифром Цезаря с ключом 3, соответствует,
В заключении нашего первого знакомства с математикой криптографии мы рассмотрим новое преобразование, известное как аффинный шифр, частным случаемкоторого является шифр Цезаря. Оно определяется следующим образом:
С(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
Буква В зашифрована по формуле C(1) = 2 x 1 + 1
Буква С
зашифрована по формуле С(2) = 2 х 2 + 1Буква D зашифрована по формуле С(3) = 2 х З + 1 = 7
Буква Е зашифрована по формуле С(4) = 2 х 4 + 1 = 9
Буква F зашифрована по формуле С(5) = 2 х 5 + 1 = 11
Предлагаемый аффинный шифр преобразует сообщения АВС и DEF в одно и то же BDF, поэтому исходное сообщение теряется. Что же случилось?
Если мы работаем с шифром, выраженным формулой С(а, b)(х) = (а•х + b) (mod n), мы можем расшифровать сообщение однозначно, только когда НОД (а, n) = 1. В нашем примере НОД (2, 6) = 2 и, следовательно, не удовлетворяет этому условию.
Математическая операция расшифровки эквивалентна нахождению неизвестного х при данном значении у по модулю n.
С(а, b)(х) = (ах + b) = y (mod n)
(ах + b) = у (mod n)
ах — у — b (mod n)
Другими словами, нам нужно найти значение а– 1 (обратное значению а), удовлетворяющее равенству а– 1а = 1, так что
а– 1ах = а– 1х(у — b)(mod n)
х = а– 1(у — b)(mod n).
Следовательно, для успешной расшифровки мы должны найти число, обратное числу а по модулю n, и, чтобы не тратить зря время, мы должны заранее знать, существует ли это обратное число.
В случае аффинного шифра С(а, b)(х) = (ах + b) (mod n) обратное значение числа а будет существовать тогда и только тогда, когда НОД (а, n) = 1.
В случае аффинного шифра в нашем примере, С(х) = 2х + 1 (mod 6), мы хотим узнать, существует ли обратное значение для числа а, в нашем случае для числа 2.
То есть существует ли целое число n, которое меньше 6 и удовлетворяет выражению 2•n = 1 (mod 6). Для ответа на этот вопрос мы подставим в данное выражение все возможные значения (0, 1, 2, 3, 4, 5):
2-0 = 0, 2–1 = 2, 2–2 = 4, 2–3 = 6
Нет такого значения, следовательно, можно заключить, что 2 не имеет обратного числа. На самом деле мы это уже знали, так как НОД (2,6)
Предположим теперь, что мы перехватили зашифрованное сообщение: YSFMG. Мы знаем, что оно было зашифровано аффинным шифром вида С(х) = 2х + 3 и изначально было написано на испанском языке с алфавитом из 27 букв (включая букву N, идущую после обычной N).
Как получить исходное сообщение?