Содержание к диссертации
Введение
1 Основы теории линейных кодов 11
1.1 Основные понятия 11
1.2 Обобщенные коды Рида - Соломона и коды Гоппы 13
1.3 Декодирование произвольного линейного кода и информационные совокупности 15
1.4 Ранговое расстояние 18
1.4.1 Верхняя граница для рангового расстояния кода 20
1.5 Линейные ранговые коды 21
1.6 Линейные МРР коды для длин п N — коды Габидулина 1.6.1 Конструкция 22
1.6.2 Быстрый алгоритм декодирования 24
1.6.3 Спектр кода 27
1.7 Некоторые свойства ранга векторов, столбцевого ранга матриц и ранговых кодов 28
1.8 Эквивалентные ранговые коды 30
2 Подкоды и удлинения МРР кодов Габидулина 32
2.1 Подкоды над подполями 32
2.2 Родительский код для произвольных подкодов 36
2.3 Удлинение ранговых кодов Габидулина
2.3.1 Удлинение единичной матрицей 42
2.3.2 Удлинение на 2 45
2.4 МДР коды с фиксированным ранговым расстоянием 46
3 Линейные ранговые коды для длин п N — приводимые коды 50
3.1 Конструкция 50
3.2 Кодирование приводимых кодов 52
3.2.1 Систематическое кодирование 53
3.3 Быстрое декодирование приводимых кодов 53
4 Декодирование произвольных кодов в ранговой метрике 55
4.1 Задача декодирования рангового кода 55
4.2 Декодирование как решение системы квадратных уравнений 56
4.3 Решение системы уравнений 60
4.3.1 Способ 1 61
4.3.2 Способ 2 62
4.3.3 Другие подходы 64
Системы защиты информации от несанкционированного доступа 66
5 Системы с открытым ключом на основе линейных кодов 66
Введение 66
5.1 Общие положения 68
5.1.1 Схема построения 69
5.1.2 Стойкость систем и атаки 70
5.1.3 Особенности систем на линейных кодах 72
5.2 Система МакЭлиса 73
5.2.1 Описание системы 73
5.2.2 Надежность системы 75
5.3 Система Нидеррайтера 77
5.3.1 Описание системы 77
5.3.2 Раскрытие системы 77
5.4 Модификация системы Нидеррайтера 81
5.4.1 Случайные подкоды ОРС кодов 81
5.4.2 Добавление шумовой матрицы 87
6 Система ГПТ 94
6.1 Описание системы 95 6.2 Атаки на систему ГПТ 97
6.2.1 Прямые атаки 97
6.2.2 Структурные атаки 99
7 Повышение стойкости систем, использующих коды в ранговой метрике 118
7.1 Случайные подкоды ранговых кодов:
прямоугольный строковый скремблер 119
7.1.1 Описание системы 119
7.1.2 Анализ системы 120
7.2 Эквивалентные ранговые коды: столбцевой скремблер 127
7.2.1 Описание системы 127
7.2.2 Анализ системы 128
7.2.3 Стойкость системы 136
7.3 Система на основе приводимых ранговых кодов 141
7.3.1 Описание системы 141
7.3.2 Анализ системы 142
8 Практические рекомендации 150
8.1 Повышение скорости передачи информации 150
8.2 Нумерация векторов заданного ранга 152
8.3 Снижение объема открытого ключа 156
8.4 Роль шумовой матрицы в системах на ранговых кодах 159
8.5 Сравнение систем 160
Заключение 165
Предметный указатель 168
Список обозначений 170
Литература
- Декодирование произвольного линейного кода и информационные совокупности
- Удлинение единичной матрицей
- Быстрое декодирование приводимых кодов
- Декодирование как решение системы квадратных уравнений
Декодирование произвольного линейного кода и информационные совокупности
Все ОРС-коды имеют алгоритм декодирования, который исправляет все ошибки веса t — \_{d — 1)/2J или меньше за 0(9t2 + 6nt) операций в поле GF(qN) при условии, что известны все элементы Х{ и Zi, і — 1,... ,п (см. [4]). Асимпотически при п — со и t - оо ОРС коды могут быть декодированы за 0(nlog га) операций.
Пусть С - (n,k,d) ОРС-код над полем GF(qN). Рассмотрим под-код Са этого кода, состоящий из всех кодовых слов с координатами из базового поля GF(q). Такой код является подходом над подполем и называется альтернантным кодом. Альтернантный код Са имеет следующие параметры: длина га, размерность ка те — (п — k)N и минимальное расстояние da га — к + 1.
Коды Гоппы являются частным случаем альтернантных кодов (фактически же они предложены много раньше, чем альтернантные). Пусть а = (с і, аг, , о.п) — некоторое множество различных элементов поля GF(qN). Пусть G(x) — примитивный неприводимый многочлен степени t над полем GF(qN), t п. Для каждого j — 1,2,..., га положим Zj — 1/G{OLJ). Код Гоппы CQ определяется как подкод над подполем обобщенного кода Рида-Соломона с проверочной матрицей Н = [a)/G{oij)l t = 0,l,..., -l, j = l,2,...,n.
В общем случае минимальное расстояние dg кода Гоппы удовлетворяет неравенству dg t + 1. Однако в двоичном случае q = 2 можно показать, что dg 2t + 1, т. е. почти в 2 раза больше. Итак, двоичные коды Гоппы имеют следующие параметры: длина n g+l = 2y+l;
Для нахождения порождающей матрицы двоичного кода Гоппы рассмотрим какую-нибудь реализацию поля GF(2N). Каждый элемент расширенного поля GF(2N) может быть представлен как вектор-столбец с элементами из поля GF(2). В соответствии с этим представлением txn проверочная матрица Н отображается в двоичную Ntxn матрицу Лип- Порождающая матрица G кода Гоппы — это любая двоичная к х п матрица с максимальным значением к, такая что GH6m = Декодирование альтернантных кодов может быть осуществлено так же, как и декодирование ОРС-кодов. Единственное отличие заключается в том, что координаты кодового вектора g, полученного вектора у и вектора ошибок е лежат в поле GF(q), а не в поле GF(qN).
Для практических целей обычно недостаточно построить код с большим минимальным расстоянием. Нужно уметь декодировать такой код, чтобы исправлять ошибки.
Различают две задачи декодирования. Пусть задан (n,k,d) код С и задано число t . Для произвольного вектора у найти какое-нибудь слово g кода С такое, что wh{y—g) t , если такое g существует. Такое декодирование называется "ограниченным" декодированием. Если t = t = [(d— l)/2j, то это — декодирование в пределах корректирующей способности, и оно всегда имеет единственное решение.
Пусть задан (n,k,d) код С. Для произвольного вектора у найти слово g кода С, ближайшее к у. Такое декодирование называется декодированием по минимуму расстояния (или полным декодированием). В случае если метрика, в которой определен код, строго согласована с каналом, то декодирование по минимуму расстояния является декодированием по максимуму правдоподобия и, значит, оптимально в том смысле, что минимизирует вероятность появления ошибки на выходе декодера. Декодирование в пределах корректирующей способности дает удовлетворительные результаты для сравнительно хороших каналов, где ошибки возникают достаточно редко. Именно таким декодированием часто и довольствуются на практике.
Если сложность построенного алгоритма полиномиально зависит от длины п декодируемого кода, то такой алгоритм называют "быстрым" (полиномиальным) алгоритмом декодирования.
В общем случае декодирование произвольного линейного кода (другие названия: случайный код, общий код) как в пределах корректирующей способности, так и по минимуму расстояния, является очень сложной математической задачей. Быстрых алгоритмов декодирования по минимуму расстояния не известно практически ни для каких кодов, за исключением тривиальных. Более того, известно [23], что такое декодирование является Л/"Р-полной задачей. Не известно, является ли декодирование в пределах корректирующей способности произвольного кода Л/"Р-полной задачей, однако число семейств кодов, для которых известны полиномиальные алгоритмы, мало.
С помощью информационных совокупностей можно декодировать произвольный линейный код в хэмминговой метрике. Пусть вектор у = g + е получен после передачи по каналу кодового вектора g, в котором произошло t или меньше ошибок.
Для заданного кода рассмотрим множество X — множество различных информационных совокупностей такое, что для каждого вектора ошибок е веса не больше чем t существует, по крайней мере, одна информационная совокупность J Є X такая, что на позициях вектора y{J) = g(i7) не произошло ни одной ошибки. Можно показать, что X не пусто.
Алгоритм может быть улучшен для некоторых кодов, если для случая t t рассматривать все ошибки веса I или меньше внутри выбранной совокупности Ji, см., например, [59]. Тем не менее асимптотически сложность алгоритма все же остается экспоненциальной от кратности исправляемой ошибки.
Удлинение единичной матрицей
Для некоторых кодов их подкоды представляют определенный практический и теоретический интерес. Иногда подкоды имеют лучшие параметры, чем родительские коды, или допускают более простое декодирование. Например коды Гоппы, являющиеся подкодами обобщенных кодов Рида-Соломона, играют важную роль в теории кодов в хэммин-говой метрике. Изучение подкодов также позволяет глубже понять и выяснить свойства самих кодов.
Удлинение кода из некоторого семейства обычно производят с целью улучшения параметров кода, например, для увеличения минимального расстояния или построения кода заданной длины в фиксированном поле, если непосредственная конструкция для семейства не позволяет построить более длинный код. В этой главе исследуются некоторые регулярные способы удлинения МРР кодов Габидулина, которые, в частности, привели к построению нового семейства МДР кодов.
Впервые подкоды над подполями ранговых кодов Габидулина были рассмотрены в работе [43]. Пусть код С — линейный (п, п — df+1, d) МРР код над полем GF(qN), заданный своей проверочной матрицей ХІ = Пусть N = si, где 5 2, І 2. Поле GF(qs) есть подполе поля GF(qN). Рассмотрим подкод кода С такой, что все координаты кодовых векторов подкода лежат в поле GF(qs) — подкод над подполем.
Рассматривается случай п — N. Пусть f{x) = «і - и2х 4-... + щх1-1 -f Xі примитивный многочлен над полем GF(qs). Любой элемент а Є GF(qN) представим в виде а = z\ + zix + ... + ZfX , где Zi Є GF(qs), і = 1,2,... ,1. То есть поле GF(qN) рассматривается как пространство GF(qs)e — линейное пространство векторов длины і над полем GF(qs). Введем взаимно однозначное отображение между GF(qN) и GF(qs)L.
Обозначение Н(а) естественным образом будем использовать для векторов и матриц с элементами из GF(qN).
Обозначим he = (hi,h,2,... ,hw) — порождающий вектор матрицы Н. Пусть полученную из матрицы He возведением каждого ее элемента в степень [г] = q\ Лемма 7. Матрицы (2.2) и (2.3) задают одно и то же 1-мерное пространство над GF(qs). Доказательство. Заметим, что 1,х, х2,..., х1 1 есть базис поля GF(qN) над полем GF(qs). Поэтому 1,а?И (ж2)И,..., (х -1) также является базисом, получаемого из предыдущего базиса умножением на некоторую невырожденную матрицу Т с элементами из GF{qs). Значит, n{hf)
Если d s, то HS5 определяет подкод длины ns = N, размерности ks N — (d — 1) ис минимальным ранговым расстоянием ds: d ds s. Для этого подкода из верхней границы (1.6) следует, что ks N — i(ds — 1), и, значит, ds = d и ks = N — l[d — 1). Таким образом, построенный подкод является МРР кодом.
Найдем для кода с проверочной матрицей (2.4) эквивалентный код (см. параграф 1.8). Лемма 8. Для кода с проверочной матрицей Не вида (2.1) существует эквивалентный код с проверочной матрицей где элементы ап,сч2,--- ,щ8 линейно независимы над полем GF(q), Доказательство. Все столбцы матрицы Не линейно независимы над полем GF(q), а все строки — над полем GF(qs), поэтому линейными преобразованиями столбцов над GF(q) приведем Н к виду где у каждого щ все координаты линейно независимы над GF(q). Длина любого а не превосходит s, а сумма длин всех векторов равна s, поэто му длина каждого аг равна точно s. Следовательно, дополнительными преобразованиями столбцов над GF(q) можно обнулить все элементы, обозначенные " ", получив матрицу (2.5).
Применяя к матрице (2.4) лемму 8 и перестановки строк, получим каноническую форму проверочной матрицы подкода над подполем [d-2] Итак, для любого (JV, k,d = N — к-\-1) МРР кода над полем GF(qN) его подкод над подполем GF(qs), N = s, эквивалентен прямому произведению штук (s, s — d + 1, d) кодов МРР.
Структура подкода в виде прямого произведения, который, к тому же, достигает верхней границы для длины, большей степени расширения поля, явилась отправной точкой для построения более общего семейства приводимых ранговых кодов, исследуемых в главе 3.
Декодировать подкод над подполем можно с помощью быстрого алгоритма декодирования родительского кода, имеющего сложность Wp = W(N,d) операций, где W(N,d) — трудоемкость декодирования (N, N — d + 1, d) МРР кода. Но рассмотренные подкоды имеют и собственный, еще более быстрый алгоритм декодирования: принятый вектор разбивается на части в соответствии с матрицами А{, и каждая часть декодируется независимо. Сложность декодирования в этом случае составляет Ws = W(s,d) операций. Поскольку W(s,d) = 0(s3), то декодирование упрощается примерно в Wp/Ws 2 раз. При этом декодирование происходит в поле GF(qs), а не GF{qN). Кроме того, алгоритм допускает естественное распараллеливание, что дает временной выигрыш в ? раз.
Для рассмотренных в предыдущем параграфе подкодов над подполями существует собственный быстрый алгоритм декодирования, не зависящий от алгоритма декодирования родительского кода.
Как декодировать произвольный подкод, даже если он имеет параметры лучше, чем у родительского кода, обычно неизвестно. Более того, может оказаться, что подкод совсем не имеет регулярной структуры, позволяющей построить алгебраический алгоритм декодирования, и этот факт было бы удобно использовать для построения криптосистемы с открытым ключом (этот вопрос обсуждается в параграфе 7.1).
В этом параграфе показано, как для случайного подкода МРР кода Габидулина восстановить его родительский код.
Пусть G — порождающая матрица (п, к, п — к + 1) МРР кода С над полем GF(qN), п N, вида (1.12). Рассмотрим подкод Ср кода С, заданный своей порождающей матрицей Сд-р = ЬрСг, где Sp — (к — р) х к матрица с элементами из GF(qN) ранга r(S\qN) = к — р. Подкод Ср имеет размерность к — р, и его минимальное ранговое расстояние находится в диапазоне от d = п — к + I RO d + р. Заметим сразу, что если какие-то последовательные к — р столбцов матрицы Sp образуют невырожденную матрицу, а остальные столбцы нулевые, то подкод Ср, очевидно, является (п, к — р, п — к +р-\-1) МРР кодом Габидулина. Свойства такого кода известны, известен и быстрый алгоритм декодирования. Поэтому далее такие подкоды не рассматриваются.
Быстрое декодирование приводимых кодов
Для длин п N конструкция (1.12) в общем случае не позволяет строить оптимальные ранговые коды, поскольку вектор g, порождающий фробениусовскую матрицу, будет содержать линейно зависимые над GF(q) элементы. Удлинения кодов Габидулина, рассмотренные в предыдущей главе, при п N также не достигают верхней границы (1.6), хотя они и могут быть оптимальными в хэмминговой метрике.
Однако для п N линейные ранговые коды, лежащие на границе (1.6), существуют. В этой главе описаны приводимые ранговые коды — новое семейство кодов, включающее МРР коды для длин п, кратных N.
Определение 6. Код С называется приводимым ранговым кодом, если существует эквивалентный ему код с порождающей матрицей вида где Gi — порождающая матрица линейного рангового (пг-, k{) кода над полем GF{qN), і = 1,...,, G — какие-то ki х rij матрицы HadGF(qN), і = 2,...,Є, j = !,...,- 1. Эквивалентность линейных ранговых кодов обсуждается в параграфе 1.8. Приведение порождающей матрицы кода С к виду (3.1) осуществляется двумя преобразованиями: умножением слева на невырожденную матрицу с элементами из GF{qN) и умножением справа на невырожденную матрицу с элементами из GF(q), при этом каждая матрица Gj должна быть полного ранга кг, чтобы задавать (щ, к{) ранговый код.
Если все Gjj = 0, то такой код С назовем кодом прямого произведения [43]. В виде прямого произведения кодов представимы подкоды кодов Габидулина над подполями (см. параграф 2.1). Оказалось, что подкод является кодом МРР с длиной, большей степени расширения поля. Обобщение конструкции кодов прямого произведения и привело к построению приводимых ранговых кодов.
Тогда приводимый ранговый код С с порождающей матрицей G вида (3.1) есть код длины п = Y i=ini размерности к = X)i=i hue ранговым расстоянием d, удовлетворяющим неравенству min(di,... ,di) d N.
Доказательство. Пусть g — кодовое слово кода С. Разобьем g на части: g = (gi, g2,. -., gt), где gj есть произведение информационного вектора m на столбцы матрицы G, в которых расположена матрица Gj. При любом m один из векторов gi,..., g имеет ранг больше или равный dj для некоторого j. Ранг вектора не меньше, чем ранг любой его части, поэтому d mm(di,..., dg). Верхняя граница для d очевидна. П Замечание 2. Если для всех і и j G = 0 (прямое произведение кодов), то d = mm(di,..., d().
Следствие 3. Пусть Gj; і — 1,...,, — порождающие матрицы (N, т, D — N — т + 1) МРР кодов над GF(qN). Тогда код С есть МРР код длины п = N, размерности к = 1т и с ранговым расстоянием d = D. Доказательство. Используя границу (1.6), будем иметь: Nm = Nk n(N-d+l) = N(N-d+l). Отсюда d N-m + l = D. С другой сто роны, из леммы 10 следует, что d min(c?i,..., di) = D. Объединяя два неравенства, получим d = D, и код С достигает верхней границы (1.6), следовательно, он — МРР код. Приводимые МРР коды длин п, кратных N, обладают тем интересным свойством, что их минимальное ранговое расстояние совершенно не зависит от недиагональных матриц G .
Пусть Gj — порождающая матрица (щ, кг) рангового кода над GF(qN), і — 1, ...,. Рассмотрим код С размерности к = Yli=i задаваемый порождающей матрицей (3.1) при некоторых фиксированных матрицах
Пусть m = (mi,m2,.. .,mjfc) — информационный вектор. Он может рассматриваться как конкатенация I блоков длин ki,...,kf. m = (mi,rri2,..., m ). Кодовое слово, задаваемое m, вычисляется по формуле
Иногда удобно иметь систематический кодер для выбранного кода, т. е. такой кодер, после которого информационная последовательность появляется на фиксированных к позициях кодового слова неизменной. Приведем порождающую матрицу (3.1) к систематическому виду следующим образом. Сделаем сначала преобразования строк такие, чтобы привести все Gj, г = 1, ...,, к систематическому виду. Далее преобразуем строки так, чтобы обнулить все элементы, расположенные под единичными матрицами, полученными на предыдущем шаге. И наконец, переставим столбцы так, чтобы на первых к столбцах получилась к х к единичная матрица. Нетрудно проверить, что систематическая форма порождающей матрицы после преобразований имеет вид Efcx 0 0 0 Ri 0 0 0 Efc2 0 0 R-21 R2 0 "syst — ; ; ; : 0 Efci-i 0 R/-i,i R -i,2 R _i 0 0 0 Efc Rn R 2 R,-l R где R.j — ki x (щ — ki) систематическая часть G : Gi — [E . Ri], R некоторые матрицы. l l Сложность систематического кодирования равна J2(ni i)kj kid/2 умножений в поле GF(qN). 3.3 Быстрое декодирование приводимых кодов Рассмотрим случай, когда матрица G; задает \тъ% к%) ранговый код, для которого известен быстрый алгоритм декодирования, і = 1,..., L
Пусть принято слово с = g + е, где g — некоторое кодовое слово, искаженное ошибкой е. Предполагаем, что ранг ошибки не больше чем [(d — 1)/2J. Разобьем с на і подблоков (как это делалось при кодировании): с = (c-i,..., Q). Возьмем последний блок С и применим к нему алгоритм быстрого декодирования, заданный матрицей G . В результате получим блок ui информационного вектора. Вычислим далее блок се-г - rr G -i = me-iGe-i + ei-i, декодируя который, получим пі_і.
На сегодняшний день только у МРР кодов Габидулина для длин щ N есть быстрый алгоритм декодирования ранговых ошибок со сложностью 0(п3) операций. Используя порождающие матрицы этих кодов в качестве Gj, получим, что сложность декодирования всего приводимого кода составит 0{кп + п3/2) операций (предполагается, что щ п/).
Из конструкции и способа декодирования приводимых кодов видно, что кроме исправления ошибок в пределах ранговой корректирующей способности, эти коды также способны исправлять ошибки большего ранга. Пусть матрицы G задают коды с ранговым расстоянием с?$, исправляющие ошибки ранга t{ — \[di — 1)/2J, і = !,...,. Пусть код С имеет порождающую матрицу G вида (3.1).
Хотя анализ приводимых ранговых кодов проведен в самом общем случае, когда матрицы Gj, стоящие на диагонали матрицы G, см. (3.1), описывают какие-то ранговые {n k di) коды, наибольший интерес представляет использование МРР кодов Габидулина. В этом случае параметры приводимого кода можно выбрать так, что он будет оптимальным или близким к оптимальному в ранговой метрике, и для такого кода сразу известен быстрый алгоритм декодирования.
МРР коды Габидулина для длин п N являются оптимальными как в хэмминговой, так и в ранговой метриках. Удлинения этих кодов, рассмотренные в параграфе 2.4, являются оптимальными в хэмминговой метрике, но в общем случае далеки от оптимальных ранговых кодов. Приводимые ранговые коды, напротив, могут быть оптимальными в ранговой метрике, но имеют, вообще говоря, маленькое хэммингово расстояние. Остается открытым вопрос: существует ли над полем GF{qN) код длины п N, кроме рассмотренных, одновременно оптимальный в ранговой и в хэмминговой метриках?
Декодирование как решение системы квадратных уравнений
Большой объем открытого ключа — один из основных факторов, ограничивающих практическое использование криптосистем, построенных на основе линейных кодов. Оригинальная система МакЭлиса на кодах Гоппы при стойкости порядка 260 двоичных операций для взлома имеет открытый ключ более 500 Кбит. Кроме использования кодов Гоппы и Рида-Соломона с системах с открытым ключом предлагалось использовать и другие коды: двоичные коды Рида-Маллера [13], алгебро-геометрические коды [54], низкоплотностные коды с проверками на четность [68]. Однако и эти коды не позволяют существенно снизить объем открытого ключа: для достижения стойкости в 285 операций требуется ключ размером не менее 200 Кбит.
Одной из наиболее успешных попыток уменьшения объема ключа при сохранении высокой стойкости была система ГПТ, предложенная Габидулиным, Парамоновым и Третьяковым в 1991 году [36, 5]. Эта система имеет два важных отличия от всех других систем. Во-первых, она использует коды в ранговой, а не в хэмминговой метрике. Во-вторых, в этой системе впервые было предложено добавлять к открытому ключу шумовую матрицу, которая сильно искажает имеющуюся структуру публикуемого кода.
Первоначально предполагалось, что система ГПТ с объемом ключа 5 Кбит обеспечит стойкость не менее операций для взлома. Однако анализ системы, проведенный в работах Гибсона (J. К. Gibson) [49, 51], показал, как вскрывать такую систему для ключей размера 10-20 Кбит.
В этой главе описана система ГПТ, все известные структурные и наиболее эффективные прямые атаки на нее. 6.1 Описание системы Открытый ключ системы — это матрица GpUb = S(G + X). Здесь S — к х к невырожденная матрица над полем GF(qN) — скрем-блирующая матрица. X — шумовая кхп матрица такая, что r(K\q) = t\ t = [ Секретный ключ образуют матрицы G и S по отдельности и (явно задаваемый G) быстрый алгоритм декодирования МРР кода. Допустимые открытые тексты суть любые fc-векторы m = (mi,ra2,.. .,тк), компоненты которых принадлежат полю GF(qN). Шифротекст с, соответствующий открытому тексту т, вычисляется по формуле с = mGpUb + е = mSG + (mSX + є), где є — вектор искусственных ошибок — n-вектор с компонентами из поля GF(qN) и ранга г t — ti, выбираемый случайно и равномерно среди всех векторов длины п ранга г. Дешифрование. Заметим, что в соответствии с леммой 4 для любого m имеет место неравенство r(mSX + e\q) r(mSXg) + r(e\q) ti + r t.
Следовательно, применяя к шифротексту с алгоритм быстрого декодирования кода МРР, мы получим вектор mS. Домножая его на матрицу S-1, получаем открытый текст т. Из способа дешифрования видно, что матрица X используется лишь на стадии вычисления открытого ключа, а далее, как при шифровании, так и при дешифровании, используется только знание ее столбцевого ранга над GF(q). Поэтому X не является частью секретного ключа, необходимо лишь сделать ее недоступной для криптоаналитика, например, уничтожив ее после создания открытого ключа.
Использование матрицы X для МРР кодов Габидулина является необходимым. В разделе 6.2.2 будет показано, что если X = 0, то открытый ключ раскладывается на секретные составляющие за O(N ) базовых операций в GF(qN).
Для создания порождающей фробениусовской матрицы G МРР кода Габидулина длины п предлагается следующий метод. Зафиксируем базис Q — (uji,..., OJ/V) поля GF(qN) над полем GF(q). Выберем случайным и равновероятным образом матрицу Q — невырожденную N х N матрицу с элементами из GF(q). Вычислим вектор f2Q и возьмем его первые п компонент в качестве порождающего вектора g матрицы G (напомним, что п N).
Чтобы построить к х п шумовую матрицу X такую, что r(Xg) = t\ и r(K\qN) = s, можно воспользоваться следующим методом. Выберем вектор а — вектор длины t\ ранга t\ с элементами из GF(qN). Возьмем набор векторов {а }, г = 2,..., /г, так, чтобы ранг матрицы
Для построения невырожденной матрицы размера т х т с элементами их некоторого конечного поля F достаточно равновероятно сгенерировать га2 элементов поля F, составить из них требуемую матрицу и проверить, что матрица невырождена. Для любого поля потребуется всего несколько попыток. Например, в двоичном случае и т 10 потребуется в среднем 3, 5 попытки, прежде чем будет создана невырожденная матрица. 6.2 Атаки на систему ГПТ
Атака заключается в угадывании искусственной ошибки, добавленной к кодовому вектору при шифровании. Не уменьшая общности, предположим, что первые к столбцов Gpub образуют невырожденную матрицу, и обозначим ее Gi. Первые к компонент шифротекста Ci = mGi + Єї, где Єї — первые к компонент вектора ошибки.
Выберем fc-вектор е\ ранга не более г, предполагая, что он совпадает с еі. Вычислим оценку открытого текста m = (ci — e G 1 и оценку вектора ошибок е = с — m Gpub. Если r(e \q) г, то е\ угадано верно и m = m . Если неравенство не выполняется, то выбираем другой е . Сложность атаки определяется числом различных векторов ef, которое В СООТВеТСТВИИ С Теоремой 9 Составляет Ar(k) g(k+N-r)r gM_ числение оценки вектора ошибок и определение его ранга занимает, соответственно, О (к(п + к)) д- -ичных и О (rnN) g-ичных операций. Итого, сложность атаки составляет Wired = О (к(п + к)Аг(к)) О (к(п + k)q k+N-r ) . (6.3) Перебор по сообщениям Выберем произвольный fc-вектор т . Вычислим вектор с = m Gpub. Определим ранг вектора е = с — с . Если этот ранг не превосходит г, то считаем, что т — это правильный открытый текст, соответствующий с, т. е. m = m . Если это не так, то берем другой т , и так до тех пор, пока условие г (с — c \q) г не выполнится. Сложность такой атаки
