Специалисты лаборатории криптографии компании «Криптонит» разработали алгоритм, позволяющий оценивать устойчивость постквантовых криптосистем, построенных на основе кодов, исправляющих ошибки. Метод основан на поиске квадратичных форм в структуре кода и дает возможность выявлять потенциальные уязвимости на этапе проектирования, до начала дорогостоящих практических испытаний.
Любой криптографический механизм требует понимания того, сколько вычислительных операций потребуется злоумышленнику для его взлома. С приближением эры квантовых компьютеров эта задача становится критичной, поэтому активно разрабатываются постквантовые схемы, устойчивые к новым угрозам. Значительная часть таких алгоритмов строится на теории кодов, исправляющих ошибки (например, алгоритм Мак-Элиса). От их надежности зависит безопасность банковских переводов, цифровых подписей и других конфиденциальных данных. В случае появления мощного квантового компьютера злоумышленник сможет подделывать подписи и перехватывать транзакции, поэтому оценка стойкости ведётся уже на этапе разработки.
Предложенный алгоритм основан на поиске скрытых закономерностей внутри линейных кодов. Автор разработки — заместитель руководителя лаборатории криптографии по научной работе Иван Чижов — сосредоточился на анализе квадратичных форм (уравнений второй степени), которые обращаются в ноль на столбцах порождающей матрицы кода. Особую опасность представляют составные квадратичные формы, распадающиеся в произведение двух линейных уравнений. Если атакующему удается найти такие формы, он получает рычаг для потенциального взлома. Чижов не только создал алгоритм поиска этих «слабых мест», но и математически описал условия их возникновения.
Отмечается, что для стандартизированных параметров вычислительная сложность такой атаки остается астрономически высокой, и о реальном взломе существующих систем речи не идет. Однако сам факт существования метода заставляет пересмотреть требования к защите и закладывать дополнительный запас прочности. Как отмечает Иван Чижов, «сам факт существования метода заставляет пересматривать требования к защите, чтобы обеспечить запас прочности».
Ценность работы — не в обнаружении уязвимостей как таковых, а в возможности их предотвращения. Метод позволяет сократить затраты на стандартизацию семейства постквантовых алгоритмов за счет раннего математического выявления слабых мест. Разработчики смогут отсеивать заведомо слабые варианты кодов и точнее подбирать параметры шифрования еще до начала дорогостоящего практического анализа.