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

ИМЕНИ М.В. ЛОМОНОСОВА

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

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

Пространство ключей криптосистемы

Мак-Элиса–Сидельникова

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

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

АВТОРЕФЕРАТ

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

Москва – 2010

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

Научный руководитель: кандидат физико-математических наук, доцент Карпунин Григорий Анатольевич.

Официальные оппоненты: доктор физико-математических наук, доцент Куракин Владимир Леонидович;

кандидат физико-математических наук, доцент Черепнв Михаил Алексеевич.

е

Ведущая организация: Томский государственный университет.

Защита диссертации состоится «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 Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография — SIBECRYPT’09», 2009 год.

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

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

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

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

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

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

Криптосистема Мак-Элиса, как и все другие известные кодовые криптосистемы обладают одним важным преимуществом — высокой скоростью зашифрования и расшифрования. Однако, в подобных крип­ тосистемах имеется недостаток — относительно низкая скорость пере­ дачи (). Обычно у кодовых криптосистем < 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. Pless, W. C. Huffman. Amsterdam: Elsevier, 1998. Pp. 649–755.

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

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

В.М. Сидельников 6 в 1994 году рассмотрел возможность использо­ вания кодов Рида–Маллера для построения криптосистемы Мак-Элиса.

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

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

В первой главе описывается криптосистема Мак-Элиса–Сидельни­ кова. Эта криптосистема строится на основе -кратного использования кодов Рида–Маллера (, ). Всюду далее через = бу­ 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’s public-key cryptosystems // IEEE Transactions on Information Theory. 1994. Vol. 40. Pp. 271–273.

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

6 Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида-Маллера // Дискретная математика. 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, 2,..., — невырожденные матрицы размера над полем (2), которые выбираются случайно и равновероятно из множе­ ства всех двоичных невырожденных матриц размера. Матрица имеет размеры · · и является перестановочной, то есть в каждой её строчке и в каждом столбце стоит ровно одна единица, поэтому можно считать, что — это перестановка на множестве из элементов.

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

Датся следующее определение эквивалентности секретных ключей в криптосистеме Мак-Элиса–Сидельникова. Два секретных ключа называются эквивалентными, если соответствующие им открытые клю­ чи совпадают, то есть выполняется соотношение Введнное отношение является отношением эквивалентности. Тем самым, вс множество секретных ключей разбивается на классы эквива­ лентности и число классов эквивалентности совпадает с числом откры­ тых ключей. Класс эквивалентности с представителем ( 1,...,, ) будем обозначать так: [( 1,...,, )].

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

Рассмотрим множество ( 1, 2,..., ), состоящее из перестано­ вок, для которых существуют невырожденные двоичные матри­ Во второй главе доказано следующее утверждение.

Теорема. 2.1. Существует взаимно однозначное соответствие меж­ ду классом эквивалентности [( 1, 2,...,, )] секретных ключей При этом класс эквивалентности [( 1, 2,...,, )] состоит из ключей вида где принадлежит множеству ( 1, 2,..., ) и Тем самым вопрос изучения структуры классов эквивалентности секретных ключей сводится к изучению структуры множества переста­ новок.

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

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

Известно, что совокупность всех автоморфизмов кода относительно операции умножения перестановок является группой. Рассмотрим неко­ торую перестановку. Построим, используя е, «длинных»е перестановок [] следующим образом. Положим []() = []() = ( 1) + ( ( 1)), для всех. Другими словами, перестановка [] в -том блоке действует как перестановка, а во всех остальных блоках — как единичная перестановка. Тогда группой расши­ ренных автоморфизмов ( (, )) кода Рида–Маллера (, ) назовм множество всех возможных произведений описанных перестано­ вок [] для всех возможных 1 и всех возможных перестановок из группы автоморфизмов кода (, ).

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

Теорема. 2.2. Пусть невырожденные матрицы 1, 2,..., зада­ ют автоморфизмы 1, 2,..., кода (, ) соответственно, то есть для 1 выполнены равенства =. Обозначим через 1 [1], 2 [2],..., [] перестановки из ( (, )), соответствующие перестановкам 1,...,. И пусть — любая невырожденная мат­ рица.

Эта теорема дает описание множества ( 1,..., ). С помо­ щью не в диссертации доказана теорема, дающая описание ряда классов эквивалентности.

Теорема. 2.4. Пусть невырожденные матрицы 1, 2,..., зада­ ют автоморфизмы 1, 2,..., кода (, ) соответственно. Обо­ значим через 1 [1], 2 [2],..., [] перестановки из ( (, )), соот­ ветствующие перестановкам 1,...,. И пусть — любая невы­ рожденная матрица.

Тогда класс эквивалентности [( 1, 2...,, )] состоит из кортежей вида где 1, 2,..., задают автоморфизмы 1, 2,..., кода Рида–Мал­ лера (, ), 1 [1], 2 [2],..., [] — соответствующие этим авто­ морфизмам расширенные автоморфизмы, а перестановка со­ храняет матрицу (... ), то есть Следует отметить, что эта структурная теорема позволяет, в част­ ности, вычислить мощность каждого класса эквивалентности.

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

Теорема. 2.6. Справедливы неравенства для числа || открытых клю­ чей криптосистемы Мак-Элиса–Сидельникова здесь — длина кода Рида–Маллера (, ), используемого для по­ строения криптосистемы, — число блоков криптосистемы, число обратимых ( )-матриц над полем (2), и ( (, )) — группа автоморфизмов кода Рида–Маллера (, ).

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

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

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

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

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

Вначале вводится в рассмотрение следующий тип матриц. Пусть = {1, 2,..., } — множество натуральных чисел таких, что выпол­ = {1, 2,..., } — множество двоичных наборов длины. Рассмот­ бы такая матрица была невырождена необходимо наложить на элемен­ ты множества дополнительное условие, а именно нужно потребовать невырожденность матрицы Далее рассматривается два случая.

Рассматривается код Рида–Маллера (, ) с > 1, так как пол­ ное описание множества (, ) для кода (1, ) и всех матриц было найдено Г.А. Карпуниным 8.

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

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

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

Теорема. 3.5. Пусть (, ) — код Рида–Маллера такой, что и > 1, — натуральное число, большее нуля; — любая невырожденная двоичная матрица; — произвольный двоичный век­ тор длины, у которого в координате с номером стоит единица.

Тогда класс эквивалентности [(,, )] состоит из кортежей вида Здесь, — автоморфизмы кода Рида–Маллера (, ), соответ­ ствующие матрицам 1 и 2, а для перестановки выполняются два условия 1) Если — ( 1) -матрица, получающаяся удалением строки с номером из матрицы, то 2) Если — строка матрицы с номером, то Приведнная структурная теорема 3.5 дат не только описание клас­ сов, но с е помощью может быть вычислена мощность каждого класса эквивалентности.

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

Описание классов эквивалентности теперь сводится к задаче описания перестановок, которые переводят подпространство размерности кода Рида–Маллера (, ) в другое подпространство того же кода.

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

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

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

Теорема. 3.6. Пусть (, ) — код Рида–Маллера такой, что 2 + 1 <. Пусть также — любая невырожденная матрица размера. Далее, пусть существует перестановка 1 — пере­ становка из (, ), представимая в виде [1] [2], где такая перестановка, что здесь — ( ) -матрица, получающаяся удалением строк с но­ мерами из множества из матрицы. Тогда класс эквивалентности [,, ] содержит кортежи вида Здесь, — автоморфизмы кода Рида–Маллера (, ), соответ­ } — множества двоичных наборов длины, а для перестановки выполняется условие: если — строка матрицы с номером, то для любого должно выполняться соотношение Приведнная структурная теорема 3.6 дат не только описание под­ множества классов эквивалентности, но с е помощью может быть вычис­ лена мощность этих подмножеств, то есть может быть получена оценка снизу на мощность каждого класса эквивалентности.

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

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

Рассматриваются следующие задачи mcRMi и mcSRM.

Задача mcRMi где — невырожденная двоичная ( 1) ( 1)-матрица, — (( 1) )-матрица, получающаяся из порождающей матрицы ко­ да Рида–Маллера (, ) выкидыванием строки с номером и — перестановочная ( )-матрица.

Найти: Невырожденную матрицу размера ( 1) ( 1) и пе­ рестановочную ( )-матрицу такие, что · · — порожда­ ющая матрица кода, порождаемого матрицей, то есть найдтся е невырожденная (( 1) ( 1))-матрица, что выполнено равенство Отметим, что если mcRMi решается эффективно, то криптосисте­ ма Мак-Элиса на основе ( 1)-мерных подкодах кода Рида–Маллера (, ) эффективно взламывается.

Задача mcSRM Вход: Число большее 2, матрица = ( 1 · 2 · ) ·, где 1 и 2 — невырожденные двоичные ( )-матрицы, принадлежащие классу эквивалентности [(,, )] для некоторой невырожденной ( )-матрицы, некоторой перестановочной (2 2)-матрицы, некоторого числа 1 и некоторого вектора, — порождающая ( )-матрица кода Рида–Маллера (, ) и — перестановочная (2 2)-матрица.

Найти: Невырожденные матрицы 1 и 2 размера ( ) и переста­ новочную (2 2)-матрицу такие, что · = ( ).

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

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

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

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

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

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

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

Утверждение. 2.11 Пусть ( (, )) — это множество переста­ новок вида, где — это перестановка из ( (, )), а — это произвольная перестановка блоков матрицы ( 1... ). Спра­ ведливо равенство В случае = 2 из утверждения 2.11 следует, что наличие во мно­ жестве (, ) перестановки, не являющейся расширенным автомор­ физмом, особым образом характеризует матрицу, поэтому множество (, ) в диссертации получило название -структуры матрицы.

Для взлома криптосистемы Мак-Элиса–Сидельникова необходимо по матрице () восстановить матрицы и и перестановку. Предположим, что злоумышленнику оказывается известной переста­ новка из множества (, ). Как он может использовать это знание для восстановления ключа? Если обозначить через произведение матриц 1, то, как доказывается в разделе 2.1, (, ) = (, ), а зна­ чит знание перестановки из множества (, ) эквивалентно знанию перестановки из -структуры матрицы.

Итак, пусть перестановка = [1][2] не является расши­ ренным автоморфизмом и принадлежит -структуре некоторой невы­ Обозначим через дополнение к множеству, то есть =. Далее, если — порождающая ( )-матрица кода Рида–Маллера (, ), то через будем обозначать столбец с номером этой матрицы. Кроме является подматрицей матрицы, то есть проверочной матрицы кода (, ), и состоит из столбцов с номерами из множества.

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

Теорема. 4.1. Используя перестановку = [1][2], можно по­ строить + линейно независимых уравнений относительно неиз­ вестных 1, 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.