|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[3] 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" определяется соотношением |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||