Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[4]

Группа обобщенных автоморфизмов В/с кода К, = RS,,(it.il) Рида-Соломона типа 3 (см. раздел 1.4) действует на координатах векторов х = (ха1,ха2, ,ха„)- Она образована всеми унипотентными матрицами (теорема 2) и является трижды транзитивной. Смысл этого понятия объяснен в разделе 1.10. Поэтому найдется дробно-линейная функция ф(х) такая, что

Ы В Аф • Л =

/ 47ЙШ4№)

471(1)4Л(о)4Л (ос)

4Л(1)4Л(о)4Л(оо)

V 47ЬШ47Ь(о)472 (оо)

47р«) \ 471 (АО

47г(Аг)

Т.е. найдется такая матрица • А, что (хт,хШ2,... • JV„ )Л0-Л = \iliXi.il:>X(,.il:>,x:. i.\----. .in). где <с

- элементы диагональной матрицы D, определяемой соотношением • Л = Л = Г • D (см. раздел 1.10).

Для этого, как нетрудно видеть, нужно подобрать такую функцию ф(х), что ф(ш\) = (3i, ф{х->) = /Зг, ф(соз) = /Зз, где элементы ft определяются тем условием, что матрица Л переводит координату хрг в координату х\, координату хр2 в .г,;, и координату хр3 в j-.v.

Таким образом, всегда можно полагать, что в (16) cui = 1, Ш2 = 0, W3 = 00.

5.2. Определение элементов Uj, j > 3. Найдем такие постоянные с. равные нулю, для которых выполнено

Е 41}Zjf,(coj) = 0, j = 1, d, d + 1,... , 2d - 4.

= 0,... , d - 2, не все

Для этого необходимо решить однородную систему линейных уравнений от d - 1 неизвестных с известной матрицей коэффициентов (zjfs(tUj)) - части матрицы В1. Эта система всегда имеет решение, так как уравнений меньше, чем число неизвестных.

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

Положим

Очень существенно то, что элементы 7) могут быть вычислены, исходя только из известных элементов Zifs(tUi) матрицы В1.

Поскольку элементы Zi отличны от нуля, то из (19) следует, что элементы cuj, j = l,d, d+1,... , 2d-4 являются корнями многочлена F(x). Заметим, что ни один из элементов.. ,t02d-4 не

равен оо, так как си$ = оо.

Степень многочлена ГП)(х) не превосходит d - 2, так как степени fjix). из которых он составлен, также не превосходят d - 2. Кроме того, многочлен F!>)(x) не равен тождественно 0, ибо многочлены fs{x) линейно-независимы, а коэффициенты <•* все отличны от нуля. Отсюда вытекает, что fw (>) = а(1Цх - 1)(х - w<i) {х - u2d-i), а(1) ф 0.

Отметим, что F(u) ф 0, если ш ф Uj, j = l,d, d + 1,... , 2d - 4, ш ф оо и fW(oo) = а(1К

Теперь проделаем ту же процедуру для элементов cuj, j = 2,d,d + 1,... ,2d - 4.. А именно, найдем

такие постоянные а , s = 0,... ,d - 2, не все равные нулю, для которых выполнено

У cfsicoj) =0.j = 2.,L,t-\.....2,1-4.

Положим

По тем же соображениям, что и выше, имеем F2\x) = ах(х - соа) (х - u>2d-i), Ф 0.


Рассмотрим отношение в(х) = р\щ*\ = °(многочленов F(~1\x) и F(2\x). Как уже было

замечено, FW(w) ф 0, г = 1,2, если w loj, j = 1,2,d,d+ 1,... , 2d - 4, ш ф оо. Таким образом, мы можем вычислить значение функции в(х) во всех точках cuj за исключением j = d,d + 1,... , 2d - 4 с

точностью до постоянного множителя .

Множитель Ц можно вычислить, если положить х = оо (значению а>з) в 6>(ж). В этом случае

z3FW(oo) = YltZo сz3fs(oo), г = 1,2. Таким образом, значение #(00) может быть вычислено непосредственно, исходя из матрицы В1, ибо гз/5(оо) - элементы третьего столбца В1. Для полноты изложения заметим, что FW(oo) ф 0, ибо по построению среди всех d - 2 корней многочлена F(x), степени не выше d - 2, нет корня оо. Отсюда вытекает, что

Как уже отмечалось, значения многочленов F(x) и, следовательно, значение еш = в(со) дробно-линейной функции в(х) можно вычислить в любой точке ш G Fg за исключением ш ф cuj, j = 1,2, d, d + 1,... ,2d - 4, си ф 00. Отсюда вытекает, что

uj = 0~1(e„j), j ф l,2,3,d,d+ 1,... ,2d-4(23)

Заметим, впрочем, что элементы иц, i = 1,2,3, уже известны.

Функция в1(х), как нетрудно вычислить, равна в1(х) = раЦт) • Таким образом, мы можем определить значения cuj для всех j, исключая j = d, d + 1,... , 2d - 4.

Недостающие cuj можно определить, если выбрать другие элементы, определяющие многочлены F(l\x). Скажем, в качестве такого набора для определения F!,)(x) можно взять элементы 1, W2d-3, W2d-2, • • • ,-t;:;s,/~.о и с их помощью вычислить недостающие tuj, j = d,d+ 1,... ,2d - 4.

В этой секции с помощью многочленов FW (>) произведена самая основная и трудная работа: найдена первая часть ключа - элементы cuj для всех j. Вся остальная работа по определению оставшейся части ключа, как это и обычно бывает, является более легкой и может быть произведена различными способами, один из которых излагается ниже. Кроме того заметим, что мы использовали нетривиальные свойства подгруппы группы автоморфизмов кода Рида-Соломона, а именно ее трижды транзитивность. Если бы подгруппа была только дважды транзитивной, то мы, например не смогли бы

вычислить множитель 1±щ и, следовательно, вычислить все cuj.

Трудозатраты этой части алгоритма, как нетрудно подсчитать, не больше 0(d3 + dn). Детального обоснования этой оценки производить не будем.

5.3. Определение элементов zj и матрицы h. Заметим, что если каждый элемент матрицы Л умножить на о G Fg \ {0}, а каждый элемент h на а 1. то произведение В = h В Л останется неизменным. Поэтому можно считать, что z\ = l.

Найдем такие элементы с\,с2,... ,с&, что

Ycszsfj{ujs)=Q, j = 0,...,d-2.(24)

Отметим, что все элементы c\,c-i, ,04 отличны от нуля, поскольку в противном случае код с проверочной матрицей В1 имел бы кодовое расстояние меньшее d (см. раздел 1.3, утверждение 1). Соотношение (24) в матричной форме имеет вид

B"d diag(zi,z2,... ,2rf)(ci,c2)... ,cdf = 0,(25)

где Bd = (Ji(cuj)), i = 0,1,... ,d - 2, j = 1,2,... ,d - матрица размера d - 1 x d. Заметим, что матрица Bd diagui. z->.... ,zd) является матрицей, совпадающей с первыми d столбцами матрицы В1.


Как нетрудно видеть />/ = • />,/. где

/ w°

i , ,d-2

, ,d-2 co2

h-Bd- -diag(2i,22,.

• • ,)(cbc2,

, cd)

)T = o,

Bd •diag(ci,c2). ,cd) (z1,z2,... ,zd)T = 0.

(27) (28)

Соотношение (28) мы будем рассматривать как линейную систему уравнений относительно неизвестных z2,zs,... ,Zd с учетом того, что ненулевые элементы ci,c2, .г,/ и элементы lo\,lo2,. .. ,Ud уже известны, a z\ = 1. Эта система имеет единственное решение, поскольку ее матрица ее коэффициентов

( <4

"d \

diag(c2,c3,... ,cd)

является, очевидно, невырожденной. Решая эту систему, найдем элементы z\,z2j Найдем теперь элементы матрицы h = (hij), i,j = 0,... ,d - 2. Имеем

Yhi,sCOSj = Zjfi(coj).

Зафиксировав какое-либо L 0 < i < d-2. и изменяя j от 1 до d - 1, получим систему линейных уравнений с неизвестными Ы$,Ы,1,... ,Ы-2- Определитель этой системы является определителем Вандермонда, поэтому ее решение ;.<,. h-,,\.... . h;.d :> находится однозначно. Решив эту систему для каждого % мы найдем матрицу h.

Таким образом, мы сумели определить матрицу h, элементы со\, со2,... , cod и элементы z\, z2,... , Zd-Для того чтобы определить оставшиеся элементы Zd+i,Zd+2,. , zn проще всего поступить следующим образом.

Умножим матрицу В1 слева на матрицу Л-1. В результате получим матрицу

/Г1 в =

( zxco\

z2co2 z2co\

znco% zncon znco\

\ zicot2

z2cot2

Вид последней матрицы делает задачу определения элементов Zd+i,Zd+2, ,zn тривиальной.

Число операций, требуемых для реализации этой части алгоритма по определению оставшейся части ключа (матрицы h и всех элементов Zj) не выше 0(d4 + dn). Таким образом, общее число операций по реализации всего алгоритма не более, чем 0(dA + dn). Следовательно, сложность этого алгоритма является полиномиальной от длины п используемого кода. Соответствующая система открытого шифрования как Маклиса так и Нидеррайтера, построенная на коде Рида-Соломона, не является стойкой. Это основной результат работы.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5]