«Если привычная криптография работает с секретными числами, которые прячут в группах, то криптография на изогениях делает ставку на принципиально иной объект — путь в абстрактном лабиринте. Все участники знают карту этого лабиринта, начальную и конечную точки, но восстановить пройденный маршрут без подсказки считается вычислительно невозможным даже для квантового компьютера.»
Изогения: не число, а путь
В основе подхода лежит эллиптическая кривая — математический объект, привычный для специалистов по ГОСТ 34.10. Изогения, это специальное отображение между двумя такими кривыми, которое сохраняет их базовую алгебраическую структуру. Можно представить это как преобразование одной сложной геометрической фигуры в другую, при котором не рвутся внутренние связи между её точками.
Криптографический потенциал возникает из-за асимметрии. Применить заранее известную изогению к кривой и получить новую — задача относительно простая. Однако, имея на руках только две кривые, вычислить связывающую их изогению считается чрезвычайно сложной вычислительной проблемой. Именно эта односторонность и используется: секретный ключ, это сама изогения (или последовательность шагов), а публичный ключ — итоговая кривая.
Почему суперсингулярные кривые
Для построения устойчивых схем нужна контролируемая среда. Эту роль играет класс суперсингулярных эллиптических кривых. Их ключевое свойство — из любой такой кривой исходит конечное и небольшое число изогений заданной малой степени (например, степени 2 или 3).
Это позволяет рассматривать всё семейство суперсингулярных кривых над заданным полем как конечный граф. Кривые становятся вершинами, а изогении малой степени — рёбрами. Этот граф обладает свойствами экспандера: он сильно перемешан, и от любой вершины до любой другой можно дойти за небольшое число шагов. При этом общее количество вершин огромно и растёт линейно с размером характеристик поля.
Суть криптографической задачи
Задача нахождения изогении формулируется так: даны две суперсингулярные кривые E и E’, которые гарантированно связаны изогенией. Требуется найти эту изогению.
Если в классической ECC (и ГОСТ 34.10) секрет, это скаляр в группе точек, то здесь секрет, это маршут в графе. Все знают карту графа (публичные параметры), стартовую точку E и конечную E’. Противник видит ту же карту и те же две точки. Его задача — среди астрономического числа возможных коротких путей найти именно тот, что использовался для генерации ключа. При корректных параметрах полный перебор всех путей выходит за рамки практической осуществимости.
Источники вычислительной сложности
- Размер пространства. Количество суперсингулярных кривых над полем характеристики p приблизительно равно p/12. Для криптографически значимых значений p (порядка 2^512 или больше) граф содержит невообразимо большое число вершин.
- Экспандерная структура. Высокая степень перемешивания в графе лишает атакующего возможности использовать локальные закономерности для оптимизации поиска. Алгоритм вынужден работать с графом глобально, что резко увеличивает вычислительную нагрузку.
- Устойчивость к квантовым атакам. Для задач факторизации и дискретного логарифма существует алгоритм Шора, дающий экспоненциальное ускорение на квантовом компьютере. Для задачи нахождения изогении подобного универсального и эффективного квантового алгоритма не найдено. Лучшие из известных квантовых атак, как алгоритм Кутюрье, предлагают лишь квадратичное ускорение или применимы к специальным, нерекомендуемым параметрам.
Атаки и выбор безопасных параметров
Общая сложность задачи не отменяет существования атак на слабые реализации. История стандарта SIKE, взломанного классической атакой в 2022 году, — яркий пример.
Основные векторы атак и способы защиты от них:
| Уязвимость | Принцип атаки | Способ парирования |
|---|---|---|
| Использование слишком малых степеней | Атака «встречей посередине» снижает сложность перебора до квадратного корня от размера пространства. | Применение больших простых степеней или сбалансированных произведений достаточно больших простых чисел. |
| Специальная структура эндоморфного кольца | Кривые с дополнительной внутренней симметрией (комплексным умножением) могут упрощать вычисления. | Использование кривых со случайным, «общим» эндоморфным кольцом, что типично для суперсингулярных кривых. |
Практические реалии: производительность и размеры
Переход от математической модели к рабочему протоколу выявляет компромиссы.
- Размер ключей. Публичный ключ, представляющий собой кривую, может занимать от нескольких сотен до нескольких тысяч байт. Это значительно больше, чем 32-байтовые открытые ключи в эллиптической криптографии ГОСТ.
- Скорость операций. Вычисление длинной цепочки изогений малой степени для генерации общего секрета — процесс ресурсоёмкий. Современные оптимизированные реализации всё ещё проигрывают в скорости классическим алгоритмам на порядки.
- Стандартизация после SIKE. Падение SIKE привело к переоценке подходов. Другие схемы, такие как CSIDH (свойство повторного использования ключа) и SQISign (для подписей), проходят углублённый анализ. Их будущее в практике, в том числе отечественной, зависит от результатов этого длительного криптоанализа.
Взгляд с позиций российского регулирования
В текущих документах ФСТЭК и 152-ФЗ криптография на изогениях прямо не упоминается. Регуляторный фокус остаётся на сертифицированных СКЗИ, основанных на проверенных отечественных алгоритмах. Однако для специалиста в области защиты информации понимание этого направления становится элементом стратегической грамотности.
Это связано с несколькими аспектами:
- Диверсификация постквантовых кандидатов. Помимо алгоритмов на решётках и кодах, важно иметь в виду и принципиально иные семейства, такие как изогенные. Их устойчивость основана на другой математической проблеме, что снижает риск одновременного краха всех направлений.
- Экспертиза для будущей оценки. Если вопрос о стандартизации постквантовых алгоритмов в России когда-либо перейдёт в практическую плоскость, потребуются специалисты, способные оценить не только заявленную стойкость, но и тонкости выбора параметров, потенциальные уязвимости и применимость в условиях отечественной ИТ-инфраструктуры.
- Гибридные схемы. Наиболее реалистичный сценарий на ближайшие годы — комбинирование классических ГОСТовых алгоритмов с одним из постквантовых. Понимание того, что изогенные схемы дают на выходе (большие ключи, медленный обмен), необходимо для архитектурного проектирования таких гибридных систем.
Сложность нахождения изогении сегодня, это прочный фундамент для целого семейства кандидатов в постквантовую криптографию. Её устойчивость к известным квантовым атакам выделяет это направление. Однако, как показывает опыт, математическая элегантность требует постоянной инженерной проверки на прочность. Для российского ИБ-сообщества это означает, что начинать накапливать экспертизу в этой сложной области стоит уже сейчас, не дожидаясь, когда регуляторный запорт станет обязательным.