автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Кодирование для помехоустойчивости и конфиденциальности передачи данных в параллельных каналах

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

на правах рукописи

ПАРАМОНОВ АЛЕКСАНДР ВИКТОРОВИЧ

КОДИРОВАНИЕ ДЛЯ ПОМЕХОУСТОЙЧИВОСТИ И • КОНФИДЕНЦИАЛЬНОСТИ ПЕРЕДАЧИ ДАННЫХ В ПАРАЛЛЕЛЬНЫХ КАНАЛАХ

05.13.16 - "Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)"

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва - 1992

Работа выполнена в Московском фнзико-техническом институте.

Научный руководитель: доктор технических наук

профессор Габидулин Э.М.

Официальные оппоненты: доктор физико-математических наук

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

кандидат физико-математических наук Кабатянскнй Г.А.

Ведущая организация: Институт проблем передачи

информации РАН

Защита состоится 199 2-г. в "10" часов на

заседании специализированного совета К.063.91.11 при Московском фнзико-техническом институте по адресу: 141700, г. Долгопрудный Московской обл., Институтский пер. д. 9.

С диссертацией можно ознакомиться в библиотеке МФТИ.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Часто информация от источника к получателю может передаваться по нескольким параллельным каналам. Такая ситуация типична для систем радиотелеметрии или радиосвязи, использующих частотнее уплотнение ' каналов. Обычно при этом информационные последовательности от нескольких источников преобразуются в частотно- или фазо-модулированные сигналы, каждая на своей поднесущей. Эти сигналы суммируются и передаются по непрерывному каналу. На выходе канала каждая поднесущая демодулируется и выделяется соответствующая информационная последовательность. Таким образом, каждая поднесущая может рассматриваться как отдельный канал передачи информации. Такая же ситуация характерна и для систем УКВ связи.

Использование методов кодирования для однопутевых каналов в применении к параллельным (независимое кодирование каналов, дублирование каналов) дает удовлетворительные результаты, когда каналы независимы и имеют примерно одинаковые характеристики. В случае наличия зависимости между

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

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

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

Целью диссертационно» работы является разработка эффективных методов защиты информации (от помех и нелегального доступа) в системах параллельных каналов. Для этого необходимо решить следующие задачи:

расширить известные классы кодов для параллельных каналов с целью исправления ошибок более сложных структур;

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

построить эффективные методы декодирования для

используемых кодов;

исследовать возможность использования кодирования в параллельных каналах для одновременного обеспечения

конфиденциальности и помехозащищенности передаваемых данных.

Методы исследования. Основным» методами исследования являются методы теории конечных полей, современной алгебры и алгебраической теории кодирования.

Новые результаты и положения, выносимые на защиту:

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

введено понятие стираний решетчатой конфигурации и разработан алгебраический метод совместного декодирования таких стираний и ошибок для широкого класса оптимальных кодов в ранговой метрике;

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

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

помехоустойчивость передаваемой информации.

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

Реализация результатов работы. Результаты

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

Апробация работы. Основные результаты работы

докладывались и обсуждались на:

Н-ом международном семинаре по алгебраической и комбинаторной теории кодирования, АССТ-П (Ленинград, 1990);

международной конференции EUROCRYPT' 91 (Brighton, U.K.,

1991);

на IV международном семинаре по теории кодирования (Дилижан, Армения, 1991);

на семинарах по теории кодирования ИППИ РАН (Москва, " 1990-1992);

на заседаниях кафедры радиотехники МФТИ (Долгопрудный, 1989-1992).

Публикации. По результатам проведенных исследований опубликовано 5 печатных работ, написано 2 отчета по НИР.

Структура н объем диссертации. Диссертация состоит из введения, четырех глав, заключения, приложений, содержит 135* страниц текста, 10 таблиц и 16 рисунков. Список литературы содержит 67 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

ВО ВВЕДЕНИИ раскрыта актуальность темы, сформулирована цель исследования, охарактеризована новизна результатов, приведены сведения об апробации работы и раскрыто основное содержание. Там же дан обзор работ, связанных с коррекцией ошибок в параллельных каналах и определено место диссертационной работы в этой тематике.

В ПЕРВОЙ ГЛАВЕ вводятся основные понятия и базовые модели, используемые в дальнейшем изложении.

При описании параллельных каналов наиболее

распространена решетчатая модель ошибок. При этом нормой

ошибки в (Мхл)-матрице сообщения над GF(q) считается

минимальное суммарное число строк и столбцов, содержащих все

ошибочные символы. Эту величину называют граничным рангом

ошибки. Такие ошибки могут эффективно корректироваться с

примененном кодов в ранговой метрике, когда нормой ошибки

является ранг ее матрицы. Коды в ранговой метрике можно

задавать и в векторном представлении, если вектору длины п N

над нолем Gl-(q ) поставить в соответствие матрицу размера

(Л/хл) над представив каждую координату - вектора

столбцом, соответствующим разложению этой координаты по некоторому базису. Ранговой нормой вектора * при этом

считают максимальное количество его координат, л.н.з. над СГ(д).

Широкий класс оптимальных линейных кодов (с!=п-к+1) в ранговой метрике с!(х,у)=г(х-у;^) дает следующая конструкция

(Э.М. Габидулин, 1985). Пусть А,.....кя • элементы поля

СР(щ ), л.н.з. над О/^?). Тогда (л,к) код с проверочной матрцей

Н

I

I 'I /

... А.

*1М

,.14

, [rf.il (<1-П 14-2]

А, ...А.

(1)

Н)

я

где [|'1=<7", является кодом с максимальным ранговым расстоянием с{-п-к+1 (код МРР). При этом порождающая матрица такого кода имеет вид

в =

{'1

в1 [ < 1

«2

■Вп

1*-'1 [*-') «I «г

(11

I* /1 8Я

где к=п-<1+], а элементы ^.....л.н.з. над 6^(9).

Важную роль при описании таких кодов играют многочлены

" I' 1 "

Р1 ). Такой многочлен называется

число п - его нормой. Множество

вида /^2)= £ Р, г 1.0

линеаризованным, линеаризованных

операциями

сложения

многочленов с F(z)+G(.z)=;E:(F( +С, )21' ' и умножения /г(г)*С(/)=^'(С(г)) образуют некоммутативное кольцо без делителей нуля с многочленом г в качестве единицы.

Естественным обобщением решетчатой модели ошибок являются ошибки непрямоугольных структур, когда нормой ошибки считается минимальное количество вычеркнутых строк и продолженных диагоналей матрицы, содержащих все ошибочные символы (периодические или ЛЧМ помехи). Корректировать такие ошибки позволяет следую .гш подход.

Пусть взаимно-однозначное отображение векторного

пространства У" на пространство IV il пусть на пространстве V" задана метрика d(x.y), x,y*v". Пусть также илсИ'".

Определение. Метрика D(u,v)=d{<// (и).Ф (v)), заданная на Vf", называется индуцированной.

Лемма. Пусть код m имеет кодовое расстояние d в метрике d(x,у). Тогда его код-образ имеет кодовое расстояние d

в индуцированной метрике D(u,v).

Если отображение Ф являются изоморфизмом группы векторов пространства и", т.е.

то эффективные методы кодирования/декодирования для кода m в метрике d могут применяться и для кода-образа m=0(m) в индуцированной метрике. Кроме того, ошибка в индуцированной метрике с связана с ошибкой е в исходной метрике соотношением

e=(!i"'(c)

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

Введение класса отображений над пространством векторов х=(х0.....■*„_/) длины п над полем GF(q )

,/ \ ,/ w I"! !•>) 1Г«- От]. и=</>(х)=*(х0.....хп _ ¡)=(хд ,х, .....хя_, )

с параметром m=JT,N^\ и выбор на этом пространстве ранговой

метрики дает класс От-метрик, позволяющих корректировать

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

£>т-метрике единичной ошибки в матричном представлении дается

выражением

El.n, =NCmD•

где N - произвольная невырожденная (NxN) матрица над GF(q), D=diag{a0,a,,...,ап_ ,} - диагональная (пхп) матрица над GF(q), а Ст - (Nxn) матрица-m-циркулянт над GF(q).

ВТОРАЯ ГЛАВА посвящена совместному исправлению ошибок и стираний решетчатой конфигурации кодами МРР с проверочной матрицей вида (1). Наличие стирании для кода, определенного над GF(q), означает, что демодулятор имеет q обычных выходных символов и (q+1)-ый символ (например "?"), соответствующий стиранию, решенне о выдаче которого выносится в том случае, когда принятый непрерывный сигнал находится далеко от всех

•сигналов, соответствующих д символам кодового алфавита. Будем считать, что в принятой матрице произошло ( стираний, если минимальное количество линий, покрывающих все символы "?" равно Л В соответствии с решетчатой моделью ошибок, будем предполагать, что если демодулятор принял решение о стирании лшшн, то все символы в этой линии заменены на символ "?". При этом под рангом ошибки т будем понимать ранг ошибки на подматрице, состоящей из нестертых символов.

Стирания / столбцов матрицы легю корректируются укорачиванием кода МРР на / позиции, поэтому рассмотрим лишь стирания строк. Заменим в принятой матрице все символы стирании на нулевые и обозначим такую матрицу через V' (вектор V'). Если в принятой матрице V (векторе V) произошло I стираний строк и ошибка ранга т, то т « г(ч' -с;(/) < и, следовательно, ошибку е можно представить в виде е-У-с=Е К=(£,.....Ет.Ет.,.....Ет.,)У=

= (£,.....Ет)Гт + (Ет.,.....£„,.,)>-,.

В этом представлении величины Е,.....Ет и матрица Ут размера

(т*п) над СЕ(ц) ранга т соответствуют происшедшим ошибкам, а

величины Е,.....Ет л.н.з. над, ОТ(</). Величины £т.......£т„( и

матрица У/ размера ('*") над • £7£(<у) соответствуют стираниям

строк принятой матрицы. При этом очевидно, что Ет.,.....Ет.(

линейно независимы и извести. Действительно, если стерта к-ая строка матрицы, то величина Е,, соответствующая этому стиранию в разложении но выбранному базису имеет вид £/¿"8^. Кроме того, величины £,.....Етл.н.з. в совокупности.

Декодеру достаточно найти величины £,.....Ет и матрицы

У т и У,. Декодирование, как и в случае исправления только ошибок, начинается с вычисления синдрома

НТ =еНТ=ВУНТ = ЕХ. (2)

где матрица Х=УНГ имеет вид

Х1 х 1/1 X, М X,

X = *} X х3 и X,

Хт• 1 X ' и хт> 1

п

причем величины х = £ V _, /i. , р=ТТт л.н.э. над GF(q). / ■ '

В координатной записи уравнение (2) эквивалентно системе уравнений относительно неизвестных Е,.....Ет, х,.....хт, t:

Y = Sf, (3)

Решив эту систему, пс известным xt легко построить матрицы Ym и У, и найтн вектор ошибки е=ЕУ.

Отметим, что в системе (3) фигурирует ранг ошибки, который заранее неизвестен и должен быть определен при декодировании. Таким образом, задача декодера состоит в решении (3) для наименьшего возможного т относительно 2т+1

неизвестных Е,.....Ет, хг...,хт.,.

Для решения системы введем линеаризованный многочлен

синдрома j(z)= Z J/z"'> линеаризованный многочлен

т.,

A(z)= Е Л г''1, Ат./"1> корнями которого являются р.о р

всевозможные линейные комбинации Е,,...,Етw с коэффициентами из OF(q) и вспомогательный линеаризованный многочлен

F(z)=m Е F zlPi, где F,-i A ¡=ТГт7П.

р.О г р-О ' г

Можно доказать, что многочлены F(z), A(z) и i(z) связаны соотношением

F(z)=i(z)*s(z) mod z1"'(4) где A(z)*i(z)=A(j(z)). Найдя A(z), легко определить величины En—>Em*t (это л.н.з. корни A (z)). Поиск A(z) облегчает

знание части его л.н.э. корней fim.,.....£mW, что позволяет

представить A(z) виде

A(z)=A'(z)*T(z),

где T(z) - линеаризованный многочлен, л.н.з. корнями которого

являются величины Ет. ......Еот.( . Обозначив через j' (z)

многочлен T(z)*5(z), приведем уравнение (4) к виду

f(z)=A'(z)*j'(z) mod zld~ "• (5)

Теорема. Уравнение (5) имеет единственное нормированное решение А' (z), Ад=1, если 2/ni-lsd-l.

Теорема дает нам границу на количество одновременно исправляемых ошибок и стираний. Эта граница аналогична известной в метрике Хэмминга.

Уравнение (5) решается стандартными методами, например с

помощью применения алгоритма Евклида в некоммутативном кольце линеаризованных многочленов. Найдя Л'(-г), легко построить Д(2), • после чего декодирование завершается стандартным способом.

Приведем теперь алгоритм совместного исправления ошибок и стираний для кода МРР. Он состоит из 6-тн этапов.

Этап 1. Если произошло /«¿-1 ошибок в столбцах принятой матрицы V, то укорачиваем код на I позиций и переходим к этапу 2, иначе отказываемся от декодирования.

Этап 2. Если произошло Г5(М-/ стираний строк матрицы V, то строим многочлен Т(г) с линейно независимыми корнями

Ет, ,.....присваиваем стертым позициям нулевые значения,

вычисляем модифицированный синдром и переходим к

этапу 3. Если г=0, то Т(2)°=2 и Если <><Л/-/, то

отказываемся от декодирования.

Эгап 3. Решаем ключевое уравнение (5) относительно Л' (г), строим 4(г)=А'(.')*Г(2) и переходим к этапу 4. Если Л(г)=0 или Г(г)-0, то отказываемся от декодирования.

Этап 4. Находим линейно независимые корни уравнения А(г)=0. Если число линейно независимых корней Д(г) не равно норме Л(г), то отказываемся от декодирования.

Этап 5. Решаем систему (3) и находим х,.....хт,

Эгап 6. По строим матрицу У и находим вектор

ошибки е=ЕУ.

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

В первом параграфе ТРЕТЬЕЙ ГЛАВЫ приведен анализ сложности декодирования кодов МРР. В процессе декодирования выделяются четыре укрупненных этапа:

г

1) Вычисление вектора синдрома %=чН и синдромного многочлена ¡(г).

2) Решение линеаризованного ключевого уравнения F(z)=A(z)*i(i) mod 2{<1'П.

3) Поиск векторов Е и х.

4) Вычисление вектора ошибки с-EY.

Верхняя граница сложности каждого из этих этапов приведена в таблице 1. При этом значком #{х} обозначено максимальное количество умножений при декодировании, значком #{+} - сложений, #{[]} - возведений в степень, а #{1/} делений. В последней колонке приведен коэффициент усложнения за счет осуществления операций в большом поле.

этап подэтап кол-во операций к.уел [

1 *{х) « (я- 1>(<1- О *{ + } « n(d- 1) N

2 *{х} « 7d3/S'd/i-3/S *{ + } * 7d3/l-d• l/a *{[]} * 7d3/t'd/г- i l/a *{1/} « " Nlog3 N N1"'3 Nlou3

3 поиск * *{x) s I3(d- I)3/a.S(d-!)/<.» *{ + } * 7(d-n3/a'(d-n/1-4 *{[]} £ 3(d-i)3/4'(d- n/i-4 #{1/} i (d- l)/l ¿oil N Nlot3 А/"''

поиск Е а) поиск Е б) "{x} л N(d- l)/t »{+} * N(d- l)/I *{[]} * (N' n(d-l)/3 *{x} <S H( Ы- 1) * N( N- 1) *{ + } « N(N- l)3+N *{[]} * N N"" N n""3

4 *{x} « Nn(d-I), *{+} < n(2N(J-2)-d'l)/3

Таблица 1. Сложность декодирования кода МРР.

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

Ускорить процесс декодирования можно за счрт применения более эффективных алгоритмов. При этом для вычисления синдрома и поиска х можно использовать классические быстрые алгоритмы для матричных вычисления и операций с многочленами в совокупности с эффективной организацией вычислений в "большом" поле.

Вопрос о решении ключевого уравнения занимает в проблеме ускорения декодирования особое место и ' требует синтеза независимых алгоритмов. Этот вопрос и рассматривается в оставшейся части 3-ей главы, где формулируется и обосновывается аналог алгоритма ' Берлекэмпа-Месси для некоммутативного кольца линеаризованных многочленов LN[z].

Можно показать, что решение уравнения (4) в кольце i-w[z] относительно многочлена Д(z) с наименьшей возможной нормой т, эквивалентно построению регистра сдвига минимальной дличы с линеаризованной обратной связью, генерирующего

последовательность компонент синдрома Такой

регистр описывается линеаризованным многочленом обратной связи A(z), Д0=1 и длиной / ((А(г),/)-регистр) и приведен на рисунке 1.

Процедура построения самого короткого регистра является индуктивной. Для каждого г, начиная с r=1, построим регистр сдвига, генерирующий первые г компонент синдрома. (Дг (z),/r )-регистр является регистром минимальной длины,

генерирующим s0,s,.....гг .К началу г+1 итерации уже будет

задан список регистров сдвига

Будем теперь строить следующий (Дг. /(z),/,. ^-регистр с использованием предыдущего регистра сдвига (Ar (z),lr). с соответствующим изменением его длины и весовых множителей.

На г+1 шаге проверим, генерирует ли (Лг, ,{z),lr„,) регистр s0.....ir, то есть выполняется ли соотношение

I*, w •»<*)£ - о,

где [b(z)]l = Е Ък (z). Величина dr ={ДГ (z) *s{z)]rr /z1r 1

k » I

называется невязкой и имеет вид

Л,- ЕА-.Л!,'- ЕЛ.

I - I < «о

Если =0, то увеличим г на единицу, сохраняя неизменным регистр. В противном случае следующим образом изменим весовые множители в обратной связи регистра сдвига

'(г).

где А - элемент поля, I - натуральное число, а - один

из многочленов регистра сдвига, встречавшихся в одной из

предыдущих итераций. Если выбрать теперь к меньше г и такое,

* I г - * 1

чтобы (¡к*0, -положить 1=г-к, а А=-<1т/ик то получим, что

новая невязка

* ы[г'к]

V - о 1 ¡¡к

и, следовательно, новый регистр сдвига будет генерировать Выбрав в качестве к номер ближайшей итерации, на которой 1к., >1к, получим в каждой итерации регистр сдвига с минимальной длиной.

1 1 ■Л,о -Л,о 1 ' \

СП [21

* *

4-1 - 1

(1-1) [1)

Рисунок 1. Регистр сдвига с линеаризованной обратной связью.

Формально алгоритм описывается следующим образом: при любом г параметры (Дг „ . ^-регистра определяются через параметры (Лг (г),1г )-регистра и параметры еще одного регистра (Ак (г),1к ) в последовательности самых коротких регистров,

г г

где кг < г.

Алгоритм. При любом г>0 целое кг определяется следующим рекуррентным соотношением

= Г кг -с если /г =/г. , ' [ если /г >1Г.,

Многочлен „ и /г,( определяются как

= M') • -rferr <*>

К '

dr = 0 )}. dr • 0

«... - f

{ max{lr, )}.

где ¿г и <1к определяются из (6).

г

Алгоритм начинает свою работу при следующих значениях

и завершается после ¿-1 итераций.

Количество операций для алгоритма ограничено сверху выражениями

#{ + } * (/-1)/2.

#{[]> < (<М)*/2 + (<М)/2.

#{*} « (</-1)г/2 + d■ 1. #;!/} * (<м)/2.

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

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

генерируемых описанным выше регистром.

В ЧН'ПШРТОИ ГЛЛПП рассматривается возможность применения кодов МРР в криптографии и предлагается модификация криптосистемы Мак-Элайса с открытым ключом на основе этих кодов.

Модифицированная схема работает следующим образом. Получатель, желающий принять секретное сообщение выбирает порождающую матрицу С линейного (п,к) кода МРР, исправляющего /=[(л-А:)/2] ошибок. Стройся невырожденная (АгхЛ)-матрнца S, случайная ранговая ошибка u„, /"(u„,-<7)«f„ желательно большого

k п

хэммннговского веса и случайный ненулевой вектор aeGF (</ ) (предпочтительно at »0, vi) и держатся в секрете. Матрица К, являющаяся открытым ключом получается как

K=SG+aT ug.

При отсылке сообщения отправитель генерирует случайную

ранговую ошибку Ки,.'?)4'*. желательно с большим

весом Хэмминга, и образует шифртекст

2=тК+и,.

Получатель, декодируя принятое сообщение как слово кода в, находит ошибку и=(£а. )и +и и сообщение ш' =ш5, из которого

получает исходное сообщение т=ш'5.

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

Основным таким свойством является то, что количество ранговых ошибок малой нормы много больше, чем количество хэмминговскнх ошибок того же веса. Количество векторов длины п ранга $ над полем ) дается выражением

где

А/ N «- /

г „ 1_(<? -!)• • (я -<? )

Ь Г(я'.г).

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

Пример. Пусть л=20, к=12, <,=2, 1^=2. Тогда

- скорость И=к/п=3/5;

2 13

- размер открытого ключа п £=4800 <* 2 ;

объем работы по раскрытию -2™ при алгоритме, аналогичном исходному для схемы Мак-Элайса-

В оценке объема работы фигурируют операции . в поле

). Приведенные параметры превосходят аналогичные для криптосистемы Мак-Элайса, для которой при примерно той же сложности раскрытия размер открытого ключа составляет примерно 2 бит.

Выбирая большее п и большее Л, возможно использовать часть избыточности для засекречивания информации, а часть избыточности - для коррекции ошибок.

В ЗАКЛЮЧЕНИИ изложены основные результаты диссертационной работы и их практическое значение. Там же приведены возможные направления дальнейших исследований н дан список открытых задач, связанных с кодами в ранговой метрике.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Приведен простой подход к построению кодов, исправляющих ошибки заранее заданной конфигурации, основанный на взаимно-однозначном преобразовании векторных пространств.

2. Введен новый класс метрик и предложен способ построения широких классов кодов для этих метрик с эффективными алгоритмами кодирования/декодирования. Введенные метрики позволяют исправлять ошибки сложных (в том числе непрямоугольных) структур в системах параллельных каналов.

3. Предложена алгебраическая процедура совместного исправления ошибок и стираний решетчатой конфигурации для кодов МРР, сложность которой оценивается сверху полиномом второй степени от длины кода. Эта процедура позволяет исправлять I стираний и ошибку ранга т одновременно, если 2т+ЫА.

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

5. Получены оценки сложности каждого из этапов декодирования кодов в ранговой метрике.

6. Предложен новый способ декодирования кодов . МРР, позволяющий сократить количество операций, допускающий существенйое распараллеливание вычислений и несложную

аппаратную реализацию. Этот способ использует новое понятие сдвигового регистра с линеаризованной обратной связью (РСЛнзОС).

7. Указана возможость применения схем на основе РСЛнзОС для вычислений в кольце линеаризованных многочленов. Описаны основные свойства последовательностей, генерируемых таким регистром.

8. Предложена модификация криптосистемы Мак-Элайса с использованием кодов в ранговой метрике. Применение этой конструкции позволяет существенно снизить объем открытого ключа (узкое место в системе Мак-Элайса) без снижения объема работ по раскрытию. Кроме того, данный подход • позволяет использовать коды в ранговой метрике для одновременного обеспечения конфиденциальности и помехозащищенности передаваемых данных.

[1] Е.М. Gabidulin, A.V. Paramonov. Generalized rank metric codes. In: Proc. of II International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-II), Leningrad, USSR, 1990.

[2] A.V. Paramonov, O.V. Tretjakov. A modification of McEliace's scheme based on codes for Rank Metric. In Proc. of II International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-II), Leningrad, USSR, 1990.

[3] E.M. Gabidulin, A.V. Paramonov, O.V. Tretjakov. Ideals over a Non-Commutative Ring and their Applications in Cryptology. In: Proc. of EUROCRYPT'91, Lecture Notes in Computer Science №547, Springer-Verlag, New York, 1991.

[4] E.M. Gabidulin, A.V. Paramonov, O.V. Tretjakov. Rank Errors and Rank Erasures Correction. In: Proc. of IV International Colloquium on Coding Theory, Dilijan,

. Armenia, 1991.

[5] A.B. Парамонов, O.B. Третьяков. Аналог алгоритма Берлекэмпа-Месси для ' декодирования кодов в ранговой метрике. В кн.: Тр. МФТИ, 1991.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Тотлпщнт iMcbTW Тирдлг, Асо

ТЪиыслнс

6/H/V2 Зака* неиер