Содержание к диссертации
Введение
Глава 1. Сведения из теории кодирования и криптографии 29
1.1. Основные сведения из теории кодирования 29
1.2. Основные сведения из криптографии 49
1.3. Выводы к первой главе 62
Глава 2. Оценка снизу на число открытых ключей . 63
2.1. Структура множества открытых ключей в случае произвольного числа блоков и оценка числа открытых ключей . 63
2.2. Выводы ко второй главе 80
Глава 3. Структура множества открытых ключей в случае двух блоков 82
3.1. Пространство ключей криптосистемы Мак-Элиса-Сидель- никова с двумя блоками. Первый случай 82
3.2. Пространство ключей криптосистемы Мак-Элиса-Сидель- никова с двумя блоками. Второй случай 88
3.3. Перестановочная эквивалентность специального вида подпространств кода Рида-Маллера 93
3.4. Пространство ключей криптосистемы Мак-Элиса-Сидель- никова с двумя блоками. Второй случай. Продолжение 119
3.5. Пространство ключей криптосистемы Мак-Элиса-Сидель- никова с двумя блоками. Третий случай 125
3.6. Выводы к третьей главе 136
Глава 4. Задачи, связанные со стойкостью криптосистемы Мак-Э лиса—Сидельникова 138
4.1. Полиномиальная эквивалентность задач взлома криптосистемы Мак-Элиса и криптосистемы Мак-Элиса-Сидельни- кова с ограничениями на ключевое пространство 138
4.2. Определение матрицы по перестановке из ее С-структуры 147
4.3. Выводы к четвертой главе 158
Заключение 160
Список публикаций 165
Цитированная литература 167
- Структура множества открытых ключей в случае произвольного числа блоков и оценка числа открытых ключей
- Пространство ключей криптосистемы Мак-Элиса-Сидель- никова с двумя блоками. Второй случай
- Пространство ключей криптосистемы Мак-Элиса-Сидель- никова с двумя блоками. Второй случай. Продолжение
- Определение матрицы по перестановке из ее С-структуры
Введение к работе
Актуальность работы определяется потребностью в исследовании альтернативных традиционным криптосистем с открытым ключом. Бурное развитие теории чисел за последние 5 лет позволило значительно снизить стойкость RSA — широко распространённой на практике криптосистемы с открытым ключом. Это диктует необходимость в исследовании других криптосистем с открытым ключом с целью поиска альтернатив криптосистеме RSA. Одной из таких альтернатив являются кодовые криптосистемы, то есть криптосистемы, основанные на задачах из теории кодов, исправляющих ошибки. В основе кодовых криптосистем лежит идея использования быстро декодируемых кодов, исправляющих ошибки, в качестве основного элемента шифрующего преобразования. В настоящее время широкую известность получили две кодовые криптосистемы — криптосистема Мак-Элиса и криптосистема Нидеррайтера, оригинальные версии которых используют коды Гоппы и расширенные коды Рида-Соломона, соответственно. В.М. Сидельников и СО. Шеста-ков показали несостоятельность идеи использования для построения кодовых криптосистем расширенных кодов Рида-Соломона, так как в этом случае такие криптосистемы не будут стойкими.
Кодовые криптосистемы имеют особенность, которая отличает их от многих других криптосистем. В кодовых криптосистемах одному и тому же открытому ключу могут соответствовать несколько секретных ключей, и поэтому секретные ключи могут быть разбиты на классы эквивалентности. При этом вопрос строения этих классов эквивалентности для кодовых криптосистем оказывается важным. Так атака В.М. Сидель-никова и СО. Шестакова использует строение ключевого пространства кодовой криптосистемы для вскрытия криптосистемы Мак-Элиса на основе обобщённых кодов Рида-Соломона. Следовательно, в некоторых случаях структура пространства ключей кодовой криптосистемы может помочь в её криптоанализе.
Атака В.М. Сидельникова и СО. Шестакова показала невозможность использовать расширенные коды Рида-Соломона для построения кодовых криптосистем, поэтому в 1994 году В.М. Сидельников предложил использовать для построения кодовых криптосистем коды Рида-Маллера, которые позволяют увеличить как скорость расшифрования криптограммы, так и скорость передачи криптосистемы. Кроме того, В.М. Сидельников предложил усиленный вариант криптосистем
Мак-Элиса, в конструкции которой используется не одна копия кода, а некоторое число и копий кода, число и становится параметром криптосистемы. Такая криптосистема в диссертации получила название криптосистемы Мак-Элиса-Сидельникова. До недавнего времени ключевое пространство усиленного варианта кодовых криптосистем на основе кодов Рида-Маллера оставалось полностью не изученным. Диссертация посвящена исследованию структуры множества ключей криптосистемы Мак-Элиса-Сидельникова и разработке методов использования структуры этого множества в криптоанализе криптосистемы Мак-Элиса-Сидельникова, что, с учётом представленных выше соображений, свидетельствует об её актуальности и практической значимости. Цель диссертационной работы заключается:
в получении оценок на число открытых ключей криптосистемы Мак-Элиса-Сидельникова;
в исследовании структуры множества отрытых ключей криптосистемы Мак-Элиса-Сидельникова;
в разработке методов, позволяющих использовать сведения о структуре открытых ключей криптосистемы Мак-Элиса-Сидельникова для криптоанализа такого вида криптосистем.
Научная новизна.
Получена нижняя оценка на мощность множества открытых ключей криптосистемы Мак-Элиса-Сидельникова, которая позволила заключить, что число ключей криптосистемы достаточно велико, чтобы противостоять атаке на криптосистему полным перебором по всему множеству открытых ключей.
Установлена связь классов эквивалентности секретных ключей со специально введенным множеством перестановок. Это множество перестановок является в некотором смысле обобщением группы автоморфизмов кодов.
В случае использования произвольного числа копий кода Рида-Маллера описывается ряд классов эквивалентности секретных ключей.
Задача изучения некоторых классов эквивалентности секретных ключей сведена к изучению перестановочной эквивалентности особого вида подпространств кода Рида-Маллера и описаны все перестановки, которые переводят подпространство особого вида в некоторое другое подпространство кода Рида-Маллера. С использованием описания перестановок были получены описания ряда классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидельникова.
Доказана полиномиальная эквивалентность некоторых задач, связанных со стойкостью криптосистемы Мак-Элиса—Сидельникова, и задачи взлома оригинальной криптосистемы Мак-Элиса на основе подкодов кода Рида-Маллера, размерность которых на единицу меньше размерности кода, а также была доказана возможность восстановления части секретного ключа криптосистемы Мак-Элиса-Сидельникова, используя знание структуры класса эквивалентности, в который попадает секретный ключ.
Практическая значимость. Работа носит теоретический характер. Вместе с тем, полученные при её выполнении результаты могут найти применение: в синтезе и криптоанализе кодовых криптосистем; при изучении перестановочной эквивалентности подпространств кодов; при изучении свойств кодов, исправляющих ошибки, полученных из других кодов операцией комбинирования; в учебном процессе.
На защиту выносятся следующие основные результаты и положения:
нижняя оценка мощности множества открытых ключей криптосистемы Мак-Элиса-Сидельникова;
описание ряда классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидельникова для произвольного числа блоков кода Рида-Маллера;
описание классов эквивалентности с представителями особого вида в случае криптосистемы с двумя блоками;
метод восстановления части секретного ключа криптосистемы Мак-Элиса-Сидельникова, использующий знание структуры класса эквивалентности, в который попадает секретный ключ;
доказательство полиномиальной эквивалентности задачи взлома
оригинальной криптосистемы Мак-Элиса, построенной на основе
подкодов кода Рида-Маллера, размерность которых на единицу
меньше размерности кода, и задачи взлома криптосистемы Мак-
Элиса-Сидельникова с ограничениями на ключевое пространство.
Апробация работы
Результаты работы докладывались:
на семинаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета Вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова;
на VII общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2009), 2009 год
на VI общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2008), 2008 года;
на V общероссийской научной конференции «Математика и безопасность информационных технологий» (МаБИТ-2007), 2007 год;
на VII международной конференции «Дискретные модели в теории управляющих систем», 2006 год;
на VIII Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография — SIBE-CRYPT09», 2009 год.
Публикации. Основное содержание диссертации опубликовано в 7 работах, список которых приведён в конце автореферата [1]—[7]. Работ, написанных в соавторстве, нет.
Личный вклад автора заключается в проведённом им исследовании пространства ключей криптосистемы Мак-Элиса-Сидельникова, в получении описаний структуры классов эквивалентности секретных ключей криптосистемы, а также в исследовании возможности применения знаний структуры этих классов в криптоанализе криптосистемы Мак-Элиса-Сидельникова.
Структура и объем диссертации Диссертационная работа, общим объёмом 170 страниц, состоит из введения, четырёх глав и заключения. Список литературы включает 34 наименования.
Структура множества открытых ключей в случае произвольного числа блоков и оценка числа открытых ключей
Кодовые криптосистемы имеют особенность, которая отличает их от многих других криптосистем. В кодовых криптосистемах одному и тому же открытому ключу могут соответствовать несколько секретных ключей, и поэтому секретные ключи могут быть разбиты на классы эквивалентности. При этом вопрос строения этих классов эквивалентности для кодовых криптосистем оказывается важным. Так атака В.М. Сидель- никова и С.О. Шестакова использует строение ключевого пространства кодовой криптосистемы для вскрытия криптосистемы Мак-Элиса на основе обобщённых кодов Рида-Соломона. Следовательно, в некоторых случаях структура пространства ключей кодовой криптосистемы может помочь в её криптоанализе.
Атака В.М. Сидельникова и С.О. Шестакова показала невозможность использовать расширенные коды Рида-Соломона для построения кодовых криптосистем, поэтому в 1994 году В.М. Сидельников предложил использовать для построения кодовых криптосистем коды Рида-Мал- лера, которые позволяют увеличить как скорость расшифрования криптограммы, так и скорость передачи криптосистемы. Кроме того, В.М. Сидельников предложил усиленный вариант криптосистем Мак-Элиса, в конструкции которой используется не одна копия кода, а некоторое число и копий кода, число и становится параметром криптосистемы. Такая криптосистема в диссертации получила название криптосистемы Мак- Элиса-Сидельникова. До недавнего времени ключевое пространство усиленного варианта кодовых криптосистем на основе кодов Рида-Маллера оставалось полностью не изученным. Диссертация посвящена исследованию структуры множества ключей криптосистемы Мак-Элиса-Сидель- никова и разработке методов использования структуры этого множества в криптоанализе криптосистемы Мак-Элиса-Сидельникова.
Цель диссертационной работы заключается: 1) в получении оценок на число открытых ключей криптосистемы Мак-Элиса-Сидельникова; 2) в исследовании структуры множества отрытых ключей криптосистемы Мак-Элиса-Сидельникова; 3) в разработке методов, позволяющих использовать сведения о структуре открытых ключей криптосистемы Мак-Элиса-Сидельникова для криптоанализа такого вида криптосистем. Научная новизна. 1) Получена нижняя оценка на мощность множества открытых ключей криптосистемы Мак-Элиса-Сидельникова, которая позволила заключить, что число ключей криптосистемы достаточно велико, чтобы противостоять атаке на криптосистему полным перебором по всему множеству открытых ключей. 2) Установлена связь классов эквивалентности секретных ключей со специально введенным множеством перестановок. Это множество перестановок является в некотором смысле обобщением группы автоморфизмов кодов. 3) В случае использования произвольного числа копий кода Рида- Маллера описывается ряд классов эквивалентности секретных ключей. 4) Задача изучения некоторых классов эквивалентности секретных ключей сведена к изучению перестановочной эквивалентности особого вида подпространств кода Рида-Маллера и описаны все перестановки, которые переводят подпространство особого вида в некоторое другое подпространство кода Рида-Маллера. С использованием описания перестановок были получены описания ряда классов эквивалентности секретных ключей криптосистемы Мак-Элиса-Сидель- никова. 5) Доказана полиномиальная эквивалентность некоторых задач, связанных со стойкостью криптосистемы Мак-Элиса—Сидельникова, и задачи взлома оригинальной криптосистемы Мак-Элиса на основе подкодов кода Рида-Маллера, размерность которых на единицу меньше размерности кода, а также была доказана возможность восстановления части секретного ключа криптосистемы Мак- Элиса-Сидельникова, используя знание структуры класса эквивалентности, в который попадает секретный ключ. Практическая значимость. Работа носит теоретический характер. Установлена оценка снизу на число открытых ключей криптосистемы Мак-Элиса-Сидельникова, которая позволяет заключить, что число в криптосистема Мак-Элиса-Сидельникова достаточно велико, чтобы противостоять атаке полного перебора по всему множеству ключей. Описана структура ряда классов эквивалентностей секретных ключей криптосистемы Мак-Элиса-Сидельникова. Доказана полиномиальная эквивалентность задачи взлома криптосистемы Мак-Элиса и задачи взлома криптосистемы Мак-Элиса-Сидельникова с ограничениями на ключевое пространство.
Пространство ключей криптосистемы Мак-Элиса-Сидель- никова с двумя блоками. Второй случай
В главе 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] рассматривается некоторое усиление криптосистемы Мак-Элиса на основе кодов Рида-Маллера — криптосистема Мак-Элиса-Сидельникова.
Пространство ключей криптосистемы Мак-Элиса-Сидель- никова с двумя блоками. Второй случай. Продолжение
Теория кодов, исправляющих ошибки, обязана своему появлению классическим работам Клода Шеннона. В 50-е года XX века в связи с появлением работ Шеннона возник большой поток исследований, по- свящённых построению эффективных схем кодирования информации для передачи по реальным каналам с шумами. С практической точки зрения существенные ограничения на все схемы кодирования и декодирования дискретных данных накладываются не шенноновской пропускной способностью, а сложностью самого декодера. Именно поэтому основые усилия направлялись на построение легко реализуемых на практике алгоритмов кодирования и декодирования. Новый подход к решению проблемы был найден в фундаментальных работах Киясу (1957) и Слепяна (1956), Рида и Соломона (1960), Хоквингема (1959), Боуза и Чоудхури (1960), Горенстейна и Цирлера (1961) и Питерсона (1961). Именно работы этих исследователей фактически положили начало новой области математики — теории кодов, исправляющих ошибки.
Коды, исправляющие ошибки, можно рассматривать фактически над любым алфавитом. Однако наиболее удобным оказывается алфавит, представляющий собой поле Галуа. В этом случае можно свести задачи кодирования и декодирования к решению алгебраических уравнений. Развитие компьютерной техники привело к тому, что наиболее часто стали рассматриваться коды над алфавитом — полем Галуа характеристики 2.
В самом общем случае кодом над некоторым алфавитом называется любое множество слов над этим алфавитом. Но такое понимание кода является очень широким, а поэтому сложным для исследования. В силу этого обычно исследуются коды, обладающие некоторым свойством. Например, таким свойством является линейность. Линейные коды, т. е. коды, которые образуют линейное пространство над некоторым полем Галуа, на сегодняшний день изучены наиболее полно по сравнению с другими классами кодов.
В диссертации рассматриваются только линейные коды. Линейные коды впервые появились в работах Киясу [17] и Слепя- на [18]. В силу того, что эти коды образуют такую хорошо изученную структуру как линейное пространство, они стали основным объектом исследований. Линейные коды могут быть определены над любым конечным полем, однако в диссертации рассматриваются только коды над полем из двух элементов. Такие коды иногда называют двоичными. Дадим определение двоичного линейного блокового кода. Определение 1. Пусть (7.Р(2) — поле Галуа порядка 2 и Уп — линейное пространство над полем 2) размерности п. Тогда двоичным линейным блоковым кодом называется линейное А;-мерное подпространство С пространства Уп. При этом к называется размерностью кода, а п его длиной. Иногда код размерности к и длины п будем называть [п, /г]-кодом. В силу того, что линейный код С является линейным конечномерным пространством, то в коде всегда можно выбрать конечный базис векторов этого пространства. При этом любой вектор из С можно представить как линейную комбинацию векторов базиса. Это замечание подводит к определению порождающей матрицы кода С. Определение 2. Двоичная (к х гг)-матрица строками которой являются векторы базиса кода С, называется пороо/сдающей матрицей кода С. Отметим общеизвестный факт. Очевидно, что для любого кодового вектора х кода С найдётся вектор о: длины к такой, что х = а - 6?. (1.1) Для изучения свойств кода важным оказывается рассмотрение скалярного произведения, определённого на двоичных векторах. Определение 3. Пусть ж = (жь гс2, , хп) и у = (уъ у2,..., уп) — векторы над полем 2). Тогда скалярным произведением векторов ж и у называется число (ж, у) е 6?-Р(2) Здесь 0 — сумма по модулю 2. Скалярное произведение принимает только два значения — 0 и 1. Легко заметить, что при таком определении скалярного произведения скалярный квадрат ненулевого вектора ж, у которого чётное число координат равны единице, обращается в ноль, другими словами для ж ф- О может случиться так, что (ж, ж) = 0. В теории кодирования важнейшими оказываются такие понятия как расстояние Хэмминга или просто расстояние между векторами и вес Хэм- минга или просто вес вектора. Определение 4. Расстоянием Хэмминга рн(х,у) или просто расстоянием р{ж, у) между двумя векторами ж и у называется число координат, в которых эти векторы отличаются. Векторы, скалярное произведение которых, равно нулю принято называть ортогональными. Определение 5. Весом Хэмминга к;#(ж) или просто весом т1(х) вектора ж называется число ненулевых координат этого вектора. Введём кроме всего прочего естественный частичный порядок на множестве двоичных векторов длины п. Будем говорить, что для векторов ж и у выполнено неравенство ж г/, если для любого номера г выполнено неравенство Xi i/г- При этом, если для векторов х и у не выполняется ни неравенство х у, ни обратное неравенство у х, то будем считать, что такие векторы несравнимы. Сформулируем в виде теоремы важные свойства скалярного произведения, расстояния и веса.
Определение матрицы по перестановке из ее С-структуры
Расцвет криптографии и формирование криптоанализа, а также самой криптографии как науки пришёлся на вторую половину XX века.
В 1949 году появляется работа Клода Шеннона «Теория связи в секретных системах» (см. [21], стр. 333-369), которая фактически положила начало криптографии как науки. В этой работе К. Шеннон вводит в рассмотрение так называемое «перемешивающее преобразование». Кроме того, там же определяются такие важные в современной криптографии понятия, как «перемешивания» и «рассеивания». Хорст Файстель — создатель первого блокового шифра — при построении шифра Люцифер использовал принципы, заложенные Шеннонам. К. Шеннон помимо прочего формализует знаменитый принцип Керкхоффса — «Функции шифрования и расшифрования общеизвестны, тайна сообщения при известном шифртексте зависит только от ключа шифрования». Именно в это время появляется понятие криптосистемы с секретным ключом.
Работа криптосистемы с секретным ключом включает в себя два преобразования: С = Е т) и т — / (С), где т — открытый текст, С — шифрованный текст, Е — функция шифрования, И — функция расшифрования и к — секретный ключ.
В 1976 году Уитфилд Диффи и Мартин Хэллман публикуют революционную для всей криптографии статью «New Directions in Cryptography» [22]. В статье говорится о возможности создания принципиально нового метода шифрования. Именно эта работа положила основу для создания криптографии с открытым ключом. Кроме того, У. Диффи и М. Хэллман предложили метод выработки одного и того же секретного ключа абонентами по открытому каналу, тем самым облегчив процедуру распределения ключей в криптосистемах с секретным ключом. Работа криптосистемы с открытым ключом включает в себя два преобразования: E}Zc(т) = С и D}Zd(C) = m, где т — открытый текст, С — шифрованный текст, Е — функция шифрования, D — функция расшифрования и ке — открытый ключ, а к — секретный ключ. При этом ключ ке получается некоторым образом из ключа kd так, что восстановить ключ kd по ключу ке — трудная задача. Предложенная У. Диффи и М. Хэллманом криптосистема с открытым ключом была не реализуема на практике. В 1978 году Рон Ривест, Ади Шамир и Леонард Адлеман [23] предложили первую практическую криптосистему с открытым ключом — криптосистему RSA. Стойкость этой криптосистемы базируется на сложности решения задачи факторизации чисел. В том же году Р. Дж. Мак-Элис[3] предложил еще одну криптосистему с открытым ключом на основе идей Шеннона о помехоустойчивом кодировании. Стойкость этой задачи основана на предположении сложности некоторых задач, возникающих в теории кодов, исправляющих ошибки. Именно рассмотрению этой криптосистемы посвящён следующий раздел. Криптосистема Мак-Элиса — одна из старейших криптосистем с открытым ключом. Она была предложена в 1978 Р. Дж. Мак-Элисом [3]. Эта криптосистема основывается на NP-трудной проблеме в теории кодирования. Основная идея её построения состоит в маскировке некоторого кода, имеющего эффективные алгоритмы декодирования, под код, не обладающий видимой алгебраической и комбинаторной структурой, такие коды принято называть кодами общего положения. Эта криптосистема обладает одним важным преимуществом — высокой скоростью зашифрования и расшифрования. Опишем устройство криптосистемы с открытым ключом, предложенной Р. Дж. Мак-Элисом [3]. Пусть С — некоторый линейный код с параметрами [п, к, d] над конечным полем GjF(2), который имеет эффективные алгоритмы декодирования, G — его порождающая матрица размера к х п, H — невырожденная к х к матрица и 7 — перестановочная матрица размера п х п. Секретным ключом в данной схеме является тройка (JET, G, 7), а открытым ключом — матрица G = Н G 7. В оригинальной криптосистеме Мак-Элиса [3] матрица G выбирается случайно из множества всех порождающих матриц некоторого класса линейных кодов, например кодов Гоппы, с заданными параметрами. Следует отметить, что иногда в секретный ключ не включается матрица G, а она фиксируется и сообщается всем абонентам по открытому каналу. Это связано с тем, что используемый класс линейных кодов, например, код Рида-Маллера RM (г, m), состоит из одного единственного кода. Именно такая криптосистема рассматривается в работах В. М. Сидельникова [1], В. М. Сидельникова и С. О. Шестакова [7]. Опишем алгоритм зашифрования. На его вход подаётся открытое сообщение га, которое является -мерным вектором над полем 2). На выходе алгоритма образуется п-мерный вектор с, который и является криптограммой открытого сообщения.
