Это база: Зачем нужна математика в повседневной жизни

Распознавать уязвимости – это, конечно, замечательно, но главный вопрос в том, что следует делать для защиты. Решение этой задачи требует совершенно новых криптографических методов. Общая идея их та же, что всегда: метод шифрования должен основываться на трудных математических задачах с возможностью какого-нибудь простого обхода. Но теперь «трудный» означает «трудный для квантового компьютера». В настоящий момент обнаружено четыре основных класса задач такого рода:

• Случайные линейные шифры с коррекцией ошибок.

• Решение систем нелинейных уравнений над большими конечными полями.

• Нахождение коротких векторов в многомерных решетках.

• Нахождение маршрутов между случайными вершинами псевдослучайного графа.

Рассмотрим кратко четвертый из этих вариантов, где задействованы новейшие идеи и очень продвинутая математика.

Для практических целей возьмем граф, который имеет около 10⁷⁵ вершин и соответственно большое число ребер. Шифр зависит от нахождения пути через этот граф между двумя конкретными вершинами. Это одна из разновидностей задачи коммивояжера, имеющая сопоставимую с ней трудность. Чтобы создать в решении этой задачи обходной путь, граф должен иметь скрытую структуру, которая делает решение простым. Центральная идея состоит в использовании так называемых суперсингулярных изогенных графов, или SIG. Они образуются с использованием эллиптических кривых, которые называют суперсингулярными. Вершины такого графа соответствуют всем суперсингулярным эллиптическим кривым над алгебраическим замыканием конечного поля с p элементами. Существует примерно p/12 таких кривых.

Изогения между двумя эллиптическими кривыми – это полиномиальное отображение одной из них на другую, сохраняющее структуру группы Морделла – Вейля. Мы используем изогении для определения ребер графа. Для этого следует взять второе простое число q. Ребра этого графа соответствуют изогениям q-й степени между двумя эллиптическими кривыми, соответствующими концам данного ребра. Из каждой вершины исходит ровно q + 1 ребер. Такие графы называются экспандерами, или расширяющими, это означает, что случайные пути, начинающиеся в любой вершине, быстро расходятся после их начала, по крайней мере на протяжении большого числа шагов.

Граф-экспандер может быть использован для создания функции хеширования – булевой функции, формирующей из n-битных строк m-битные, где m много меньше n. Алиса может использовать хеш-функцию, чтобы убедить Боба, что она знает конкретную n-битную строку, известную также и Бобу, не раскрывая самой строки. Для этого она формирует намного более короткую хеш-функцию этой строки и отправляет ее Бобу. Боб вычисляет хеш-функцию своей строки и сравнивает.

Для того чтобы этот метод надежно работал, необходимо выполнить два условия. Одно из них – это условие потайного входа, известное как стойкость к восстановлению прообраза: с вычислительной точки зрения невозможно обратить хеш-функцию и найти n-битную строку, которая дает данный хеш. В общем случае таких строк существует множество, но дело в том, что на практике невозможно найти ни одной. Второе условие – стойкость функции хеширования к коллизиям. Это означает, что с вычислительной точки зрения невозможно найти две разные n-битные строки с одним и тем же m-битным хешем. Раз так, то даже если Ева – любительница подслушивать (или устройство перехвата сообщений) – сумеет подслушать разговор, то хеш, который Алиса пересылает Бобу, не поможет ей разобраться, что представляла собой первоначальная n-битная строка.

Если у нас имеется два простых числа p и q, удовлетворяющие дополнительным формальным условиям, мы можем воспользоваться этой идеей, построив соответствующий SIG, а затем использовать его свойства экспандера, чтобы определить стойкую как к восстановлению прообраза, так и к коллизиям функцию хеширования. Эту функцию можно использовать для создания высоконадежного шифра. Взлом такого шифра требует вычисления множества изогений между эллиптическими кривыми. Лучший квантовый алгоритм для одного такого расчета выполняется за время p^1/4. Сделайте p и q достаточно большими (математика подсказывает, насколько большими), и вы получите криптосистему, которую не сможет взломать даже квантовый компьютер.

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

Теория чисел, столь любимая Харди, оказалась куда более полезной, чем он мог вообразить. Но некоторые из сегодняшних ее применений наверняка разочаровали бы его. Думается, нам следовало бы извиниться перед ним за это.

6 Числовая плоскость