Система открытого шифрования Маклисп.
Отметим, что 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. Поэтому найдется дробно-линейная функция ір(х) такая, что
| Ь! ¦ В ¦ Аш ¦ А |
|
элементы диагональной матрицы 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.
