Математики НовГУ выявили, какие свойства делают цифровой шифр устойчивым к взлому
07 января 2026, 10:00 814
Ученые НовГУ комплексно исследуют характеристики псевдослучайных последовательностей, которые имеют необычайно широкий спектр применений. Их используют в системах связи, радиолокации, для имитационного моделирования, решения задач методом Монте-Карло (статистических расчетов путем «проб и ошибок»), в криптографии для надежной и безопасной передачи информации и во многих других областях. Исследование позволит в перспективе создавать более стойкие к взлому алгоритмы шифрования для защиты банковских операций, мессенджеров, спутниковой навигации и других критически важных систем.
Научный руководитель проекта, доктор физико-математических наук, профессор и доцент кафедры прикладной математики и информатики — Владимир Едемский. В исследовании также приняли участие старший преподаватель кафедры Сергей Гарбарь и студент третьего курса Рауль Русаков.
Множество информации в интернете — от переписки в мессенджере до транзакций по банковской карте — шифруется с помощью специальных кодов. Они представляют собой длинные последовательности нулей и единиц, которые выглядят совершенно произвольным набором цифр. На самом деле это не так — подобная информация зашифрована сложными алгоритмами различных типов последовательностей. Они генерируются математическими законами и называются псевдослучайными. Если есть ключ — знание верного алгоритма — такую цепочку цифр легко расшифровать и «прочесть» сообщение.
Для оценки качества псевдослучайных последовательностей, которые генерируются с использованием различных алгоритмов и, строго говоря, не являются случайными, применяются различные их параметры (меры сложности), определяемые областью их использования.
Один из самых простых — сбалансированность: частота появления каждого члена последовательности должна быть примерно одинакова — если, например, единиц 90%, а нулей 10%, то это уже не похоже на случайность. Другой параметр — автокорреляция, которая ищет повторяемость: если последовательность слишком похожа на саму себя при сдвиге, то это тоже не напоминает случайный набор цифр.
Линейная сложность определяет, какую наиболее простую схему подобрать, чтобы воспроизвести последовательность. Такому инструменту, например, подчиняется последовательность цифр: 2, 4, 6, 8 и т. д. Более сложный тест — нелинейная сложность. Это очередность цифр, например, с таким шагом: 1, 4, 9, 16 и т. д. Здесь речь идет уже не о прибавлении одного и того же числа (2 — как в предыдущем примере), а об умножении последующего числа самого на себя (1х1, 2х2, 3х3, 4х4 и т. д.).
Один из самых важных тестов — 2-адическая сложность. Это особый показатель, связанный с современными генераторами чисел и оценивающий устойчивость системы к мощным хакерским атакам. Такой инструмент показывает, насколько сложно представить бесконечную двоичную последовательность в виде особенной дроби — в 2-адической системе счисления. В такой системе числа тем «меньше», чем на большее количество нулей в конце они оканчиваются. Например, число 1000000 очень «маленькое», поэтому порождает простую, легко предсказуемую последовательность. Его 2-адическая сложность низкая. Число 1100101011 — «большое» и порождает хаотичную последовательность, поэтому его 2-адическая сложность высокая.
— Для криптографических приложений важно, чтобы последовательность была непредсказуемой. Для ее оценки применяются различные меры сложности, которые определяются как наименьшая длина соответствующего генератора сдвига, способного синтезировать последовательность. Чем длиннее должен быть гипотетический генератор (регистр сдвига), чтобы повторить последовательность, тем она сложнее и непредсказуемее, а значит, и криптографически надежнее, — рассказал Владимир Едемский.
Часто эти параметры изучали по отдельности, но, чтобы назвать последовательность по-настоящему надежной, — она должна успешно пройти проверку всеми этими инструментами сразу. Так было неясно, например, если последовательность получила высокий балл по 2-адической сложности, то пройдет ли она проверку также сложностью нелинейной. Здесь уместно провести простую аналогию с автомобилем, у которого может быть лучший в мире двигатель, но он не подходит к существующей у этой модели коробке передач.
Исследователи из НовГУ пытались соотнести эти параметры между собой, наладив связь между разрозненными инструментами оценки последовательностей. В том числе, создали комплекс программ, который может не только генерировать множество разных типов псевдослучайных последовательностей, но и проверять их всеми известными методами сразу.
На первом этапе они изучили два класса последовательностей на основе простых чисел — Лежандра и простых чисел-близнецов: математических алгоритмов, которые позволяют генерировать длинные цепочки, внешне похожие на случайные.
Оказалось, что если перемешать их особым образом и скомбинировать (чередованием, циклическими сдвигами), то самый надежный показатель — симметричная 2-адическая сложность (обычная 2-адическая сложность оценивает последовательность «с начала», а симметричная учитывает, что хакер может атаковать ее, начиная с любого места, даже «с конца») достигает максимально возможного значения.
Это означает, что такие последовательности становятся устойчивы к атаке с помощью так называемого алгоритма рациональной аппроксимации — метода, который пытается подобрать к последовательности короткую математическую формулу (дробь). Если такую формулу удалось найти быстро, и она короткая — последовательность ненадежна. Если длинная и сложная — последовательность устойчива к атаке.
Затем ученые рассмотрели так называемые полу-I-последовательности. Это особый класс последовательностей, которые математики создают по определенным правилам, чтобы изучать на них общие законы.
Для таких последовательностей ученые доказали, что их нелинейная сложность и 2-адическая сложность почти равны — они отличаются не более чем на 1. Поэтому при создании последовательностей с высокой 2-адической сложностью можно быть уверенным, что и нелинейная сложность их будет столь же высокой.
Помимо прочих инструментов, математики работали с арифметической автокорреляцией изучаемых последовательностей (в частности, на основе простых чисел, специальных регистров сдвига, полу-I-последовательностей и других). Она оказалась почти не отличима от автокорреляции белого шума — абсолютно случайного сигнала без каких-либо закономерностей. Однако низкая автокорреляция сама по себе не гарантирует криптографическую стойкость, так как можно создать легко предсказуемые последовательности с почти нулевой корреляцией. Это значит, что последовательность успешно прошла один важный тест на «случайность», но для полной уверенности необходимо, чтобы она выдержала проверку и по другим, более строгим критериям сложности. При этом исследователи показали, что для последовательностей, состоящих не из нулей и единиц, а четырех символов (0, 1, 2, 3) массово создать сигналы с идеальной арифметической корреляцией невозможно.
Работа новгородских ученых носит фундаментальный характер и закладывает основу для создания более стойких алгоритмов шифрования в будущем. Исследования были начаты совместно с китайским коллегами во время выполнения проекта, поддержанного РФФИ России и ГФЕН Китая. Сейчас это сотрудничество также продолжается. На данном этапе делать выводы о создании «практически неуязвимых» ключей преждевременно, однако исследование вносит важный вклад в понимание взаимосвязей между различными критериями криптографической стойкости. В долгосрочной перспективе такие разработки критически важны для повышения безопасности цифровых систем — от защиты личной переписки до обеспечения надежности банковских операций и критической инфраструктуры государства.
Финансирование исследований ведётся на средства гранта РНФ.
Эту и другие новости читайте в официальном МАХ-канале Новгородского университета.
