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


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




[2]

Из теоремы 1 и соотношений (7) и (10) следует

Следствие 1. Для числа Aq(n,d) различных обобщенных Рида-Соломона К, = RSq(n,d) в ансамбле Лк, имеет место оценка

А (п d) > nl(q-1)n - nl(q-1)n (11)

Aq(n,a)> N " (-1 1)(-1 д)...(-1 -2)»W

где k = n - d + 1 - размерность кода К. = RSq(n,d) и Nq<k - число различных невырожденных матриц размера k х к.

Далее мы докажем, что группа В/с содержит подгруппу, изоморфную группе дробно-линейных преобразований. Строение последней группы мы изучим в следующем разделе.

1.10. Группа дробно-линейных преобразований. Элементами группы дробно-линейных преобразований Фд множества Fg = Fg U {оо} в себя являются дробно-линейные функции ф(х) = ffpf,

отличные от постоянной, т.е. функции, у которых определитель матрицы ( а ] отличен от нуля.

\ с е J

Очевидно, каждое дробно-линейных преобразование ф(х) взаимно однозначно отображает множество F в себя.

Множество Фд действительно является некоммутативной группой. "Умножением" ® в ней служит суперпозиция функций, т.е. ф® ф = ф(ф(х)). Группа Ф? = PGL(2,q) имеет порядок (q + l)q(q - 1). Очень интересным свойством группы Фд является ее трижды транзитивность. Это означает, что для любых двух пар троек (oi, а2,03) и (pi, 62, &з), b-, 6 Fg, с попарно различными координатами в группе Ф? найдется элемент ф (всегда один), для которого выполнено ф(а;) = bi, i = 1,2,3. Доказательство этих свойств несложно и предоставляется читателю (см. также [23] и [24]).

Теорема 2. Группа В/с обобщенных автоморфизмов кода К. = RSq(n,d), п = q + 1, Рида-Соломона с проверочной матрицей В (см. (4)) содержит подгруппу, которая изоморфна группе дробно-линейных преобразований множества F.

Доказательство. Как и выше, будем индексировать столбцы матрицы В (см. (4)) элементами множества Fq. Так столбец B(ctj) = (а®,а}-,... ,ad~2)T имеет номер (индекс) oij.

Пусть ф(х) = -р! - дробно-линейная функция. Через Г обозначим подстановочную матрицу, реализующую перестановку х -> ф(х) элементов множества Fg и через Д;, =

diag((cai + e)d~2, (саг + e)d~2, , (са„ + e)d~2) - диагональную матрицу, определяемую значениями знаменателя функции ф(х) на всех элементах множества Fg.

Прямое вычисление показывает, что />(а;) • Г • Д;, = ((га / + с)12, (aotj + Ь)(с<ъ> + с)1".... , (aotj + 6)r/ 3(га2 + в), («а;- + Ь)1 ). Каждый многочлен (ах + Ь)1 2 (сх + <•) может быть представлен как линейная функция мономов 1, X j j » » » j X d 2. Поэтому столбец />(а,) • Г,;, • Д, можно представить как />(а;)Г,;, • Д, = h(l,x,x2,... .х! ). и, следовательно, матрицу В • Гс, • Д, - в виде В • Гс, • Д, = h В. где строки невырожденной матрицы h = {h} определяются равенством (ах + Ь)1 2 (сх + с) = Yli=o /../•"• Таким образом, при любом ф матрица Г,;,-Д*;, входит в группу обобщенных автоморфизмов Вк.

Матрицы = Г • Вф образуют группу изоморфную группе Фд. Для того, чтобы это проверить, заметим, что Г1 • Оф, Гф = diag((c(ai) + e)d~2,... , [сф(ап) + e)d~2) = Оф,ф, если ф(х) = frffr-Отсюда Ду • Г = Г • Вфф. Следовательно, Гф> Ду Гф Д;, = Гф>®ф Вфф Д;,. Прямая выкладка показывает, что Вф1 ф Д;, = Вфиф, т.е. группа, образованная матрицами Г • Д;,. изоморфна дробно-линейной группе Ф?. Теорема доказана.

Этот результат будет использован при анализе стойкости системы открытого шифрования, построенной с помощью кода Рида-Соломона (см. §4).

Группа В/с обобщенных автоморфизмов кода Рида-Соломона также является трижды транзитивной в следующем смысле. Для любой пары упорядоченных троек из попарно различных элементов (/3i,/32,/33) и (71,72,73), где {/3i,/32,/33}, {71,72,73} € 21 = {аьа2,... ,а„} = Fg существует такая унипотентная матрица € В/с, которая переводит координаты xt31,xt32,xt33 вектора х = (ха1,ха2,ха„) в координаты х1г,ж72,х1з вектора хА с умножением их на соответствующие постоянные, определяемые диагональной матрицей Д;, = diag(<iai,da2,• • • ,da„)- Например, с помощью подходящей матрицы можно передвинуть на первые три места любые три координаты вектора х. В частности, если {/3i = 1,/32 = 0,/Зз = оо} и 71 = ai,72 = а2,7з = аз, то

хЛ = (daiX1,da2X0,da3Xoo,da4,Xlpa4), • • • ,a„(a„)) ДЛЯ НвКОТОрОЙ ПОДХОДЯЩвЙ фуНКЦИИ ф(х).


2. Декодирование

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

Неформально говоря, под термином "декодирование" понимается алгоритм, который позволяет по искаженному ошибками кодовому вектору а восстановить исходный кодовый вектор а. Таким образом, декодирование сводится к решению уравнения

а=а + е, а 6/С, wt(e) < t,(12)

где неизвестными являются кодовый вектор а и вектор ошибки е. Имеется несколько различных типов декодирования.

i.Корреляционное декодирование кода К.. Это алгоритм, который по предъявленному вектору х G F™ находит один или несколько кодовых векторов а € К-, ближайших (в метрике Хемминга) к х.

ii.Декодирование кода К. в пределах его кодового расстояния. Это алгоритм, который по вектору х, который отстоит от одного из кодовых векторов К. на расстояние < !К*Г • вычисляет этот ближайший кодовый вектор. Этот вектор обязательно является единственным. Векторы х, которые отстоят от всех кодовых точек на расстояние большее, чем половина кодового расстояния, могут быть декодированы как угодно, в частности, алгоритм может вообще отказаться от их декодирования.

Ш. Декодирование кода К, за пределами его кодового расстояния. (Алгоритм промежуточного положения между i. и ii.) Это алгоритм, который по вектору х, находящемуся не очень далеко (</(х.а) < t) от некоторого кодового вектора а кода К,, вычисляет один или несколько кодовых векторов а, находящихся на расстоянии < t от х, где t > dK1 - некоторая постоянная (параметр алгоритма).

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

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

Наиболее легким для реализации является алгоритм декодирования типа ii.. Для большинства, так называемых, алгебраических кодов известны алгоритмы декодирования в пределах их кодового расстояния, сложность которых возрастает как полином небольшой степени от длины кода. К таким кодам относятся и, рассмотренные нами, обобщенные коды Рида-Соломона RSq(n,d). Их декодирование в пределах кодового расстояния может быть осуществлено не более, чем за 0(п3) операций в поле F,, [7], [2].

Не надо думать, что для каждого кода существует простой алгоритм декодирования в пределах его кодового расстояния. По современным представлениям такие алгоритмы могут существовать только для кодов, которые снабжены определенной алгебраической или комбинаторной структурой. Вместе с тем у большинства кодов, не очень точно выражаясь, отсутствует в проверочной матрице какая-либо структура, - это коды "общего положения". Примером первого типа кодов является код Рида-Соломона или код Рида-Маллера (совершенно разные коды), а примером второго - код, у которого проверочная матрица выбрана случайно среди всех матриц определенной размерности.

Декодирование в пределах кодового расстояния (типа ii.) некоторых типов кодов общего положения является NP-полной задачей, т.е. предположительно не может быть осуществлено за полиномиальное время от их длины. Более того, общепринято, что

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

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


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

Приведем одно почти очевидное утверждение о сложности декодирования любого кода с помощью алгоритма типа ii..

Утверждение 2. Любой линейный код К, с параметрами [п, k,d]r, d < п/2, имеет алгоритм декодирования в пределах его кодового расстояния, сложность которого не выше 0(mm(nrk, п Sj=o ("))> zdet = {].

Отметим, что rk - число элементов в коде К. и 0(nrk) - число операций требуемых для перебора всех элементов кода и сравнения каждого из них с искаженным кодовым вектором а. Далее, Ylj=o (™)(r ~~ 1)J - число элементов в шаре радиуса t с центром в точке х и 0(п Ylj=o (")) - число операций, требуемых для перебора всех элементов шара с целью нахождения среди них кодового вектора.

3. Система открытого шифрования на основе кода, корректирующего

3.1. Система открытого шифрования Маклиса. Идею построения системы открытого шифрования проще всего пояснить на примере кода Боуза-Чоудхури-Хоквингема />(. ,. (»•</) размерности к.

Пусть А - фиксированная порождающая матрица обобщенного кода BCHr(n,d) над F,.. т.е. матрица ранга к и размера кхп, для которой А СТ = 0, где С - матрица, определенная соотношением (8). Между прочим, в качестве А можно взять матрицу, которая имеет тот же вид, что и С. Этот факт мы использовать не будем.

Ансамбль Ar(n,d) порождающих матриц обобщенного кода />(. ,. (»•</) определим как множество всех матриц вида h А Г • D, где h пробегает множество всех невырожденных к х -матриц над Fr, D - множество всех диагональных матриц с ненулевыми на диагоналями элементами, а Г - множество всех перестановочных матриц размера п х п. Соответственно, ансамбль кодов fCr(n,d) определяется как множество всех кодов с порождающими матрицами из ансамбля Ar (п, d). Матрицы h, Г, D "маскируют" матрицу А.

Передача секретного сообщения абонента У. предназначенного абоненту Л, предваряется следующими действиями. Абонент X случайно, равновероятно в соответствующем множестве и независимо от других абонентов выбирает матрицы h = hx, D = dx, Г = Fx и вычисляет матрицу А = Ах = hx А Тх Dx из ансамбля Ar(n,d). Матрица Ах является открытым (общедоступным для всех абонентов) ключом (public key), а матрицы hx,tx,dx~ секретным ключом (private key) абонента X.

Шифрованная информация b (криптограмма), которую абонент У передает по общедоступному каналу абоненту X, в системе Маклиса [1] представляет собой вектор длины п и вида b = ЗАХ + е, где а - г-значный вектор длины к, несущий конфиденциальную информацию абонента У. а е - секретный вектор ошибок веса, не превосходящего t, и длины п, который случайно и равновероятно выбирается абонентом У среди всех векторов веса не выше г.

Таким образом, для того чтобы расколоть открытую информацию необходимо представить вектор b в виде

Ь = а + е,(13)

где вектор а = аАх принадлежит коду К = Кх с порождающей матрицей Ах, а вектор е имеет вес < *•

Другими словами, злоумышленнику необходимо декодировать код К с известной порождающей матрицей Ах. Матрица Ах замаскирована матрицами Л, В и Г и поэтому она, вообще говоря, представляется нападающей стороне как матрица общего положения. По тезису А в этом случае сложность декодирования не является полиномиальной от длины п кода К. Следовательно, при достаточно больших п процедура декодирования недоступна для злоумышленника из-за ее большой вычислительной сложности. Вместе с тем декодирование кода К той же длины п для легитимного абонента X, знающего секретный ключ, является вычислительно достижимым.

Действительно, абонент X, получив вектор Ь, восстанавливает кодовый вектор ЗАХ следующим образом. Сначала он строит вектор Ь = ы) 1 • 11. который , очевидно, является вектором кода



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