BCHr(n,d) с порождающей матрицей А, искаженный не более, чем в f разрядах. Как раз здесь используется тот факт, что унипотентная матрица /.) 1 • 11 сохраняет вес вектора е (см. раздел 1.9). Затем с помощью какого-либо общеизвестного полиномиального алгоритма декодирования кода BCHr(n,d) находится вектор о, который удовлетворяет условию b = а1 А + е, где w(e) < f. Затем вычисляется вектор а в виде а = аЬ 1.

Мы будем предполагать, что t < (d - 1 )/2. Вместе с тем можно полагать, что t > d - 1)/2, но t меньше некоторой границы. При этом надо использовать алгоритм декодирования работы [5] или работы [], которые работают при определенном ограничении на величину f "почти всегда" правильно. Как будет видно ниже, чем больше алгоритм декодирования исправляет ошибок, тем выше будет стойкость системы шифрования. Вместе с тем при возрастании числа исправляемых ошибок, как правило, возрастает и сложность его реализации. В идеале, лучше всего использовать корреляционный алгоритм, но его сложность является слишком высокой и он не доступен для реализации. Обычно в системе Маклисп используют алгоритмы типа ii. или ш..

3.2.Система открытого шифрования Нидеррайтера. В системе Нидеррайтера [4] рассматривается ансамбль Br(n,d) проверочных матриц кода BCHr(n,d), который определяется как множество всех матриц вида В = h С D Г, где С - фиксированная проверочная матрица вида (8), h пробегает множество всех невырожденных п - к х п - к-матриц над F,.. /.) - множество всех диагональных матриц с ненулевыми на диагонали элементами, а Г - множество всех перестановочных матриц размера п х п.

Подобно системе Маклиса открытым ключом абонента X в системе Нидеррайтера является матрица В1, а секретным - матрицы h, D, Г.

Шифрованная информация с абонента У и предназначенная абоненту X в системе Нидеррайтера представляет собой r-значный длины п - к и вида

с = еВ,Т,(14)

где В1 = Вх проверочная матрица, которая случайно выбрана абонентом X из ансамбля Br(n,d) и к - размерность кода с этой проверочной матрицей. Вектор е является вектором длины п и веса, не превосходящего t, который несет конфиденциальную информацию абонента У.

Заметим, что конфиденциальная информация является одним из решений уравнения

с = хВТ(15)

Найти какое-либо решение этого уравнения простая задача - это линейное уравнение сп - к уравнениями и п неизвестными. Найти среди всех решений (их число 2*) решение с минимальным весом это уже сложная задача, которая эквивалентна задаче декодирования кода с проверочной матрицей В1. Доказательство последнего утверждения просто. Если мы умеем находить решение е уравнения (15) минимального веса, то решение уравнения (12) производится следующим образом. Сначала вычислим вектор а/>" = еВ/Т (синдром а), найдем вектор ошибок е, а затем и кодовый вектор а = а - е.

Также как в системе Маклиса в системе Нидеррайтера матрица В представляется нападающей стороне матрицей общего положения.

В теории кодирования вектор с из (14) называют синдромом вектора е. Отметим, что матрицы В и А связаны соотношением В Ат = 0, где А - одна из матриц ансамбля Ar(n,d). Строки матрицы В1 являются базисом подпространства размерности N - к ортогонального к пространству строк матрицы А1.

Абонент X, получив сообщение с, находит какой-либо вектор Ь, который является решением уравнения х/>" = с. Очевидно, вектор b является вектором вида b = а А + е при некотором неизвестном о G F*. Затем абонент X также, как в системе Маклиса, декодирует вектор Ь11 • /.) 1 = b = аА + е, но вместо кодового вектора аА находит вектор е = Ь - аА, а затем и вектор е = еГ • D. Отметим, что в отличие от системы Маклиса, в системе при расшифровании (восстановлении вектора е) никак не участвует матрица h. Она нужна только для маскировки матрицы В1.

Как и выше, предполагаем, что используемый алгоритм декодирования кода BCHr(n,d) всегда правильно восстанавливает вектор ошибок е.

3.3.Сравнение систем открытого шифрования Маклиса и Нидеррайтера. Системы Маклиса и Нидеррайтера обладают одинаковой стойкостью к нападению, ибо криптографическая атака на одну из систем может быть легко трансформирована в атаку на другую. Поясним это подробно.

Мы полагаем, что обе взаимно ортогональные матрицы А (открытый ключ системы Маклиса) и В (открытый ключ системы Нидеррайтера) известны нападающей стороне, так как одна из другой может быть получена как решение линейной системы уравнений А1 Вт = 0, т.е. с помощью не более, чем 0(п3) операций.

При известном синдроме с = еВт нетрудно вычислить вектор b = и А + е с некоторым вектором о G F* такой, что с = ЪВ/Т. Для этого надо найти какое-либо решение b уравнения (15). Вектор b мы будем рассматривать как криптограмму в системе Маклиса. Если для системы Маклиса найдена криптографическая атака со сложностью Q. т.е. известен алгоритм вычисления вектора а (конфиденциальная информация в системе Маклиса), то вектор е (конфиденциальная информация в системе Нидеррайтера), очевидно, представляется в виде е = b - ЗА1, т.е. сложность определения е, по существу, совпадает со сложностью определения о.

Наоборот, если для системы Нидеррайтера известна криптографическая атака со сложностью Q, то используя в качестве криптограммы этой системы вектор с = ЬВТ = (ЗА + е)Вт = еВт, где b

-криптограмма системы Маклиса, вычислим вектор ошибок е, а затем и вектор 3, который является единственным решением линейного уравнения у А = Ь - е.

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

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

Две эти системы различаются скоростью передачи. Если код К. является низкоскоростным, т.е. к/п

-малое число, то скорость передачи у системы Нидеррайтера всегда выше по сравнению с системой Маклиса. Поэтому далее будем рассматривать только ее. Вместе с тем будем предполагать, не оговаривая этого особо, что криптограммой системы Нидеррайтера является /(-мерный вектор b = ЗА + е, который является каким-либо решением системы (15), где с = ЪВТ = еВт и е - вектор веса не выше f (информационный вектор абонента У). Это связано с тем, что алгоритм декодирования кода RSq(n,d), рассмотренный в [5], и некоторые известные криптографические атаки оперируют с искаженным кодовым вектором Ь, а не с его синдромом с.

Шифрование сообщения е состоит в вычислению его синдрома и поэтому его сложность шифрования равна 0((N - k)N) операций. Сложность расшифрования (сложность восстановления вектора е) определяется, в основном, трудоемкостью алгоритма декодирования кода RSq(n,d) и при использовании алгоритма декодирования работы [5] не превосходит 0(п3) операций. Для декодирования в пределах кодового расстояния известны и более быстрые алгоритмы (см. [],[]).

Как известно [8], кодовые системы открытого шифрования имеют большую скорость шифрования по сравнению с другими подобными системами, например, с системой RSA. Вместе с тем они обладают, по меньшей мере, двумя недостатками.

Во-первых, скорость передачи у кодовой системы всегда меньше 1 (обычно меньше 1/2), в то время как в системе RSA (см. [9] и многие другие работы) она равна 1.

Во-вторых, открытый ключ (в рассматриваемой кодовой системе - матрица В) имеет объем примерно вп - к раз больший, чем у упомянутой системы RSA. Если к относительно маленькое число то выгодней в качестве открытого ключа системы рассматривать матрицу А, которая связана с В соотношением В А = 0.

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

В системе открытого шифрования Нидеррайтера в качестве открытой информации выступают векторы е веса t и менее. Для ее реализации необходимо иметь алгоритм, который отображает множество всех r-значных векторов длины s в множество IV, векторов длины п и веса не выше t, где s < r(t,N) = [lgr Х)=о Ci)(r ~~ 1)1 (логарифм числа возможных сообщений в системе Нидеррайтера). Этого относительно простого вопроса мы касаться не будем.

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

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

4. Как раскалывается система открытого шифрования Нидеррайтера, построенная с помощью обобщенного кода Рида-Соломона ? Общие

подходы.

В этом разделе мы рассматриваем систему Нидеррайтера, построенную с помощью g-значного кода из ансамбля Bq(n,d) (см. начало раздела 3.2). Как было установлено в разделе 3.3, соответствующая система Маклиса (система, в которой порождающие матрицы выбираются из ансамбля Aq(n,n - d+1) имеет примерно ту же стойкость к нападению, что и рассматриваемая система открытого шифрования.

Имеется два вида атак на систему открытого шифрования.

i."Чтение" открытого сообщения абонента У без использования секретного ключа абонента X (бесключевое чтение). В данном случае секретным ключом являются матрицы h,T,D.

ii.Вычисление секретного ключа абонента X с последующим вычислением открытых сообщений абонента У. направляемых им абоненту X.

Рассмотрим сначала атаку L. Для ее реализации необходимо решить уравнение (15). С точки зрения нападающей стороны матрица В является матрицей общего положения. Поэтому для нахождения решения е уравнения (15) веса wt(e) < t в соответствие с тезисом А необходимо проделать экспоненциальное от его длины п число операций. Можно полагать, что при большем п » 100 это не возможно на современном уровне развития вычислительной техники.

Другой подход, реализующий атаку L, состоит в следующем. Можно "угадать" обобщенный код Рида-Соломона, определяемый проверочной матрицей В1, и произвести декодирование (решить уравнение (15)) в этом коде. По следствию 1 число таких кодов Aq(n,d) не меньше (gd-i1)(gd-!ig)1?..(gd-igd-2) • Это число при п » 100, d < п/2 и q > 2 больше, чем 1077. Поэтому это событие очень маловероятно и его можно не рассматривать.

Таким образом, по современным представлением с учетом тезиса А бесключевое чтение (атака i.) в рассматриваемой системе невозможно при достаточно большом п.

Рассмотрим теперь атаку ii.. Задачей в этом случае является определение матрицы h,T,D, исходя из известной матрице В. Как будет показано ниже и это основной результат работы эта задача может быть решена за 0(s4 + sn) операций в поле Fg.

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

Любая матрица ансамбля Bq(n,d) имеет вид

( 2l/o(wi)

Z\fl{tO\)

г2/о(2) 22/1(2)

22/2(2)

2n/o(w„) \ 2n/l(w„)

\ 2l/d-2(wi) 22/(2(2) ••• Znfd2(Un) )

где fi(x) многочлен степени не выше d - 2, который определяются матрицей h = {hij} следующим образом fi(x) = JZjZo hij- Многочлены fc(x) являются линейно-независимыми.

Итак, перед нами стоит задача: по заданной матрице В1 найти невырожденную матрицу h, элементы u>i,L02, - - - , w„ 6 Fg = Fg U {оо} и элементы z±,Z2, - - - . zn € F,; \ {0} такие, что В = h- В - Г • D, D = diag(zi,z2,... ,zn).

Задачу будем решать в два этапа: сначала найдем элементы ш\,Ш2, - • • ,шп, а затем элементы zi, z2, - - - , zn и матрицу h.

5.1. Как определить первые три элемента cuj? Перед тем как искать элементы ш\,L02, ,шп сделаем несколько замечаний.

Пусть h, А - некоторое решение уравнения (16), т.е. />" = • /> • А. А = Г • /). и Ас, = Гс, • Dc,. Бф = diag(z(, z2,... ,zn), - некоторый обобщенный автоморфизм кода К. с порождающей матрицей В (см. 8), соответствующий дробно-линейной функции ф(х) (см. раздел 1.10). Тогда решением уравнения (16)

является также пара NА, где Ы = h - h" h" -В = В-кф.

А = Аф А, где матрица h" определяется соотношением