Пространство ключей криптосистемы Мак-Элиса-Сидельникова

• Автор: Чижов, Иван Владимирович
• Шифр специальности: 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 170 с.

Содержание
Введение.

Обзор литературы.

Краткий обзор результатов диссертации

Глава 1. Сведения из теории кодирования и криптографии

1.1. Основные сведения из теории кодирования

1.2. Основные сведения из криптографии

1.3. Выводы к первой главе

Глава 2. Оценка снизу на число открытых ключей

2.1. Структура множества открытых ключей в случае произвольного числа блоков и оценка числа открытых ключей .

2.2. Выводы ко второй главе

Глава 3. Структура множества открытых ключей в случае
двух блоков.
3.1. Пространство ключей криптосистемы МакЭлиса Сидель
никова с двумя блоками. Первый случай.
3.2. Пространство ключей криптосистемы МакЭлисаСидель
никова с двумя блоками. Второй случай.
3.3. Перестановочная эквивалентность специального вида подпространств кода РидаМаллера
3.4. Пространство ключей криптосистемы МакЭлисаСидельникова с двумя блоками. Второй случай. Продолжение. .
3.5. Пространство ключей криптосистемы МакЭлисаСидельникоиа с двумя блоками. Третий случай
3.6. Выводы к третьей главе
Глава 4. Задачи, связанные со стойкостью криптосистемы
МакЭлисаСидельникова.
4.1. Полиномиальная эквивалентность задач взлома криптосистемы МакЭлиса и криптосистемы МакЭлиса Сидельникова с ограничениями на ключевое пространство
4.2. Определение матрицы по перестановке из ее 7структуры
4.3. Выводы к четвертой главе
Заключение
Список публикаций
Цитированная литература.
Введение
Актуальность


Обычно у кодовых криптосистем R < 1, тогда как у криптосистемы RSA — пожалуй, самой распространённой в настоящее время криптосистемы, — скорость равна 1. С развитием вычислительной техники и с увеличением производительности вычислительных систем низкая скорость передачи кодовых систем может перестать быть существенным недостатком, сдерживающим использование этих криптосистем на практике. Нидеррайтера. Криптосистема Мак-Элиса и криптосистема Нидеррайтера, построенные на основе одних и тех же кодов, например, кодов Гоппы, с точки зрения стойкости являются эквивалентными [б]. В той же работе [5) автор предлагает использовать для построения как новой криптосистемы, так и криптосистемы Мак-Элиса обобщённые коды Рида-Соломона. В году В. М. Сидсльников и С. О. Шестаков показали, что использование обобщенных кодов Рида-Соломона для построения криптосистем Мак-Элиса и Нидеррайтера делает эти криптосистемы нестойкими |7]. При этом атака В. М. Сиделышкова и С. О. Шестакова использует для взлома знание свойств структуры классов эквивалентности секретных ключей. Одним из активно проводимых исследований является изучение атак, связанных с алгоритмами эффективного декодирования кодов общего положения. На сегодняшний день самой эффективной такой атакой является атака, предложенная Шабо и Канто [8] в году. Так, например, для восстановления секретного сообщения, зашифрованного оригинальной криптосистемой Мак-Элиса на основе кодов Гоппы с длиной , исправляющего не менее 4 ошибок, с помощью алгоритма Шабо и Канто потребуется 2м'2 операций. Другое направление исследований — это так называемые структурные атаки, то есть атаки, основанные на использовании алгебраической или комбинаторной структуры кодов, используемых для построения криптосистем. Самыми значительными работами здесь являются — атака Б. М. Сидельникова и С. О. Шестакова [7] на криптосистему Мак-Элиса на основе обобщённых кодов Рида-Соломопа, атака Н. Ссндрие [9| на криптосистему на основе каскадных кодов, атака Л. Рида-Маллера, а также алгоритм разбиения носителя, предложенный Н. Седрис []. С помощью этого алгоритма можно строить атаки на криптосистему, построенную на основе случайных кодов, так как почти всегда случайные коды имеют группу автоморфизмов, состоящую только из тождественной перестановки. Гоипы какие-либо другие коды. Так известны модификации, предложенные Э. М. Габиду-линым [] и []. Однако указанные модификации снизили стойкость криптосистемы, известны эффективные атаки на криптосистемы Габи-дулина и её модификации []. В году Янва и Морено впервые выдвинули идею использовать в кодовых криптосистемах эллиптические кривые []. В году П. Жаборит предложил использовать для построения криптосистемы Мак-Элиса коды БЧХ []. В.М. Сидельников [1] в году рассмотрел возможность использования кодов Рида-Маллера для построения криптосистемы Мак-Элиса. Он провёл криптографический анализ такой криптосистемы. Результаты показали, что криптосистема Мак-Элиса на основе кодов Рида-Маллера не обеспечивает достаточной стойкости. Кроме того в году J1. Миндер в работе [] усилил атаку В. М. Сидельникова, однако она остаётся до сих пор иеполиномиальной. В той же работе [1] рассматривается некоторое усиление криптосистемы Мак-Элиса на основе кодов Рида-Маллера — криптосистема Мак-Элиса-Сидельиикова. Криптосистема Мак-Элиса-Сидельникова строится на основеп-крат-ного использования кодов Рида-Маллера RM(г, га). В диссертации исследуются вопросы, связанные со структурой классов эквивалентности секретных ключей, то есть секретных ключей, порождающих одинаковые открытые ключи, новой криптосистемы. Опишем устройство криптосистемы Мак-Элиса- Сидельникова. Здесь Я1,Я2,. Яи — невырожденные матрицы размера к х к над полем 2), которые выбираются случайно и равновероятно из множества всех двоичных невырожденных матриц размера к х к. Здесь к — размерность кода Рида-Маллера Г1М(г,т). Матрица Г имеет размеры и-пхип и является перестановочной, то есть в каждой её строчке и в каждом столбце стоит ровно одна единица, поэтому можно считать, что Г — это перестановка на множестве из ип элементов. К — стандартная форма порождающей матрицы кода Ш(г,т). НиН2,. НгиГ).