|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Применение реберного локального дополнения в структурном анализе криптосистемы Мак-Элисадипломная работа (Бакалавр)
- Научный руководитель: Чижов Иван Владимирович
- Автор: Соколова Анастасия Александровна
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2016
- Аннотация: На данный момент активное развитие теории чисел повлекло за собой снижение стойкости криптосистемы RSA. Вследствие этого возникла необходимость разработки альтернативных криптосистем с открытым ключом. Именно поэтому данное направление исследований сейчас является крайне перспективным и многообещающим. \par\bigskip Одним из возможных и актуальных вариантов решения проблемы являются кодовые криптосистемы - криптосистемы, основанные на задачах из теории кодов, исправляющих ошибки. В их основе лежит идея использования быстро декодируемых кодов, исправляющих ошибки, в качестве основного элемента шифрующего преобразования. В настоящее время наиболее известны криптосистема Мак–Элиса и криптосистема Нидеррайтера. \par\bigskip Основная идея построения криптосистемы Мак-Элиса состоит в том, что некоторый линейный код, имеющий эффективные алгоритмы декодирования, маскируруется под код, не обладающий видимой алгебраической и комбинаторной структурой. Такие коды принято называть кодами общего положения. %Стойкость данной системы основывается на NP-трудной задаче в теории кодирования. Предполагается, что декодирование кода общего положения является трудной задачей, так как не зная структуры кода, невозможно построить эффективный алгоритм его декодирования. \par\bigskip Алгоритмы эффективного декодирования кодов общего положения на данный момент интенсивно исследуются. Так, например, при наиболее эффективной атаке для восстановления секретного сообщения, зашифрованного оригинальной криптосистемой Мак-Элиса на основе кодов Гоппы с длиной 1024, исправляющего не менее 524 ошибок, потребуется $2^{64,2}$ операций. \par\bigskip Отличительным свойством кодовых криптосистем является то, что одному и тому же открытому ключу могут соответствовать несколько секретных ключей. Вследствие этого секретные ключи могут быть разбиты на классы эквивалентности. Возможность подобрать эквивалентный ключ напрямую влияет на стойкость данного метода шифрования, так как ключ для расшифрования не уникален. \par\bigskip Этот вопрос является основным объектом изучения в данной работе. В работе \"{O}sterg\r{a}rd \cite{second} показывается, что с помощью простых преобразований двоичный линейный код можно представить в виде графа, а так же продемонстрировал алгоритм определения эквивалентности кодов. L.E. Danielsen и M.G. Parker в работе \cite{first} вводят альтернативное представление линейного двоичного кода в виде двудольного графа; таким же образом будет реализовано преставление и в данной дипломной работе. \par\bigskip Вводя над графами операции LC (local complementation, локальное дополнение) и ELC (edge local complemetation, реберное локальное дополнение), авторы доказывают, что ELC над таким двудольным графом позволяет рассматривать различные эквивалентные коды и что орбита двудольного графа под ELC является полным классом эквивалентности для кода, отвечающего данному графу. Кроме того, демонстрируется, как ELC на двудольном графе порождает все информационные наборы исходного кода. Помимо этого показано, что минимальное расстояние между кодами связано с минимальной степенью вершины для соответствующей ELC орбиты соответствующего двудольного графа. \par\bigskip Графы, не являющиеся двудольными, не рассматриваются, поскольку на данный момент не имеют каких-либо применений в классической теории кодирования. Метод представления и обработки графов из \cite{first} позволяет по-новому представить классы эквивалентности двоичных кодов и классифицировать все ELC орбиты кодов различной длины. \par\bigskip В данной дипломной работе на языке C были реализованы алгоритмы для нахождения классов эквивалентности циклических кодов с помощью графов и операции ELC, а так же определение эквивалентности кода данному циклическому. \newpage
- Добавил в систему: Чижов Иван Владимирович