Сидельников В. - Криптография и теория кодирования

Современная криптография является наукой и одновременно искусством защиты информации. Наиболее известные математической общественности результаты современной криптографии относятся к теории чисел и теории сложности.
Менее известно, что теория кодирования так же или даже более необходима для решения широкого круга криптографических задач.
Настоящий доклад призван рассказать о достижениях криптографии, которые получены с помощью теории кодирования, и указать на их значимость.
Теория кодирования в первую очередь связана с традиционной криптографией, а именно с ее главным разделом, в котором изучается так называемое симметрическое шифрование.
Симметрическое шифрование это современное название процедуры шифрования и расшифрования, которые реализуются на обоих концах линии связи с помощью одинаковых или почти одинаковых шифровальных устройств (шифраторов). Между прочим, еще 25 лет назад других шифрований, одно из которых сейчас называется асимметрическим, не было известно, все системы шифрования были симметрическими.
Симметрическое шифрование является наиболее распространенным в современном мире, хотя усилия известных математиков в последние годы по ряду причин почти полностью были направлены на исследования проблем, связанных с асимметрическим шифрованием и открытым распределением ключей.
Особым видом симметрического шифрования является, так называемый, шифр Вернама, который представляет из себя наложение на открытую информацию белой гаммы. Это один из немногих видов шифрования, для которого можно строго доказать (см. [1]) его абсолютную нераскрываемость.
Шифры, подобные шифру, Вернама обычно изучают в рамках теории информации, которая и возникла в трудах К. Шеннона под сильным влиянием его занятий криптографией. Подобные шифры и связанные с ними теоретико-информационные проблемы мы в настоящей работе рассматривать не будем.
В работе под симметрическим шифрованием понимается автоматное шифрование с относительно небольшим ключом.
При симметрическом шифровании нападающая сторона (противник) не может прочитать зашифрованное сообщение из-за того, что он не знает алгоритма шифрования, который в значительной мере определяется секретным ключом.
Асимметрическое шифрование принципиально отличается от симметрического тем, что его алгоритм шифрования, который представляет собой отображение некоторого множества в себя, общеизвестен. Стойкость этого шифрования основывается на том, что противник (нелегитимный пользователь) не в состоянии доступными ему средствами вычислить обратное отображение.
Вместе с тем вычисление обратного отображения для легитимного пользователя вычислительно доступно из-за того, что он знает некоторый секрет, который был использован при построении прямого отображения.
Из материалов конференции Московский университет и развитие криптографии в России (МГУ, 17-18 октября 2002 г.).
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (код проекта 0201-00687).
Асимметрическое шифрование принципиально отличается от симметрического еще также тем, что для него не нужен абсолютно надежный канал для рассылки секретных ключей. Это свойство в некоторых случаях дает асимметрическим системам шифрования значительные практические преимущества перед традиционным симметрическим.
Вместе с тем необходимо отметить, что, во-первых, сложность вычисления значений одностороннего отображения и его обратного, т.е. сложность асимметрического зашифрования и расшифрования, обычно значительно выше, чем сложность этих процедур при традиционных симметрических автоматных методах шифрования, и, во-вторых, в настоящее время неизвестны практически реализуемые системы асимметрического шифрования, для которых достаточно убедительно доказана невозможность их раскалывания квалифицированным незаконным пользователем.
Следует сказать, что всегда (это справедливо и в данном случае) высокую стойкость криптографической системы криптографу удается обосновать лишь в рамках рассматриваемых им же методов анализа этой системы.
Стойкость всех асимметрических систем шифрования, подвергнувшихся серьезному криптографическому анализу, всегда существенно ниже, чем мощность пространства ключей, и имеет явную тенденцию к постоянному снижению.
Настоящая работа включает в себя несколько этюдов по отдельным разделам криптографии, которые так или иначе связаны с теорией кодирования. Автор на полноту охвата предмета не претендует.
Особенно существенным и интересным автору представляется последний раздел работы (часть II), где конкретно и подробно рассматривается один метод определения ключей асимметрической системы шифрования. Как может увидеть читатель, для того чтобы расколоть даже относительно несложную систему необходимо использовать нетривиальные и глубокие математические результаты.
По мнению автора, стойкость криптографической системы существенно зависит от квалификации и способностей того, кто анализирует эту систему.

Теоретико-кодовые асимметрические системы шифрования

В настоящее время известно только 3-4 типа асимметрических систем с предположительно высокой стойкостью шифрования. Одним из них являются системы открытого шифрования МакЭлиса и Нидеррайтера, в основе которых лежат коды, корректирующие ошибки. Их стойкость основана на том, что декодирование кодов общего положения является NP-трудной задачей [20], в то время как сложность декодирования некоторых алгебраических кодов является относительно простой вычислительной задачей. Поэтому основная идея, которая используется при построении этих систем, состоит в маскировке алгебраических кодов под коды общего положения.
Стойкость этих систем в основном зависит от того, насколько хорошо выполнена такая маскировка.
Теоретико-кодовые системы отличаются от других систем тем, что у них, с одной стороны, скорость зашифрования и расшифрования заметно выше, а с другой стороны объем их открытого ключа значительно больше, чем у остальных систем открытого шифрования. Первое является значительным преимуществом, а второе недостатком.
Теория кодирования доставляет несколько примеров стойких систем открытого шифрования. Остановимся на одном из них.
Пусть С линейный код с параметрами (n,k,d) над конечным полем Fg, который имеет простое декодирование, и М его порождающая к х п-матрица. Пусть Л невырожденная к х ^-матрица и Г перестановочная п х п-матрица.
Открытой информацией, подлежащей шифрованию, в теоретико-кодовой асимметрической системе шифрования является к-мерный вектор ш G Fg, а шифрованной информацией п-мерный вектор ш = шН ¦ М ¦ Г + е, где е случайный вектор веса wt(e) ^ [рр]. Секретный ключ образуют матрицы Л и Г, а общедоступным ключом является матрица М' = Н-М-Т. Случайный элемент е генерирует отправитель.
Матрицы Л и Г маскируют порождающую матрицу М с простым алгоритмом декодирования.
Получив ш, легитимный абонент X, который знает секретный ключ, вычисляет следующие элементы: ш' = иіГ '. декодирует га', т.е. представляет его в виде ш' = а + е', а € С. wt(e') ^ [рр], где а = шН ¦ М, и, наконец, с помощью последнего соотношения находит ш = all 1.
Проделать последнюю цепочку вычислений злоумышленнику трудно из-за того, что он не знает Г. Поэтому ему трудно декодировать код С с порождающей матрицей М', который для него является кодом общего положения.
Известно, что сложность N декодирования таких кодов общего положения имеет вид N = 2cmm(i,n-t) [22, 23]. Поэтому даже при относительно небольших кшп к вычислительная сложность декодирования для таких кодов является неприемлемо большой.
Если в качестве С взять Боуза Чоудхури Хок?ингема код [18] или Рида Маллера код [12], то при подходящем k ж п мы получим предположительно стойкую систему асимметрического шифрования. Если же в качестве С взять Рида Соломона код, то получим заведомо слабую систему [И].

О стойкости симметрических систем шифрования

Возвратимся снова к симметрическим системам шифрования. По-видимому, наиболее значительным полем применения теоретико-кодовых конструкций, но в то же время наименее известным математической общественности, является анализ стойкости и синтез шифраторов. Традиционно стойкость шифратора определяется как число операций, необходимых для определения его ключа при некоторых предположениях.
В первом приближении предполагается, что нападающая сторона, называемая также противником или злоумышленником, знает устройство шифратора, но не его ключ. Противник знает и некоторое число знаков, которые выработал шифратор на данном ключе.
Многие проблемы теоретической криптографии, относящиеся к анализу стойкости симметрических систем шифрования, изучаются в рамках давно сложившихся направлений математики: теории вероятностей и статистики, теории чисел, алгебры, теории кодирования, комбинаторики, теории сложности вычислений. В качестве примера укажем на методы построения рекуррентных последовательностей с определенными свойствами, методы выявления статистических закономерностей в массивах дискретной информации, поиск эффективных способов разложения на множители больших целых чисел, свойства булевых функций и преобразований, методы дискретной оптимизации и многие другие.
Особенно большое значение для криптографии имеют результаты, связанные с построением эффективных алгоритмов решения тех или иных конкретных задач. Например, решение системы линейных уравнений, умножение матриц, вычисление значений некоторых булевых функций и преобразований, а также и многие другие, являются массовыми задачами для многих методов определения ключа.
Поэтому знание эффективных оценок сложности их решения (как верхних, так и нижних) позволяют делать относительно обоснованные выводы о стойкости систем шифрования.
Ввиду того, что задача определения ключа может быть представлена как задача решения некоторой системы нелинейных уравнений в конечном поле, для криптографии представляют значительный интерес методы решения систем того или иного вида и оценки их сложности. С примерами криптографических исследований можно познакомиться по многочисленным работам, связанным с изучением свойств преобразования DES, которые опубликованы в последние 20 лет в Procedings of Crypto, Pro-cedings of Eurocrypt, Journal of Cryptology и в [6, 4].
Если говорить обобщенно, как правило при анализе и синтезе необходимо решить многие задачи, которые похожи или совпадают с традиционными задачами теории кодирования. При этом не следует умалять роль и многих других математических дисциплин, задачи которых также возникают при анализе криптосхем. Вместе с тем задачи теории кодирования играет здесь наиболее заметную роль. Это связано с тем, что теория кодирования и криптография, без сомнения, имеют родственные генетические основы: первая борется с атаками природы (ошибками), а вторая с атаками злоумышленников.
Методология защиты от этих атак во многом совпадают. Недаром основоположник научной криптографии К.Шеннон одновременно является и основоположником научных основ как криптографии, так и теории кодирования.

Аппроксимация булевыми функциями

Одним из примеров криптографической задачи, в решении которой значительную роль играют идеи и методы теории кодирования, является задача приближения одной сложной и не до конца известной булевой функции другой простой, которая принадлежит некоторому узкому классу булевых функций.
Более подробно: пусть нам известна двоичная последовательность
(1)
7 = (f(a,i),f(a2),...,f(aN)),aj G F™,
где / неизвестная булева функция, связанная некоторым образом с неизвестным ключом шифратора. Координаты последовательности 7 определяются известными нам входами а,-. Мы хотим приблизить в метрике Хемминга последовательность 7 последовательностью
Th = (h(ai),h(a2),...,h(aN)), (2)
где h, например, является аффинной функцией. Ближайшая функция h, как правило, дает некоторую информацию об устройстве функции /. Эта информация может быть полезна при определении ключа шифратора.
На самом деле в этой задаче заложено две подзадачи. Во-первых, надо выбрать схему шифратора так, чтобы последовательность 7 плохо приближалась последовательностями сг/,. определяемыми функциями h, которые принадлежат узкому классу L. Во-вторых, надо иметь эффективные алгоритмы, которые позволяют находить ближайшую к 7 последовательность т/, и, следовательно, функцию Ь.
Последний алгоритм естественно рассматривать как алгоритм декодирования искаженной последовательности 7 кода К длины N, который образован всевозможными последовательностями 07,. h G L. Подробно подобная задача рассматривалась в работе [13].
В теории кодирования известно не так много кодов, которые имеют эффективные алгоритмы декодирования. Одним из таких кодов является код Рида Маллера первого порядка.
Для него и некоторых его модификаций известно [21] , [25] несколько различных алгоритмов быстрого декодирования. Все они так или иначе используют быстрый алгоритм умножения вектора на матрицу Адамара Уолша.
Последний алгоритм весьма широко используется в современной криптографии.

Криптографические протоколы

Переходим теперь к обсуждению некоторых криптографических протоколов. Упомянем из них только те, в которых по существу используются теоретико-кодовые конструкции.
В симметрических системах шифрования все пользователи должны быть тем или иным способом снабжены ключами. Обычно это осуществляется с помощью дополнительных секретных каналов связи, которые в свою очередь подвержены атакам противника. Безопасное хранение и использование таких секретных ключей является также весьма нетривиальной проблемой.
Задачи безопасной пересылки и сохранения ключей в секрете решаются как с помощью физических методов, так и в последнее время с помощью методов теории кодов, корректирующих ошибки. В частности, рассматривались теоретико-кодовые методы разделения секретов и методы, защищающие секретные ключи от компрометации при их пересылке и хранении.
Некоторые из этих весьма нетривиальных и практически полезных методов защиты ключей были разработаны в России.
Одной из важнейших задач криптографии является разработка методов, защищающих информацию, например, финансовую или командную, от неконтролируемого ее изменения при передаче ее по общедоступным каналам связи, при хранении и при некоторых других видах ее использования. В этому же кругу задач относятся и механизмы доказательства принадлежности.
При этом скрытие информации не всегда является необходимым.
К криптографическим протоколам, решающих подобные задачи, относится цифровая подпись и имитозащита информации. Цифровая подпись является общеизвестным криптографическим протоколом, в котором широко используются теоретико-числовые конструкции.
Вместе с тем известны подходы по созданию цифровой подписи на базе кодов, корректирующих ошибки.
С другой стороны, методы имитозащиты информации полностью базируются на очень изящных конструкциях, которые родственны или совпадают с конструкциями, которые разработаны в теории кодирования. Так, одна из основных таких конструкций называется кодами, обнаруживающими обман.
Пусть необходимо передать элемент а из конечного множества А. В качестве а часто выступает значение хеш-функции. Будем предполагать, что на обоих концах канала связи имеется секретный элемент Ъ (ключ) из множества В. Пусть функция р(х,у) : А х В -^4- (' инъективна при каждом фиксированном у и обладает тем свойством, что для каждого а и с множество S(a,c),S(a,c) С В, решений уравнения ір(а, у) = с имеет достаточно много элементов.
В рассматриваемой системе имитозащиты по общедоступному каналу связи вместо элемента а из А передается элемент с = ір{а,Ъ). Законный пользователь знает ключ Ъ, поэтому он, получив элемент с, решает уравнение с = ір(х, Ь) и определяет элемент а.
Представим, что элемент а известен незаконному пользователю (злоумышленнику), который предполагает заменить его на другой элемент а' (навязать фиксированный элемент а'). Для этого злоумышленник вместо с должен послать с' такое, что уравнение с' = ір(х,Ь) имело решение х = а'; только в этом случае законный пользователь не заметит подмены и произойдет неконтролируемое изменение информации.
Стратегия поведения злоумышленника в этом случае может состоять только в переборе элементов множества ip(a',S(a, с)) с надеждой напасть на подходящий элемент с'. Если это множество имеет достаточно много элементов, то эта стратегия становится неэффективной.
Рассмотренная выше идея может быть реализована, например, с помощью множеств А = Fq, В = {b = (bi,b2)\bi 6 Fq,bi Ф 0}, С = Fq и аффинной функции ір(а,Ь) вида с = а ¦ Ъ\ + Ьг, где Fq конечное поле с q элементами. Отметим, что при каждом Ъ из В функция ір(х, Ь) является перестановкой элементов поля а функции {Г?(.г.
Ь);Ъ € В} дважды транзитивной группой перестановок на Fq. Несколько более сложная конструкция позволяет построить систему имитозащиты, которая практически исключает возможность навязывания не только фиксированного элемента а', но и какого-либо а', отличного от а. Отметим, что в рассмотренном примере одновременно с имитозащитой осуществляется и шифрование сообщения а.
Часть II

Как раскалывается одна асимметрическая система шифрования

Основной целью данного раздела работы является рассказ со всеми подробностями о том, как можно расколоть за полиномиальное время систему открытого шифрования Нидеррайтера или МакЛиса, построенную на основе кодов Рида Соломона. Основные результаты этой статьи впервые изложены в работе Шестакова С. О. и автора [11].
Как полагает автор, статья будет полезной молодым исследователям.
Не надо думать, что все системы открытого шифрования, основанные на кодах, корректирующих ошибки, являются не стойкими. Данная работа является единственным известным примером кодовой системы открытого шифрования, которая раскалывается за полиномиальное время.
Даже эту относительно простую систему расколоть, как будет видно ниже, весьма нетривиально. Для этого используются многие замечательные алгебраические конструкции: группы, матрицы, конечные поля и т.п.
Как представляет себе автор, доказательство нестойкости даже отдельной системы шифрования, которая только деталями отличается от подобных стойких систем, имеет существенное как педагогическое, так и научное значение не всё предлагаемое в открытой криптографии является качественным. Автор попытался сделать изложение замкнутым, но, по-видимому, полностью осуществить это ему не удалось.
7 Коды Рида Соломона

Основные понятия теории кодирования.

В настоящем разделе будут даны только начальные сведения о теории кодирования, необходимые для определения систем открытого шифрования, предложенных Маклисом [10] и Нидеррайтером [14]. Для простоты, мы рассматриваем только частные случаи кодов, которые имеют наибольшее значение для криптографии.
Значительно более полное изложение теории кодирования имеется в книгах [17] и [35].
Мы рассматриваем конечное поле Fg, ц = р1, где р простое число и I положительное целое, содержащее q элементов. Множество FJ = (ж = (жі,... ,xn)\xj G Fg}, мы обычным образом рассматриваем как линейное пространство размерности п.
На пространстве Fg! задана метрика Хемминга, которая определяется следующим образом. Расстояние і(х,у) между двумя векторами ж и у из F равно числу координат, в которых эти векторы различаются.
Например, расстояние между векторами (0,1,2) и (2,1,0) из F| (трехмерное пространство над полем F3 = {0,1,2} из трех элементов) равно 2, так как эти векторы различаются только в первой и последней координате. Метрическое пространстве FJ с метрикой Хемминга будем называть пространством Хемминга. На пространстве Хемминга рассматривают еще одну функцию wt^) вес вектора ж, равный числу его ненулевых координат.
Функции d(ж, у) и wt^) связаны соотношениями d(x,y) = wt(x - у), d(0,ж) = wt^).
Кодом называется произвольное подмножество JC пространства F. Кодовое расстояние іЦк'А кода К, определяется как минимальное расстояние между двумя различными элементами К,, т.е. іІ(к'А = пипц-.у.;.?:ш /yd(x. у). Всюду далее мы в качестве кодов К, будем рассматривать только линейные подпространства L пространства F. Размерность L всегда будем обозначать буквой к. Такие коды называются g-значными линейными кодами.
Их параметры коротко записываются в виде [и. к. d\,r где п длина кода К, к его размерность и d = il(k'A его кодовое расстояние. Число г = п к обычно называют избыточностью кода.
Следует заметить, что кодовое расстояние линейного кода может представлено и несколько иным, во многих случаях более удобным способом. А именно, d(K.) = минимальному весу ненулевого элемента кода к'..
Определенные выше коды используются для коррекции ошибок при передачи информации в канале связи. Схема такого использования состоит в следующем.
Под одиночной ошибкой типа замещения мы понимаем замену одного из символов в векторе ж G F на другой символ. Если в векторе ж произошло t ошибок, то t координат изменило свое значение.
То, что пространство F является метрическим, позволяет утверждать, что і-кратная ошибка превращает кодовый вектор ж в вектор ж', отстоящий от ж на расстояние t, т.е. d(ж, ж') = t. Таким образом, если в канале связи происходит не более, чем t ошибок, то искаженный кодовый вектор ж' находится в шаре (в метрике Хемминга) радиуса t с центром в точке ж € К..

Геометрическая интерпретация кода.

Если все шары радиуса t с центрами в кодовых точках кода К, не пересекаются, то из очевидных геометрических соображений следует, что код может исправить любые t или меньше ошибок, которые поразили кодовый вектор ж в канале связи. Для этого необходимо использовать процедуру декодирования, которая находит тот центр шара ж (кодовый вектор), к которому принадлежит искаженный вектор ж'. Из сказанного выше вытекает, что если код имеет кодовое расстояние d(k'A ^ 2t + 1, то он может корректировать все ошибки кратности t.
Вектору и = (I...../.- )- aj е Fg, который переносит информацию, поставим в соответствие
кодовый вектор х(а) G к'-. Для передачи информационного вектора а по каналу связи с шумами в канал вместо а посылают кодовый вектор ж (а). На выходе канала после декодирования определяется вектор ж (а), а затем и информационный вектор а.
Рассмотренную геометрическую модель коррекции ошибок можно построить из-за того, что F является метрическим пространством, метрика которого в согласована с видом искажений, которые возникают в канале связи. Можно сказать, что с геометрической точки зрения теория кодов, исправляющих ошибки, представляет собой науку, которая занимается упаковками шаров в метрических пространствах, в частности, в пространстве Хемминга, а также задачами декодирования кодов того или иного вида.
Таким образом, такое весьма абстрактное математическое понятие, как метрическое пространство, оказывается весьма полезным для содержательных и наглядных представлений кодов К,, корректирующих ошибки, и в конечном итоге для их построения и использования.
Одной из основных задач теории кодирования является задача построения кода длины п с кодовым расстоянием d с возможно большим числом элементов, т.е. в случае линейного кода с возможно большой размерностью к. За многие годы развития теории кодирования создано большое число разнообразных кодов. Мы остановимся только на относительно узком классе: классических и давно известных кодах Рида Соломона и кодах Боуза Чоудхури Хоквингема (БЧХ-код).
Код Рида Соломона является частным случаем БЧХ-кода.

Проверочная и порождающая матрицы линейного кода и их свойства.

Будем пользоваться без объяснений стандартными понятиями теории конечных полей и линейной алгебры.
Подпространство К, (линейный код над конечным полем Fg) пространства F может быть определено (задано) двумя способами: как своим базисом, так и базисом пространства К .

Коды Рида — Соломона

двойственного к К (определение ниже). Первый способ определения кодов является более естественным, но зато второй во многих случаях более удобен для их построения и исследования их свойств. Он преимущественно используется в теории кодирования.
Мы также часто будем пользоваться вторым способом задания линейного кода. Подробно объясним, что это такое.
Скалярное произведение (х,у) векторов х = (.щ----, ж„), у = і;у\----,уп) ? Fg! в поле F,; определя
ется соотношением
П
*,?) = 5И, (з)
і=1
где сложение и умножение в последней сумме выполняется в поле F?.
Код А: над Fg состоит из всех векторов Ь ? Fg!. таких, что (6, а) = 0 для всех а ? к'.. Но другому,
если і.....а/.. базис кода к'.. то базисом кода к', являются векторы Ьі.....Ьп для которых
(bj,as) = 0 для всех s = 1,..., к. Отметим, что сумма размерностей кодов К. и к', равна п.
Матрица В, строками которой являются базисные векторы bs кода К (их число п к) называется проверочной матрицей кода К. а матрица А, строками которой являются базисные векторы кода к'.. называется порождающей матрицей кода к'.. Таким образом, коду К. принадлежат все векторы а, для которых выполнено
/’' =(). а G F. (4)
где значок ' обозначает транспонирование соответствующего объекта, или все векторы а, которые имеют вид
а = йЛ. aeFg, a ? F. (5)
Заметим, что в формуле (4) а1 столбец высоты п. Матрицы /’ и ,4 по определению взаимно ортогональны: А ¦ Вт = О, В ¦ Ат = 0.
Утверждение 1. Код К, имеет кодовое расстояние d, если выполнены два условия
i. Любой комплект из d 1 столбцов матрицы В является линейно-независимым.
ii. Найдется комплект из d столбцов матрицы В, который является линейно-зависимым.
С помощью утверждения 1 все или почти все методы построения кодов К. с кодовым расстоянием d сводятся к построению проверочной матрицы В, у которой любой комплект из d 1 ее столбцов является линейно-независимым.
Наиболее известными матрицами В, для которых выполнено утверждение 1, являются матрицы

В = Вц =

аі а% а\ QLi 0.2 а5 2 2 Щ а; d-2 d2 d- а2 - (У 'лп

(6)
d 2,
где п ^ g 1 и 21 = {ад, ад,..., ап} комплекта из d 1 столбцов матрицы определитель
/з? at
Pl $2
al at
различные ненулевые элементы поля Fg. Столбцы любого В является линейно-независимыми. Это следует из того, что
аі
Pd-
д2
d-1‘
ad-2 ad-2 Rd-2
Pi P2 ‘ ‘ ‘ Pd-1
с попарно различными fij является отличным от 0 определителем Вандермонда.
Множество 21 часто расширяют, а именно, добавляют к нему элементы 0 ё F, и особый элемент оо. Мы далее будем полагать, что матрица В в (6) определена именно для такого расширенного множества 21. О подробностях такого определения удобно рассказать ниже в разделе 7.4.
Нумерацию столбцов матрицы В будем производить с помощью элементов множества 21. Так, столбец с номером а является j-ым столбцом, если а = otj. Совершенно аналогично поступаем с координатами вектора х = (хаі,ха2,... ,хап) G F, их также индексируем элементами множества 21, которые записаны в определенном порядке.

Коды Рида Соломона.

Мы рассмотрим три вида кодов Рида Соломона длин п = q 1, q, q+1. Все они имеют в качестве проверочной матрицу вида (6), но различные множества 21.
Тип 1. п = q 1. В этом случае множество Л состоит из всех ненулевых элементов поля F,;.
Тип 2. п = q. В этом случае множество Л состоит из всех элементов поля F,;. Следует сказать, что столбец (aj,aj,..., а^-2)т, у которого aj = 0 имеет вид (1,0,...,0)т.
Тип 3. п = q+1, d 3. В этом случае множество Л состоит из всех элементов поля F,; и еще одного элемента оо (бесконечности). Предполагается, что элемент оо обладает естественными свойствами
этого понятия. Например, аоо = оо, а Ф 0. = 0 и т.п. Столбец (а'-.а,-.....aj . у которого
aj = оо по определению имеет вид (0,0,..., 1)т. Более обще, мы считаем, что значение многочлена /(.г) = о fsXS степени не выше d2 в точке оо является коэффициент /,/ В частности, /(оо) = О, если степень f(x) меньше d 2. В этом случае мы говорим, что f(x) имеет корень оо.
Можно сказать, что мы рассматриваем проективное пространство Fg U {оо} и многочлены на нем.
Коды Рида Соломона всех типов будем обозначать одним символом RSq(n,d). Все они имеют параметры [п,п d+l,d\q и являются, так называемым, g-значными МДР-кодами (см. [17]), а именно кодами, которые имеют максимально возможную размерность п d + 1 при заданных п и d.
Одна из модификаций кода типа 3 (длины п = q 1) будет далее использована как основа для построения системы открытого шифрования, которую мы будем подробно изучать. В частности, мы рассмотрим группу автоморфизмов (определение ниже) этого кода. Эта группа имеет наиболее сложное строение по сравнению с группами автоморфизмов кодов типов 1 и 2. Поэтому мы сначала достаточно подробно изучим группу автоморфизмов кодов типа 2, а затем в основном без доказательства приведем нужные свойства группы автоморфизмов кода типа 3.
Надо сказать, что коды типа 3, в некотором смысле, являются наиболее интересными среди определенных ранее трех типов кодов Рида Соломона. В частности, они имеют наиболее мощную группу автоморфизмов и наибольшую длину и размерность при заданном кодовом расстоянии d. Коды типа 1 используются для построения циклических кодов Боуза Чоудхури Хоквингема.
Коды RSg(n,d) всех типов могут быть заданы (определены) и несколькими другими способами.

Код Боуза Чоудхури Хоквингема.

Предположим, что поле F,..r = р1 , где число I' делит I является подполем поля F,;. q = р1. В
этом случае мы будем рассматривать r-значный подкод кода RSg(n,d), п = q 1, который состоит из всех векторов RSg(n,d), координаты которых принадлежат полю F,.. Этот код называют кодом Боуза Чоудхури Хоквингема (обозначение: ВСНг(п, /)).
Он имеет параметры [q \ .d'. k']r, где d' ^ d, к1 ^ q 1 (d 1 [^г]){г- По поводу этих оценок и замечательных свойств кода BCHr(n,d) см. книгу [17].
Следует обратить внимание на то, что размерности кода RSq(n, d) и кода BCHr(n, d) вычисляются над разными полями: размерность первого над F,;. а размерность второго над его подполем Fr.

Группа автоморфизмов кода RSq(n, d), п = q.

Если переставить координаты кодового вектора а кода К. то полученный вектор а' может как принадлежать, так и не принадлежать коду К. Если перестановка координат а такова, что а (а) = a' G К, для всех а € к'., то она называется автоморфизмом кода К,. Очевидно, что если а' другой автоморфизм, то произведение а ¦ а' также является автоморфизмом.
Поэтому все автоморфизмы кода К, образуют группу Л/с, которая называется группой автоморфизмов кода АГ Заметим, что на множестве перестановок координат векторов пространства F можно естественным образом определить операцию по отношению к которой все они образуют группу Sn порядка пі, называемую симметрической группой.
Перестановку а удобно представлять себе в виде перестановочной матрицы IV = Г = Цу^Ц, которая реализует эту перестановку в виде матричного умножения. А именно, элемент матрицы 7ij равен 1 тогда и только тогда, когда координата с номером % переходит посредством действия а в координату с номером j. Во всех остальных случаях 7^ = 0. Таким образом, матрица Г представляет из себя матрицу, у которой в любой строке и в любом столбце имеется ровно одна 1. Перестановочная матрица Г реализует перестановку а координат вектора а в виде матричного умножения следующим образом !т(а) = аГ. Матричная группа автоморфизмов G = Gc образована всеми матрицами IV, у которых а 6 Л/с-
Если Г 6 G?. а матрица В является проверочной матрицей кода к'., то В - Г, очевидно, также является проверочной матрицей этого кода к'.. Поэтому она может быть представлена в виде В ¦ Г = h ¦ В. где невырожденная матрица h размера пкхпк является матрицей перехода от одного базиса пространства строк матрицы В к другому В'. Последнее высказывание на языке матриц записывается как раз в виде В' = h ¦ В.
Интересно отметить, что указанное отображение Г -л h реализует гомоморфизм матричной группы G;c автоморфизмов кода К, (матрицы размера п х п) в матричную группу, образованную матрицами h размера п кхп к. Ядро JQC) этого гомоморфизма образуют элементы Г, которые оставляют на месте все векторы кода АГ Поэтому матрицы Н, на которые отображается группа 6\-посредством соответствия В-Г = h ¦ В. изоморфна факторгруппе 6\-/./(АГ). Так как далее мы ограничимся рассмотрением только кодов, у которых ядро JQC) тривиально (состоит из одного элемента), то мы всегда будем полагать, группа, образованная матрицами Н, изоморфна группе GК таким кодам относятся коды RSq(n, d) и коды BCHq(n, d).
Доказательство этого утверждения в более общей форме см. ниже (Лемма 2).
Рассмотрим ансамбль (множество) В/с кодов, определяемых проверочными матрицами из множества ® = {В ¦ Г|Г 6 Sn}. где В одна, не важно какая, матрица вида (6). Число Чq(n,d) различных (как множеств) кодов к'. = RSg(n,d) в ансамбле /V (по другому, кодов с проверочной матрицей вида (6)), как нетрудно видеть, равно
Т) f
%(n,d) = ~ (8)
|Ьх|
где К, = RSq(n,d) один из фиксированных кодов Рида Соломона с проверочной матрицей (6).
Как мы видим, число различных кодов Рида Соломона полностью определяется порядком его группы автоморфизмов. К настоящему времени группа автоморфизмов G\- кода К, = RSq(n, d) не вычислена.
Можно только утверждать, в Gnsq(n,d) входят подстановочные матрицы, которые реализуют подстановку х ах, а € F,; \ {0} = F*, элементов поля F,; в себя. Эти матрицы образуют группу, которая изоморфна, так называемой, мультипликативной группе поля F?.
Эта группа является циклической, поэтому и коды Рида Соломона также как и коды Боуза Чоудхури Хоквингема при п = q 1 с помощью соответствующей нумерации множества 21 могут быть сделаны циклическими. На этом здесь останавливаться не будем (см. [17]).

Число проверочных матриц кода RSq(n, d)

Если h невырожденная матрица размера d 1 х d 1, то, как нетрудно видеть, проверочные матрицы В и НВ определяют один и тот же код RSq(n, d). Матрицы В и НВ различны, если Нф Е (единичная матрица). Отсюда следует, что число различных проверочных матриц, которые определяют один и тот же код RSq(n,d), равно Nq^-1, где Nq.s число невырожденных квадратных матриц Н размера s х s.
Лемма 1. Число Nq.s равно
Nq,s = (qs - 1 )(?* -?)¦¦ ¦ (qs - q8-1 )- (9)

Обобщенные коды RSq(n, d), n = q + 1, Рида Соломона.

Нам удобно рассмотреть несколько более широкий по сравнению с RSq(n,d) класс кодов, который мы будем называть обобщенные коды Рида Соломона и обозначать их тем же символом RSq(n,d).
Пусть FJ; = F,; U ос поле, к которому добавлен элемент оо. Рассмотрим матрицу

	(	ZiOti	Z20-2	Znan	\
		z±ai	Z2O.2	ZnOtn
с =		ziaf	Z2CX2	ZnOLn		, d 3, n = q = 1,	(10)
	\	ziaf-2	Z20!2_2 ¦	¦ znafc2	/

где ctj G F'g, ctj Ф oti при j ф і и при ctj = оо соответствующий столбец матрицы С имеет вид (0,...,0,^-)т.
Так же, как для обычного кода Рида Соломона, обобщенный код длины п = q + 1 имеет кодовое расстояние равное d и размерность п d + 1.
Матрица С, очевидно, может быть представлена в виде С = В ¦ D, где D = diag(zi, z2, ¦ ¦ ¦, zn), Zj G Fg \ {0}, диагональная матрица и В проверочная матрица кода Рида Соломона типа 3. Преобразованная матрица С будет выступать далее как проверочная матрица системы открытого шифрования. В этой связи значительный интерес представляет строение группы обобщенных автоморфизмов кода Рида Соломона с проверочной матрицей В, к изучению которой мы переходим.
Обобщенный код BCHr(n,d) определяется аналогично тому, как это было сделано в разделе 7.5: BCHr(n,d) = RSq(n,d) П FJ?, т.е. коду BCHr(n,d) принадлежат все векторы кода RSq(n,d), координаты которых принадлежат подполю F,. поля F,;. Обобщенные коды BCHr(n,d) включают в себя и, так называемые, кода Гоппы (см. [17]).
Код можно задать и с помощью своей проверочной матрицы над полем Fr размера пкхп, где к размерность (над Fr) кода BCHr(n,d). Эта матрица также может иметь вид (10). Определить размерность к даже в частных случаях обобщенных кодов BCHr(n, d). в отличие от размерности любого кода RSq(v.d). очень нетривиально.
В общем случае сделать это не представляется возможным.

Группа обобщенных автоморфизмов кода RSq(n, d), п = q + 1, Рида Соломона

. Если в качестве обычных автоморфизмов кода К, выступали перестановочные матрицы Г, то в качестве обобщенных автоморфизмов выступают матрицы вида Л = Г ¦ D, где D невырожденная диагональная матрица, которые носят название мономиальных. Другими словами, Л перестановочная матрица, у которой ненулевыми элементами являются ненулевые элементы поля F,;.
Мономиальные матрицы сохраняют расстояние Хемминга. А именно, d(a,b) = d(aA,bA).
Как будет видно ниже, это свойство позволяет использовать эти матрицы в системе открытого шифрования. Нашей основной целью является получение нетривиальных нижних верхних оценок порядка группы обобщенных автоморфизмов кода RSg(n,d) и затем оценок для числа различных кодов RSg(n,d).
Теперь переформулируем для обобщенных автоморфизмов некоторые из определений раздела 7.6.
Если мономиальная матрица А такова, что а А = a’ G К. для всех а € к'-, то она называется обобщенным автоморфизмом кода К,. Очевидно, что если А' другой автоморфизм, то произведение А ¦ А' также является автоморфизмом.
Поэтому все обобщенные автоморфизмы кода К. образуют группу Б/с, которая называется группой обобщенных автоморфизмов кода К,. Элементами группы Бю являются, так называемые, мономиальные матрицы размера п х п. Также как в разделе 7.6 можно рассмотреть представление Н/с группы обобщенных автоморфизмов Б/с в виде невырожденных матриц над Fg размера п кхп к. А именно, элементу А из Б/с сопоставим матрицу h = ііа, которая определяется соотношением
ііа-В = В-А. (И)
Произведению А ¦ А' двух элементов из Б соответствует произведение д(А ¦ А') = //.у ¦ На двух элементов из Н/с- Заметим, что порядок следования сомножителей в Н^ обратный по сравнению с Б/с- Поэтому рассматриваемое отображение является гомоморфизмом д : А На группы Б а: в группу матриц размера п к х п к над полем F?.
Лемма 2. Для кода К, = RSq(n,d) гомоморфизм g является изоморфизмом, т.е. |Sjc| = |Дс|.
Теорема 1. Порядок группы Бавтоморфизмов кода Рида Соломона К, = RSg(n,d) не превосходит iVgjCi-i, где :?д.5. число невырожденных квадратных матриц Н размера s х s над полем Fg.
Хотя оценка для числа Зк во многих случаях, по-видимому, весьма грубая, ничего лучшего не известно.
Рассмотрим ансамбль (множество) Лк, К. = RSq(n,d), кодов, определяемых проверочными матрицами из множества 'В = {/’Л|Л G }. где В одна, не важно какая, матрица вида (6), а множество всех мономиальных матриц над полем Fg. Заметим, что ансамбль Лк совпадает с множеством кодов, проверочные матрицы которых имеют вид (10).
Кроме того, нетрудно установить, что \Uq,n\ = nl(q 1). Нас будет интересовать число различных кодов в ансамбле Лк-
По тем же соображениям, что приведены в разделе 7.6, для числа Aq(n,d) различных обобщенных кодов Рида Соломона JC = RSq (п, d) в ансамбле Лк имеет место равенство
= (12)
р /с|
К сожалению, группа 3к обобщенных автоморфизмов кода Рида Соломона не известна. Поэтому мы не можем воспользоваться равенством (12) для вычисления числа Aq(n,d).
Из теоремы 1 и соотношений (9) и (12) следует
Следствие 1. Для числа Aq(n,d) различных обобщенных Рида Соломона К, = RSq(n,d) ? ансамбле Лк имеет место оценка
n\(q 1)
n\(q 1)г
(13)
Aq(n,d) ^
(qd х 1 ){qd 1 q) ¦ ¦ ¦ (qd 1 qd 2) ’
= RSq(n,d) и Nqj- число различных невырожденных
где к = п d + 1 размерность кода К, матриц размера к х к.
Далее мы докажем, что группа 3к содержит подгруппу, изоморфную группе дробно-линейных преобразований. Строение последней группы мы изучим в следующем разделе.

Группа дробно-линейных преобразований.

Элементами группы дробно-линейных преобразований Ф,; множества F(; = F,; U {ос} в себя являются дробно-линейные функции ір(х) = , отличные от постоянной, т.е. функции, у которых определи
тель матрицы
отличен от нуля. Очевидно, каждое дробно-линейных преобразование р(х)
взаимно однозначно отображает множество F'q в себя.
Множество Фд действительно является некоммутативной группой. Умножением ® в ней служит суперпозиция функций, т.е. ір ® ір' = рір'іх)). Группа Ф? = PGL(2, q) имеет порядок (q + 1 )q(q 1). Очень интересным свойством группы Фд является ее трижды транзитивность.
Это означает, что для любых двух пар троек (а,. и-,. 3) и (Іц. h-,.h-,). о.;.
Ь-, е F(;. с попарно различными координатами в группе Ф? найдется элемент ір (всегда один), для которого выполнено р{щ) = Ьі, і = 1,2,3.
Теорема 2. Группа 3к обобщенных автоморфизмов кода К, = RSq(n,d), п = q + 1, Рида Соломона с проверочной матрицей В (см. (6)) содержит подгруппу, которая изоморфна группе дробнолинейных преобразований множества Fg.
Этот результат будет использован при анализе стойкости системы открытого шифрования, построенной с помощью кода Рида Соломона.
Группа 3к обобщенных автоморфизмов кода Рида Соломона также является трижды транзитивной в следующем смысле. Для любой пары упорядоченных троек из попарно различных элементов (/3г,/32,/3з) и (7і,72,7з), где {/Зг,/32,/З3}, {71,72,73} G Я = {аь а2,... ,а„} = Fg существует такая мономиальная матрица А? € 3к, которая переводит координаты хрг, хр2, хр3 вектора ж = (хаі, Ха-21 - - - 1 хап) в координаты х1г, х12, хГі вектора хА? с умножением их на соответствующие постоянные, определяемые диагональной матрицей Dv = diag(dai,da2,... ,dan).
Например, с помощью подходящей матрицы А? можно передвинуть на первые три места любые три координаты вектора х. В частности, если {/Зі = 1,/32 = 0,/33 = оо} и 71 = 1,72 = а2,73 = а3. то хА? = (d at %1 j da2XQj da3Xoo,da4xv(a^,.. .,danx^an)) для некоторой подходящей функции ір(х).

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

Мы приведем ряд утверждений о декодировании кодов, которые будут играть центральную роль при обосновании стойкости рассматриваемых систем открытого шифрования.
Неформально говоря, под термином декодирование понимается алгоритм, который позволяет по искаженному ошибками кодовому вектору а’ восстановить исходный кодовый вектор а. Таким образом, декодирование сводится к решению уравнения
а' = а + е, а ? К, wt(e) ^ t, (14)
где неизвестными являются кодовый вектор а и вектор ошибки е.
Имеется несколько различных типов декодирования.
i. Корреляционное декодирование кода К. Это алгоритм, который по предъявленному вектору ж ? F находит один или несколько кодовых векторов а ? К, ближайших (в метрике Хемминга) к х.
ii. Декодирование кода К, в пределах его кодового расстояния. Это алгоритм, который по вектору ж, который отстоит от одного из кодовых векторов К. на расстояние ^ ; вычисляет этот
ближайший кодовый вектор. Этот вектор обязательно является единственным.
Векторы ж, которые отстоят от всех кодовых точек на расстояние большее, чем половина кодового расстояния, могут быть декодированы как угодно, в частности, алгоритм может вообще отказаться от их декодирования.
iii. Декодирование кода К, за пределами его кодового расстояния. (Алгоритм промежуточного положения между і. и іі.) Это алгоритм, который по вектору ж, находящемуся не очень далеко (іІ(х. а) ^ f) от некоторого кодового вектора а кода К,, вычисляет один или несколько кодовых векторов а', находящихся на расстоянии ^ f от ж, где t' d^K.g-1 некоторая постоянная (параметр алгоритма).
Наиболее сильным и трудным для реализации является алгоритм і. В настоящее время не известно ни одного нетривиального класса кодов, которые имеют алгоритм декодирования этого типа с простой реализацией. Другими словами, этот алгоритм может быть реализован только с помощью перебора.
А именно, можно сравнивать ж со всеми векторами кода и выделять среди них ближайшие кодовые векторы, или осуществлять просмотр векторов из окрестности ж, пытаясь найти в ней кодовый вектор. Какой из этих упомянутых алгоритмов перебора выгодней с вычислительной точки зрения зависит от соотношений между параметрами кода.
Сложность реализации корреляционного декодирования нетривиальных кодов возрастает как экспоненциальная функция от их длины. На практике ни один из таких кодов на современных вычислительных средствах не может быть декодирован, начиная с длины и 100.
Наиболее легким для реализации является алгоритм декодирования типа іі. Для большинства так называемых алгебраических кодов известны алгоритмы декодирования в пределах их кодового расстояния, сложность которых возрастает как полином небольшой степени от длины кода.
К таким кодам относятся и, рассмотренные нами, обобщенные коды Рида Соломона RSq(n,d). Их декодирование в пределах кодового расстояния может быть осуществлено не более, чем за О(іг') операций в поле Fg [17], [15].
Не надо думать, что для каждого кода существует простой алгоритм декодирования в пределах его кодового расстояния. По современным представлениям такие алгоритмы могут существовать только для кодов, которые снабжены определенной алгебраической или комбинаторной структурой.
Вместе с тем у большинства кодов, не очень точно выражаясь, отсутствует в проверочной матрице какая-либо структура, это коды общего положения. Примером первого типа кодов является код Рида Соломона или код Рида Маллера (совершенно разные коды), а примером второго код, у которого проверочная матрица выбрана случайно среди всех матриц определенной размерности.
Декодирование в пределах кодового расстояния (типа іі.) некоторых типов кодов общего положения является NP-полной задачей, т.е. предположительно не может быть осуществлено за полиномиальное время от их длины. Более того, общепринято, что
Тезис А: декодирование последовательности кодов, которые не обладают полезной для декодирования алгебраической или комбинаторной структурой, не может быть осуществлено за полиномиальное время от их длины.
Это достаточно расплывчатое, но очень правдоподобное утверждение строго не доказано и в настоящее время возможность его доказательства весьма проблематична. Вместе с тем на этом утверждении держится обоснование стойкости открытого шифрования на базе кодов, корректирующих ошибки.
Мы далее, специально не указывая на это, будем постоянно его придерживаться.
Обычно при построении кода, корректирующего ошибки, стараются наделять его определенной структурой, которая обеспечивает, с одной стороны, заданное значение его кодового расстояния, и, с другой, позволяет осуществлять его декодирование с малой вычислительной сложностью.
Приведем одно почти очевидное утверждение о сложности декодирования любого кода с помощью алгоритма типа іі.
Утверждение 2. Любой линейный код К, с параметрами [n,k,d\r, d п/2, имеет алгоритм декодирования в пределах его кодового расстояния, сложность которого не выше 0(mm(nrk, п]Г^._0 ()), гдеі = {^]. 3

Система открытого шифрования Маклисп.

Отметим, что rk число элементов в коде К, и 0(пгк) число операций, требуемых для перебора всех элементов кода и сравнения каждого из них с искаженным кодовым вектором а'. Далее, Y?j=о (j)(r ~~ 1)J число элементов в шаре радиуса t с центром в точке х и 0(п Y^j=e ()) число операций, требуемых для перебора всех элементов шара с целью нахождения среди них кодового вектора.
9 Система открытого шифрования на основе кода, корректирующего ошибки

Система открытого шифрования Маклисп.

Идею построения системы открытого шифрования проще всего пояснить на примере кода Боуза Чоудхури Хоквингема BCHr(n,d) размерности к.
Пусть А фиксированная порождающая матрица обобщенного кода BCHr(n,d) над F,.. т.е. матрица ранга к и размера к х п, для которой А ¦ Ст = 0, где С матрица, определенная соотношением (10). Между прочим, в качестве А можно взять матрицу, которая имеет тот же вид, что и С. Этот факт мы использовать не будем.
Ансамбль Ar(n,d) порождающих матриц обобщенного кода BCHr(n,d) определим как множество всех матриц вида h ¦ А ¦ Г ¦ D, где h пробегает множество всех невырожденных к х ^-матриц над F,.. D множество всех диагональных матриц с ненулевыми на диагонали элементами, а Г множество всех перестановочных матриц размера п х п. Соответственно, ансамбль кодов k'.r(v.d) определяется как множество всех кодов с порождающими матрицами из ансамбля Ar(n,d). Матрицы Іі, Г, D маскируют матрицу А.
Передача секретного сообщения абонента У, предназначенного абоненту X, предваряется следующими действиями. Абонент X случайно, равновероятно в соответствующем множестве и независимо от других абонентов выбирает матрицы h = hx, D = Dx, Г = Гд- и вычисляет матрицу А' = А’х = hx ¦ А ¦ Т'х ¦ Dx из ансамбля A, (n.d). Матрица А’х является открытым (общедоступным для всех абонентов) ключом (public key), а матрицы hx,^x,Dx секретным ключом (private key) абонента X.
Шифрованная информация b (криптограмма), которую абонент У передает по общедоступному каналу абоненту X, в системе Маклиса [10] представляет собой вектор длины п и вида Ь = аА’х + е, где а r-значный вектор длины к, несущий конфиденциальную информацию абонента У, а е секретный вектор ошибок веса, не превосходящего t, и длины п, который случайно и равновероятно выбирается абонентом У среди всех векторов веса не выше t.
Таким образом, для того чтобы расколоть открытую информацию, необходимо представить вектор Ъ в виде
Ь = а + е, (15)
где вектор а = аА’х принадлежит коду К = Кх с порождающей матрицей А’х, а вектор е имеет вес
Другими словами, злоумышленнику необходимо декодировать код К с известной порождающей матрицей А’х. Матрица А’х замаскирована матрицами h, D и Г и поэтому она, вообще говоря, представляется нападающей стороне как матрица общего положения.
По тезису А в этом случае сложность декодирования не является полиномиальной от длины п кода К. Следовательно, при достаточно больших п процедура декодирования недоступна для злоумышленника из-за ее большой вычислительной сложности. Вместе с тем декодирование кода К той же длины п для легитимного абонента X, знающего секретный ключ, является вычислительно достижимым.
Действительно, абонент X, получив вектор Ъ, восстанавливает кодовый вектор аА'х следующим образом. Сначала он строит вектор У = Ы) 1 ¦ Г 1. который , очевидно, является вектором кода BCHr(n,d) с порождающей матрицей А, искаженный не более, чем в t разрядах.
Как раз здесь используется тот факт, что мономиальная матрица D 1 ¦ Г 1 сохраняет вес вектора е (см. раздел 7.9). Затем с помощью какого-либо общеизвестного полиномиального алгоритма декодирования кода BCHr(n,d) находится вектор а', который удовлетворяет условию У = а'А + е', где w(e') ^ t. Затем вычисляется вектор а в виде а = it'h 1.
Мы будем предполагать, что t ^ (d 1)/2. Вместе с тем можно полагать, что t d 1)/2, но t меньше некоторой границы.
При этом надо использовать алгоритм декодирования работы [15], который работают при определенном ограничении на величину t почти всегда правильно. Как будет видно ниже, чем больше алгоритм декодирования исправляет ошибок, тем выше будет стойкость системы шифрования. Вместе с тем при возрастании числа исправляемых ошибок, как правило, возрастает и сложность его реализации.
В идеале, лучше всего использовать корреляционный алгоритм, но его сложность является слишком высокой и он не доступен для реализации. Обычно в системе Маклиса используют алгоритмы типа іі или ііі.

Система открытого шифрования Нидеррайтера.

В системе Нидеррайтера [14] рассматривается ансамбль В, (?. d) проверочных матриц кода BCHr(n, d). который определяется как множество всех матриц вида В' = h ¦ С ¦ D ¦ Г, где С фиксированная проверочная матрица вида (10), h пробегает множество всех невырожденных п к х п ^-матриц над Fг, D множество всех диагональных матриц с ненулевыми на диагонали элементами, а Г множество всех перестановочных матриц размера п х п.
Подобно системе Маклиса открытым ключом абонента X в системе Нидеррайтера является матрица В', а секретным матрицы h, D, Г.
Шифрованная информация с абонента У и предназначенная абоненту X в системе Нидеррайтера представляет собой г-значный длины п к и вида
с = еВ'Т, (16)
где В' = В'х проверочная матрица, которая случайно выбрана абонентом X из ансамбля Br(n,d) и к размерность кода с этой проверочной матрицей. Вектор е является вектором длины п и веса, не превосходящего t, который несет конфиденциальную информацию абонента У.
Заметим, что конфиденциальная информация является одним из решений уравнения
с = хВ''. (17)
Найти какое-либо решение этого уравнения простая задача, так как это линейное уравнение с п к уравнениями и п неизвестными. Найти среди всех решений (их число 2*) решение с минимальным весом это уже сложная задача, которая эквивалентна задаче декодирования кода с проверочной матрицей В'.
Также как в системе Маклиса в системе Нидеррайтера матрица В' представляется нападающей стороне матрицей общего положения.
В теории кодирования вектор с из (16) называют синдромом вектора е. Отметим, что матрицы В' и А' связаны соотношением В' ¦ А'т = 0, где А' одна из матриц ансамбля Ar(n,d). Строки матрицы В' являются базисом подпространства размерности п к, ортогонального к пространству строк матрицы А'.
Абонент X, получив сообщение с, находит какой-либо вектор Ъ, который является решением уравнения хВ' = с. Очевидно, вектор Ъ является вектором вида Ъ = и А' + е при некотором неизвестном а ? F*. Затем абонент X также, как в системе Маклиса, декодирует вектор 6Г 1 - D 1 = У = а'А + е', но вместо кодового вектора а'А находит вектор е' = У а!А, а затем и вектор е = е'Г ¦ D. Отметим, что в отличие от системы Маклиса, в системе при расшифровании (восстановлении вектора е) никак не участвует матрица h. Она нужна только для маскировки матрицы В'.
Как и выше, предполагаем, что используемый алгоритм декодирования кода BCHr(n,d) всегда правильно восстанавливает вектор ошибок е.

Сравнение систем открытого шифрования Маклисп и Нидеррайтера.

Системы Маклиса и Нидеррайтера обладают одинаковой стойкостью к нападению, ибо криптографическая атака на одну из систем может быть легко трансформирована в атаку на другую. Поясним это подробно.
Мы полагаем, что обе взаимно ортогональные матрицы А' (открытый ключ системы Маклиса) и В' (открытый ключ системы Нидеррайтера) известны нападающей стороне, так как одна из другой может быть получена как решение линейной системы уравнений А' ¦ В'т = 0, т.е. с помощью не более, чем 0(п3) операций.
При известном синдроме с = еВ'т нетрудно вычислить вектор Ь = ЗА' + е с некоторым вектором 3 е F* такой, что с = ЬВ'Т. Для этого надо найти какое-либо решение Ь уравнения (17).
Вектор Ъ мы будем рассматривать как криптограмму в системе Маклиса. Если для системы Маклиса найдена криптографическая атака со сложностью Q, т.е. известен алгоритм вычисления вектора а (конфиденциальная информация в системе Маклиса), то вектор е (конфиденциальная информация в системе Нидеррайтера), очевидно, представляется в виде е = Ъ ЗА', т.е. сложность определения е, по существу, совпадает со сложностью определения 3.
Наоборот, если для системы Нидеррайтера известна криптографическая атака со сложностью Q, то используя в качестве криптограммы этой системы вектор с = ЬВ'Т = (ЗА' + е)В'т = еВ'т, где Ь криптограмма системы Маклиса, вычислим вектор ошибок е, а затем и вектор 3, который является единственным решением линейного уравнения у А' = Ъ е.
Соображения, использованные в предыдущих двух абзацах, любезно сообщены автору в устной беседе Г.А. Кабатянским.

Некоторые свойства систем открытого шифрования Маклиса и Нидеррайтера.

Две эти системы различаются скоростью передачи. Если код К, является низкоскоростным, т.е. к/п малое число, то скорость передачи у системы Нидеррайтера всегда выше по сравнению с системой Маклиса. Поэтому далее будем рассматривать только ее.
Вместе с тем будем предполагать, не оговаривая этого особо, что криптограммой системы Нидеррайтера является п-мерный вектор Ъ = ЗА' + е, который является каким-либо решением системы (17), где с = ЪВ'1 = еВ'1 и е вектор веса не выше t (информационный вектор абонента 3;). Это связано с тем, что алгоритм декодирования кода RSq(n,d), рассмотренный в [16], и некоторые известные криптографические атаки оперируют с искаженным кодовым вектором 6, а не с его синдромом с.
Шифрование сообщения е состоит в вычислению его синдрома и поэтому его сложность равна 0((пк)п) операций. Сложность расшифрования (сложность восстановления вектора е) определяется, в основном, трудоемкостью алгоритма декодирования кода RSq(n,d) и при использовании алгоритма декодирования работы [16] не превосходит О(іг') операций.
Для декодирования в пределах кодового расстояния известны и более быстрые алгоритмы.
Как известно [18], кодовые системы открытого шифрования имеют большую скорость шифрования по сравнению с другими подобными системами, например, с системой RSA. Вместе с тем они обладают, по меньшей мере, двумя недостатками.
Во-первых, скорость передачи у кодовой системы всегда меньше 1 (обычно меньше 1/2), в то время как в системе RSA (см. [19] и многие другие работы) она равна 1.
Во-вторых, открытый ключ (в рассматриваемой кодовой системе матрица В') имеет объем примерно в п к раз больший, чем у упомянутой системы RSA. Если к относительно маленькое число, то выгодней в качестве открытого ключа системы рассматривать матрицу А', которая связана с В' соотношением В' ¦ А' = 0.
Кроме того, работ по оценке стойкости кодовых систем известно значительно меньше, чем для системы RSA.
В системе открытого шифрования Нидеррайтера в качестве открытой информации выступают векторы е веса t и менее. Для ее реализации необходимо иметь алгоритм, который отображает множество всех r-ных векторов длины s в множество И'/ векторов длины п и веса не выше t, где s r(t,N) = [lgr J2l=о (Т)(г ~~ 1)г] (логарифм числа возможных сообщений в системе Нидеррайтера).
Система Нидеррайтера полностью определяется как проверочной матрицей В', так и ортогональной к ней порождающей матрицей А', и наоборот. Поэтому открытым ключом этой системы естественно считать матрицу, которая содержит меньшее число строк, хотя криптограмма с = еВ' всегда реально строится с помощью матрицы В'.
Переход от системы Маклиса к системе Нидеррайтера полезен не только с точки зрения повышения скорости передачи, но и, что, возможно, более важно, позволяет с помощью несложной модернизации существенно усилить ее стойкость к криптографическим атакам. По поводу этого вопроса см. работу [12].
10 Как раскалывается система открытого шифрования Нидеррайтера, построенная с помощью обобщенного кода Рида Соломона? Общие подходы.
В этом разделе мы рассматриваем систему Нидеррайтера, построенную с помощью д-значного кода из ансамбля Bq(n,d) (см. начало раздела 9.2). Как было установлено в разделе 9.3, соответствующая система Маклиса (система, в которой порождающие матрицы выбираются из ансамбля Aq(n,n d+1) имеет примерно ту же стойкость к нападению, что и рассматриваемая система открытого шифрования.
Имеется два вида атак на систему открытого шифрования.
i. Чтение открытого сообщения абонента У без использования секретного ключа абонента X (бесключевое чтение). В данном случае секретным ключом являются матрицы h. Г. D.
ii. Вычисление секретного ключа абонента X с последующим вычислением открытых сообщений абонента У. направляемых им абоненту X.
Рассмотрим сначала атаку і. Для ее реализации необходимо решить уравнение (17). С точки зрения нападающей стороны матрица В' является матрицей общего положения. Поэтому для нахождения решения е уравнения (17) веса wt(e) ^ t в соответствие с тезисом А необходимо проделать экспоненциальное от его длины п число операций.
Можно полагать, что при большем п и 100 это невозможно на современном уровне развития вычислительной техники.
Другой подход, реализующий атаку L, состоит в следующем. Можно угадать обобщенный код Рида Соломона, определяемый проверочной матрицей В', и произвести декодирование (решить уравнение (17)) в этом коде.
По следствию 1 число таких кодов Aq(n,d) не меньше (qd-i_i)(qd-'il~qy..(qd-i_qd-2) ¦ Это число при п и 100, d ^ п/2 и д ^ 2 больше, чем 1077. Поэтому это событие очень маловероятно и его можно не рассматривать.
Таким образом, по современным представлением с учетом тезиса А бесключевое чтение (атака і) в рассматриваемой системе невозможно при достаточно большом п.
Рассмотрим теперь атаку іі. Задачей в этом случае является определение матрицы h. Г. D. исходя из известной матрице В'.
Как будет показано ниже, и это основной результат работы, эта задача может быть решена за 0(s4 + sn) операций в поле F,;.
11 Алгоритм определения секретного ключа системы открытого шифрования, использующего обобщенный код Рида Соломона
Любая матрица ансамбля Bq(n,d) имеет вид
Znfoi^n) ^
Zn fl (Xn)
Zn f2 (Xn)
2і/о(^і)
zifiixi)
2і/2(^і)
?2/0 (^г) 22/1 (w2) 22/2^2)
В' =
(18)
ZnfdliXn) )
\ 2l/d-2(wi) z2fd-2(^2)
где fi(x) многочлен степени не выше d 2, который определяются матрицей h = {hij} следующим образом fi(x) = YjjZo^hi- Многочлены fi(x) являются линейно-независимыми.
Итак, перед нами стоит задача: по заданной матрице В' найти невырожденную матрицу h, элементы ші, ш2, ¦ ¦ ¦,= Fg U {ос} и элементы z\. z-.....z„ € F,; \ {0} такие, что В' = h ¦ В - Г - D.
D = diag (z1,z2,...,zn).
Задачу будем решать в два этапа: сначала найдем элементы ш\, С02, ¦ ¦ ¦, шп, а затем элементы zi, Z2, - - -, zn и матрицу h.

Как определить первые три элемента а,'/?

Перед тем как искать элементы ¦ ¦ ¦, wn сделаем несколько замечаний.
Пусть Ъ. Л некоторое решение уравнения (18), т.е. В' = h ¦ В ¦ А, Л = Г ¦ D, и А? = Г? ¦ Dv, Dv = diagi'rj. z'.,...., z'n), некоторый обобщенный автоморфизм кода К, с порождающей матрицей В (см.
10), соответствующий дробно-линейной функции ір(х) (см. раздел 7.10). Тогда решением уравнения (18) является также пара h', Л', где Ы = h ¦ h 1. Л' = А? ¦ Л, где матрица h определяется соотношением h ¦ В = В ¦ А?.
Группа обобщенных автоморфизмов 3/с кода К, = RSq(n,d) Рида Соломона типа 3 (см. раздел 7.4) действует на координатах векторов х = (хаі,ха2, ¦ ¦ ¦ ,ха„)- Она образована всеми мономиальными матрицами А? (теорема 2) и является трижды транзитивной. Смысл этого понятия объяснен в разделе 7.10. Поэтому найдется дробно-линейная функция ір(х) такая, что

Ь! ¦ В ¦ Аш ¦ А

( 4 т 4fm 4т) 4т 471(0) 471(0) 47о() 471 (О 471 (оо) ¦¦¦ 4Шп) \ ¦¦¦ 4/1Ш ¦¦¦ 4/1 (Рп) (19) V 4/d-2(i) 4772(о) 471-2 (э) ¦¦¦ 471-г(4) у А? ¦ А, что (х У У * * У xWn) А (р 'А (dixiidbxoidsxoo, fa ,...,/3„),гдейш

элементы диагональной матрицы D', определяемой соотношением А? ¦ А = А' = Г' ¦ D' (см. раздел 7.10).
Для этого, как нетрудно видеть, нужно подобрать такую функцию ір(х), что ) = /Зі, ір(Ш2) = /З2, РІШз) = /?3і где элементы /3і определяются тем условием, что матрица А переводит координату хрг в координату х\, координату хр2 в .г,;, и координату хр3 в хз.
Таким образом, всегда можно полагать, что в (18) wi = 1, о2 = 0, оз = оо.

Определение элементов toj, j 3.

Найдем такие постоянные ci1^, s = 0,... ,d 2, не все равные нулю, для которых выполнено
d-2
= 0, j = l,d,d+l,...,2d 4. (20)
s=G
Для этого необходимо решить однородную систему линейных уравнений от d 1 неизвестных с известной матрицей коэффициентов (zjfs(tUj)) части матрицы В'. Эта система всегда имеет решение, так как уравнений меньше, чем число неизвестных.
Следует отметить, что все элементы сі1^ отличны от нуля, так как в противном случае в матрице В' нашлись бы d 1 линейно-зависимых столбцов, что по ее построению не может иметь место. Положим
р(В(х) = J2c(^fs(x), 7і1] = = ZiF(l){wi). (21)
s=0 s=0
Очень существенно то, что элементы могут быть вычислены, исходя только из известных элементов Zifs(cui) матрицы В'.
Поскольку элементы Zi отличны от нуля, то из (21) следует, что элементы Uj, j = 1, d, d+1,..., 2d4 являются корнями многочлена F^^x). Заметим, что ни один из элементов wi, Wd,Wd+i,..., W2d-4 не равен оо, так как = оо.
Степень многочлена F111 (.г) не превосходит d 2, так как степени /д.г). из которых он составлен, также не превосходят d 2. Кроме того, многочлен /ч 11 (.г) не равен тождественно 0, ибо многочлены /*¦ (.г) линейно-независимы, а коэффициенты сі1^ все отличны от нуля. Отсюда вытекает, что F'11 (ж) = а^(ж - 1)(ж - зд) ¦ ¦ ¦ (х - W2di), Ф 0.
Отметим, что FW(w) Ф 0, если ш Ф ccj, j = 1, d, d+ 1,..., 2d 4, ш Ф оо и F^\oo) = а Теперь проделаем ту же процедуру для элементов coj, j = 2, d, d + 1,..., 2d 4.. А именно, найдем такие постоянные с* , s = 0,... ,d 2, не все равные нулю, для которых выполнено
d2
(22)
X] сі2)ЛК0 = о. j = 2. d.d- 1.....2d 4.
s=0
Положим
F(2)(®) = ^42)/5(ж), 7|2) =^cf]Zifs(uH) = ZiF(2\ui). (23)
s=0 s=0
По тем же соображениям, что и выше, имеем F^(x) = а^х(х соф) ¦ ¦ ¦ (х co2d-4), Ф 0-Рассмотрим отношение ?(х) = = а ат~г^ многочленов F^(x) и F^(x). Как уже было
замечено, F^ (w) ф 0, г = 1,2, если со Ф coj, j = 1,2, d, d + 1,..., 2d 4, со Ф оо. Таким образом, мы можем вычислить значение функции ?(х) во всех точках coj за исключением j = d, d + 1,..., 2d 4 с
а(1)
ТОЧНОСТЬЮ ДО ПОСТОЯННОГО множителя
Множитель можно вычислить, если положить х = оо (значению ш3) в ?(х). В этом случае
z3F^(oo) = сіг^з/5(оо), г = 1,2. Таким образом, значение ?(оо) может быть вычислено не
посредственно, исходя из матрицы В’, ибо z3fs(oo) элементы третьего столбца В1. Для полноты изложения заметим, что F^(оо) ф 0, ибо по построению среди всех d 2 корней многочлена F^(x), степени не выше d 2, нет корня оо. Отсюда вытекает, что
F( оо) F(2)(oo)
?{х)
(24)
Как уже отмечалось, значения многочленов F'x!)ix) и, следовательно, значение еш = ?(со) дробнолинейной функции ?(х) можно вычислить в любой точке со G F'g за исключением си Ф си j, j = 1,2 ,d,d + 1.....2d - 4. х Ф оо. Отсюда вытекает, что
(25)
coj = ? 1 {eWj), j ф 1.2.3. d.d 1.....2d - 1
Заметим, впрочем, что элементы соі, г = 1,2,3, уже известны.
Функция ?^1(х), как нетрудно вычислить, равна ?^1(х) = pmfa^xFWioo) - Таким образом, мы
можем определить значения coj для всех j, исключая j = d.d 1.....2d 4.
Недостающие coj можно определить, если выбрать другие элементы, определяющие многочлены F'l)ix). Скажем, в качестве такого набора для определения F111 (х) можно взять элементы
1; ^2d-3, ^2d-2, ¦¦¦, ^3,/ (! И С ИХ ПОМОЩЬЮ ВЫЧИСЛИТЬ НСЛОСТаЮЩИС CJj, j = d.d 1.....2d 4.
В этой секции с помощью многочленов F^ (х) произведена самая основная и трудная работа: найдена первая часть ключа элементы coj для всех j. Вся остальная работа по определению оставшейся части ключа, как это и обычно бывает, является более легкой и может быть произведена различными способами, один из которых излагается ниже. Кроме того, заметим, что мы использовали нетривиальные свойства подгруппы группы автоморфизмов кода Рида Соломона, а именно ее трижды транзитивность. Если бы подгруппа была только дважды транзитивной, то мы, например не смогли
Й а(1)
бы вычислить множитель и, следовательно, вычислить все coj.
Трудозатраты этой части алгоритма, как нетрудно подсчитать, не больше 0(d3 + dn).

Определение элементов Zj и матрицы h.

Заметим, что если каждый элемент матрицы А умножить на а € F,; \ {0}, а каждый элемент h на а то произведение В' = h ¦ В ¦ А останется неизменным. Поэтому можно считать, что zi = 1.
Найдем такие элементы а, сг,..., са, что
d
Y^CsZsfj^s) = 0, з =0,...,d-2. (26)
S=1
Отметим, что все элементы сі,сг,... , q отличны от нуля, поскольку в противном случае код с проверочной матрицей В' имел бы кодовое расстояние меньшее d (см. раздел 7.3, утверждение 1). Соотношение (26) в матричной форме имеет вид
В[I ¦ diag(2i, #2, - - - , ^г)(сі, сг, - - - , Cd)T = 0, (27)
где В" = (Ji(tUj)), % = 0,1,..., d 2, j = 1,2,..., d матрица размера dlxd. Заметим, что матрица
В" ¦ (Ііадйі. z:,.....г,/) является матрицей, совпадающей с первыми d столбцами матрицы В'. Как
нетрудно видеть В = h ¦ В,/, где

	f w?	, ,o CJ2	8 N
	coi	CO 2	COd
Bd =	uf	col			(28)
	i , .d2 \ W1	d-2 C02	udd-2 )
Откуда и из (27) вытекает, что
h-Bd- -diag(2i,22,	* * у Zd)(Ci,C2,	...,cd)T = 0,	(29)
ИЛИ
Bd ¦ diag(ci,c2,...	у ^d) ' (.Z\ , Z2, *	¦¦yZdf	= 0.	(30)

Соотношение (30) мы будем рассматривать как линейную систему уравнений относительно неизвестных Z2,zs,...,ZdC учетом того, что ненулевые элементы а, сг,..., Cd и элементы соі,со2 ,¦¦¦ ,cod уже известны, a zi = 1. Эта система имеет единственное решение, поскольку ее матрица ее коэффициентов
/ , ,о , ,о
/ со2 со3
U2 СО3
, ,2 , ,2
ш2 СО3
Ud, ,2
¦ diag(c2,c3,... ,Cd)
(31)
d-2
3
d-2
d
d2
2
CO
CO
CO
является, очевидно, невырожденной. Решая эту систему, найдем элементы Z\,Z2, ¦ ¦ ¦ ,Zd-Найдем теперь элементы матрицы h = (hij), i,j = 0,..., d 2. Имеем
d-2
Zj ^ ( hj.s'Zj Zjfiivj). (32)
s=о
Зафиксировав какое-либо i, 0 ^ i ^ d 2, и изменяя j от 1 до d 1, получим систему линейных уравнений с неизвестными 1ц$,Лід, - - - ,hi,d-2- Определитель этой системы является определителем Вандермонда, поэтому ее решение hі. - .., - ¦ находится однозначно. Решив эту систему для
каждого і, мы найдем матрицу h.
Таким образом, мы сумели определить матрицу h, элементы соі,со2, ¦ ¦ ¦ ,cod ш элементы z\, Z2, ¦ ¦ ., Zd-Для того чтобы определить оставшиеся элементы Zd+1, Zd+2, ...,zn, проще всего поступить следующим образом.
Умножим матрицу В1 слева на матрицу h-1. В результате получим матрицу

Z\COi	Z2C02	ZnA, \
ZlCOi	Z2C02	ZnUJn
Zicof	Z2COI	ZnCol
Zico	z2coI-2 -	¦ znto*-2 J
	19

(33)
Вид последней матрицы делает задачу определения элементов Zd+i,Zd+2, ¦ ¦ ¦, zn тривиальной.
Число операций, требуемых для реализации этой части алгоритма по определению оставшейся части ключа (матрицы h и всех элементов zj), не выше 0(d4+dn). Таким образом, общее число операций по реализации всего алгоритма не более, чем 0(d4 + dn). Следовательно, сложность этого алгоритма является полиномиальной от длины п используемого кода.

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

Заключительные замечания

Естественно встает вопрос о модернизации рассмотренной системы шифрования для того, чтобы увеличить ее стойкость. Наиболее естественный путем является выбор для ее построения другого кода не Рида Соломона.
Напомним, что для использования в системе шифрования подходит только тот код, который имеет легкое декодирование. Таких кодов известно не очень много.
Возможно, подходящим вариантом может послужить обобщенный код Боуза Чоудхури Хоквингема длины п = q+ 1 (см. конец раздела 7.8) над полем F,.. где число г существенно меньше числа і/. Нечетко выражаясь, в этом случае построить многочлены не удается из-за того,
матрица h, определенная над Fr, размазывает Zj между различными коэффициентами многочленов fj(x). Имеются и некоторые другие сложности.
Вместе с тем у автора имеются основания считать, что система шифрования, построенная на основе обобщенного кода Боуза Чоудхури Хоквингема, может быть расколота за полиномиальное время.
Другим направлением является использование в системе шифрования двоичных кодов Рида Маллера. В работе [12] рассмотрена такая система и ее модификации. Проведен подробный анализ ее криптографических свойств.
В частности, оценена ее стойкость, которая оказалась высокой.
Третьем направлением являются алгебро-геометрические коды. Эти коды образуют значительно более мощные ансамбли по сравнению с ансамблями, построенными с помощью кода Рида Соломона.
Происходит это из-за того, что мы можем варьировать не только матрицы h и А. как в случае использования кода Рида Соломона, но и вид алгебраической кривой, с помощью которой построен этот код. Это является очень мощным методом маскировки свойств открытого ключа проверочной матрицы В'.
Четвертым совсем не исследованным направлением является использование каскадных кодов или сверточных кодов. По мнению автора на этом направлении могут быть найдены хорошие системы открытого шифрования.

Литература

[1] Шеннон К., Теория связи в секретных системах, в кн.: Шеннон К. Э., Работы по теории информации и кибернетике, М.: ИЛ, 1963.
[2] Защита информации. ТИИЭР Т.78, N5, 1988
[3] Menezes A.J., van Oorshot P.S., Vanstone, Handbook of applied cryptography. CRC Press.
1997.
[4] А. Чмора, Современная прикладная криптография, Гелиос АРБ, 2001
[5] Neal Koblitz, Algebraic Aspects of Cryptography, Springer, 1997
[6] H.Beker, F. Piper, Cipher System, Northwood Books, 1982.
[7] Cryptology and computational number theory, Proc. of Symp. in Appl. Math., v. 42, 1990.
[8] M. Luby, Pseudorandmness and cryptographic applications, N.Y., Princeton Univ. Press, 1996.
[9] Сидельников В. M., Черепнев М. А., Ященко В. В., Системы открытого распределения ключей на основе некоммутативных полугрупп, Доклады РАН, 1993, т. 332, 5.
[10] R.J. МсЕ1іесе,А Public-Key Cryptosystem Based on Algebraic Coding Theory,pp.
114 116 in DGN Progres Report 42 44, Jet Propulsi on Lab.,Pasadena, CA, January- February,1978.
[11] Сидельников В. М., Шестаков С. О., О системе шифрования, построенной на основе обобщенных кодов Рида Соломона, Дискретная математика, 1992, т. 4, 3, 57-63.
[12] Сидельников В.М., Открытое шифрование на основе двоичных кодов Рида Маллера, Дискретная математика, т.6, вып. 3 .стр.
3-20 ,1994.
[13] Сидельников В.М., Быстрые алгоритмы построения набора маркировок массивов дискретной информации, Труды по дискретной математике, т. 1, стр. 251-263, Из-во ТВП, 1997.
[14] Н. Niederreiter. Knapsack-Type Cryptosystems and Algebraic Coding Theory. Probl.
Control and Inform. Theory, 1986, V. 15,pp.l9 - 34.
[15] Сидельников B.M. Декодирование кода Рида Соломона при числе ошибок, большем и нули многочленов нескольких переменных, Пробл. перед, инф. т.30, вып.
3 .стр. 51-69 ,1994.
[16] Сидельников В.М., Першаков А.С. Декодирование кодов Рида Маллера при большом числе ошибок. Пробл. перед, инф. т.28, N3 .стр.
80-94 ,1992.
[17] МакВильямс Ф.Д., Слоэн Н.Дж. Теория кодов, исправляющих ошибки.
М., Связь, 1979.
[18] Riek J.R. Observations on the Application of Error-Correcting Codes to Public Key Encryption.
Inter. Carnahan Conf. on Security Technology.
1990,pp.l5 18.
[19] Cryptology and Computational Number Theory. Proc. of Sym. in App. Math.
Vol 42,1989.
[20] E.R.Berlekamp, R.J. McEliece, H.C.A.van Tilborg.On the Inherent Intractability of Certain Coding Problem IEEE Trans. vol.IT-24,pp384 - 386,1978.
[21] Зайцев Г.В., Зиновьев В.А., Семаков Н.В. Быстрое корреляционное декодирование блочных кодов. Сб.
Кодирование и передача дискретных сообщений в системах связи М. Наука, 1976, стр.74 85.
[22] Евсеев Г.С. О сложности декодирования линейных кодов Пробл. перед, инф. т.19, N 1, 1983.
[23] Крук Е.А. Границы для сложности декодирования линейных кодов Пробл. перед, инф. т.25, N З.стр.
103 - 107,1989.
[24] Бассалыго Л.А.,Зяблов В.В., Пинскер М.С. Проблемы сложности в теории корректирующих кодов Пробл. перед, инф. т.13, стр.
5 13,1977.
[25] Корякин Ю.Д. Быстрое корреляционное декодирование кодов Рида Маллера.
Пробл. перед, инф. т. 23, вып 2,1987, стр. 40 49.
[26] L.В.Levitin. C.P.Hartman, A New Approach to the General Minimum Distance Decoding Problem: The zero-neighbors Algorithm IEEE Trans. vol.IT-31, N3,pp378 384,1985.
[27] G.C. Ntafos, G.L.
Hakimi, On The Complexity of Gome Coding Problems IEEE Trans. vol.IT27,pp794 - 796,1981.
[28] Coffey J.T.,Goodman R.M. The Complexity of Informatin Get Decoding. IEEE Trans, on Information Theory, vol.
IT-36, N5,ppl031 - 1037,1990.
[29] C.M.Adams, H.Meijer, Security-Related Coments Regarding McEliac's Public-Key Cryptosystem in Advancts in Cryptology CRYPTO‘87 (Ed. C. Pomerance), pp 224-228, Lecture Notes in Computer Sci.No.293, Heidenberg and New York: Spinger-Verlag, 1988.
[30] P.J.Lee and E.F.Brickell, An Observation on the Security of the McEliace Public-Key Cryptosystem in Advancts in Cryptology EUROCRYPT‘88 (Ed. C. Gunther), pp 224-228, Lecture Notes in Computer Sci.No.230 ,Heidenberg and New York: Spinger-Verlag, 1988.
[31] J.G.Leon, A Probalistic Algorithm for Computing Weights of Large Error-Correcting Codes. IEEE Trans.,vol.IT-34, N 5 , pp.1354-1359, 1988.
[32] Кнут Д. Искусство программирования для ЭВМ. т.З. Сортировка и поиск. М. Мир.
1979.
[33] Ленг С., Алгебра, М. Мир, 1968.
[34] Глухов М.М., Елизаров В.П, Нечаев А.А., Алгебра, часть 2, стр. 344-345, М. 1991.
[35] Петерсон У., Уэлдон Э., Коды, корректирующие ошибки, М. Мир, 1976.




    Работа с информацией: Безопасность - Защита - Софт - Криптография

• Информационная безопасность
  
• Аспекты информационной безопасности
  
• Системы информационной безопасности
  
• Софт и информационная безопасность
  
• IInternet Information Services
  
  
• Защита и безопасность
  
• Защита с Firewall
  
• Атаки и информационная безопасность
  
• Информационная безопасность в интернет
  
  
• Борьба с вирусами
  
• Антивирусы против вирусов
  
• Хакеры и информационная безопасность
  
  
• Криптография
  

---

---