Publication: АЛГОРИТМ ПОЛУЧЕНИЯ ИНВАРИАНТОВ
| creativeworkseries.issn | 2074-7128 (Print) | |
| dc.contributor.author | Зачёсов, Ю. Л. | |
| dc.contributor.author | Ядыкин, И. М. | |
| dc.contributor.author | Ядыкин, Игорь Михайлович | |
| dc.date.accessioned | 2024-08-19T13:24:11Z | |
| dc.date.available | 2024-08-19T13:24:11Z | |
| dc.date.issued | 2024 | |
| dc.description.abstract | Для защиты информации часто используются две криптографических парадигмы: хэш-функции и алгоритмы, стойкость которых основана на сложности задачи факторизации. При этом хэш-функции обеспечивают стойкость разовых ключей, а алгоритмы, требующие для своего дешифрования решения задачи факторизации, долговременные ключи. Лучшие алгоритмы, решающие задачу факторизации, это субэкспоненциальные алгоритмы, которые для своего выполнения требуют много ресурсов. С 1994 г. часто обсуждается квантовый алгоритм Питера Шора, который также требует для решения большие ресурсы из-за сложностей связанных с новой техникой. Известно, что наиболее стойкий модуль факторизации состоит из двух множителей 𝑁 = 𝑝𝑞. Поэтому актуален любой подход, позволяющий снизить объём ресурсов для решения задач такого рода. В статье описан и, по возможности, строго доказан алгоритм получения инвариантных систем многочленов, взаимно-однозначно соответствующих элементам приведённой системы вычетов (ПСВ). Алгебраические структуры, получаемые на выходе алгоритма, в случае удачного решения с их помощью задачи выбора, приводят к полиномиальному методу факторизации. Алгоритм развивает некоторые идеи, связанные с решением задачи «короткой экспоненты», Д. Копперсмита и других авторов. Излагаемый материал относится к первой подзадаче динамической системы (ДС), которая состоит в том, что исходная задача включается в семейство подзадач разного размера, и они решаются одна за другой в правильном порядке. Для получения систем инвариантных уравнений применяется аппарат полиномиальных сравнений и LLL-алгоритм. Доказывается, что с помощью алгоритма всегда можно получать необходимое число многочленов. Предполагается, что алгоритм будет выполняться несколько раз с различными небольшими простыми числами 𝑅, в качестве управляющих входных параметров. Выполнение алгоритма позволит подготовить возмущающие входные данные для подзадачи выбора, описание которой выходит за рамки статьи. Подзадача выбора наведёт соответствие между элементом множества множеств многочленов и элементом ПСВ, который фактически является остатком 𝑠 от деления простого числа на управляющий параметр 𝑅 в формуле замены переменных 𝑝 = 2𝑅(𝑥 + 𝑦) + 𝑠. Без наличия инвариантных многочленов взаимно-однозначно связанных с ПСВ такая подзадача была бы в принципе невозможна. Набрав достаточное количество пар {𝑅, 𝑠}, применив аппарат китайской теоремы об остатках, найдём множители числа, состоящего из двух множителей. В статье предлагается описание первого этапа ДС, который заменит алгоритм факторизации, зависящий от разрядности составного числа, на новый алгоритм, который будет иметь другие входные данные, меньшей, чем составное число разрядности. | |
| dc.identifier.citation | ЗАЧЁСОВ, Юрий Л.; ЯДЫКИН, Игорь М. АЛГОРИТМ ПОЛУЧЕНИЯ ИНВАРИАНТОВ. Безопасность информационных технологий, [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 | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/14325 | |
| dc.publisher | НИЯУ МИФИ | |
| dc.title | АЛГОРИТМ ПОЛУЧЕНИЯ ИНВАРИАНТОВ | |
| dc.title.alternative | НАУЧНЫЕ СТАТЬИ | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | b153a04d-e26d-474b-a94f-08f530d024ed | |
| relation.isAuthorOfPublication.latestForDiscovery | b153a04d-e26d-474b-a94f-08f530d024ed | |
| relation.isJournalIssueOfPublication | ebb6a468-d413-41c6-9f27-91e67a195035 | |
| relation.isJournalIssueOfPublication.latestForDiscovery | ebb6a468-d413-41c6-9f27-91e67a195035 | |
| relation.isJournalOfPublication | 3b9ae913-eaeb-4d29-a767-7f6ca8a0e066 | |
| relation.isOrgUnitOfPublication | 010157d0-1f75-46b2-ab5b-712e3424b4f5 | |
| relation.isOrgUnitOfPublication.latestForDiscovery | 010157d0-1f75-46b2-ab5b-712e3424b4f5 |