автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Пространство ключей криптосистемы Мак-Элиса-Сидельникова

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

0046040

На правах рукописи

Чижов Иван Владимирович

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

05.13.19 - Методы и системы защиты информации, информационная

безопасность

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 7 ИЮН 7010

Москва - 2010

004604056

Работа выполнена на кафедре математической кибернетики факультета Вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

кандидат физико-математических наук, доцент Карпунин Григорий Анатольевич доктор физико-математических наук, доцент Куракин Владимир Леонидович; кандидат физико-математических наук, доцент Черепнёв Михаил Алексеевич.

Томский государственный университет.

Защита диссертации состоится «16» июня 2010 года в 16 часов 45 минут на заседании диссертационного совета Д 501.002.16 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Российская Федерация, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 14 мая 2010 года.

Научный руководитель: Официальные оппоненты:

Ведущая организация:

Ученый секретарь

диссертационного совета,

доктор физико-математических наук, доцент

Корнев А. А.

Общая характеристика работы

Актуальность работы определяется потребностью в исследовании альтернативных традиционным криптосистем с открытым ключом. Бурное развитие теории чисел за последние 5 лет позволило значительно снизить стойкость RSA — широко распространённой на практике криптосистемы с открытым ключом. Это диктует необходимость в исследовании других криптосистем с открытым ключом с целью поиска альтернатив криптосистеме RSA. Одной из таких альтернатив являются кодовые криптосистемы, то есть криптосистемы, основанные на задачах из теории кодов, исправляющих ошибки. В основе кодовых криптосистем лежит идея использования быстро декодируемых кодов, исправляющих ошибки, в качестве основного элемента шифрующего преобразования. В настоящее время широкую известность получили две кодовые криптосистемы — криптосистема Мак-Элиса и криптосистема Нидеррайтера, оригинальные версии которых используют коды Гоппы и расширенные коды Рида-Соломона, соответственно. В.М. Сидельников и С.О. Шеста-ков показали несостоятельность идеи использования для построения кодовых криптосистем расширенных кодов Рида-Соломона, так как в этом случае такие криптосистемы не будут стойкими.

Кодовые криптосистемы имеют особенность, которая отличает их от многих других криптосистем. В кодовых криптосистемах одному и тому же открытому ключу могут соответствовать несколько секретных ключей, и поэтому секретные ключи могут быть разбиты на классы эквивалентности. При этом вопрос строения этих классов эквивалентности для кодовых криптосистем оказывается важным. Так атака В.М. Сидель-никова и С.О. Шестакова использует строение ключевого пространства кодовой криптосистемы для вскрытия криптосистемы Мак-Элиса на основе обобщённых кодов Рида-Соломона. Следовательно, в некоторых случаях структура пространства ключей кодовой криптосистемы может помочь в её криптоанализе.

Атака В.М. Сидельникова и С.О. Шестакова показала невозможность использовать расширенные коды Рида-Соломона для построения кодовых криптосистем, поэтому в 1994 году В.М. Сидельников предложил использовать для построения кодовых криптосистем коды Рида-Маллера, которые позволяют увеличить как скорость расшифрования криптограммы, так и скорость передачи криптосистемы. Кроме того, В.М. Сидельников предложил усиленный вариант криптосистем

Мак-Элиса, в конструкции которой используется не одна копия кода, а некоторое число и копий кода, число и становится параметром криптосистемы. Такая криптосистема в диссертации получила название криптосистемы Мак-Элиса-Сидельникова. До недавнего времени ключевое пространство усиленного варианта кодовых криптосистем на основе кодов Рида-Маллера оставалось полностью не изученным. Диссертация посвящена исследованию структуры множества ключей криптосистемы Мак-Элиса-Сидельникова и разработке методов использования структуры этого множества в криптоанализе криптосистемы Мак-Элиса-Сидельникова, что, с учётом представленных выше соображений, свидетельствует об её актуальности и практической значимости.

Цель диссертационной работы заключается:

• в получении оценок на число открытых ключей криптосистемы Мак-Элиса-Сидельникова;

• в исследовании структуры множества отрытых ключей криптосистемы Мак-Элиса-Сидельникова;

• в разработке методов, позволяющих использовать сведения о структуре открытых ключей криптосистемы Мак-Элиса-Сидельникова для криптоанализа такого вида криптосистем.

Научная новизна.

• Получена нижняя оценка на мощность множества открытых ключей криптосистемы Мак-Элиса-Сидельникова, которая позволила заключить, что число ключей криптосистемы достаточно велико, чтобы противостоять атаке на криптосистему полным перебором по всему множеству открытых ключей.

• Установлена связь классов эквивалентности секретных ключей со специально введенным множеством перестановок. Это множество перестановок является в некотором смысле обобщением группы автоморфизмов кодов.

• В случае использования произвольного числа копий кода Рида-Маллера описывается ряд классов эквивалентности секретных ключей.

• Задача изучения некоторых классов эквивалентности секретных ключей сведена к изучению перестановочной эквивалентности особого вида подпространств кода Рида-Маллера и описаны все перестановки, которые переводят подпространство особого вида в некоторое другое подпространство кода Рида-Маллера. С использованием описания перестановок были получены описания ряда классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидельникова.

• Доказана полиномиальная эквивалентность некоторых задач, связанных со стойкостью криптосистемы Мак-Элиса—Сидельникова, и задачи взлома оригинальной криптосистемы Мак-Элиса на основе подкодов кода Рида-Маллера, размерность которых на единицу меньше размерности кода, а также была доказана возможность восстановления части секретного ключа криптосистемы Мак-Элиса-Сидельникова, используя знание структуры класса эквивалентности, в который попадает секретный ключ.

Практическая значимость. Работа носит теоретический характер. Вместе с тем, полученные при её выполнении результаты могут найти применение: в синтезе и криптоанализе кодовых криптосистем; при изучении перестановочной эквивалентности подпространств кодов; при изучении свойств кодов, исправляющих ошибки, полученных из других кодов операцией комбинирования; в учебном процессе.

На защиту выносятся следующие основные результаты и положения:

• нижняя оценка мощности множества открытых ключей криптосистемы Мак-Элиса-Сидельникова;

• описание ряда классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидельникова для произвольного числа блоков кода Рида-Маллера;

• описание классов эквивалентности с представителями особого вида в случае криптосистемы с двумя блоками;

• метод восстановления части секретного ключа криптосистемы Мак-Элиса-Сидельникова, использующий знание структуры класса эквивалентности, в который попадает секретный ключ;

• доказательство полиномиальной эквивалентности задачи взлома оригинальной криптосистемы Мак-Элиса, построенной на основе подкодов кода Рида-Маллера, размерность которых на единицу меньше размерности кода, и задачи взлома криптосистемы Мак-Элиса-Сидельникова с ограничениями на ключевое пространство.

Апробация работы

Результаты работы докладывались:

• на семинаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета Вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова;

• на VII общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2009), 2009 год

• на VI общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2008), 2008 года;

• на V общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2007), 2007 год;

• на VII международной конференции «Дискретные модели в теории управляющих систем», 2006 год;

• на VIII Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография — SIBE-CRYPT'09», 2009 год.

Публикации. Основное содержание диссертации опубликовано в 7 работах, список которых приведён в конце автореферата [1]—[7]. Работ, написанных в соавторстве, нет.

Личный вклад автора заключается в проведённом им исследовании пространства ключей криптосистемы Мак-Элиса-Сидельникова, в получении описаний структуры классов эквивалентности секретных ключей криптосистемы, а также в исследовании возможности применения знаний структуры этих классов в криптоанализе криптосистемы Мак-Элиса-Сидельникова.

Структура и объем диссертации Диссертационная работа, общим объёмом 170 страниц, состоит из введения, четырёх глав и заключения. Список литературы включает 34 наименования.

Содержание работы

Во Введении обоснована актуальность диссертационной работы, сформулирована цель и аргументирована научная новизна исследований, показана практическая значимость полученных результатов, представлены выносимые на защиту научные положения.

В первой главе приводятся основные сведения из теории кодов, исправляющих ошибки и вводятся необходимые в дальнейшем изложении термины и определения. Даётся краткое введение в криптографию и криптосистемы с открытым ключом. Приводится описание криптосистемы Мак-Элиса.

Криптосистема Мак-Элиса — одна из старейших криптосистем с открытым ключом. Она была предложена в 1978 Р. Дж. Мак-Эли-сом1. Стойкость рассматриваемой криптосистемы основывается на NP-трудной задаче в теории кодирования. Основная идея её построения состоит в маскировке некоторого линейного кода, имеющего эффективные алгоритмы декодирования, под код, не обладающий видимой алгебраической и комбинаторной структурой. Такие коды принято называть кодами общего положения. Предполагается, что декодирование кода общего положения является трудной задачей2. Не зная структуры кода, невозможно построить эффективный алгоритм декодирования такого кода. Именно эта идея и заложена в конструкции криптосистемы, предложенной Р. Дж. Мак-Элисом.

Криптосистема Мак-Элиса, как и все другие известные кодовые криптосистемы обладают одним важным преимуществом — высокой скоростью зашифрования и расшифрования. Однако, в подобных криптосистемах имеется недостаток — относительно низкая скорость передачи (Л). Обычно у кодовых криптосистем R < 1, тогда как почти у всех криптосистем, используемых на практике, скорость равна 1. С развитием вычислительной техники и с увеличением производительно-

1 McEliece R. J. A public-key cryptosystem based on algebraic coding theory // DSN Prog. Rep., Jet Prop. Lab., California Inst. Technol. 1978. Vol. January. Pp. 114-116.

2 Barg A. Complexity Issues in Coding Theory // Handbook of Coding Theory Volume II / Ed. by V. S. Pleas, W. C, Huffman. Amsterdam: Elsevier, 1998. Pp. 649-755.

сти вычислительных систем низкая скорость передачи кодовых систем может перестать быть существенным недостатком, сдерживающим использование этих криптосистем на практике.

В 1986 году Нидеррайтер 3 предложил модификацию криптосистемы Мак-Элиса, которая получила название криптосистемы Нидеррайте-ра. Криптосистема Мак-Элиса и криптосистема Нидеррайтера, построенные на основе одних и тех же кодов, например, кодов Гоппы, с точки зрения стойкости являются эквивалентными4. В той же работе 3 автор предлагает использовать для построения как новой криптосистемы, так и криптосистемы Мак-Элиса обобщённые коды Рида-Соломона. В 1992 году В.М. Сидельников и С.О. Шестаков показали, что использование обобщённых кодов Рида-Соломона для построения криптосистем Мак-Элиса и Нидеррайтера делает эти криптосистемы нестойким^. При этом атака В.М. Сидельникова и С.О. Шестакова использует для взлома знание свойств структуры классов эквивалентности секретных ключей.

В.М. Сидельников 6 в 1994 году рассмотрел возможность использования кодов Рида-Маллера для построения криптосистемы Мак-Элиса. Он провёл криптографический анализ такой криптосистемы. Результаты показали, что криптосистема Мак-Элиса на основе кодов Рида-Маллера не обеспечивает достаточной стойкости. Кроме того в 2007 году JI. Мин-дер в работе7 усилил атаку В.М. Сидельникова, однако она остаётся до сих пор неполиномиальной. В той же работе 6 рассматривается некоторое усиление криптосистемы Мак-Элиса на основе кодов Рида-Маллера — криптосистема Мак-Элиса-Сидельникова.

В диссертации исследуются вопросы, связанные со структурой классов эквивалентности секретных ключей, то есть секретных ключей, порождающих одинаковые открытые ключи, новой криптосистемы.

В первой главе описывается криптосистема Мак-Элиса-Сидельникова. Эта криптосистема строится на основе u-кратного использования кодов Рида-Маллера RM(r,m). Всюду далее через к = (*?) бу-

3 Niederreiter H. Knapsack-type crytosystems and algebraic coding theory // Prob. Contr. Inform. Theory. 1986. Vol. 15(2). Pp. 157-166.

4 Li Y. X., Deng R. H., Wang X. M. The equivalence of McEliece's and Niederreiter'3 public-key cryptosyBtems // IEEE Transactions on Information Theory. 1994. Vol. 40. Pp. 271-273.

5 Сидельников В. M., Шестаков С. О. О безопасности системы шифрования, построенной на основе обобщенных кодов Рида-Соломона // Дискретная математика. 1992. Т. 4(3). С. 57-63.

8 Сидельников В. М. Открытое шифрование на основе двоичных кодов Рвда-Маллера // Дискретная математика. 1994. Т. 6(2). С. 3-20.

7 Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem // Advances in Cryptology- EUROCRYPT 2007, Lecture Notes in Computer Science. 2007. Vol. 4515. Pp. 347-360.

дет обозначаться размерность кода Рида-Маллера ЯМ (г, т), а через п = 2т — его длина.

Секретным ключом криптосистемы является кортеж

О)

Здесь Н\,Н<1,..., Ни — невырожденные матрицы размера к х к над полем которые выбираются случайно и равновероятно из множе-

ства всех двоичных невырожденных матриц размера к х к. Матрица Г имеет размеры и ■ п х и ■ п и является перестановочной, то есть в каждой её строчке и в каждом столбце стоит ровно одна единица, поэтому можно считать, что Г — это перестановка на множестве из ип элементов.

Открытым ключом криптосистемы Мак-Элиса-Сидельникова явля- ■ ется матрица

С = (.Н1Щ\Н2Щ\... IIНиЯ) ■ Г, (2)

где символом || обозначена конкатенация матриц по столбцам, а Д -стандартная форма порождающей матрицы кода ЯМ(г,т). Под стандартной формой порождающей матрицы понимается (к х п)-матрица вида

здесь П/ — вектор значений булевой функции /(¡/1,... ,ут). Отметим, что в дальнейшем мы не будем делать различий между булевыми функциями и их векторами значений.

Даётся следующее определение эквивалентности секретных ключей в криптосистеме Мак-Элиса-Сидельникова. Два секретных ключа

А =

\вг/

где

(Ни Н2, ■■•, Ни> Г) и (Н\,Н'2,.. •, Н'и, Г')

называются эквивалентными, если соответствующие им открытые ключи совпадают, то есть выполняется соотношение

(НгЩЩЩ ... IlHUR) • Г = (Вддаяи... • Г'. (3)

Введённое отношение является отношением эквивалентности. Тем самым, всё множество секретных ключей разбивается на классы эквивалентности и число классов эквивалентности совпадает с числом открытых ключей. Класс эквивалентности с представителем (Hi,... ,Ни, Г) будем обозначать так: [(Hi,..., Ни, Г)].

Во второй главе изучается ключевое пространство криптосистемы Мак-Элиса-Сидельникова. Устанавливается связь классов эквивалентности секретных ключей со специально введенным множеством перестановок Q.

Рассмотрим множество Q(Hi, Н2, ■ ■ ■, Ни), состоящее из перестановок Г € Зип, для которых существуют невырожденные двоичные матрицы H'lt H'2,..., Н'и такие, что

(НгЩН2Щ ... ||Я„Л)Г = (H[R\\H'2R\\... \\H'UR). (4)

Во второй главе доказано следующее утверждение.

Теорема. 2.1. Существует взаимно однозначное соответствие между классом эквивалентности [(Hi,H2,.-.,Hu,r)] секретных ключей и множеством G(Hi, Н2,.. ■, Ни).

При этом класс эквивалентности [{Н\, H2,..., Ни, Г)] состоит из ключей вида

{Н[, Н'2,..., Н'и, Г"1 ■ Г), (5)

где Г3 принадлежит множеству G{H\, Н2, ■ ■■, Ни) и

(Н,Щ\Н2Щ ... \\HuR)r3 = (H[R\\H'2R\\... \\H'UR). (6)

Тем самым вопрос изучения структуры классов эквивалентности секретных ключей сводится к изучению структуры множества перестановок Q.

Далее во второй главе описывается ряд классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидельникова в случае использования произвольного числа блоков кода Рида-Маллера.

Для этого с помощью автоморфизмов кода Рида-Маллера вводится понятие группы расширенных автоморфизмов. Напомним, что

автоморфизмом некоторого кода С называется множество перестановок координат кодовых слов, которые переводят код С в себя. Известно, что совокупность всех автоморфизмов кода относительно операции умножения перестановок является группой. Рассмотрим некоторую перестановку а £ 5„. Построим, используя её, г «длинных» перестановок сг[г] 6 5ип следующим образом. Положим сг[г](у) = для любого ] £ I — {(г - 1) • п + 1,(г - 1) • п + 2,...,г ■ п}, а СТЙ0) = (г ~~ 1)п + ~ ~ 1)п)> Для всех 3 6 Другими словами, перестановка <т[г] в г-том блоке действует как перестановка а, а во всех остальных блоках — как единичная перестановка. Тогда группой расширенных автоморфизмов Аи,(НМ(г, т)) кода Рида-Маллера ЯМ(г, т) назовём множество всех возможных произведений описанных перестановок а[г\ для всех возможных всех возможных перестановок а из группы автоморфизмов кода ЯМ (г, т).

В диссертации доказана следующая теорема.

Теорема. 2.2. Пусть невырожденные матрицы £>2) •■•> -Ои задают автоморфизмы с\) ¿Г2>..., сги кода В,М(г, т) соответственно, то есть для 1 ^ г ^ и выполнены равенства £>¿21 = 11аОбозначим через <71[1],<Т2[2],.. .,(ти[и] перестановки из Аи(11М(г,т)), соответствующие перестановкам <х¡,... ,еги. И пусть Н — любая невырожденная матрица.

Тогда

д(НОи ..., НИи) = о-Гг[1]" о-2_1Й • • • «Г^М • д(Е, ...,£). (7)

Эта теорема дает описание множества 1,..., НОи). С помо-

щью неё в диссертации доказана теорема, дающая описание ряда классов эквивалентности.

Теорема. 2.4. Пусть невырожденные матрицы Л>1, -Ог,... ,.Ои задают автоморфизмы ег\, о"2, ■■■,(ти кода В,М(г, т) соответственно. Обозначим через <Т1[1],гг2[2],.. .,сти[и} перестановки из Аи(ЯМ{г,т)), соответствующие перестановкам <гх,...,<тщ. И пусть Н — любая невырожденная матрица.

Тогда класс эквивалентности ¡(НИ 1, НОч..., Г)] состоит из кортежей вида

(.НАь НА2,НАи, тГ1^] • 72_1[2]... %1[и]Г' • (8)

чп[1]чг2[2]...«т|,[и]Г),

где Ai, А2,..., Аи задают автоморфизмы 7j,72i • • • > lu кода Рида-Маллера RM(r,m), 71W172H) • ■ • >7uM — соответствующие этим автоморфизмам расширенные автоморфизмы, а перестановка Г' G Sun сохраняет матрицу (Н||Л||... ||Я), то есть

(Л||Я||... ||Д)Г' = (Я||Я||... ||Л). (9)

Следует отметить, что эта структурная теорема позволяет, в частности, вычислить мощность каждого класса эквивалентности.

Во второй главе также получена нижняя оценка на мощность множества £ открытых ключей криптосистемы Мак-Элиса-Сидельникова (верхняя оценка получена Г.А. Карпуниным 8 .

Теорема. 2.6. Справедливы неравенства для числа \Е\ открытых ключей криптосистемы Мак-Элиса-Сидельникова

(ц • n)!hk . . (и ■ n)l(hk)u

(u\)n\Aut(RM(r,m))\ ^ 1 u\\Aut{RM{r,m))\v'

здесь п — длина кода Рида-Маллера RM(r,m), используемого для построения криптосистемы, и — число блоков криптосистемы,

hk = (2k - 1)(2* - 2) (2* - 22)... (2* - 2*-1) -

число обратимых (k х к)-матриц над полем GF(2), и Aut(RM(r, m)) — группа автоморфизмов кода Рида-Маллера RM (г, m).

Оценка на число открытых ключей опубликована в работе [1]. Нижняя оценка позволяет определить насколько богато множество открытых ключей криптосистемы Мак-Элиса-Сидельникова при каждых конкретных значениях параметров и, г, т. Если обнаружится, что число открытых ключей невелико, то криптосистема заведомо окажется не стойкой. Так для предложенных В.М. Сидельниковым 6 значений и = 4, г = 3, m = 10 из нижней оценки (10) следует, что число открытых ключей будет не меньше, чем

ю20897 < |4 (и)

Тем самым число ключей в криптосистеме Мак-Элиса-Сидельникова достаточно велико, чтобы противостоять атаке полным перебором ключей.

8 Карпунин Г. А. О ключевом пространстве криптосистемы Мак-Элиса на основе двоичных кодов Рида-Маллера // Дискретная математика. 2004. Т. 16(2). С. 79-84.

10)

Результаты второй главы опубликованы в работах [1] и [2].

В третьей главе даётся описание классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидельникова с представителем особого вида в случае использования только двух копий кода Рида-Мал-лера для построения криптосистемы.

Вначале вводится в рассмотрение следующий тип матриц. Пусть I = {¿1,¿2,...,гр} — множество натуральных чисел таких, что выполнена цепочка неравенств 1 ^ ¿1 < ^ • •. ^ гр < к. Пусть также А = {а*1, а12,..., а'"} — множество двоичных наборов длины к. Рассмотрим матрицу Т ~ вида

н

к

1 0 «1 4 ... 0 ч 1 ... 0 . 1р .. 0 . . 0

0 1 ... 0 ... 0 . .. 0 . . 0

••• < .. а? - ■ 4

< .. а? . ь • 4

ь а2 ::: к ::: 4: н гр ■ 4

0 0 ... 0 ... 0 . .. 0 . . 1

ч »2, ' ' 5 ак) для 1 < 3 < V- При этом для

, (12)

\

здесь а1' =

бы такая матрица была невырождена необходимо наложить на элементы множества А дополнительное условие, а именно нужно потребовать невырожденность матрицы

/

Ц

а-.

\

(13)

/

а•

В случае когда I = {г}, А = {5} матрицу Т~ будем обозначать как Далее рассматривается два случая.

Первый случай — и = 2 и / = {г}.

Рассматривается код Рида-Маллера RM(r, т) с г > 1, так как полное описание множества Q(E,H) для кода RM(l,m) и всех матриц Н было найдено Г.А. Карпуниным 8 .

Оказывается, что в этом случае задача описания классов эквивалентности сводится к задаче изучения перестановочной эквивалентности (к—1)-мерных подпространств кодаRM(r, т). Особый интерес представляют подпространства

Пи, = {v е RM{r,m)\{w,v) = 0},

где w — моном вида Х\Х2.. ■ xm-t при t > 0.

Для таких подпространств в диссертации доказана теорема.

Теорема. 3.3. Пусть 2г < т, 0 < t ^ г, и w = xjXg... xm-t- Тогда, если Г(Пги) — множество перестановок, переводящих гсодПц, в подкод кода RM(r,m), то

Г(П„) = /(П„) х Aut[RM{r,га)). (14)

Здесь I(T1W) — множество перестановок 7 таких, что х~> — х для любого х из подпространства П№.

Используя эту теорему, в диссертации получено описание множества классов эквивалентности в первом случае.

Теорема. 3.5. Пусть RM(r,m) — код Рида-Маллера такой, что 2r ^ m « г > 1, ! - натуральное число, большее нуля; Н — любая невырожденная двоичная матрица; а — произвольный двоичный вектор длины к, у которого в координате с номером г стоит единица. Тогда класс эквивалентности \(Н, НТ%, Г)] состоит из кортежей вида

(HT~D\, HTiD2, о^Ч Wflr'^r). (15)

Здесь <tl, (Гц — автоморфизмы кода Рида-Маллера RM(г, т), соответствующие матрицам Di и D2, а для перестановки Г' выполняются два условия

1) Если В! — (к — 1) х п-матрица, получающаяся удалением строки с номером г из матрицы R, то

(Я'ЦЯ')Г' = (Я'|| Я'); (16)

2) Если г* — строка матрицы R с номером i, то

(г£||аЯ)Г/ = (ßR\fiR) 6 RM(r, т) х RM(r, тп). (17)

Приведённая структурная теорема 3.5 даёт не только описание классов, но с её помощью может быть вычислена мощность каждого класса эквивалентности.

Второй случай — и = 2, |/| > 1. В этом случае рассматривается матрица Т~, где |/| = р > 1. в другое подпространство того же кода. Описание классов эквивалентности теперь сводится к задаче описания перестановок, которые переводят подпространствоП^ размерности к—р кода Рида-Маллера ДМ (г, т) в другое подпространство того же кода. При этом, если V — множество из р линейно независимых векторов длины п, то подпространство Пу определяется следующим образом

Uv = {го б RM{r, m)\{w, v) = 0, Vu € V}. (18)

Для целей описания классов эквивалентности секретных ключей в диссертации рассматриваются только подпространства Пу, которые задаются множеством V — V, где

V = {ZjiSji .. . х^, XqXq . . . Х^, . . . , • . .2^}. (19)

В диссертации доказано утверждение.

Утверждение. 3.11. Пусть Пр — подкод кода RM(r,m), задаваемый множеством V. Пусть также m —1 > 2r > jj, где — общее число различных переменных, встречающихся в мономах из множества V. Рассмотрим перестановку а такую, что (Пу)а — подкод RM(r,m). Тогда а принадлежит группе автоморфизмов Aut(RM(г, т)) кода Рида-Маллера RM (г, т).

Используя это утверждение, в диссертации получено описание подмножеств классов эквивалентности [Н, НТГ].

Теорема. 3.6. Пусть RM(r,m) — код Рида-Маллера такой, что 2г + 1 < т. Пусть также Н — любая невырожденная матрица размера k х к. Далее, пусть существует перестановка Г"1 — перестановка из Q{E,TI~], представимая в виде Г"<Т£[1]<7д[2], где Г' такая перестановка, что

(R'\\R')r' = (R'\\R'), (20)

здесь В! — (к —р) х п-матрица, получающаяся удалением р строк с номерами из множества I из матрицы Я. Тогда класс эквивалентности [Н, НТГ] содержит кортежи вида

(ЯТ|£> ь НГ^Я 2, «пГ 1[1]«Тд1[2]Г'-1Г). (21)

Здесь аь, <тд — автоморфизмы кода Рида-Маллера ЯМ (г, т), соответствующие матрицам £>1 и £>2; В = {¡5Ч, /З®2,..., /3®?}, С = {7®1,7'2,..., 7,р} — множества двоичных наборов длины к, а для перестановки Г' выполняется условие: если — строка матрицы К с номером г, то для любого г е I должно выполняться соотношение

(г|||а*Я)Г' = ОЗЯЦ^Я) € ЯМ (г, т) х КМ {г, то). (22)

Приведённая структурная теорема 3.6 даёт не только описание подмножества классов эквивалентности, но с её помощью может быть вычислена мощность этих подмножеств, то есть может быть получена оценка снизу на мощность каждого класса эквивалентности.

Результаты третьей главы опубликованы в работах [2]—[6].

В четвёртой главе рассматривается вопрос, связанный с полиномиальной эквивалентностью оригинальной криптосистемы Мак-Эли-са, построенной на основе кодов Рида-Маллера и криптосистемы Мак-Элиса-Сидельникова с ограничениями на ключевое пространство.

Рассматриваются следующие задачи тсИМ и тсБНМ. Задача тсШШ

Вход: Число т большее 2г и 1 < г < к, матрица С = Н' • Я' • 7', где Н' — невырожденная двоичная (к — 1) х [к — 1)-матрица, Я' — ((к — 1) х п)-матрица, получающаяся из порождающей матрицы Я кода Рида-Маллера КМ {г, т) выкидыванием строки с номером г и 7' — перестановочная (п х п)-матрица.

Найти: Невырожденную матрицу М' размера (к — 1) х (к - 1) и перестановочную (п х п)-матрицу а' такие, что М' ■ О • а' — порождающая матрица кода К', порождаемого матрицей Я', то есть найдётся невырожденная ((к -1 )х(к — 1))-матрица I/, что выполнено равенство М' • в ■ а' = I] • Я'.

Отметим, что если тс11М1 решается эффективно, то криптосистема Мак-Элиса на основе (к — 1)-мерных подкодах кода Рида-Маллера КМ(г,т) эффективно взламывается. Задача тсБИМ

Вход: Число т большее 2г, матрица в = (Н\ • ЩН2 • Я) ■ Д, где Н\ и Н2 — невырожденные двоичные (к х /г)-матрицы, принадлежащие классу эквивалентности [(Н,НТ~,Т)] для некоторой невырожденной (к х &)-матрицы Н, некоторой перестановочной (2п х 2п)-матрицы Г, некоторого числа 1 ^ г ^ к и некоторого вектора а, Я — порождающая (/с х га)-матрица кода Рида-Маллера ИМ (г, тп) и Д — перестановочная (2п х 2п)-матрица.

Найти: Невырожденные матрицы Н\ и Н'2 размера (к х к) и перестановочную (2п х 2п)-матрицу Д' такие, что С • Д' = (Я^ЯЦН^Я).

Сложность задачи тсБИМ определяет сложность восстановления по открытому ключу секретного ключа криптосистемы Мак-Элиса-Сидель-никова, при условии, если он попадает в некоторый особый класс эквивалентности.

В диссертации доказана теорема.

Теорема. 4.1. Пусть существует алгоритм МТтсЯМ{, который решает задачу тсИМ1 за полиномиальное время. Тогда существует алгоритм ИТтсБЯМ, который решает задачу тсБЯМ за полиномиальное время.

Теорема 4.1 позволяет заключить, что в криптосистеме Мак-Элиса-Сидельникова имеются классы секретных ключей, выбор которых не увеличивает стойкость новой криптосистемы по сравнению с оригинальной криптосистемой Мак-Элиса.

Этот результат опубликован в работе [7].

В заключении в диссертации рассматривается вопрос о возможности определить часть ключа криптосистемы Мак-Элиса-Сидельникова по перестановке из множества Я.

В четвёртой главе доказано следующее утверждение.

Утверждение. 2.11 Пусть Ли (ИМ (г, т)) — это множество перестановок вида Уу, где 7 — это перестановка из Ли (ЯМ (г, т)), а V — это произвольная перестановка блоков матрицы (Д^ЯЦ... ||НиЯ). Справедливо равенство

р| д(Нь...,Ни) = Аи(ЯМ(г,т)), (23)

Ни-,НиевЦк, 2)

В случае и — 2 из утверждения 2.11 следует, что наличие во множестве 0(Е,Н) перестановки, не являющейся расширенным автомор-

физмом, особым образом характеризует матрицу Н, поэтому множество 0(Е, Н) в диссертации получило название (З-структуры матрицы Н.

Для взлома криптосистемы Мак-Элиса-Сидельникова необходимо по матрице (АЛ||ВЛ)Г восстановить матрицы А я В ш перестановку Г. Предположим, что злоумышленнику оказывается известной перестановка из множества 9 {А, В). Как он может использовать это знание для восстановления ключа? Если обозначить через Н произведение матриц А~1В, то, как доказывается в разделе 2.1, Я {А, В) = 5(Е, Н), а значит знание перестановки из множества Я {А, В) эквивалентно знанию перестановки из С-структуры матрицы Н.

Итак, пусть перестановка Г = Г/^^7[1]ст[2] не является расширенным автоморфизмом и принадлежит (^-структуре некоторой невырожденной матрицы Н, здесь I = {¿1, г'г,..., г^} С {1,2, ...,гг} = Л/-, J = {зъ32, ■ ■ ■ ,3а} £ -А/", а =п + за, Г + за) = г8 для всех

в = 1,2, ...Д и_Г/ы(|) = г для всех г ф ¿1,..., г3, п + ¡ъ..., п + з Обозначим через I дополнение к множеству 7, то есть / = А/" \ /. Далее, если Я — порождающая (к х п)-матрица кода Рида-Маллера ЯМ (г, тп), то через Д* будем обозначать столбец с номером г этой матрицы. Кроме того, через р/ обозначим ранг ((п — к) х |/|)-матрицы Д/, которая является подматрицей матрицы Нх, то есть проверочной матрицы кода ЯМ {г, тп), и состоит из столбцов Л1 с номерами из множества I.

В диссертации доказана следующая теорема.

Теорема. 4.1. Используя перестановку Г = Г/++^'у[1]сг[2], можно построить Р7+Р7 линейно независимых уравнений относительной неизвестных НЯ\, НЯ2, ..НЯъ-

Из этой теоремы следует, что знание перестановки из (^-структуры, которая не является расширенным автоморфизмом, позволяет получить некоторое число линейных соотношений на матрицу Н, что позволяет восстановить часть ключа криптосистемы Мак-Элиса-Сидельникова. В силу этого понимание структуры классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидельникова может оказаться важным для её взлома. Кроме того, прослеживается связь перестановок из б-структуры с перестановками из группы автоморфизмов кода. При переходе к рассмотрению криптосистемы Мак-Элиса-Сидельникова от криптосистемы Мак-Элиса перестановки из (^-структуры являются обобщением понятия автоморфизмов. Такое обобщение оказывается даже более полезным для криптоанализа модифицированной криптосисте-

мы Мак-Элиса, нежели группа автоморфизмов для оригинальной. Причина в том, что перестановки из (З-структуры дают систему линейных соотношений на элементы ключа криптосистемы Мак-Элиса-Сидельни-кова, в то время как автоморфизмы задают линейные соотношения, если они образуют группу со свойством транзитивности. Транзитивные группы автоморфизмов позволяют фиксировать ряд столбцов в матрице — элементе ключа криптосистемы.

Результаты третьей главы опубликованы в работе [7]. В Заключении приводятся основные результаты диссертационной работы.

Благодарности

Автор выражает искреннюю благодарность своему научному руководителю кандидату физико-математических наук, доценту Карпунину Григорию Анатольевичу за постановку задач, постоянное внимание, многочисленные плодотворные обсуждения, помощь в работе и терпение.

Автор выражает глубокую благодарность всей кафедре математической кибернетики факультета ВМК МГУ имени М.В. Ломоносова за содействие в подготовке диссертационной работы и создание творческой атмосферы.

Автор выражает искреннюю признательность Применко Эдуарду Андреевичу за неустанную поддержку и помощь в подготовке диссертации.

Публикации по теме диссертации

1. Чижов И. В. Число открытых ключей криптосистемы Мак-Элиса-Сидельникова // Вестник Московского университета. 2009. Т. 3. С. 40-45.

2. Чижов И. В. Ключевое пространство криптосистемы Мак-Элиса-Сиделышкова // Дискретная математика. 2009. Т. 21(3). С. 132-158.

3. Чижов И. В. Об эквивалентных ключах криптосистемы Мак-Элиса-Сидельникова // Труды VII международной конференции «Дискретные модели в теории управляющих систем». 2006. С. 412-419.

4. Чижов И. В. Эквивалентные ключи криптосистемы Мак-Элиса-Сидельникова // Материалы Международного семинара «Дискретная математика и ее приложения», посвященного 75-летию со дня рождения академика О. Б. Лупанова. 2007. С. 461-464.

5. Чижов И. В. Эквивалентные подпространства кодов Рида-Маллера и множество открытых ключей криптосистемы Мак-Элиса-Сидельни-кова // Материалы VI общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2008). 2009. С. 28-32.

6. Чижов И. В. Эквивалентные подпространства кода Рида-Маллера и пространство ключей криптосистемы Мак-Элиса-Сидельникова // Тезисы докладов VIII Сибирской научной школы-семинара с международным участием «Компьютерная безопасность и криптография -SIBECRYPT'09». 2009. С. 36-38.

7. Чижов И. В. О сложности некоторых задач, связанных со стойкостью криптосистемы Мак-Элиса-Сидельникова // Материалы VII общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2009). 2010. С. 35-41.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 13.05.2010 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 220. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение.

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

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

Глава 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. Определение матрицы по перестановке из ее С-структуры

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

Актуальность работы определена потребностью в исследовании альтернативных традиционным криптосистем с открытым ключом. Бурное развитие теории чисел за последние 5 лет позволило значительно снизить стойкость RSA — широко распространённой на практике криптосистемы с открытым ключом. Это диктует необходимость в исследовании других криптосистем с открытым ключом с целью поиска альтернатив криптосистеме RSA. Одной из таких альтернатив являются кодовые криптосистемы, то есть криптосистемы, основанные на задачах из теории кодов, исправляющих ошибки. В основе кодовых криптосистем лежит идея использования быстро декодируемых кодов, исправляющих ошибки, в качестве основного элемента шифрующего преобразования. В настоящее время широкую известность получили две кодовые криптосистемы — криптосистема Мак-Элиса и криптосистема Нидеррайтера, оригинальные версии которых используют коды Гоппы и расширенные коды Рида-Соломона, соответственно. В.М. Сидельников и С.О. Шеста-ков показали несостоятельность идеи использования для построения кодовых криптосистем расширенных кодов Рида-Соломона, так как в этом случае такие криптосистемы не будут стойкими.

Кодовые криптосистемы имеют особенность, которая отличает их от многих других криптосистем. В кодовых криптосистемах одному и тому же открытому ключу могут соответствовать несколько секретных ключей, и поэтому секретные ключи могут быть разбиты на классы эквивалентности. При этом вопрос строения этих классов эквивалентности для кодовых криптосистем оказывается важным. Так атака В.М. Сидельникова и С.О. Шестакова использует строение ключевого пространства кодовой криптосистемы для вскрытия криптосистемы Мак-Элиса на основе обобщённых кодов Рида-Соломона. Следовательно, в некоторых случаях структура пространства ключей кодовой криптосистемы может помочь в её криптоанализе.

Атака В.М. Сидельникова и С.О. Шестакова показала невозможность использовать расширенные коды Рида-Соломона для построения кодовых криптосистем, поэтому в 1994 году В.М. Сидельников предложил использовать для построения кодовых криптосистем коды Рида-Мал-лера, которые позволяют увеличить как скорость расшифрования криптограммы, так и скорость передачи криптосистемы. Кроме того, В.М. Сидельников предложил усиленный вариант криптосистем Мак-Элиса, в конструкции которой используется не одна копия кода, а некоторое число и копий кода, число и становится параметром криптосистемы. Такая криптосистема в диссертации получила название криптосистемы Мак-Элиса-Сидельникова. До недавнего времени ключевое пространство усиленного варианта кодовых криптосистем на основе кодов Рида-Маллера оставалось полностью не изученным. Диссертация посвящена исследованию структуры множества ключей криптосистемы Мак-Элиса-Сидель-никова и разработке методов использования структуры этого множества в криптоанализе криптосистемы Мак-Элиса-Сидельникова.

Цель диссертационной работы заключается:

1) в получении оценок на число открытых ключей криптосистемы Мак-Элиса-Сидельникова;

2) в исследовании структуры множества отрытых ключей криптосистемы Мак-Элиса-Сидельникова;

3) в разработке методов, позволяющих использовать сведения о структуре открытых ключей криптосистемы Мак-Элиса-Сидельникова для криптоанализа такого вида криптосистем.

Научная новизна.

1) Получена нижняя оценка на мощность множества открытых ключей криптосистемы Мак-Элиса-Сидельникова, которая позволила заключить, что число ключей криптосистемы достаточно велико, чтобы противостоять атаке на криптосистему полным перебором по всему множеству открытых ключей.

2) Установлена связь классов эквивалентности секретных ключей со специально введенным множеством перестановок. Это множество перестановок является в некотором смысле обобщением группы автоморфизмов кодов.

3) В случае использования произвольного числа копий кода Рида-Маллера описывается ряд классов эквивалентности секретных ключей.

4) Задача изучения некоторых классов эквивалентности секретных ключей сведена к изучению перестановочной эквивалентности особого вида подпространств кода Рида-Маллера и описаны все перестановки, которые переводят подпространство особого вида в некоторое другое подпространство кода Рида-Маллера. С использованием описания перестановок были получены описания ряда классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидель-никова.

5) Доказана полиномиальная эквивалентность некоторых задач, связанных со стойкостью криптосистемы Мак-Элиса—Сидельникова, и задачи взлома оригинальной криптосистемы Мак-Элиса на основе подкодов кода Рида-Маллера, размерность которых на единицу меньше размерности кода, а также была доказана возможность восстановления части секретного ключа криптосистемы Мак-Элиса-Сидельникова, используя знание структуры класса эквивалентности, в который попадает секретный ключ.

Практическая значимость. Работа носит теоретический характер. Установлена оценка снизу на число открытых ключей криптосистемы Мак-Элиса-Сидельникова, которая позволяет заключить, что число в криптосистема Мак-Элиса-Сидельникова достаточно велико, чтобы противостоять атаке полного перебора по всему множеству ключей. Описана структура ряда классов эквивалентностей секретных ключей криптосистемы Мак-Элиса-Сидельникова. Доказана полиномиальная эквивалентность задачи взлома криптосистемы Мак-Элиса и задачи взлома криптосистемы Мак-Элиса-Сидельникова с ограничениями на ключевое пространство.

Полученные результаты могут найти применение: для синтеза и криптоанализа кодовых криптосистем; для изучения перестановочной эквивалентности подпространств кодов; при изучении свойств кодов, исправляющих ошибки, полученных из других кодов операцией комбинирования; в учебном процессе.

На защиту выносятся следующие основные результаты и положения:

1) нижняя оценка мощности множества открытых ключей криптосистемы Мак-Элиса-Сидельникова;

2) описание ряда классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидельникова для произвольного числа блоков кода Рида-Маллера;

3) описание классов эквивалентности с представителями особого вида в случае криптосистемы с двумя блоками;

4) метод восстановления части секретного ключа криптосистемы Мак-Элиса-Сидельникова, использующий знание структуры класса эквивалентности, в который попадает секретный ключ;

5) доказательство полиномиальной эквивалентности задачи взлома оригинальной криптосистемы Мак-Элиса, построенной на основе подкодов кода Рида-Маллера, размерность которых на единицу меньше размерности кода, и задачи взлома криптосистемы Мак-Элиса-Сидельникова с ограничениями на ключевое пространство.

Апробация работы

Результаты работы докладывались на:

• семинаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета Вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова;

• VII общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2009), 2009 год

• VI общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2008), 2008 года;

• V общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2007), 2007 год;

• VII международной конференции «Дискретные модели в теории управляющих систем», 2006 год;

• VIII Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография — SIBECRYPT'09», 2009 год.

Публикации. Основное содержание диссертации опубликовано в 7 работах, список которых приведён в конце диссертации [Al]—[А7].

Структура и объем диссертации

Диссертационная работа состоит из четырёх глав и заключения.

В главе 1 приводятся основные сведения из теории кодов, исправляющих ошибки и вводятся необходимые в дальнейшем изложении термины и определения. Даётся краткое введение в криптографию и криптосистемы с открытым ключом. Описывается криптосистема Мак-Элиса: приводится её секретный и открытый ключи и алгоритмы зашифрования и расшифрования, ряд известных фактов о связи ключевого пространства с автоморфизмами кода, используемого для построения криптосистемы Мак-Элиса. Приводится подробное описание криптосистемы

Мак-Элиса-Сидельникова. Описываются алгоритмы шифрования и расшифрования такой криптосистемы. Доказывается ряд свойств классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидель-никова. Эти свойства используются для получения результатов следующих глав. В той же главе формулируется основная проблематика работы и приводится описание постановки задачи.

В главе 2 изучается ключевое пространство криптосистемы Мак-Элиса-Сидельникова. Устанавливается связь классов эквивалентности секретных ключей со специально введенным множеством перестановок 0. Доказывается теорема о том, что изучение классов эквивалентности секретных ключей сводится к задаче изучения свойств множества Оставшаяся часть главы посвящена изучению ключевого пространства криптосистемы Мак-Элиса-Сидельникова в случае использования произвольного числа блоков кода Рида-Маллера. Описывается ряд классов эквивалентности секретных ключей. Кроме того, получается нижняя оценка на мощность множества открытых ключей криптосистемы Мак-Элиса-Сидельникова. В работе [1] В.М. Сидельников высказал предположение о мощности множества открытых ключей криптосистемы Мак-Элиса-Сидельникова, которое позже было опровергнуто Г.А. Карпупи-ным [2]. В своей работе Р.А. Карпунин получил оценку сверху на мощность множества открытых ключей. В диссертации получена нижняя оценка. Эта оценка позволяет заключить о том, что число ключей такой криптосистемы велико настолько, что взлом криптосистемы методом полного перебора невозможен на существующей вычислительной технике за приемлемое на практике время. I

В главе 3 изучается криптосистема Мак-Элиса-Сидельникова в случае двух блоков (и = 2). В общем случае задача описания классов эквивалентности оказывается сложной, поэтому во второй главе исследуется случай двух блоков (и = 2). К тому же, изучение двух блоков является фундаментом для изучения криптосистемы с большим числом блоков. В главе 3 показывается, что задача изучения некоторых классов эквивалентности секретных ключей сводится к изучению перестановочной эквивалентности особого вида подпространств кода Рида-Маллера Ш(г,т). В результате описываются все перестановки, которые переводят подпространство особого вида в некоторое другое подпространство кода Рида-Маллера. Оказывается, что эти перестановки лежат в группе автоморфизмов кода Рида-Маллера. С использованием описания перестановок были получены описания ряда классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидельникова.

В главе 4 вводится ряд задач, связанных со стойкостью оригинальной криптосистемы Мак-Элиса, а также формулируется задача, на которой основана стойкость криптосистемы Мак-Элиса-Сидельникова с ограничениями на ключевое пространство. Ограничения диктуются результатами третьей главы. Далее доказывается полиномиальная эквивалентность задач взлома криптосистемы Мак-Элиса и взлома криптосистемы Мак-Элиса-Сидельникова с ограничениями на ключевое пространство. Изучается вопрос связи структуры классов эквивалентности с криптоанализом криптосистемы Мак-Элиса-Сидельникова. Доказывается, что используя знание структуры класса эквивалентности, в который попадает секретный ключ, возможно построить достаточно большую систему линейно независимых уравнений, накладывающих ограничения на часть секретного ключа.

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

Криптосистема Мак-Элиса — одна из старейших криптосистем с открытым ключом. Она была предложена в 1978 Р. Дж. Мак-Элисом [3]. Стойкость рассматриваемой криптосистемы основывается наМР-трудной задаче в теории кодирования. Основная идея её построения состоит в маскировке некоторого линейного кода, имеющего эффективные алгоритмы декодирования, под код, не обладающий видимой алгебраической и комбинаторной структурой. Такие коды принято называть кодами общего положения. Предполагается, что декодирование кода общего положения является трудной задачей [4]. Не зная структуры кода, невозможно построить эффективный алгоритм декодирования такого кода. Именно эта идея и заложена в конструкции криптосистемы, предложенной Р. Дж. Мак-Элисом.

Криптосистема Мак-Элиса, как и все другие известные кодовые криптосистемы обладают одним важным преимуществом — высокой скоростью зашифрования и расшифрования. Однако, в подобных криптосистемах имеется недостаток — относительно низкая скорость передачи (.R). Обычно у кодовых криптосистем R < 1, тогда как у криптосистемы RSA — пожалуй, самой распространённой в настоящее время криптосистемы, — скорость равна 1. С развитием вычислительной техники и с увеличением производительности вычислительных систем низкая скорость передачи кодовых систем может перестать быть существенным недостатком, сдерживающим использование этих криптосистем на практике.

В 1986 году Нидеррайтер в работе [5] предложил модификацию криптосистемы Мак-Элиса, которая получила название криптосистемы

Нидеррайтера. Криптосистема Мак-Элиса и криптосистема Нидеррайте-ра, построенные на основе одних и тех же кодов, например, кодов Гоппы, с точки зрения стойкости являются эквивалентными [6]. В той же работе [5] автор предлагает использовать для построения как новой криптосистемы, так и криптосистемы Мак-Элиса обобщённые коды Рида-Соломона. В 1992 году В.М. Сидельников и С.О. Шестаков показали, что использование обобщённых кодов Рида-Соломона для построения криптосистем Мак-Элиса и Нидеррайтера делает эти криптосистемы нестойкими [7]. При этом атака В.М. Сидельников а и С. О. Шестаков а использует для взлома знание свойств структуры классов эквивалентности секретных ключей.

Одним из активно проводимых исследований является изучение атак, связанных с алгоритмами эффективного декодирования кодов общего положения. На сегодняшний день самой эффективной такой атакой является атака, предложенная Шабо и Канто [8] в 1998 году. Так, например, для восстановления секретного сообщения, зашифрованного оригинальной криптосистемой Мак-Элиса на основе кодов Гоппы с длиной 1024, исправляющего не менее 524 ошибок, с помощью алгоритма Шабо и Канто потребуется 264'2 операций.

Другое направление исследований — это так называемые структурные атаки, то есть атаки, основанные на использовании алгебраической или комбинаторной структуры кодов, используемых для построения криптосистем. Самыми значительными работами здесь являются — атака В.М. Сидельникова и С.О. Шестакова [7] на криптосистему Мак-Элиса на основе обобщённых кодов Рида-Соломона, атака Н. Сендрие [9] на криптосистему на основе каскадных кодов, атака Л. Миндера [10] на криптосистемы на основе кодов Рида-Маллера, а также алгоритм разбиения носителя, предложенный Н. Седрие [11]. С помощью этого алгоритма можно строить атаки на криптосистему, построенную на основе случайных кодов, так как почти всегда случайные коды имеют группу автоморфизмов, состоящую только из тождественной перестановки.

Практически с момента появления криптосистемы Мак-Элиса де лались попытки её модифицировать, которые за редким исключением сводятся к предложению использовать вместо кодов Гоппы какие-либо другие коды. Так известны модификации, предложенные Э.М. Габиду-линым [12] и [13]. Однако указанные модификации снизили стойкость криптосистемы, известны эффективные атаки на криптосистемы Габи-дулина и её модификации [14]. В 1996 году Янва и Морено впервые выдвинули идею использовать в кодовых криптосистемах эллиптические кривые [15]. В 2005 году П. Жаборит предложил использовать для построения криптосистемы Мак-Элиса коды БЧХ [16].

В.М. Сидельников [1] в 1994 году рассмотрел возможность использования кодов Рида-Маллера для построения криптосистемы Мак-Элиса. Он провёл криптографический анализ такой криптосистемы. Результаты показали, что криптосистема Мак-Элиса на основе кодов Рида-Маллера не обеспечивает достаточной стойкости. Кроме того в 2007 году Л. Миндер в работе [10] усилил атаку В.М. Сидельникова, однако она остаётся до сих пор неполиномиальной. В той же работе [1] рассматривается некоторое усиление криптосистемы Мак-Элиса на основе кодов Рида-Маллера — криптосистема Мак-Элиса-Сидельникова.

Криптосистема Мак-Элиса-Сидельникова строится на основе ^-кратного использования кодов Рида-Маллера ЯМ (г, т).

В диссертации исследуются вопросы, связанные со структурой классов эквивалентности секретных ключей, то есть секретных ключей, порождающих одинаковые открытые ключи, новой криптосистемы.

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

Опишем устройство криптосистемы Мак-Элиса-Сидельникова. Секретным ключом криптосистемы является кортеж

Здесь Н2, ■., Ни — невырожденные матрицы размера к х к над полем 2), которые выбираются случайно и равновероятно из множества всех двоичных невырожденных матриц размера к х к. Здесь к — размерность кода Рида-Маллера КМ(г,т). Матрица Г имеет размеры и ■ п х и - п и является перестановочной, то есть в каждой её строчке и в каждом столбце стоит ровно одна единица, поэтому можно считать, что Г — это перестановка на множестве из ип элементов.

Открытым ключом криптосистемы Мак-Элиса-Сидельникова является матрица где символом || обозначена конкатенация матриц по столбцам, а Д — стандартная форма порождающей матрицы кода Ш(г,т). Под стандартной формой порождающей матрицы понимается (к х п)-матрица

Н\,Н2, - - - ,Ни,Т).

1)

С = (Д-1Й||Д-2Л||. ||Я„Я) ■ г,

2) вида

11 =

С?1 где г/

С?1 =

ЬЬут

1у2

Ц/1 / а

Утп—1Ут

Ц/1 Уз \ Ц/13/2 у п.

Ут-г+1Утп-г+2---Ут п.

У1У2—Уг-1Уг+1 Ц/Ш—2/г-1Уг у здесь Qf — вектор значений булевой функции . ,ут)- Отметим, что в дальнейшем мы не будем делать различий между булевыми функциями и их векторами значений.

Дадим следующее определение эквивалентности секретных ключей в криптосистеме Мак-Элиса-Сидельникова. Два секретных ключа

Н1, Й2,., Ни, Г) и (Н'ъ Н'2,., Н'и, Г') назовем эквивалентными, если соответствующие им открытые ключи совпадают, то есть выполняется соотношение н^цнэЩ. IIНия) • г = даяуяуги. \\н'ип) ■ г', (з)

Заметим, что введённое отношение действительно является отношением эквивалентности. Тем самым, всё множество секретных ключей разбивается на классы эквивалентности и число классов эквивалентности совпадает с числом открытых ключей. Класс эквивалентности с представителем (H 1,., Ни, Г) будем обозначать так: [(Hi,., Ни, Г)].

Рассмотрим множество Q(Hi, Н2, ■ ■ •, -Ни), состоящее из перестановок Г 6 Sun, для которых существуют невырожденные двоичные матрицы H2,., Н'и такие, что

НгЩ\Н2К\\. II Д-„Л)Г = (Н'.ЩЩЩ. IlH'UR). (4)

В диссертации доказана следующее утверждение.

Утверждение 0.1. Существует взаимно однозначное соответствие между классом эквивалентности [(-ffi, H2,. •, Ни, Г)] секретных ключей и MHoatcecmeoM G(H\, H2,., Ни).

При этом класс эквивалентности [(-HTi, Н2, • • • > Ни, Г)] состоит из ключей вида

Н[,Н'2,.,Н'и: Г,-Г), (5) где Г~ принадлежит множеству Q(JEÎ\^ H2■> • • • ■> H-и) и

ЩЩЩЩ . WH^r-1 = (Н'гЩН'гЩ . Ц^Д). (6)

Тем самым вопрос изучения структуры классов эквивалентности секретных ключей сводится к изучению структуры множества перестановок Q.

В диссертации получена нижняя оценка на мощность множества £ открытых ключей криптосистемы Мак-Элиса-Сидельникова (верхняя оценка получена Г.А. Карпуниным [2]).

Теорема 0.1. Справедливы неравенства для числа |£| открытых клю

4 •У"-» < £ < v- -yy-ft./ u\)n\Aut(RM(r,m))\^ 1 1 u здесь п — длина кода Рида-Маллера ДМ(г, т), используемого для построения криптосистемы, и — число блоков криптосистемы, число обратимых (к х к)-матриц над полем и АиЬ{В.М(г, т)) — группа автоморфизмов кода Рида-Маллера В.М(г, га).

Оценка на число открытых ключей опубликована в работе [А1].

Нижняя оценка позволяет определить насколько богато множество открытых ключей криптосистемы Мак-Элиса-Сидельникова при каждых конкретных значениях параметров и, г, т. Если обнаружится, что число открытых ключей невелико, то криптосистема заведомо окажется не стойкой. Так для предложенных В.М. Сидельниковым [1] значений и — 4, г — 3, га = 10, число открытых ключей будет не меньше, чем

Тем самым число ключей в криптосистеме Мак-Элиса-Сидельникова достаточно велико, чтобы противостоять атаке полным перебором ключей.

В диссертации описание структуры множества открытых ключей разбивается на ряд случаев.

Случай первый — нет ограничения на и.

Рассмотрим некоторую перестановку <r G Sn. Построим, используя её, г «длинных» перестановок сг[г] G Sun следующим образом. Положим hk = (2k - l)(2k - 2)(2k - 22). (2k - 2k~l) q20897

8) аШ(з) ~ Э Для любого ^ £ I = {(г — 1) ■ п + 1, (г — 1) • п + 2,., г ■ п}, а ст[г](/) = сг(/). Другими слова перестановка аЩ в г-том блоке действует как перестановка сг, а во всех остальных блоках — как единичная перестановка. Тогда группой расширенных автоморфизмов Ли(КМ(г^ гп)) кода Рида-Маллера ЯМ(г,т) назовём множество всех возможных произведений описанных перестановок <т[г] для всех возможных 1 ^ г ^ и и всех возможных перестановок а из группы автоморфизмов кода ИМ {г, т).

В диссертации доказана следующая теорема.

Теорема 0.2. Пусть невырожденные матрицы £>1, • • •, задают автоморфизмы сг2,., аи кода ЯМ{г,т) соответственно, то есть для 1 ^ г ^ и выполнены равенства ЛУ^ — Обозначим через

Т1[1],<Т2[2],. .,<ти\и\ перестановки из Ли{11М(г,т)), соответствующие перестановкам ., сги. И пусть Н — любая невырожденная матрица.

Тогда д{НПъ ., Н1)и) = О-ГМЧ ■ ^[2] • • • ■ .,Е). (9)

Эта теорема дает описание множества 0(НЮ\:., НГ)и). С помощью ее в диссертации доказана теорема, дающая описание ряда классов эквивалентности в первом случае.

Теорема 0.3. Пусть невырожденные матрицы Г)\, Т>2-> • • ■, задают автоморфизмы сг1, сг2,., сти кода ЯМ (г, т) соответственно. Обозначим через <Т1[1],<Т2[2],. . .,сги\и[ перестановки из Ли(ПМ(г, то)), соответствующие перестановкам о~1,., <ти. И пусть Н — любая невырожденная матрица.

Тогда класс эквивалентности \(НГ) 1, НГ-02 • • •, НГ)и, Г)] состоит из кортежей вида

НАЪ НА2,., А», -гГМЧ " 72 М2] • • ■ 7й1[«Г ' (10) где Ах, А2,., Аи задают автоморфизмы"Уъ 72> • • • > 7и кода Рида-Мал-лера 11М(г,т), ТхЕ^]? 72• • • ?7иМ ~ соответствующие этим автоморфизмам расширенные автоморфизмы, а перестановка Г' 6 Зип сохраняет матрицу . \\И), то есть

ВД|.||Я)Г' = (ВД|.||Я). (11)

Следует отметить, что эта структурная теорема позволяет, в частности, вычислить мощность каждого класса эквивалентности.

Для того, чтобы перейти к другим случаям, введём в рассмотрение следующий тип матриц. Пусть I — {¿1, ¿2,. , ¿р} — множество натуральных чисел таких, что 1 ^ ^ ¿2 ^ . ^ гр ^ к. Пусть также А — {а?1, а12,., а1р} — множество двоичных наборов длины к. Рассмотрим матрицу Т~ виДа

1 0 . ч ; . 0 . . 0 . Ър . 0 . . 0

0 1 . . 0 . . 0 . . 0 . . 0

Ч 4 ■ ■• 4 - а*1 . 12 • а? • • ак г2 а\2 42 ■ . О?-2 . 12 . а*2 . гр ■ ак гр гр «2 - ■ < • а-р *2 1р ■ 4Р

0 0 . . 0 . . 0 . . 0 . . 1 (12) здесь аг' = (аг^, а^,. •, ) для 1 ^ ^ ^ р. При этом для того, чтобы такая матрица была невырождена необходимо наложить на элементы множества А дополнительное условие, а именно нужно потребовать невырожденность матрицы < <

Ър Ъп а- (ха\> гр а/

13)

В случае когда I = {г}, А = {а} матрицу Т~ будем обозначать как ггп

-Ж

Итак, рассмотрим второй случай — и = 2 и I — {г}. Будем рассматривать код Рида-Маллера КМ (г, т) с г > 1. Отметим, что полное описание множества Н) для кода ЯМ( 1, т) и всех матриц Н было найдено Г.А. Карпуниным в [2].

Оказывается, что в этом случае задача описания классов эквивалентности сводится к задаче изучения перестановочной эквивалентности {к— 1)-мерных подпространств кода ДМ (г, т). Особый интерес представляют подпространства где но — моном вида Х\Х2 ■ ■ • жто-г при t > 0.

Для таких подпространств в диссертации доказана теорема.

Теорема 0.4. Пусть 2т ^ т, 0 < £ ^ г, и IV = Х\Х2 Тогда, если Г(Пг„) — множество перестановок, переводящих кодПц, в подкод кода ИМ {г, ш), то

Здесь /(Пад) — множество перестановок 7 таких, что ж7 = х для любого х из подпространства П^.

Используя эту теорему, в диссертации получено описание множества классов эквивалентности во втором случае.

Теорема 0.5. Пусть ЛМ(г,ш) — код Рида-Маллера такой, что выполнено неравенство 2г^тиг>1, I — натуральное число, большее нуля, Н — любая невырожденная двоичная матрица, а — произвольный двоичный вектор длины к, у которого в координате с номером г стоит единица. Тогда класс эквивалентности [(Н,НТ~С,Т)] состоит из кортежей вида

- {у 6 ЛМ(г,т)|(г17,17) - 0},

Г(Пги) = /(П«,) х А^(Ш(г,т)).

14)

НТ1~0ь ИТсг£-1 [1]сгд1 [2]Г/-1Г).

15)

Здесь (Ть^сщ — автоморфизмы кода Рида-МаллераЯМ(г,т), соответствующие матрицам Г)\ и Г)2, а для перестановки Г' выполняются два условия

1) Если И! — (к — 1) х п-матрица, получающаяся удалением строки с номером г из матрицы П,, то

Я'ЦЯ')Г' = (Я'||Я'); (16)

2) Если г* — строка матрицы Н с номером г, то

Й#)Г' = (рЩ^П) е ЯМ (г, т) х ЯМ (г, т). (17)

Наконец, последний третий случай — и = 2, \1\ > 1. В этом случае рассматривается матрица Т~, где |/| = р > 1.

Описание классов эквивалентности теперь сводится к задаче описания перестановок, которые переводят подпространство размерности к— р кода Рида-Маллера ЯМ (г, т)

11у = {IV € ЯМ(г,т) |(«7,1?) = 0, \/у € V}, (18) здесь V — множество векторов, в другое подпространство того же кода. Здесь V — множество из р линейно независимых векторов длины п. Необходимо при этом только рассмотреть подпространства Пу, которые задаются множеством V = V, где

V = {х{1х{1. х^, .х^,., Х{рх% . х,*}. (19)

В диссертации доказано утверждение.

Утверждение 0.2. Пусть Пу — подкод кода RM(r,m), задаваемый множеством V. Пусть также т—1 > 2r > jj, где Ц — общее число различных переменных, встречающихся в мономах из множества^/. Рассмотрим перестановку а такую, что — подкод RM(г, т). Тогда о принадлежит группе автоморфизмов Aut(RM(г, га)) кода Рида-Мал-лера RM{r, т).

Используя это утверждение, в диссертации получено описание подмножеств классов эквивалентности [Н, Г].

Теорема 0.6. Пусть ДМ (г, т) — код Рида-Маллера такой, что 2г+1 < Пусть также Н — любая невырожденная матрица размера k х к. Далее, пусть I = {¿1, ¿2,., гр} — множество натуральных чисел таких, что 1 ^ ¿1 ^ ¿2 ^ -. ^ ip ^ к и г > р. Пусть далее А = {с?1, а12,., агр} множество двоичных наборов длины к. Пусть существует перестановка Г"1 — перестановка из представимая в виде Т'а^ЩсгцЩ, где Г' такая перестановка, что

Д'ЦЯ')Г' = (R'\\R% (20) здесь R' — (k— р) х п-матрица, получающаяся удалением р строк с номерами из множества I из матрицы R. Тогда класс эквивалентности [Н", JFfT~, Г] содержит кортежи вида

НТ^Юг, HT~D2, ст£-1[Ц^1[2]Г/-1Г). (21)

Здесь ctl,(Tr — автоморфизмы кода Рида-Маллера RM(г, т), соответствующие матрицам и jD2, В — {¡Зч, /З*2,., /31р}, С = {7^, -у22,.,} 7гр} — множества двоичных наборов длины к, а для перестановки Г' выполняется условие: если Гг — строка матрицы И с номером ъ, то для любого г £ / долэюно выполняться соотношение г£||й\К)Г' = фгЩ\^В) е М(г, т) х ЯМ(г,т). (22)

Описание классов эквивалентности опубликованы в работах [А2], [АЗ], [А4], [А5], [А6].

В диссертации также рассматривается вопрос, связанный с полиномиальной эквивалентностью криптосистем Мак-Элиса и Мак-Элиса-Сидель-никова с ограничениями на ключевое пространство.

Рассмотрим следующие задачи тсШШ и тсЭПМ. Задача тсКМ!

Вход: Число т большее 2г и 1 < г < к, матрица С = Н' ■ Ш ■ 7', где Н' — невырожденная двоичная (к — 1) х (к — 1)-матрица, Н! — ((/с — 1) х п)-матрица, получающаяся из порождающей матрицы И кода Рида-Маллера ИМ (г, т) выкидыванием строки с номером г и 7' — перестановочная (п х п)-матрица.

Найти: Невырожденную матрицу Ш.' размера (к — 1) х (к — 1) и перестановочную (п х п)-матрицу а' такие, что М' • С? • о' — порождающая матрица кода 72/, порождаемого матрицей И!, то есть найдётся невырожденная ((к —1) X (к — 1))-матрица Ь\ что выполнено равенство М' ■ С • <т' = И • В!.

Рассмотрим теперь задачу, связанную со стойкостью криптосистемы Мак-Элиса-Сидельникова. Однако здесь криптосистема Мак-Элиса-Си-дельникова рассматривается не на всём ключевом пространстве, а только на полностью описанных в третьей главе классах эквивалентности. Задача тсЗЫМ

Вход: Число ш большее 2г, матрица С? = (-Н-! • Н\\Н2 * -К) • А, где и й"2 —■ невырожденные двоичные (к х &)-матрицы, принадлежащие классу эквивалентности [(-Н", НТ~, Г)] для некоторой невырожденной (.к х &)-матрицы Д", некоторой перестановочной (2п х 2п)-матрицы Г, некоторого числа 1 ^ г ^ к и некоторого вектора а, И — порождающая (,к х п)-матрица кода Рида-Маллера ИМ (г, т) и Д — перестановочная (2п х 2п)-матрица.

Найти: Невырожденные матрицы Н\ и Н'2 размера {к х к) и перестановочную (2п х 2п)-матрицу А' такие, что • А' =

Сложность задачи тсБКМ определяет сложность восстановления по открытому ключу секретный ключ криптосистемы Мак-Элиса-Сидель-никова, при условии, если он попадает в некоторый особый класс эквивалентности.

Справедлива следующая теорема.

Теорема 0.7. Пусть существует алгоритм МТтсКМг, который решает задачу тсКМг за полиномиальное время. Тогда существует алгоритм МТтсЗЯМ, который решает задачу тсЗИМ за полиномиальное время.

Этот результат опубликован в работе [А7].

В заключении в диссертации рассматривается вопрос о возможности определить часть ключа криптосистемы Мак-Элиса-Сидельникова по перестановке из множества 0.

Оказывается справедливым следующее утверждение.

Утверждение 0.3. Пусть Аи(В,М(г, т)) — это множество перестановок вида где 'у — это перестановка из Аи{11М(г, т)), а V — это произвольная перестановка блоков матрицы (-Н^-КЦ . \\Ни11). Справедливо равенство р| д{нъ .,ни) = Ли{ям(г, т)), (23)

Н!,.,ниеСЦк,2)

В случае и = 2 из утверждения следует, что наличие во множестве 6{Е,Н) перестановки, не являющейся расширенным автоморфизмом, особым образом характеризует матрицу Н, поэтому множество Н) в диссертации получило название С-структуры матрицы Н.

Для взлома криптосистемы Мак-Элиса-Сиделышкова необходимо по матрице (А11\\ВК)Г восстановить матрицы АиВи перестановку Г. Предположим, что злоумышленнику оказывается известной перестановка из множества (А, В). Как он может использовать это знание для восстановления ключа? Если обозначить через Н произведение матриц А~гВ, то, как доказывается в разделе 2.1, 0(А,В) = д(Е,Н), а значит знание перестановки из множества б (А, В) эквивалентно знанию перестановки из С-структуры матрицы Н.

Итак, пусть перестановка Г = Г/<^7[1]сг[2] не является расширенным автоморфизмом и принадлежит С-структуре некоторой невырожденной матрицы 22", здесь I = {гх, г2,., г^} С {1,2,., п} = .Л/", J = {к,32, • • •,Эй} £ Я, а Г7о./(гв) = п + д,, Г+ ¿3) = г5 для всех 5 = 1,2,., и Г/^Дг) = ъ для всех г ф гь., гв, п+Зъ-.Тогда в диссертации доказана следующая теорема.

Теорема 0.8. Используя перестановку Г = Г/077[1]сг[2]; можно построить ру+ру линейно независимых уравнений относительно п неизвестных НВ,\, НВ,2, .НЯп, здесь В^ — столбец с номером г пороо/с-дающей матрицы II кода Рида-Маллера Ш(г,т). Здесь I = ЛГ \ I,

J = N \ 3, Р2 — ранг матрицы , которая является подматрицей матрицы , то есть проверочной матрицы кода ЯМ(г, га), и состоит из столбцов с номерами из множества I, pJ — ранг матрицы щ.

Оказывается, что знание перестановки из (^-структуры, которая не является расширенным автоморфизмом, позволяет получить некоторое число линейных соотношений на матрицу Н, что позволяет восстановить часть ключа криптосистемы Мак-Элиса-Сидельникова. В силу этого понимание структуры классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидельникова может оказаться важным для её взлома. Кроме того, прослеживается связь перестановок из С-структуры с перестановками из группы автоморфизмов кода. При переходе к рассмотрению криптосистемы Мак-Элиса-Сидельникова от криптосистемы Мак-Элиса перестановки из С-структуры являются обобщением понятия автоморфизмов. Такое обобщение оказывается даже более полезным для криптоанализа модифицированной криптосистемы Мак-Элиса, нежели группа автоморфизмов для оригинальной, причина в том, что перестановки из (^-структуры дают систему линейных соотношений на элементы ключа криптосистемы Мак-Элиса-Сидельникова, в то время как автоморфизмы задают линейные соотношения, если они образуют группу со свойством транзитивности. Транзитивные группы автоморфизмов позволяют фиксировать ряд столбцов в матрице — элементе ключа криптосистемы.

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

В первом параграфе четвертой главы были рассмотрены задачи, связанные со стойкостью криптосистемы Мак-Элиса и Мак-Элиса-Сидель-никова. Была доказана полиномиальная эквивалентность задач взлома оригинальной криптосистемы Мак-Элиса, построенной на основе подпространств размерности (к — 1) кода Рида-Маллера, и криптосистемы Мак-Элиса-Сидельникова с ограничениями на ключевое пространство. Во втором параграфе рассматривалась возможность определения матрицы по её С-структуре. Оказалось, что знание перестановки из Ст-структуры, которая не лежит в С-структуре единичной матрицы, позволяет получить некоторое число линейных соотношений на матрицу. В силу этого понимание структуры классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сиделыгакова может оказаться важным для её взлома. Кроме того прослеживается связь перестановок из С-структуры с перестановками из группы автоморфизмов кода. При переходе к рассмотрению криптосистемы Мак-Элиса-Сидельникова от криптосистемы Мак-Элиса перестановки из С-структуры является обобщением понятия автоморфизмов. Такое обобщение оказывается даже более полезным для криптоанализа модифицированной криптосистемы Мак-Элиса, нежели группа автоморфизмов для оригинальной, так как перестановки из (?-структуры дают систему линейных соотношений на элементы ключа криптосистемы Мак-Элиса-Сидельникова, в то время как автоморфизмы задают линейные соотношения, если они образуют группу со свойством транзитивности. Транзитивные группы автоморфизмов позволяют фиксировать ряд столбцов в матрице — элементе ключа криптосистемы.

Заключение

В диссертационной работе рассматривалась одна из модификаций старейшей кодовой криптосистемы — криптосистема Мак-Элиса-Сидельникова, которая строится с использованием и-кратного повторения копии кода Рида-Маллера ДМ (г, т).

В работе изучались вопросы оценки числа открытых ключей криптосистемы Мак-Элиса-Сидельникова, структуры классов эквивалентности секретных ключей и полиномиальной эквивалентности задач взлома криптосистемы Мак-Элиса и Мак-Элиса-Сидельникова с ограничениями на ключевое пространство.

Вначале была получена оценка снизу на число открытых ключей криптосистемы Мак-Элиса-Сидельникова. Нижняя оценка позволяет определить насколько богато множество открытых ключей криптосистемы Мак-Элиса-Сидельникова для каждых конкретных значений параметров и, г, т. Так для предложенных В.М. Сидельниковым [1] значений и = 4, г = 3, т = 10, число открытых ключей будет не меньше, чем

1020897 < (4 34)

Тем самым число ключей в криптосистеме Мак-Элиса-Сидельникова достаточно велико, чтобы противостоять атаке полным перебором ключей.

Далее была исследована структура классов эквивалентности секретных ключей. Рассмотрены четыре случая. Первый случай не накладывает ограничения на число копий кода Рида-Маллера. В этом случае было получено описание классов эквивалентности с представителями вида НГ>2 - ■ •, НОи, Г)], где невырожденные матрицы £>1, £>2, • ■ ■ > Ни задают автоморфизмы кода Ш(г,ш), то есть для каждой матрицы £)г найдётся автоморфизм <Т{ такой, что

1Э{И — И(Т{.

В остальных рассмотренных случаях число копий кода Рида-Мал-лера было ограничено двумя, то есть и — 2. При этом рассматривались классы эквивалентности с представтелями [(Н, НТГ)], здесь I = {¿1, {г*2, - - -, V) — множество натуральных чисел таких, что

1 < Ч < г2 ^ . < гр к,

А — {а4, а4,., а1"} — множество двоичных наборов длины к, а матрица ТТд имеет вид

1 0 . Ч 4. о . 4. о . Ър 4. о . . 0

0 1 . . 0 . . 0 . . 0 . . 0

Ч а*1 «21 • . о?1 . ч . а1-1 . 12 Ър •

2 ~» «I2 42 . . а*2 . 11 а1-2 12 . а?2 . 1р • 42 гр а{ а2р . -V ^Р ■ аг1 ■ • <4. ' ар Ър • 4

0 0 . . 0 . . 0 . . 0 . . 1 (4.35)

При этом для того, чтобы такая матрица была невырождена необходимо наложить на элементы множества А дополнительное условие, а именно нужно потребовать невырожденность матрицы а. а а а а

4.36) Ш- 1Л- . СХ; Ч г2 гр у

В случае когда |/| = 1 было получено полное описание указанного класса эквивалентности. В другом случае было получено описание подмножества класса эквивалентности. Для описания структуры классов была предложена новая техника сведения исходной задачи описания структуры классов к описанию подстановок, осуществляющих перевод некоторого подпространства кода Рида-Маллера в некоторое другое подпространство того же кода.

В процессе получения описания структуры классов было введено множество подстановок С/, которое в случае и = 2 зависит от матрицы Н и является характеристикой этой матрицы. Это множество было названо (^-структурой матрицы Н относительно кода Рида-Маллера. В последнем параграфе диссертации было установлено, что подстановки С-структуры позволяют накладывать линейные ограничения на столбцы матрицы Н. В силу этого прослеживается связь подстановок из С-струк-туры с подстановками из группы автоморфизмов кода. При переходе к рассмотрению криптосистемы Мак-Элиса-Сидельникова от криптосистемы Мак-Элиса подстановки из С-структуры являются обобщением понятия автоморфизмов. Такое обобщение оказывается даже более полезным для криптоанализа модифицированной криптосистемы Мак-Элиса, нежели группа автоморфизмов для оригинальной, так как подстановки из С-структуры дают систему линейных соотношений на элементы ключа криптосистемы Мак-Элиса-Сидельникова, в то время как автоморфизмы задают линейные соотношения, если они образуют группу со свойством транзитивности. Транзитивные группы автоморфизмов позволяют фиксировать ряд столбцов в матрице — элементе ключа криптосистемы.

Кроме того в последней части диссертации был затронут вопрос полиномиальной эквивалентности задач взлома криптосистемы Мак-Элиса и криптосистемы Мак-Элиса-Сидельникова с ограничениями па ключевое пространство. А именно, была доказана эквивалентность задач тсЬШл и тсЭИМ. Задача тсИМл

Вход: Число т большее 2г и 1 ^ г ^ к, матрица в = Н' • В! ■ 7', где Н' — невырожденная двоичная (к — 1) х (к — 1)-матрица, Н! — ((к — 1) х п)-матрица, получающаяся из порождающей матрицы И. кода Рида-Маллера ЛМ(г, т) выкидыванием строки с номером г и 7' — перестановочная (п х п)-матрица.

Найти: Невырожденную матрицу М' размера (к — 1) х (к — 1) и перестановочную (п х п)-матрицу а' такие, что М' • Сг • а' — порождающая матрица кода 7?/, порождаемого матрицей И!, то есть найдётся невырожденная ((к — 1)х(к — 1))-матрица Ь', что выполнено равенство М' ■ <2 • а' = Ь' • Ш. Задача тсБКМ

Вход: Число т большее 2г, матрица С = (7?! • 11\\Н2 ■ И) • А, где Н\ и Нч — невырожденные двоичные (к х &)-матрицы, принадлежащие классу эквивалентности [(-КГ, НТг~, Г)] для некоторой невырожденной (к х А;)-матрицы Н, некоторой перестановочной (2та х 2та)-матрицы Г, некоторого числа 1 ^ г ^ к и некоторого вектора а, Н. — порождающая (к х п)-матрица кода Рида-Маллера ЯМ (г, таг) и Д — перестановочная (2та х 2та)-матрица.

Найти: Невырожденные матрицы -НГ^ и Н2 размера {к х к) и перестановочную (2та х 2та)-матрицу А' такие, что С? • А' = Н'2К).

Из результатов диссертации видно, что использование нескольких копий кода для построения криптосистемы Мак-Элиса приводит к тому, что появляется достаточно богатое множество ключей новой криптосистемы, использование которого не приводит к увеличению стойкости. Такие ключи можно считать «слабыми». Тем самым при использовании криптосистемы Мак-Элиса-Сидельникова необходимо генерировать ключи таким образом, чтобы они не попадали в описанные в диссертации классы.

Автор диссертации выражает благодарность своему научному руководителю кандидату физико-математических наук, доценту Карпунину Григорию Анатольевичу за неоценимую помощь, оказанную при подготовке диссертации, внимание к работе, ценные советы, постоянную поддержку и научное руководство.

Автор выражает искреннюю признательность Применко Эдуарду Андреевичу за неустанную поддержку и помощь в подготовке диссертации.