A METHOD FOR STRENGTHENING SIGNATURE RANDOMIZATION IN SIGNATURE ALGORITHMS ON NON-COMMUTATIVE ALGEBRAS
Voprosy kiberbezopasnosti · 2024
Цель работы: устранение уязвимости известных алгебраических алгоритмов ЭЦП с многократным вхождением подписи в проверочное уравнение к потенциальным атакам с использованием множества известных подписей.Метод исследования: известные результаты по изучению строения четырехмерных конечных некоммутативных ассоциативных алгебр применяются для генерации параметров алгоритма ЭЦП.Устранение указанной в цели работы уязвимости реализуется путем усиления рандомизации подписи.Последняя обеспечивается за счет вычисления ЭЦП в зависимости от двух уникальных четырехмерных векторов, принадлежащим двум различным скрытым коммутативным группам четырехмерной некоммутативной алгебры, используемой в качестве алгебраического носителя.выполнение формального доказательства обеспечения почти полной рандомизации ЭЦП.Результаты исследования: доказан ряд математических утверждений, лежащих в основе обоснования выбора параметров алгебраических алгоритмов ЭЦП, стойкость которых основана на вычислительной трудности решения больших систем степенных уравнений.Показано, что вычисление подписи в зависимости от двух уникальных векторов, выбираемых из различных коммутативных подалгебр, обеспечивает почти полную рандомизацию подписи, которая устраняет потенциальные атаки с использованием нескольких известных подписей, по отношению к которым являются уязвимыми известные алгебраические алгоритмы ЭЦП с многократным вхождением подписи в проверочное уравнение.На основе предложенного способа усиления рандомизации разработан алгебраический алгоритм ЭЦП, использующий в качестве алгебраического носителя четырехмерные конечные некоммутативные ассоциативные алгебры.В отличии от известных версий алгоритмов ЭЦП со скрытой группой и удвоенным проверочным уравнением используются две скрытые группы.Дана оценка стойкости к прямой атаке и к подделке подписи.Научная и практическая значимость результатов статьи состоит в разработке и апробации способа усиления рандомизации подписи, перспективного для реализации на его основе практичных постквантовых алгоритмов ЭЦП, стойкость которых определяется вычислительной трудностью решения больших систем степенных уравнений.Предложен конкретный алгоритм такого типа, обладающий сравнительно малыми размерами подписи и открытого и секретного ключей.