Разработка новых кодов в ранговой метрике и криптосистем с открытым ключом

• Автор: Кшевецкий, Александр Сергеевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 128 с.

Оглавление
Введение

1 Ранговые коды

1.1 Стандартные известные конструкции ранговых кодов

1.1.1 Введение.

1.1.2 Конструкция

1.1.3 Алгоритмы кодирования и декодирования .

1.1.4 Приводимые ранговые коды.

1.1.5 Симметричные ранговые п, 1,пкоды

1.2 Разработка ранговых кодов новой конструкции

1.2.1 Введение.

1.2.2 Конструкция
1.2.3 Взаимосвязь с обычными ранговыми кодами .
1.2.4 Алгоритмы кодирования и декодирования .
1.3 Построение декодирования но информационным совокупностям
1.3.1 Введение.
1.3.2 Информационные совокупности для матричных кодов
1.3.3 Декодирование для ранговых кодов.
1.3.4 Приложение к симметричным ранговым кодам
и результаты моделирования
1.3.5 Результаты моделирования стираний линиями
1.3.6 Оценка числа оставшихся элементов после стирания линиями.
1.3.7 Максимальное число стертых линий, позволяющих декодирование
1.3.8 Выводы.
2 Криптосистемы с открытым ключом на ранговых кодах
2.1 Введение
2.2 Оценка стойкости криптосистемы ГПТ.
2.2.1 Описание криптосистемы ГПТ со строковым и
столбцевым скремблерами и шумовой матрицей
2.2.2 Анализ представлений открытого ключа .
2.2.3 Построение атаки.
2.2.4 Выбор стойких параметров.
2.3 Разработка криптосистемы с ошибками высокого веса
2.3.1 Криптосистема
2.3.2 Криптоанализ.
2.3.3 Пример.
2.4 Выводы
3 Криптосистемы в мнимом квадратичном поле
3.1 Введение
3.2 Математические основы.
3.3 Известные криптосистемы
3.3.1 Аналоги схем ДиффиХеллмана, и Эль
Гамаля.
3.3.2 IX с квадратичным временем расшифрования
3.4 Реализация и анализ криптосистемы IX
3.4.1 Описание реализации криптосистемы
3.4.2 Достоинства и недостатки
3.5 Новая модификация криптосистемы IX
3.5.1 Оптимизация шифрования
3.5.2 Генерирование стойких ключей.ИЗ
3.5.3 Программная реализация
3.5.4 Замечания по цифровой подписи.
3.6 Выводы.
Заключение
Литература


В году была опубликована криптосистема с открытым ключом, основанная на ранговых кодах (Габидулин, Парамонов, Третьяков, , []). Она получила название ГПТ по фамилиям авторов в русскоязычной литературе и вРТ в англоязычной. По сравнению с другими криптосистемами, основанными на линейных кодах, ее преимуществом является маленькая длина открытого ключа и, как следствие, высокая скорость шифрования/расшифрования из-за быстрого алгоритма декодирования. К сожалению, для исходных заявленных параметров криптосистема ГПТ была взломана Гибсоном [,]. Одновременно, Гибсон показал, как выбирать параметры криптосистемы. В дальнейшем были предложены модификации, использующие столбцевой и строковый скремблеры [] и приводимые ранговые коды [6]. В г. Овербек предложил расширенную атаку Гибсона в [. ГПТ. В практических приложениях число выполняемых шифрований данных существенно меньше числа выполняемых расшифрований. Интерес представляют криптосистемы, имеющие быстрое расшифрование. RSA, Эль-Гамаля с кубическим временем расшифрования по битовой длине параметров характеризуется квадратичным временем расшифрования. Криптосистема построена в мнимом квадратичном поле. Актуальность темы исследования. Расширение классов кодов и создание новых кодов является важной задачей теорией кодирования. Во-первых, новые коды могут обладать лучшей корректирующей способностью. Во-вторых, новые коды могут быть более эффективными в частных применениях. С г. Важной задачей теории ранговых кодов является расширение класса ранговых кодов, исследование их свойств и построение новых алгоритмов декодирования. При наличии в канале сильных шумов становятся актуальными методы декодирования за пределами корректирующей способности кода. Важной задачей является построение единых методов совместных помехоустойчивого кодирования и защиты от несанкционированного доступа. Проблема является особенно актуальной для мобильных устройств связи, в которых уменьшение числа вычислительных модулей означает большее энергосбережение. Актуальной задачей является построение и анализ криптосистем с открытым ключом, обладающих высокой скоросгью шифрования/расшифрования с тем, чтобы использовать криптосистемы с открытым ключом для шифрования большого объема данных. Особенно важно обеспечить высокую скорость расшифрования, так как данные шифруются реже, чем расшифруются. В соответствии с поставленной целью были определены следующие задачи и вопросы. Расширение класса кодов в ранговой метрике и построение новых алгоритмов декодирования. Проведение криптоанализа криптосистем с открытым ключом, основанных на ранговых кодах, и построение криптосистем с улучшенными характеристиками. Криптоанализ и анализ эффективности криптосистем с открытым ключом, построенных в мнимом квадратичном поле, имеющих быстрое расшифрование. Методами исследования для решения поставленных задач являются методы дискретной математики, алгебры, теории информации, теории вероятностей, линейной алгебры, комбинаторики. Научная новизна результатов, полученных в диссертации, заключается в том, что в ней впервые предложено следующее. Для построения ранговых кодов в качестве порождающей матрицы выбрана (к х п) матрица Фробениуса над конечным полем вида ||д? V) = 1. Обычная матрица Фробениуса определяется как ||д? Го. Г-г Использование матрицы нового вида как порождающей матрицы линейного рангового (п, ку с1)~кода позволило обобщить и расширить единственную известную конструкцию ранговых кодов г. GF(2Л), имеют равномерное распределение элементов над полем 2). На основе гипотезы построен метод исправления ошибок стирания веса п для линейных ранговых (гг, 1,п)-кодов алгоритмом декодирования по информационным совокупностям. Проведенное моделирование подтвердило гипотезу и показало эффективность алгоритма декодирования. Показана эквивалентность разных вариантов криптосистемы ГПТ на основе ранговых кодов одной общей форме открытого ключа. Проведенный криптоанализ общей формы криптосистемы, а не исходных вариантов, позволил найти условия существования и зависимость полиномиальных и экспоненциальных атак относительно параметров криптосистемы.