Publication: АЛГОРИТМ ПОЛУЧЕНИЯ ИНВАРИАНТОВ
Дата
2024
Авторы
Journal Title
Journal ISSN
Volume Title
Издатель
НИЯУ МИФИ
Аннотация
Для защиты информации часто используются две криптографических парадигмы: хэш-функции и алгоритмы, стойкость которых основана на сложности задачи факторизации. При
этом хэш-функции обеспечивают стойкость разовых ключей, а алгоритмы, требующие для своего дешифрования решения задачи факторизации, долговременные ключи. Лучшие алгоритмы, решающие задачу факторизации, это субэкспоненциальные алгоритмы, которые для своего выполнения требуют много ресурсов. С 1994 г. часто обсуждается квантовый алгоритм Питера Шора, который также требует для решения большие ресурсы из-за сложностей связанных с новой техникой. Известно, что наиболее стойкий модуль факторизации состоит из двух множителей 𝑁 = 𝑝𝑞. Поэтому актуален любой подход, позволяющий снизить объём ресурсов для решения задач такого рода. В статье описан и, по возможности, строго доказан алгоритм получения инвариантных систем многочленов, взаимно-однозначно соответствующих элементам приведённой системы вычетов (ПСВ). Алгебраические структуры, получаемые на выходе алгоритма, в случае удачного решения с их помощью задачи выбора, приводят к полиномиальному методу факторизации. Алгоритм развивает некоторые идеи, связанные с решением задачи «короткой экспоненты», Д. Копперсмита и других авторов. Излагаемый материал относится к первой подзадаче динамической системы (ДС), которая состоит в том, что исходная задача включается в семейство подзадач разного размера, и они решаются одна за другой в правильном порядке. Для получения систем инвариантных уравнений применяется аппарат полиномиальных сравнений и LLL-алгоритм. Доказывается, что с помощью алгоритма всегда можно получать необходимое число многочленов. Предполагается, что алгоритм будет выполняться несколько раз с различными небольшими простыми числами 𝑅, в качестве управляющих входных параметров. Выполнение алгоритма позволит подготовить возмущающие входные данные для подзадачи выбора, описание которой выходит за рамки статьи. Подзадача
выбора наведёт соответствие между элементом множества множеств многочленов и элементом ПСВ, который фактически является остатком 𝑠 от деления простого числа на управляющий параметр 𝑅 в формуле замены переменных 𝑝 = 2𝑅(𝑥 + 𝑦) + 𝑠. Без наличия инвариантных многочленов взаимно-однозначно связанных с ПСВ такая подзадача была бы в принципе невозможна. Набрав достаточное количество пар {𝑅, 𝑠}, применив аппарат китайской теоремы об остатках, найдём множители числа, состоящего из двух множителей. В статье предлагается описание первого этапа ДС, который заменит алгоритм факторизации, зависящий от разрядности составного числа, на новый алгоритм, который будет иметь другие входные данные, меньшей, чем составное число разрядности.
Описание
Ключевые слова
Цитирование
ЗАЧЁСОВ, Юрий Л.; ЯДЫКИН, Игорь М. АЛГОРИТМ ПОЛУЧЕНИЯ ИНВАРИАНТОВ. Безопасность информационных технологий, [S.l.], т. 31, № 2, с. 65–80, 2024. ISSN 2074-7136. URL: https://bit.spels.ru/index.php/bit/article/view/1634. DOI: http://dx.doi.org/10.26583/bit.2024.2.04