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


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




[0]

Открытые системы шифрования на основе кодов, корректирующих ошибки, и как некоторые из них можно

расколоть

В. М. Сидельников

Основная цель данной работы рассказать со всеми подробностями о том, как можно расколоть за полиномиальное время систему открытого шифрования Нидеррайтера, построенную на основе кодов Рида-Соломона. Основные результаты этой статьи впервые изложены в работе Шестакова СО и автора [2]. Как полагает автор, статья будет полезной молодым исследователям.

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

1. Несколько слов о теории кодов, корректирующих ошибки, и кодах

Рида-Соломона

1.1. Основные понятия. В настоящем разделе будут даны только начальные сведения о теории кодирования, необходимые для определения систем открытого шифрования, предложенных Маклисом [1] и Нидеррайтером [4]. Для простоты, мы рассматриваем только частные случаи кодов, которые имеют наибольшее значение для криптографии. Значительно более полное изложение теории кодирования имеется в книгах [7] и [25].

Мы рассматриваем конечное поле F,;. q = р1. где р - простое число и I - положительное целое, содержащее q элементов. Множество F™ = {х = (х±,... ,xn)\xj G Fg}, мы обычным образом рассматриваем как линейное пространство размерности п.

На пространстве F™ задана метрика Хемминга, которая определяется следующим образом. Расстояние d(x, у) между двумя векторами х и у из F™ равно числу координат, в которых эти векторы различаются. Например, расстояние между векторами (0,1,2) и (2,1,0) из F (трехмерное пространство над полем F:>, = {0,1,2} из трех элементов) равно 2, так как эти векторы различаются только в первой и последней координате. Метрическое пространстве F™ с метрикой Хемминга будем называть пространством Хемминга. На пространстве Хемминга рассматривают еще одну функцию wt(x) - вес вектора х, равный числу его ненулевых координат. Функции d(x, у) и wt(x) связаны соотношениями d(x,y) = wt(x - у), d(0,x) = wt(x).

Кодом называется произвольное подмножество К пространства F™. Кодовое расстояние /ЦК.) кода К. определяется как минимальное расстояние между двумя различными элементами К., т.е. d(fC) = minx]y(ek;;xyd(x, у). Всюду далее мы в качестве кодов К, будем рассматривать только линейные подпространства L пространства F™. Размерность L всегда будем обозначать буквой к. Такие коды называются q-значными линейными кодами. Их параметры будем коротко записываются в виде [n,k,d\q, где п - длина кода К., к - его размерность и d = d(K) - его кодовое расстояние. Число г = п - к обычно называют избыточностью кода.

Следует заметить, что кодовое расстояние линейного кода может представлено и несколько иным во многих случаях более удобным способом. А именно, d{K) = минимальному весу ненулевого элемента кода К (доказать самостоятельно).


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

Под одиночной ошибкой типа замещения мы понимаем замену одного из символов в векторе х G F™ на другой символ. Если в векторе х произошло t ошибок, то t координат изменило свое значение. То, что пространство F™ является метрическим, позволяет утверждать, что t-кратная ошибка превращает кодовый вектор х в вектор х, отстоящий от х на расстояние t, т.е. d(x,x) = t. Таким образом, если в канале связи происходит не более, чем t ошибок, то искаженный кодовый вектор х находится в шаре (в метрике Хемминга) радиуса t с центром в точке х € К..

1.2.Геометрическая интерпретация кода. Если все шары радиуса t с центрами в кодовых точках кода К. не пересекаются, то из очевидных геометрических соображений следует, что код может исправить любые t или меньше ошибок, которые поразили кодовый вектор х в канале связи. Для этого необходимо использовать процедуру декодирования, которая находит тот центр шара х (кодовый вектор), к которому принадлежит искаженный вектор х. Из сказанного выше вытекает, что если код имеет кодовое расстояние d(K) > It + 1, то он может корректировать все ошибки кратности < *•

Вектору а = («.....«*•). <tj € F,;. который переносит информацию, поставим в соответствие кодовый вектор х(о) € К.. Для передачи информационного вектора а по каналу связи с шумами в канал вместо а посылают кодовый вектор х(о). На выходе канала после декодирования определяется вектор х(о), а затем и информационный вектор о.

Рассмотренную геометрическую модель коррекции ошибок можно построить из-за того, что F™ является метрическим пространством, метрика которого в согласована с видом искажений, которые возникают в канале связи. Можно сказать, что с геометрической точки зрения теория кодов, исправляющих ошибки, представляет собой науку, которая занимается упаковками шаров в метрических пространствах, в частности, в пространстве Хемминга, а также задачами декодирования кодов того или иного вида. Таким образом, такое весьма абстрактное математическое понятие, как метрическое пространство, оказывается весьма полезным для содержательных и наглядных представлений кодов К., корректирующих ошибки, и в конечном итоге для их построения и использования.

Одной из основных задач теории кодирования является задача построения кода длины п с кодовым расстоянием d с возможно большим числом элементов, т.е. в случае линейного кода с возможно большой размерностью к. За многие годы развития теории кодирования создано большое число разнообразных кодов. Мы остановимся только на относительно узком классе: классических и давно известных кодах Рида-Соломона и кодах Боуза-Чоудхури-Хоквингема (БЧХ-код). Код Рида-Соломона является частным случаем БЧХ-кода.

1.3.Проверочная и порождающая матрицы линейного кода и их свойства. Будем пользоваться без объяснений стандартными понятиями теории конечных полей и линейной алгебры.

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

Скалярное произведение (х,у) векторов х = (>----..г„). у = (у\.... ,уп) G F™ в поле F,; определяется соотношением

где сложение и умножение в последней сумме выполняется в поле Fg.

Код К над Fg состоит из всех векторов b G F™ таких, что (Ь, а) = 0 для всех а € К. По другому,

если Hi----, а& - базис кода К., то базисом кода К.1- являются векторы b----. b,для которых

(bj, as) = 0 для всех s = 1,... , к. Отметим, что сумма размерностей кодов К. и Ai равна п (доказать самостоятельно).

Матрица В, строками которой являются базисные векторы кода К.1- (их число п - к) называется проверочной матрицей кода К., а матрица А, строками которой являются базисные векторы кода К.,


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

/>а =0. а € F;;.(2)

где значок о обозначает " транспонирование" соответствующего объекта (общепринятое обозначение), или все векторы а, которые имеют вид

а = а А. « € Ff;. a G F™.(3)

Заметим, что в формуле (2) а - столбец высоты п. Матрицы В и А по определению взаимно ортогональны: А Вт = 0, В А1 = 0.

Утверждение 1. Код К. имеет кодовое расстояние d, если выполнены два условия

i.Любой комплект из d - 1 столбцов матрицы В является линейно-независимым.

ii.Найдется комплект из d столбцов матрицы В, который является линейно-зависимым.

Это достаточно простое утверждение может быть доказано самостоятельно. Отметим только, что если выполнено лишь условие i, то d(K) > d.

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

Наиболее известными матрицами В, для которых выполнено утверждение 1, является матрица

В = В% =

а°2

<*°п \

а±

al

d>2,

/з2°

#-i

/32

Aj-i

/31

, fij G {ai,a2,..

• ,a„},

at2

Ptl

l2lxn /

где n < q - 1и21 = {ai .ai----.а,,} - различные ненулевые элементы поля F,;. Столбцы любого

комплекта из d - 1 столбцов матрицы В является линейно-независимыми. Это следует из того, что определитель

с попарно различными (3j является отличным от 0 определителем Вандермонда.

Множество 21 часто расширяют, а именно, добавляют к нему элементы 0 G F? и особый элемент

00.Мы далее будем полагать, что матрица В в (4) определена именно для такого расширенного множества 21. О подробностях такого определения удобно рассказать ниже в разделе 1.4.

Нумерацию столбцов матрицы В будем производить с помощью элементов множества 21. Так столбец с номером а является j-ым столбцом, если а = ctj. Совершенно аналогично поступаем с координатами вектора х = (ха1,ха2, ,ха„) € F™, их также индексируем элементами множества 21, которые записаны в определенном порядке.

1.4. Коды Рида-Соломона. Мы рассмотрим три вида кодов Рида-Соломона длин п = q-1, q, q+

1.Все они имеют в качестве проверочной матрицу вида (4), но различные множества 21.

Тип 1. п = q-1. В этом случае множество 21 состоит из всех ненулевых элементов поля F,;.

Тип 2. п = q. В этом случае множество 21 состоит из всех элементов поля F,;. Следует сказать, что столбец (a°,aj,... ,а~2)т, у которого aj = 0 имеет вид (1,0,... ,0)т.

Тип 3. п = q+1, d> 3. В этом случае множество 21 состоит из всех элементов поля Fg и еще одного элемента оо (бесконечности). Предполагается, что элемент оо обладает естественными свойствами

этого понятия. Например, ооо = -х;. а ф 0. " = 0 и т.п. Столбец (a%aj,...

) , у которого

ctj = оо по определению имеет вид (0,0,... , 1)т. Более общо, мы считаем, что значение многочлена /(.г) = 53i о степени не выше d-2 в точке оо является коэффициент /,/....•.;. В частности, /(оо) = О, если степень f(x) меньше d - 2. В этом случае мы говорим, что f(x) имеет корень оо. Можно сказать, что мы рассматриваем проективное пространство Fg U {оо} и многочлены на нем.



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