Исследование систем линейных запретов над конечным полем
|
1. Обзор методов алгебраического криптоанализа и теории сложности 6
1.1. Методы алгебраического криптоанализа потоковых шифров 6
1.2. Необходимые определения и утверждения из теории сложности . 14
2. Алгебраические и комбинаторные свойства систем линейных запретов
над конечным полем 21
2.1. Определения и свойства систем линейных запретов 21
2.2. Критерий существования решений систем линейных запретов 26
2.3. Свойства решений систем линейных запретов с нулевыми правыми
частями 32
2.4. Системы линейных запретов с нулевыми правыми частями,
сгенерированные неизвестным фиксированным вектором 35
2.5. Системы линейных запретов с ненулевыми правыми частями,
сгенерированные неизвестным фиксированным вектором 42
2.6. Поиск алгоритма решения систем линейных запретов над конечным
полем 51
3. Исследование сложности задач, связанных с системами линейных
запретов 59
3.1. Основные задачи, связанные с системами линейных запретов 59
3.2. Алгоритмы поиска решения систем линейных запретов 63
3.3. Сложность частных случаев задачи проверки существования решения
систем линейных запретов 68
Заключение 77
Список используемой литературы 79
1.1. Методы алгебраического криптоанализа потоковых шифров 6
1.2. Необходимые определения и утверждения из теории сложности . 14
2. Алгебраические и комбинаторные свойства систем линейных запретов
над конечным полем 21
2.1. Определения и свойства систем линейных запретов 21
2.2. Критерий существования решений систем линейных запретов 26
2.3. Свойства решений систем линейных запретов с нулевыми правыми
частями 32
2.4. Системы линейных запретов с нулевыми правыми частями,
сгенерированные неизвестным фиксированным вектором 35
2.5. Системы линейных запретов с ненулевыми правыми частями,
сгенерированные неизвестным фиксированным вектором 42
2.6. Поиск алгоритма решения систем линейных запретов над конечным
полем 51
3. Исследование сложности задач, связанных с системами линейных
запретов 59
3.1. Основные задачи, связанные с системами линейных запретов 59
3.2. Алгоритмы поиска решения систем линейных запретов 63
3.3. Сложность частных случаев задачи проверки существования решения
систем линейных запретов 68
Заключение 77
Список используемой литературы 79
Актуальность темы. Стандартные модели алгебраического криптоанализа рассматривают зависимость между открытыми текстами, шифротекстами и ключами в виде системы полиномиальных уравнений над конечным полем. Можно рассмотреть альтернативную задачу, в которой известны лишь ограничения на возможные значения некоторых зависимостей с неизвестными параметрами. Исследование такой задачи является целесообразным, поскольку существует много методов, которые предоставляют возможность получить частичную информацию о промежуточных значениях некоторых параметров в процессе шифрования. Эти методы могут указывать на то, что определенные зависимости с неизвестными параметрами не могут принимать некоторый конечный набор значений. Такая информация может быть получена из побочного канала связи или из особенностей реализации криптосистемы. Учитывая это, возникает задача восстановления неизвестного вектора по частичной информации, представленной в форме определенных линейных зависимостей.
Цель и задачи исследования. Целью исследования является развитие и уточнение алгебраических моделей и методов криптоанализа. Для достижения цели необходимо решить следующие задачи исследование:
- сформулировать определение системы линейных запретов и задачи ее решения; исследовать алгебраические и комбинаторные свойства систем линейных запретов;
- рассмотреть системы линейных запретов с гарантированно однозначным решением и исследовать вопросы восстановления решения таких систем;
- предложить алгоритмы решения частных случаев систем линейных запретов;
- исследовать сводимость задачи решения системы линейных запретов к известным теоретико-сложным задачам; установить класс сложности данной задачи.
Объектом исследования являются информационные процессы в системах криптографической защиты.
Предметом исследования является система линейных запретов и ее свойства.
Научная новизна. В работе получены следующие результаты:
- определен критерий существования решения системы линейных запретов. Построен полиномиальный вероятностный алгоритм проверки существование решения для некоторых частичных случаев. Доказано свойства решений системы линейных запретов в случае нулевых правых частей;
- сформулирован и доказан ряд утверждений о количестве решений системы линейных запретов в случае, когда система линейных запретов порождена фиксированным неизвестным вектором. Получена нетривиальная оценка точки насыщения в случае ненулевых правых частей системы;
- сформулированы задачи проверки существования и поиска решения системы линейных запретов. Доказана эквивалентность по Тьюрингом этих задачу. Построен вероятностный алгоритм поиска решения системы линейных запретов в некоторых частичных случаях. Построен вероятностный эвристический алгоритм поиска нескольких решений системы линейных запретов в некоторых частичных случаях. Сформулирован ряд смежных задач и доказана принадлежность этих задач соответствующим классам сложности.
Практическое значение. Результаты данной работы могут быть использованы как самостоятельным, так и вспомогательным инструментом для алгебраического криптоанализа потоковых шифров и криптосистем на линейных кодах.
Цель и задачи исследования. Целью исследования является развитие и уточнение алгебраических моделей и методов криптоанализа. Для достижения цели необходимо решить следующие задачи исследование:
- сформулировать определение системы линейных запретов и задачи ее решения; исследовать алгебраические и комбинаторные свойства систем линейных запретов;
- рассмотреть системы линейных запретов с гарантированно однозначным решением и исследовать вопросы восстановления решения таких систем;
- предложить алгоритмы решения частных случаев систем линейных запретов;
- исследовать сводимость задачи решения системы линейных запретов к известным теоретико-сложным задачам; установить класс сложности данной задачи.
Объектом исследования являются информационные процессы в системах криптографической защиты.
Предметом исследования является система линейных запретов и ее свойства.
Научная новизна. В работе получены следующие результаты:
- определен критерий существования решения системы линейных запретов. Построен полиномиальный вероятностный алгоритм проверки существование решения для некоторых частичных случаев. Доказано свойства решений системы линейных запретов в случае нулевых правых частей;
- сформулирован и доказан ряд утверждений о количестве решений системы линейных запретов в случае, когда система линейных запретов порождена фиксированным неизвестным вектором. Получена нетривиальная оценка точки насыщения в случае ненулевых правых частей системы;
- сформулированы задачи проверки существования и поиска решения системы линейных запретов. Доказана эквивалентность по Тьюрингом этих задачу. Построен вероятностный алгоритм поиска решения системы линейных запретов в некоторых частичных случаях. Построен вероятностный эвристический алгоритм поиска нескольких решений системы линейных запретов в некоторых частичных случаях. Сформулирован ряд смежных задач и доказана принадлежность этих задач соответствующим классам сложности.
Практическое значение. Результаты данной работы могут быть использованы как самостоятельным, так и вспомогательным инструментом для алгебраического криптоанализа потоковых шифров и криптосистем на линейных кодах.
В ходе исследования выполнены следующие задачи:
- формализована задача восстановления неизвестного вектора по частичной информации, представленной в форме линейных зависимостей, с помощью введения нотации системы линейных запретов над конечным двоичным полем. Сформулирован и доказан критерий существования решения системы линейных запретов. На основе этого критерия построен полиномиальный вероятностный алгоритм проверки существования решения для случая т < 2к-1. Проведен анализ этого алгоритма и вычислена вероятность ошибки, которая является односторонней и составляет 2~d-, где d — фиксированное число, которое определяет порядок точности алгоритма. Этот алгоритм был имплементирован и проверен на определенных наборах входных параметров;
- рассмотрен случай, когда систему линейных запретов сгенерирована неизвестным фиксированным вектором, и исследована принципиальная возможность восстановления неизвестного вектора в таком случае. Это исследование позволило построить систему линейных запретов, которая содержит небольшое количество линейных запретов (в сравнении с количеством всех возможных линейных запретов в системе), но имеет единственное решение. Этот результат дал возможность получить нетривиальную оценку на точку насыщения в случае ненулевых правых частей;
- сформулированы задачи проверки существования решения и поиска решений для системы линейных запретов. Доказана эквивалентность этих задач по Тьюрингу, что дало возможность построить полиномиальный вероятностный алгоритм поиска хотя бы одного решения системы линейных запретов в случае т < 2к-1 . Алгоритм был имплементирован и апробирован на определенных наборах входных данных. На основе этого алгоритма был построен другой эвристический алгоритм для поиска нескольких решений системы линейных запретов. В ходе апробации было обнаружено, что лучшие результаты этот алгоритм показывает в случае, когда мощность множества решения системы линейных запретов составляет примерно 1 — 10 векторов;
- установлен класс сложности задачи проверки существования решения системы линейных запретов. Также для этой задачи сформулированы определенный набор задач, которые являются частичными случаями исходной задачи. Для всех частичных случаев установлена их принадлежность соответствующим классам сложности. Эти результаты позволили выдвинуть гипотезы по уточнению сложности задачи проверки существования решения системы линейных запретов.
В дальнейших исследованиях планируется выполнить поиск полиномиального вероятностного алгоритма проверки существования решения системы линейных запретов над конечным полем в общем случае. Также планируется исследовать возможность уточнения оценки сложности задачи проверки существования решения системы линейных запретов.
- формализована задача восстановления неизвестного вектора по частичной информации, представленной в форме линейных зависимостей, с помощью введения нотации системы линейных запретов над конечным двоичным полем. Сформулирован и доказан критерий существования решения системы линейных запретов. На основе этого критерия построен полиномиальный вероятностный алгоритм проверки существования решения для случая т < 2к-1. Проведен анализ этого алгоритма и вычислена вероятность ошибки, которая является односторонней и составляет 2~d-, где d — фиксированное число, которое определяет порядок точности алгоритма. Этот алгоритм был имплементирован и проверен на определенных наборах входных параметров;
- рассмотрен случай, когда систему линейных запретов сгенерирована неизвестным фиксированным вектором, и исследована принципиальная возможность восстановления неизвестного вектора в таком случае. Это исследование позволило построить систему линейных запретов, которая содержит небольшое количество линейных запретов (в сравнении с количеством всех возможных линейных запретов в системе), но имеет единственное решение. Этот результат дал возможность получить нетривиальную оценку на точку насыщения в случае ненулевых правых частей;
- сформулированы задачи проверки существования решения и поиска решений для системы линейных запретов. Доказана эквивалентность этих задач по Тьюрингу, что дало возможность построить полиномиальный вероятностный алгоритм поиска хотя бы одного решения системы линейных запретов в случае т < 2к-1 . Алгоритм был имплементирован и апробирован на определенных наборах входных данных. На основе этого алгоритма был построен другой эвристический алгоритм для поиска нескольких решений системы линейных запретов. В ходе апробации было обнаружено, что лучшие результаты этот алгоритм показывает в случае, когда мощность множества решения системы линейных запретов составляет примерно 1 — 10 векторов;
- установлен класс сложности задачи проверки существования решения системы линейных запретов. Также для этой задачи сформулированы определенный набор задач, которые являются частичными случаями исходной задачи. Для всех частичных случаев установлена их принадлежность соответствующим классам сложности. Эти результаты позволили выдвинуть гипотезы по уточнению сложности задачи проверки существования решения системы линейных запретов.
В дальнейших исследованиях планируется выполнить поиск полиномиального вероятностного алгоритма проверки существования решения системы линейных запретов над конечным полем в общем случае. Также планируется исследовать возможность уточнения оценки сложности задачи проверки существования решения системы линейных запретов.
Содержание магистерской диссертации - Исследование систем линейных запретов над конечным полем
Выдержки из магистерской диссертации - Исследование систем линейных запретов над конечным полем
Подобные работы
- СЕМАНТИЧЕСКИЙ АНАЛИЗ ЛЕКСИКИ В СИСТЕМЕ
РАЗНОСТРУКТУРНЫХ ЯЗЫКОВ
(на материале семантического поля « − انسانЧеловек»)
Диссертация , языкознание. Язык работы: Русский. Цена: 5790 р. Год сдачи: 2016 - Империя: теоретико-правовая характеристика (Алтайский Государственный Университет)
Дипломные работы, ВКР, теория государства и права. Язык работы: Русский. Цена: 2000 р. Год сдачи: 2020