Корректность алгоритма

Покажем, что выполняется главное свойство криптосистемы, т.е что

Боб посылает . Алиса вычисляет . Поскольку — матрица перестановки, то вес не более, чем .

Код Гоппа исправляет до ошибок. Расстояние Хемминга . Поэтому Алиса получает верное сообщение . После этого Алиса вычисляет исходное сообщение .

1. Ко́ ды Хэ́ мминга — вероятно, наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Построены применительно к двоичной системе счисления. Позволяет исправлять одиночную ошибку (ошибка в одном бите) и находить двойную^[1].

Названы в честь американского математика Ричарда Хэмминга, предложившего их.

Систематические коды образуют большую группу из блочных, разделимых кодов (в которых все символы слова можно разделить на проверочные и информационные). Особенностью систематических кодов является то, что проверочные символы образуются в результате линейных операций над информационными символами. Кроме того, любая разрешенная кодовая комбинация может быть получена в результате линейных операций над набором линейно независимых кодовых комбинаций.

Коды Хэмминга являются самоконтролирующимися кодами, то есть кодами, позволяющими автоматически обнаруживать ошибки при передаче данных. Для их построения достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру этого разряда так, чтобы общее количество единиц в изображении любого числа было, например, нечетным. Одиночная ошибка в каком-либо разряде передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок.

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

Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно. Как видно из дальнейшего, количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенство или , где m — количество основных двоичных разрядов кодового слова. Минимальные значения k при заданных значениях m, найденные в соответствии с этим неравенством, приведены в таблице.

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

Основными характеристиками самокорректирующихся кодов являются:

1. Число разрешенных и запрещенных комбинаций. Если n — число символов в блоке, r — число проверочных символов в блоке, k — число информационных символов, то — число возможных кодовых комбинаций, — число разрешенных кодовых комбинаций, — число запрещенных комбинаций.

2. Избыточность кода. Величину называют избыточностью корректирующего кода.

3. Минимальное кодовое расстояние. Минимальным кодовым расстоянием d называется минимальное число искаженных символов, необходимое для перехода одной разрешенной комбинации в другую.

4. Число обнаруживаемых и исправляемых ошибок. Если g — количество ошибок, которое код способен исправить, то необходимо и достаточно, чтобы

5. Корректирующие возможности кодов.

Граница Плоткина даёт верхнюю границу кодового расстояния или при

Граница Хемминга устанавливает максимально возможное число разрешенных кодовых комбинаций где — число сочетаний из n элементов по i элементам. Отсюда можно получить выражение для оценки числа проверочных символов: Для значений разница между границей Хемминга и границей Плоткина невелика.

Граница Варшамова — Гильберта для больших n определяет нижнюю границу числа проверочных символов Все вышеперечисленные оценки дают представление о верхней границе d при фиксированных n и k или оценку снизу числа проверочных символов

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

. — ошибки нет, однократная ошибка. Такой код называется или . Первое число — количество элементов последовательности, второе — количество информационных символов. Для каждого числа проверочных символов существует классический код Хэмминга с маркировкой то есть — . При иных значениях k получается так называемый усеченный код, например международный телеграфный код МТК-2, у которого . Для него необходим код Хэмминга , который является усеченным от классического . Для Примера рассмотрим классический код Хемминга . Сгруппируем проверочные символы следующим образом:

знак здесь означает сложение по модулю 2.

Получение кодового слова выглядит следующим образом:

=

На вход декодера поступает кодовое слово где штрихом помечены символы, которые могут исказиться в результате помехи. В декодере в режиме исправления ошибок строится последовательность синдромов:

называется синдромом последовательности.

Получение синдрома выглядит следующим образом:

=

Кодовые слова кода Хэмминга

Синдром указывает на то, что в последовательности нет искажений. Каждому ненулевому синдрому соответствует определенная конфигурация ошибок, которая исправляется на этапе декодирования. Для кода в таблице указаны ненулевые синдромы и соответствующие им конфигурации ошибок (для вида: ).

Синдром
Конфигурация ошибок
Ошибка в символе

Предположим, что нужно сгенерировать код Хемминга для некоторого информационного кодового слова. В качестве примера возьмём 15-битовое кодовое слово x ₁… x ₁₅, хотя алгоритм пригоден для кодовых слов любой длины. В приведённой ниже таблице в первой строке даны номера позиций в кодовом слове, во второй — условное обозначение битов, в третьей — значения битов.

Вставим в информационное слово контрольные биты r ₀… r ₄ таким образом, чтобы номера их позиций представляли собой целые степени двойки: 1, 2, 4, 8, 16… Получим 20-разрядное слово с 15 информационными и 5 контрольными битами. Первоначально контрольные биты устанавливаем равными нулю. На рисунке контрольные биты выделены розовым цветом.

В общем случае количество контрольных бит в кодовом слове равно двоичному логарифму числа, на единицу большего, чем количество бит кодового слова (включая контрольные биты); логарифм округляется в большую сторону. Например, информационное слово длиной 1 бит требует двух контрольных разрядов, 2-, 3- или 4-битовое информационное слово — трёх, 5…11-битовое — четырёх, 12…26-битовое — пяти и т. д.

Добавим к таблице 5 строк (по количеству контрольных битов), в которые поместим матрицу преобразования. Каждая строка будет соответствовать одному контрольному биту (нулевой контрольный бит — верхняя строка, четвёртый — нижняя), каждый столбец — одному биту кодируемого слова. В каждом столбце матрицы преобразования поместим двоичный номер этого столбца, причём порядок следования битов будет обратный — младший бит расположим в верхней строке, старший — в нижней. Например, в третьем столбце матрицы будут стоять числа 11000, что соответствует двоичной записи числа три: 00011.

В правой части таблицы мы оставили пустым один столбец, в который поместим результаты вычислений контрольных битов. Вычисление контрольных битов производим следующим образом. Берём одну из строк матрицы преобразования (например, r₀) и находим её скалярное произведение с кодовым словом, то есть перемножаем соответствующие биты обеих строк и находим сумму произведений. Если произведение получилось больше единицы, находим остаток от его деления на 2. Иными словами, мы подсчитываем сколько раз в кодовом слове и соответствующей строке матрицы в одинаковых позициях стоят единицы и берём это число по модулю 2.

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

Например, для строки r₀:

r₀ =(1·0+0·0+1·1+0·0+1·0+0·0+1·1+0·0+1·0+0·0+1·1+0·0+1·1+0·1+1·1+0·0+1·0+0·0+1·0+0·1) mod 2 = 5 mod 2 = 1.

Полученные контрольные биты вставляем в кодовое слово вместо стоявших там ранее нулей. Кодирование по Хэммингу завершено. Полученное кодовое слово — 11110010001011110001.

Алгоритм декодирования по Хэммингу абсолютно идентичен алгоритму кодирования. Матрица преобразования соответствующей размерности умножается на матрицу-столбец кодового слова и каждый элемент полученной матрицы-столбца берётся по модулю 2. Полученная матрица-столбец получила название «матрица синдромов». Легко проверить, что кодовое слово, сформированное в соответствии с алгоритмом, описанным в предыдущем разделе, всегда даёт нулевую матрицу синдромов.

Матрица синдромов становится ненулевой, если в результате ошибки (например, при передаче слова по линии связи с шумами) один из битов исходного слова изменил своё значение. Предположим для примера, что в кодовом слове, полученном в предыдущем разделе, шестой бит изменил своё значение с нуля на единицу (на рисунке обозначено красным цветом). Тогда получим следующую матрицу синдромов.

Заметим, что при однократной ошибке матрица синдромов всегда представляет собой двоичную запись (младший разряд в верхней строке) номера позиции, в которой произошла ошибка. В приведённом примере матрица синдромов (01100) соответствует двоичному числу 00110 или десятичному 6, откуда следует, что ошибка произошла в шестом бите.

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

Алиса выбирает матрицу

и матрицу перестановки

Тогда

Если Боб хочет послать сообщение Алисе, то он сначала генерирует вектор с весом , например и вычисляет шифротекст и посылает его Алисе.

После получения сообщения, Алиса сначала вычисляет , где

получая .

После этого Алиса расшифровывает используя быстрый алгоритм декодирования (в этом примере — алгоритм Хэмминга. Синдромом является , таким образом ошибка произошла в позиции (подробности опущены). Тогда сообщение будет . получается путем отбрасывания лишних битов у . Вследствие «правильного» выбора , Алиса знает, что и может теперь получить из путем умножения на матрицу

В итоге Алиса получает

Описано достаточно большое количество атак на McElice. Некоторые атаки, называемые структурными атаками, основаны на получении закрытого ключа из открытого ^[7]. Другие атаки направлены на получения исходного текста сообщения из шифрованного сообщения. Большинство из них основаны на декодировании множества данных (ISD (англ.)) или на алгоритме Дня Рождения, их обобщениях и улучшениях. Существуют такие атаки, как, например, итерационное декодирование ^[8] и статическое декодирование, но они не являются успешными. Атака ISD оказалась наименее сложной. В последние годы было описано несколько алгоритмов и их улучшения. Наиболее важные перечислены в таблице вместе с их двоичным показателем затрат для декодирования (1024, 524, 50) кода Гоппа(стандартные параметры для McEliece^[1]). Для этих алгоритмов известны их предельные показатели ^[9].

Год	Алгоритм	Сложность ()
	Адамс-Мейер	80, 7
	Ли-Брикелл	70, 89
	Штерн	66, 21
	Кантеаут-Шабанн	65, 5
	Кантеаут-Шабант	64, 1
	Бернштейн-Ланг-Петерс	60, 4
	Финиаз-Сендреир	59, 9

Основные недостатки криптосистемы McEliece:

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

Безопасность McEliece в зависимости от параметров
Степень защиты	Параметры , кол-во ошибок	Размер открытого ключа в Кбит	Размер секретного ключа в Кбит
Краткосрочная (60 бит)	(1024, 644, 38), 38		(0, 38, 10, 405)
Среднесрочная (80 бит)	(2048, 1751, 27), 27	3, 502	(0, 30, 22, 2994)
Долгосрочная (256 бит)	(6624, 5129, 115), 117	33, 178	(1, 47, 104, 25690)

Зашифрованное сообщение гораздо длиннее исходного. Увеличение полосы пропускания канала делает систему более подверженной ошибкам при передаче сообщения.

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

Криптосистема Мак-Элиса — одна из старейших криптосистем с открытым ключом. Она была предложена в 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. 7

/такие записи идут в конец содержания в виде литературы. Просто ссылайтесь на них, указывая очередной порядковый номер.. Ниже тоже такие ссылки встретитлись/сти вычислительных систем низкая скорость передачи кодовых систем может перестать быть существенным недостатком, сдерживающим использование этих криптосистем на практике. В 1986 году Нидеррайтер 3 предложил модификацию криптосисте­ мы Мак-Элиса, которая получила название криптосистемы Нидеррайте­ ра. Криптосистема Мак-Элиса и криптосистема Нидеррайтера, постро­ енные на основе одних и тех же кодов, например, кодов Гоппы, с точки зрения стойкости являются эквивалентными4. В той же работе 3 ав­ тор предлагает использовать для построения как новой криптосистемы, так и криптосистемы Мак-Элиса обобщ¨ енные коды Рида–Соломона. В 1992 году В.М. Сидельников и С.О. Шестаков показали, что использо­ вание обобщ¨ енных кодов Рида–Соломона для построения криптосистем Мак-Элиса и Нидеррайтера делает эти криптосистемы нестойкими5. При этом атака В.М. Сидельникова и С.О. Шестакова использует для взлома знание свойств структуры классов эквивалентности секретных ключей. В.М. Сидельников 6 в 1994 году рассмотрел возможность использо­ вания кодов Рида–Маллера для построения криптосистемы Мак-Элиса. Он пров¨ ел криптографический анализ такой криптосистемы. Результаты показали, что криптосистема Мак-Элиса на основе кодов Рида–Маллера не обеспечивает достаточной стойкости. Кроме того в 2007 году Л. Мин­ дер в работе7 усилил атаку В.М. Сидельникова, однако она оста¨ ется до сих пор неполиномиальной. В той же работе 6 рассматривается некото­ рое усиление криптосистемы Мак-Элиса на основе кодов Рида–Малле­ ра — криптосистема Мак-Элиса–Сидельникова. В диссертации исследуются вопросы, связанные со структурой клас­ сов эквивалентности секретных ключей, то есть секретных ключей, по­ рождающих одинаковые открытые ключи, новой криптосистемы. В первой главе описывается криптосистема Мак-Элиса–Сидельни­ кова. Эта криптосистема строится на основе -кратного использования кодов Рида–Маллера 𝑅 𝑀 (𝑟, 𝑚). Всюду далее через 𝑘 = ∑ ︀ 𝑟 𝑖 =0 (︀ 𝑚 𝑖)︀ бу­ 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. 8 дет обозначаться размерность кода Рида–Маллера 𝑅 𝑀 (𝑟, 𝑚), а через 𝑛 = 2𝑚 — его длина. Секретным ключом криптосистемы является кортеж (𝐻 1, 𝐻 2,..., 𝐻 𝑢, Γ). (1) Здесь 𝐻 1, 𝐻 2,..., 𝐻 𝑢 — невырожденные матрицы размера 𝑘 × 𝑘 над полем 𝐺 𝐹 (2), которые выбираются случайно и равновероятно из множе­ ства всех двоичных невырожденных матриц размера 𝑘 × 𝑘. Матрица Γ имеет размеры 𝑢 ·𝑛 × 𝑢 ·𝑛 и является перестановочной, то есть в каждой её строчке и в каждом столбце стоит ровно одна единица, поэтому можно считать, что Γ — это перестановка на множестве из 𝑢 𝑛 элементов. Открытым ключом криптосистемы Мак-Элиса–Сидельникова явля­ ется матрица 𝐺 ′ = (𝐻 1𝑅 ‖ 𝐻 2𝑅 ‖... ‖ 𝐻 𝑢 𝑅) · Γ, (2) где символом ‖ обозначена конкатенация матриц по столбцам, а 𝑅 — стандартная форма порождающей матрицы кода 𝑅 𝑀 (𝑟, 𝑚). Под стан­ дартной формой порождающей матрицы понимается (𝑘 × 𝑛)-матрица вида 𝑅 = ⎛ ⎜ ⎜ ⎝ 𝐺 0 𝐺 1... 𝐺 𝑟 ⎞ ⎟ ⎟ ⎠, где 𝐺 0 = (1, 1..., 1), 𝐺 1 = ⎛ ⎜ ⎜ ⎝ Ω 𝑦 𝑚... Ω 𝑦 2 Ω 𝑦 1 ⎞ ⎟ ⎟ ⎠, 𝐺 2 = ⎛ ⎜ ⎜ ⎝ Ω 𝑦 𝑚 − 1𝑦 𝑚... Ω 𝑦 1𝑦 3 Ω 𝑦 1𝑦 2 ⎞ ⎟ ⎟ ⎠, 𝐺 𝑟 = ⎛ ⎜ ⎜ ⎝ Ω 𝑦 𝑚 − 𝑟 +1𝑦 𝑚 − 𝑟 +2...𝑦 𝑚... Ω 𝑦 1𝑦 2...𝑦 𝑟 − 1𝑦 𝑟 +1 Ω 𝑦 1𝑦 2...𝑦 𝑟 − 1𝑦 𝑟 ⎞ ⎟ ⎟ ⎠, здесь Ω 𝑓 — вектор значений булевой функции 𝑓 (𝑦 1,..., 𝑦 𝑚). Отметим, что в дальнейшем мы не будем делать различий между булевыми функ­ циями и их векторами значений. Дается следующее определение эквивалентности секретных ключей в криптосистеме Мак-Элиса–Сидельникова. Два секретных ключа (𝐻 1, 𝐻 2,..., 𝐻 𝑢, Γ) и (𝐻 ′ 1, 𝐻 ′ 2,..., 𝐻 ′ 𝑢, Γ ′) 9 называются эквивалентными, если соответствующие им открытые клю­ чи совпадают, то есть выполняется соотношение (𝐻 1𝑅 ‖ 𝐻 2𝑅 ‖... ‖ 𝐻 𝑢 𝑅) · Γ = (𝐻 ′ 1𝑅 ‖ 𝐻 ′ 2𝑅 ‖... ‖ 𝐻 ′ 𝑢 𝑅) · Γ ′ /откорректируйте выражение/. (3) Введенное отношение является отношением эквивалентности. Тем самым, вс¨ е множество секретных ключей разбивается на классы эквива­ лентности и число классов эквивалентности совпадает с числом откры­ тых ключей. Класс эквивалентности с представителем (𝐻 1,..., 𝐻 𝑢, Γ) будем обозначать так: [(𝐻 1,..., 𝐻 𝑢, Γ)]. Во второй главе изучается ключевое пространство криптосистемы Мак-Элиса–Сидельникова. Устанавливается связь классов эквивалентно­ сти секретных ключей со специально введенным множеством перестано­ вок 𝒢. Рассмотрим множество 𝒢 (𝐻 1, 𝐻 2,..., 𝐻 𝑢), состоящее из перестано­ вок Γ ∈ 𝑆 𝑢 𝑛, для которых существуют невырожденные двоичные матри­ цы 𝐻 ′ 1, 𝐻 ′ 2,..., 𝐻 ′ 𝑢 такие, что (𝐻 1𝑅 ‖ 𝐻 2𝑅 ‖... ‖ 𝐻 𝑢 𝑅)Γ = (𝐻 ′ 1𝑅 ‖ 𝐻 ′ 2𝑅 ‖... ‖ 𝐻 ′ 𝑢 𝑅). (4) Во второй главе доказано следующее утверждение. Теорема. 2.1. Существует взаимно однозначное соответствие меж­ ду классом эквивалентности [(𝐻 1, 𝐻 2,..., 𝐻 𝑢, Γ)] секретных ключей и множеством 𝒢 (𝐻 1, 𝐻 2,..., 𝐻 𝑢). При этом класс эквивалентности [(𝐻 1, 𝐻 2,..., 𝐻 𝑢, Γ)] состоит из ключей вида (𝐻 ′ 1, 𝐻 ′ 2,..., 𝐻 ′ 𝑢, Γ − 1 𝑔 · Γ), (5) где Γ 𝑔 принадлежит множеству 𝒢 (𝐻 1, 𝐻 2,..., 𝐻 𝑢) и (𝐻 1𝑅 ‖ 𝐻 2𝑅 ‖... ‖ 𝐻 𝑢 𝑅)Γ 𝑔 = (𝐻 ′ 1𝑅 ‖ 𝐻 ′ 2𝑅 ‖... ‖ 𝐻 ′ 𝑢 𝑅). (6) Тем самым вопрос изучения структуры классов эквивалентности секретных ключей сводится к изучению структуры множества переста­ новок 𝒢. Далее во второй главе /измените начало предложения/описывается ряд классов эквивалентности секретных ключей криптосистемы Мак-Элиса–Сидельникова в случае использования произвольного числа блоков кода Рида–Маллера. Для этого с помощью автоморфизмов кода Рида–Маллера вво­ дится понятие группы расширенных автоморфизмов. Напомним, что 10 автоморфизмом некоторого кода 𝒞 называется множество переста­ новок координат кодовых слов, которые переводят код 𝒞 в себя. Известно, что совокупность всех автоморфизмов кода относительно операции умножения перестановок является группой. Рассмотрим неко­ торую перестановку 𝜎 ∈ 𝑆 𝑛. Построим, используя е¨ е, 𝑖 «длинных» перестановок 𝜎 [𝑖 ] ∈ 𝑆 𝑢 𝑛 следующим образом. Положим 𝜎 [𝑖 ](𝑗) = 𝑗 для любого 𝑗 ̸ ∈ 𝐼 = {(𝑖 − 1) · 𝑛 + 1, (𝑖 − 1) · 𝑛 + 2,..., 𝑖 · 𝑛 }, а 𝜎 [𝑖 ](𝑗) = (𝑖 − 1)𝑛 + 𝜎 (𝑗 − (𝑖 − 1)𝑛), для всех 𝑗 ∈ 𝐼. Другими словами, перестановка 𝜎 [𝑖 ] в -том блоке действует как перестановка 𝜎, а во всех остальных блоках — как единичная перестановка. Тогда группой расши­ ренных автоморфизмов 𝒜 𝑢 (𝑅 𝑀 (𝑟, 𝑚)) кода Рида–Маллера 𝑅 𝑀 (𝑟, 𝑚) назов¨ ем множество всех возможных произведений описанных перестано­ вок 𝜎 [𝑖 ] для всех возможных 1 6 𝑖 6 𝑢 и всех возможных перестановок 𝜎 из группы автоморфизмов кода 𝑅 𝑀 (𝑟, 𝑚)./проверьте так далее в тексте/ В диссертации доказана следующая теорема. Теорема. 2.2. Пусть невырожденные матрицы 𝐷 1, 𝐷 2,..., 𝐷 𝑢 зада­ ют автоморфизмы 𝜎 1, 𝜎 2,..., 𝜎 𝑢 кода 𝑅 𝑀 (𝑟, 𝑚) соответственно, то есть для 1 6 𝑖 6 𝑢 выполнены равенства 𝐷 𝑖 𝑅 = 𝑅 𝜎 𝑖. Обозначим через 𝜎 1[1], 𝜎 2[2],..., 𝜎 𝑢 [𝑢 ] перестановки из 𝒜 𝑢 (𝑅 𝑀 (𝑟, 𝑚)), соответствующие перестановкам 𝜎 1,..., 𝜎 𝑢. И пусть 𝐻 — любая невырожденная мат­ рица. Тогда 𝒢 (𝐻 𝐷 1,..., 𝐻 𝐷 𝑢) = 𝜎 − 1 1 [1] · 𝜎 − 1 2 [2]...𝜎 − 1 𝑢 [𝑢 ] · 𝒢 (𝐸,..., 𝐸). (7) Эта теорема дает описание множества 𝒢 (𝐻 𝐷 1,..., 𝐻 𝐷 𝑢). С помо­ щью не¨ е в диссертации доказана теорема, дающая описание ряда классов эквивалентности. Теорема. 2.4. Пусть невырожденные матрицы 𝐷 1, 𝐷 2,..., 𝐷 𝑢 зада­ ют автоморфизмы 𝜎 1, 𝜎 2,..., 𝜎 𝑢 кода 𝑅 𝑀 (𝑟, 𝑚) соответственно. Обо­ значим через 𝜎 1[1], 𝜎 2[2],..., 𝜎 𝑢 [𝑢 ] перестановки из 𝒜 𝑢 (𝑅 𝑀 (𝑟, 𝑚)), соот­ ветствующие перестановкам 𝜎 1,..., 𝜎 𝑢. И пусть 𝐻 — любая невы­ рожденная матрица. Тогда класс эквивалентности [(𝐻 𝐷 1, 𝐻 𝐷 2..., 𝐻 𝐷 𝑢, Γ)] состоит из кортежей вида (𝐻 𝐴 1, 𝐻 𝐴 2,..., 𝐻 𝐴 𝑢, 𝛾 − 1 1 [1] · 𝛾 − 1 2 [2]... 𝛾 − 1 𝑢 [𝑢 ]Γ ′ · (8) ·𝜎 1[1] · 𝜎 2[2]...𝜎 𝑢 [𝑢 ]Γ), 11 где 𝐴 1, 𝐴 2,..., 𝐴 𝑢 задают автоморфизмы 𝛾 1, 𝛾 2,..., 𝛾 𝑢 кода Рида–Мал­ лера 𝑅 𝑀 (𝑟, 𝑚), 𝛾 1 [1], 𝛾 2 [2],..., 𝛾 𝑢 [𝑢 ] — соответствующие этим авто­ морфизмам расширенные автоморфизмы, а перестановка Γ ′ ∈ 𝑆 𝑢 𝑛 со­ храняет матрицу (𝑅 ‖ 𝑅 ‖... ‖ 𝑅), то есть (𝑅 ‖ 𝑅 ‖... ‖ 𝑅)Γ ′ = (𝑅 ‖ 𝑅 ‖... ‖ 𝑅). (9) Следует отметить, что эта структурная теорема позволяет, в част­ ности, вычислить мощность каждого класса эквивалентности. Во второй главе также получена нижняя оценка на мощность мно­ жества ℰ открытыхключейкриптосистемыМак-Элиса–Сидельникова (верхняя оценка получена Г.А. Карпуниным 8. Теорема. 2.6. Справедливы неравенства для числа |ℰ | открытыхклю­ чей криптосистемы Мак-Элиса–Сидельникова (𝑢 · 𝑛)! ℎ 𝑘 (𝑢!)𝑛 |𝐴 𝑢 𝑡 (𝑅 𝑀 (𝑟, 𝑚))| 6 |ℰ | < (𝑢 · 𝑛)! (ℎ 𝑘) 𝑢 𝑢! |𝐴 𝑢 𝑡 (𝑅 𝑀 (𝑟, 𝑚))| 𝑢, (10) здесь 𝑛 — длина кода Рида–Маллера 𝑅 𝑀 (𝑟, 𝑚), используемого для по­ строения криптосистемы, 𝑢 — число блоков криптосистемы, ℎ 𝑘 = (2𝑘 − 1)(2𝑘 − 2)(2𝑘 − 2 2)...(2𝑘 − 2 𝑘 − 1) — число обратимых (𝑘 × 𝑘)-матриц над полем 𝐺 𝐹 (2), и 𝐴 𝑢 𝑡 (𝑅 𝑀 (𝑟, 𝑚)) — группа автоморфизмов кода Рида–Маллера 𝑅 𝑀 (𝑟, 𝑚). Оценка на число открытых ключей опубликована в работе [1]. Нижняя оценка позволяет определить насколько богато множество открытых ключей криптосистемы Мак-Элиса–Сидельникова при каж­ дых конкретных значениях параметров 𝑢, 𝑟, 𝑚. Если обнаружится, что число открытых ключей невелико, то криптосистема заведомо окажет­ ся не стойкой. Так для предложенных В.М. Сидельниковым 6 значений 𝑢 = 4, 𝑟 = 3, 𝑚 = 10 из нижней оценки (10) следует, что число открытых ключей будет не меньше, чем 1020897 < |ℰ |. (11) Тем самым число ключей в криптосистеме Мак-Элиса–Сидельникова до­ статочно велико, чтобы противостоять атаке полным перебором ключей. 8 Карпунин Г. А. О ключевом пространстве криптосистемы Мак-Элиса на основе двоичных кодов Рида-Маллера // Дискретная математика. 2004. Т. 16(2). С. 79-84. 12 Результаты второй главы опубликованы в работах [1] и [2]. В третьей главе да¨ ется описание классов эквивалентности секрет­ ных ключей криптосистемы Мак-Элиса–Сидельникова с представителем особого вида в случае использования только двух копий кода Рида–Мал­ лера для построения криптосистемы. Вначале вводится в рассмотрение следующий тип матриц. Пусть 𝐼 = {𝑖 1, 𝑖 2,..., 𝑖 𝑝 } — множество натуральных чисел таких, что выпол­ нена цепочка неравенств 1 6 𝑖 1 6 𝑖 2 6... 6 𝑖 𝑝 6 𝑘. Пусть также 𝐴 ̃ ︀ = {𝛼 ̃ ︀ 𝑖 1, 𝛼 ̃ ︀ 𝑖 2,..., 𝛼 ̃ ︀ 𝑖 𝑝 } — множество двоичных наборов длины 𝑘. Рассмот­ рим матрицу 𝑇 𝐼 𝐴 ̃ ︀ вида 𝑇 𝐼 𝐴 ̃ ︀ = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 𝑖 1 𝑖 2 𝑖 𝑝 ↓ ↓ ↓ 1 0... 0... 0... 0... 0 0 1... 0... 0... 0... 0.............................. 𝑖 1 → 𝛼 𝑖 1 1 𝛼 𝑖 1 2... 𝛼 𝑖 1 𝑖 1... 𝛼 𝑖 1 𝑖 2... 𝛼 𝑖 1 𝑖 𝑝... 𝛼 𝑖 1 𝑘.............................. 𝑖 2 → 𝛼 𝑖 2 1 𝛼 𝑖 2 2... 𝛼 𝑖 2 𝑖 1... 𝛼 𝑖 2 𝑖 2... 𝛼 𝑖 2 𝑖 𝑝... 𝛼 𝑖 2 𝑘.............................. 𝑖 𝑝 → 𝛼 𝑖 𝑝 1 𝛼 𝑖 𝑝 2... 𝛼 𝑖 𝑝 𝑖 1... 𝛼 𝑖 𝑝 𝑖 2... 𝛼 𝑖 𝑝 𝑖 𝑝... 𝛼 𝑖 𝑝 𝑘.............................. 0 0... 0... 0... 0... 1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠, (12) здесь 𝛼 ̃ ︀ 𝑖 𝑗 = (𝛼 𝑖 𝑗 1, 𝛼 𝑖 𝑗 2,..., 𝛼 𝑖 𝑗 𝑘) для 1 6 𝑗 6 𝑝. При этом для того, что­ бы такая матрица была невырождена необходимо наложить на элемен­ ты множества 𝐴 ̃ ︀ дополнительное условие, а именно нужно потребовать невырожденность матрицы ⎛ ⎜ ⎝ 𝛼 𝑖 1 𝑖 1 𝛼 𝑖 1 𝑖 2... 𝛼 𝑖 1 𝑖 𝑝 𝛼 𝑖 2 𝑖 1 𝛼 𝑖 2 𝑖 2... 𝛼 𝑖 2 𝑖 𝑝 𝛼 𝑖 𝑝 𝑖 1 𝛼 𝑖 𝑝 𝑖 2... 𝛼 𝑖 𝑝 𝑖 𝑝 ⎞ ⎟ ⎠. (13) В случае когда 𝐼 = {𝑖 }, 𝐴 ̃ ︀ = {𝛼 ̃ ︀ } матрицу 𝑇 𝐼 𝐴 ̃ ︀ будем обозначать как 𝑇 𝑖 𝛼 ̃ ︀. Далее рассматривается два случая. 13 Первый случай — 𝑢 = 2 и 𝐼 = {𝑖 }. Рассматривается код Рида–Маллера 𝑅 𝑀 (𝑟, 𝑚) с 𝑟 > 1, так как пол­ ное описание множества 𝒢 (𝐸, 𝐻) для кода 𝑅 𝑀 (1, 𝑚) и всех матриц 𝐻 было найдено Г.А. Карпуниным 8. Оказывается, что в этом случае задача описания классов эквива­ лентности сводится к задаче изучения перестановочной эквивалентности (𝑘 − 1)-мерных подпространств кода 𝑅 𝑀 (𝑟, 𝑚). Особый интерес представ­ ляют подпространства Π 𝑤 = {𝑣 ∈ 𝑅 𝑀 (𝑟, 𝑚)|(𝑤, 𝑣) = 0}, где 𝑤 — моном вида 𝑥 1𝑥 2... 𝑥 𝑚 − 𝑡 при 𝑡 > 0. Для таких подпространств в диссертации доказана теорема. Теорема. 3.3. Пусть 2𝑟 6 𝑚, 0 < 𝑡 6 𝑟, и 𝑤 = 𝑥 1𝑥 2... 𝑥 𝑚 − 𝑡. Тогда, если Γ (Π 𝑤) — множество перестановок, переводящих код Π 𝑤 в подкод кода 𝑅 𝑀 (𝑟, 𝑚), то Γ (Π 𝑤) = 𝐼 (Π 𝑤) × Aut(𝑅 𝑀 (𝑟, 𝑚)). (14) Здесь 𝐼 (Π 𝑤) — множество перестановок 𝛾 таких, что 𝑥 𝛾 = 𝑥 для любого 𝑥 из подпространства Π 𝑤. Используя эту теорему, в диссертации получено описание множества классов эквивалентности в первом случае. Теорема. 3.5. Пусть 𝑅 𝑀 (𝑟, 𝑚) — код Рида–Маллера такой, что 2𝑟 6 𝑚 и 𝑟 > 1, 𝑖 — натуральное число, большее нуля; 𝐻 — любая невырожденная двоичная матрица; 𝛼 ̃ ︀ — произвольный двоичный век­ тор длины 𝑘, у которого в координате с номером 𝑖 стоит единица. Тогда класс эквивалентности [(𝐻, 𝐻 𝑇 𝑖 𝛼 ̃ ︀, Γ)] состоит из кортежей вида (𝐻 𝑇 𝑖 𝛽 ̃ ︀ 𝐷 1, 𝐻 𝑇 𝑖 𝛾 ̃ ︀ 𝐷 2, 𝜎 𝐿 − 1 [1]𝜎 − 1 𝑅 [2]Γ ′ − 1Γ). (15) Здесь 𝜎 𝐿, 𝜎 𝑅 — автоморфизмы кода Рида–Маллера 𝑅 𝑀 (𝑟, 𝑚), соответ­ ствующие матрицам 𝐷 1 и 𝐷 2, а для перестановки Γ ′ выполняются два условия 1) Если 𝑅 ′ — (𝑘 − 1) × 𝑛 -матрица, получающаяся удалением строки с номером 𝑖 из матрицы 𝑅, то (𝑅 ′ ‖ 𝑅 ′)Γ ′ = (𝑅 ′ ‖ 𝑅 ′); (16) 14 2) Если − → 𝑟 𝑖 — строка матрицы 𝑅 с номером 𝑖, то (− → 𝑟 𝑖 ‖ 𝛼 𝑅 ̃ ︀)Γ ′ = (𝛽 𝑅 ̃ ︀ ‖ 𝛾 𝑅 ̃ ︀) ∈ 𝑅 𝑀 (𝑟, 𝑚) × 𝑅 𝑀 (𝑟, 𝑚). (17) Привед¨ енная структурная теорема 3.5 да¨ ет не только описание клас­ сов, но с е¨ е помощью может быть вычислена мощность каждого класса эквивалентности. Второй случай — 𝑢 = 2, |𝐼 | > 1. В этом случае рассматривается матрица 𝑇 𝐼 𝐴 ̃ ︀, где |𝐼 | = 𝑝 > 1. в другое подпространство того же кода. Описание классов эквивалентности теперь сводится к задаче описания перестановок, которые переводят подпространство Π 𝑉 размерности 𝑘 − 𝑝 кода Рида–Маллера 𝑅 𝑀 (𝑟, 𝑚) в другое подпространство того же кода. При этом, если 𝑉 — множество из 𝑝 линейно независимых векторов дли­ ны 𝑛, то подпространство Π 𝑉 определяется следующим образом Π 𝑉 = {𝑤 ∈ 𝑅 𝑀 (𝑟, 𝑚)|(𝑤, 𝑣) = 0, ∀ 𝑣 ∈ 𝑉 }. (18) Для целей описания классов эквивалентности секретных ключей в диссертации рассматриваются только подпространства Π 𝑉, которые за­ даются множеством 𝑉 = 𝑉 ˇ, где 𝑉 ˇ = {𝑥 𝑖 1 1 𝑥 𝑖 1 2... 𝑥 𝑖 2 𝑡 1, 𝑥 𝑖 2 1 𝑥 𝑖 2 2... 𝑥 𝑖 2 𝑡 2,..., 𝑥 𝑖 𝑝 1 𝑥 𝑖 𝑝 2... 𝑥 𝑖 𝑝 𝑡 𝑝 }. (19) В диссертации доказано утверждение. Утверждение. 3.11. Пусть Π 𝑉 ˇ — подкод кода 𝑅 𝑀 (𝑟, 𝑚), задаваемый множеством 𝑉 ˇ. Пусть также 𝑚 − 1 > 2𝑟 > ♯, где♯ —общеечислораз­ личных переменных, встречающихся в мономах из множества 𝑉 ˇ. Рас­ смотрим перестановку 𝜎 такую, что (Π 𝑉 ˇ) 𝜎 — подкод 𝑅 𝑀 (𝑟, 𝑚). Тогда 𝜎 принадлежит группе автоморфизмов 𝐴 𝑢 𝑡 (𝑅 𝑀 (𝑟, 𝑚)) кода Рида–Мал­ лера 𝑅 𝑀 (𝑟, 𝑚). Используя это утверждение, в диссертации получено описание под­ множеств классов эквивалентности [𝐻, 𝐻 𝑇 𝐼 𝐴 ̃ ︀, Γ ]. Теорема. 3.6. Пусть 𝑅 𝑀 (𝑟, 𝑚) — код Рида–Маллера такой, что 2𝑟 + 1 < 𝑚. Пусть также 𝐻 — любая невырожденная матрица размера 𝑘 × 𝑘. Далее, пусть существует перестановка Γ − 1 𝑔 — пере­ становка из 𝒢 (𝐸, 𝑇 𝐼 𝐴 ̃ ︀), представимая в виде Γ ′ 𝜎 𝐿 [1]𝜎 𝑅 [2], где Γ ′ такая перестановка, что (𝑅 ′ ‖ 𝑅 ′)Γ ̸