Математики, шпионы и хакеры. Кодирование и криптография | страница 17
Например, найдем НОД (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.
В случае аффинного шифра в нашем примере,
