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

Шрифт
Интервал

Например, найдем НОД (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) =+ 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.

С>(а, 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.

В случае аффинного шифра в нашем примере, С(х) =+ 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 

0, 2–4 = 8 
2, 2–5 = 10 
4.

Нет такого значения, следовательно, можно заключить, что 2 не имеет обратного числа. На самом деле мы это уже знали, так как НОД (2,6) 

1.

Предположим теперь, что мы перехватили зашифрованное сообщение: YSFMG. Мы знаем, что оно было зашифровано аффинным шифром вида С(х) = 2х + 3 и изначально было написано на испанском языке с алфавитом из 27 букв (включая букву N, идущую после обычной N).

Как получить исходное сообщение?

Сначала мы посчитаем НОД (2,27), который равен 1. Значит, сообщение можно расшифровать! Для этого для функции С(х) = 2х + 3 мы должны найти обратную функцию по модулю 27:

у = + 3

= у 3.

Чтобы найти x, мы должны умножить обе части уравнения на число, обратное 2.

Число, обратное числу 2 по модулю 27, — это целое число n такое, что 2n 

1 (mod 27), а именно 14. И действительно:

14∙2 = 28 

1.

Итак, мы имеем

x = 14∙(у 3).

Теперь мы можем расшифровать сообщение YSFMG.

Буква Y стоит на позиции 25, ей соответствует расшифрованная буква, стоящая на позиции

14∙(25—3) = 308 

11 (mod 27).

Буква, стоящая в алфавите на позиции 11, — это L.

Для буквы S имеем 14∙(19—3) = 224 

8 (mod 27), эта позиция соответствует букве I.

Для буквы F имеем 14∙(5–3) = 28 

1 (mod 27), что соответствует букве В.

Для буквы М имеем 14∙(12—3) = 126 

18 (mod 27), что соответствует букве R.

Для буквы G имеем 14∙(6–3) = 42 

15 (mod 27), что соответствует букве О.

Расшифрованное сообщение является испанским словом LIBRO, что означает «книга».


За пределами аффинного шифра

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

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

Если мы снимем какие-либо ограничения относительно порядка букв шифроалфавита, то потенциальное количество ключей резко возрастет. Количество ключей для стандартного алфавита из 26 символов (расположенных в произвольном порядке) составляет 26! = 403291461126605635584000000, то есть более 403 септиллионов ключей. Криптоаналитику, который тратит на проверку одного ключа всего лишь одну секунду, потребуется в миллиард раз больше времени, чем ожидаемое время существования Вселенной, чтобы исчерпать все возможности!


Еще от автора Жуан Гомес
Когда прямые искривляются. Неевклидовы геометрии

Многие из нас слышали о том, что современная наука уже довольно давно поставила под сомнение основные постулаты евклидовой геометрии. Но какие именно теории пришли на смену классической доктрине? На ум приходит разве что популярная теория относительности Эйнштейна. На самом деле таких революционных идей и гипотез гораздо больше. Пространство Минковского, гиперболическая геометрия Лобачевского и Бойяи, эллиптическая геометрия Римана и другие любопытные способы описания окружающего нас мира относятся к группе так называемых неевклидовых геометрий.


Рекомендуем почитать
Квантовый оптоэлектронный генератор

В книге развита теория квантового оптоэлектронного генератора (ОЭГ). Предложена модель ОЭГ на базе полуклассических уравнений лазера. При анализе доказано, что главным источником шума в ОЭГ является спонтанный шум лазера, обусловленный квантовой природой. Приводятся схемы и экспериментальные результаты исследования малошумящего ОЭГ, предназначенного для применения в различных областях военно-космической сферы.


Флатландия. Сферландия

Произведения Э. Эбботта и Д. Бюргера едины по своей тематике. Авторы в увлекательной форме с неизменным юмором вводят читателя в русло важных геометрических идей, таких, как размерность, связность, кривизна, демонстрируя абстрактные объекты в различных «житейских» ситуациях. Книга дополнена научно-популярными статьями о четвертом измерении. Ее с интересом и пользой прочтут все любители занимательной математики.


Стратегии решения математических задач

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


Вначале была аксиома. Гильберт. Основания математики

Давид Гильберт намеревался привести математику из методологического хаоса, в который она погрузилась в конце XIX века, к порядку посредством аксиомы, обосновавшей ее непротиворечиво и полно. В итоге этот эпохальный проект провалился, но сама попытка навсегда изменила облик всей дисциплины. Чтобы избавить математику от противоречий, сделать ее «идеальной», Гильберт исследовал ее вдоль и поперек, даже углубился в физику, чтобы предоставить квантовой механике структуру, названную позже его именем, — гильбертово пространство.


Симпсоны и их математические секреты

Саймон Сингх рассказывает о самых интересных эпизодах мультсериала, в которых фигурируют важнейшие математические идеи – от числа π и бесконечности до происхождения чисел и самых сложных проблем, над которыми работают современные математики.Книга будет интересна поклонникам сериала «Симпсоны» и всем, кто увлекается математикой.На русском языке публикуется впервые.


Истина и красота: Всемирная история симметрии

На протяжении многих веков симметрия оставалась ключевым понятием для художников, архитекторов и музыкантов, однако в XX веке ее глубинный смысл оценили также физики и математики. Именно симметрия сегодня лежит в основе таких фундаментальных физических и космологических теорий, как теория относительности, квантовая механика и теория струн. Начиная с древнего Вавилона и заканчивая самыми передовыми рубежами современной науки Иэн Стюарт, британский математик с мировым именем, прослеживает пути изучения симметрии и открытия ее основополагающих законов.