Теме криптографии посвящён сериал Prime Target (в русской локализации называется «Опасные числа»). Он включает в себя множество математических и криптографических отсылок, которые обогащают его сюжет и подчёркивают интеллектуальные вызовы, стоящие перед героями. В этой статье вместе с настоящими криптографами мы разберём, какие атрибуты были использованы в сериале, и что из них похоже на правду.

— Коллеги, пожалуйста, представьтесь нашим читателям.
— Иван Чижов, заместитель руководителя лаборатории криптографии по научной работе компании «Криптонит».

— Илья Герасимов. Я аспирант кафедры информационной безопасности ВМК МГУ и работаю специалистом-исследователем в лаборатории криптографии «Криптонита».

— Интересно! Главный герой сериала — тоже аспирант.

— И тоже математик, но на этом наше сходство заканчивается [смеётся]. Скажем так, область научных интересов у него другая. Я занимаюсь криптографией на эллиптических кривых, а главный герой сериала ищет закономерности в числовых рядах.

— В этом есть какой-то смысл?

— Да. Этим занимается теория чисел. Математика отражает законы природы и выявляет закономерности. Например, у главного героя на стене висит вырезка из газеты с фотографией раковины моллюска и заголовком «Primes of the Past».

— И что это значит?

— Дословно: «простые числа прошлого», или даже «древности». Раковина моллюска Nautilus имеет структуру, которая описывается спиралью Фибоначчи. Однако отсылка к простым числам здесь не совсем верная. Это геометрический пример другой числовой последовательности, в которой каждый следующий член равен сумме двух предыдущих.

— Какие ещё наглядные примеры есть в сериале?

— Пожалуй, самый любопытный — узор из спиралей. Он есть в заставке, а потом встречается в виде рисунка на доске у главного героя. Это схема расположения семян подсолнечника и отсылка к одной из последних работ Алана Тьюринга по математическим основам морфогенеза растений. Семена расположены по спиралям, которые снова дают последовательность Фибоначчи. Подробнее об этом расскажет Иван Чижов.

— [Иван] Семена располагаются на спиралях, завернутых вправо и влево. Если подсчитать число спиралей, которые закручиваются влево и вправо, а потом поделить одно число на другое, то получится 1,617647... Это «золотое сечение». Очень известное отношение в природе и искусстве. Здесь «золотое сечение» обеспечивает наиболее равномерное распределение семян в корзинке за счёт лучшего его приближения рациональными числами и максимизации числа спиралей небольшого ранга, вдоль которых упорядочены семена.

— Во время лекции мы видим доску, исписанную формулами. Они в фильме для антуража, или это что-то осмысленное?

— Это теорема о модулярности, которая использовалась для доказательства Великой теоремы Ферма. То есть, вполне осмысленная запись, которая действительно могла иметь отношение к лекции.

— В кабинете профессора стоит доска поменьше, а на ней совсем непонятная запись.

— Это определение нормы, математического механизма, обобщающего такие понятия, как длина и модуль на произвольные векторные пространства. Оно тоже вполне корректное и уместное по сюжету. Однако в нём не хватает пункта про однородность нормы: норма вектора, умноженного на число, равна норме самого вектора, умноженного на модуль числа.

— Что вы скажете о сцене со скатертью, на которой главный герой что-то увлечённо пишет?

— Нам специально показывают лишь кусочки записи, оставляя другие вне зоны резкости. Скорее всего, там подразумевалось доказательство теоремы Вильсона, так как расписывается критерий простоты через факториал (n-1)!.

— Вы заметили ещё какие-то нестыковки?

— Я отношусь к сериалу как к художественному произведению и не стремлюсь обнаружить несоответствия, но кое-что всё-таки бросается в глаза. Например, следующая сцена, в которой профессор переписывает со скатерти в тетрадь. Первое сравнение там и есть теорема Вильсона, а второе является тавтологией: натуральное число всегда делится на само себя без остатка. Также не к месту упоминание простых чисел близнецов: доказательство теоремы Вильсона является строгим и не требует гипотезы о числах близнецах.

— В чём особенность простых чисел и какова их роль в криптографии?

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

— Могут ли существовать какие-то скрытые закономерности у простых чисел?

— Да, могут. Их поиск лежит в области теории чисел. Например, согласно гипотезе Римана можно уточнить строение функции распределения простых чисел. Однако эта гипотеза ещё не доказана.

— По словам сценаристов обнаружение неизвестной закономерности в простых числах «положит конец криптографии» и «откроет доступ ко всем компьютерам мира». Неужели так и есть?

— Нет, конечно. Это гипербола для драматизма. Если мы научимся эффективно вычислять простые числа, мы сможем понизить стойкость определённых задач, лежащих в основе конкретных алгоритмов шифрования (например, RSA). Однако существуют принципиально иные алгоритмы, которые базируются на доказуемой сложности математических задач других классов. Например, наша лаборатория занимается криптографическим анализом и построением постквантовых алгоритмов шифрования и электронной подписи. Их стойкость не пострадает при открытии гипотетически возможных закономерностей в простых числах.

— Илья, что вы думаете о сериале Prime Target в целом?

— Думаю, в нём хотели показать доказанные теоремы из теории чисел и сделать предположение, что задача факторизации имеет эффективное решение. В этом есть здравый смысл. Решение задачи факторизации действительно позволяет нарушить стойкость некоторых криптографических механизмов. Самым ярким примером является RSA. Соответственно если будет построен эффективный алгоритм факторизации, то всё, что было зашифровано с помощью RSA, можно будет дешифровать (провести атаку вида «сохранить сейчас, дешифровать потом»). Однако это не запрещает использовать другие криптографические механизмы, не опирающиеся на задачу факторизации.

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

— Коллеги, насколько точно в сериале используют формулы и другие математические атрибуты?

— [Илья] С одной стороны, в нём пытаются изобразить некоторые вещи реалистично. Видно, что их консультировал математик. С другой стороны, буквально в следующей сцене могут показать что-то общеизвестное и не оптимизирующее поставленную перед героями задачу просто ради антуража.

— [Иван] Всё так, однако это и не документальный фильм. Если сериал показал вам красоту математики и заинтересовал криптографией, значит, вы не зря его смотрели!

Подробнее о математических отсылках из сериала Prime Target читайте здесь:

[1] Turing A. M. The chemical basis of morphogenesis //Bulletin of mathematical biology. – 1990. – Т. 52. – С. 153-197. https://marconlab.org/papers/turing.pdf

[2] Andrew Wiles, Modular Elliptic Curves and Fermat’s Last Theorem, Annals of Mathematics Second Series, 141 3 (1995) 443-551 https://sites.math.rutgers.edu/~zeilberg/EM22/AW1995.pdf

[3] Виноградов И.М. Основы теории чисел.

[4] Василенко О.Н. Теоретико-числовые алгоритмы в криптографии.

Prime Target — разбираем сериал «Опасные числа» вместе с криптографами