Содержание к диссертации
Введение
Глава 1. Анализ известных криптосистем на основе помехоустойчивых кодов. Цели и задачи исследования 10
1.1. Помехоустойчивое кодирование. Основные классы кодов 10
1.2. Известные системы шифрования на основе кодов, корректирующих ошибки 18
1.3. Актуальные направления изучения криптосистем. Цели и задачи исследования 23
Глава 2. Разработка и исследование криптосистемы на основе каскадного кодирования 27
2.1. Общая схема каскадного кодирования. Кодирование с использованием внешнего элементного и линейного кодов 27
2.2. Криптоалгоритмы на основе каскадного кода. Оценка сложности процессов шифрования и дешифрования. Гарантированно стойкие криптоалгоритмы 32
2.3. Возможные методы криптоанализа алгоритмов шифрования 40
2.4. Подход Шеннона для обеспечения секретности. Энтропия в криптосистемах 49
Глава 3. Практическая реализация симметричной системы шифрования 52
3.1. Реализация каскадной схемы кодирования в симметричной системе шифрования 52
3.1.1. Внутренний код 52
3.1.2. Внешний элементный код 54
3.2. Внесение ошибок 57
3.2.1. Модель канала связи 57
3.2.2. "Идеальная" модель 67
3.3. Декодирование помехоустойчивых кодов. Адаптивное декодирование 70
3.4. Энтропия шифрованного текста 88
3.5. Управление ключами. Критерии стойкости и сроки действия 90
3.6. Оценка быстродействия 92
3.7. Эффективность системы с учетом современных требований 95
3.8. Программная реализация криптосистемы 97
Заключение. Результаты работы 100
Список литературы
- Известные системы шифрования на основе кодов, корректирующих ошибки
- Актуальные направления изучения криптосистем. Цели и задачи исследования
- Криптоалгоритмы на основе каскадного кода. Оценка сложности процессов шифрования и дешифрования. Гарантированно стойкие криптоалгоритмы
- Декодирование помехоустойчивых кодов. Адаптивное декодирование
Введение к работе
В современных условиях развития общества роль цифровых технологий в различных отраслях неуклонно растет. Значимость информации, хранящейся на носителях, обрабатываемой приложениями или передаваемой по каналам связи для организаций и частных лиц, выходит на передний план. С другой стороны, критичность информации с точки зрения ее безопасности, секретности и потери заставляет применять те или иные методы обработки данных. Поэтому разработка, исследование и реализация систем, обеспечивающих все вышеперечисленное, представляются очень важными.
Одним из методов обеспечения безопасности или секретности является использование криптографии. Некоторые криптографические протоколы позволяют исключить возможность несанкционированного доступа к информации, передаваемой по каналам связи, заодно гарантируя ее достоверность. В ряде случаев заданную достоверность можно обеспечить при помощи помехоустойчивого кодирования, основной задачей которого является коррекция ошибок. Современные системы обработки, передачи и хранения информации нередко используют различные средства шифрования и коррекции ошибок одновременно. Повышение эффективности таких систем может быть достигнуто за счет интеграции в одном модуле кодирования как криптоалгоритмов, так и помехоустойчивых кодов. Это позволяет использовать полезные качества и устранять недостатки обоих направлений теории кодирования, а также заметно повысить быстродействие, что является особенно актуальным в связи с постоянно увеличивающимся объемом информационных потоков.
На сегодняшний день существует несколько систем шифрования, основанных на кодах, корректирующих ошибки. Так, хорошо известны системы, предложенные МакЭлисом и Нидеррайтером. За счет специфических свойств помехоустойчивых кодов возможно построение как симметричных, так и несимметричных систем. Существует ряд работ (например, В.М. Сиделышкова, И.В. Прониной и Г.П. Агибалова), позволяющих считать одни системы не криптостойкими, а другие сложными или неэффективными для практической реализации. Есть и стойкие шифры, но среди них широко известны только открытые системы, несмотря на то, что помехоустойчивые ко-
ды потенциально обладают хорошими свойствами для построения симметричных систем. Исследование научных источников по данной тематике показало, что существует большая брешь в области изучения криптосистем на основе целых классов помехоустойчивых кодов. Поэтому задачу разработки и исследования симметричной системы шифрования на основе каскадного кода можно считать актуальной, и результаты могут быть использованы в таких областях прикладной деятельности, как помехоустойчивое кодирование и защита информации.
Что касается практической (программной или аппаратной) реализации систем шифрования на основе кодов, корректирующих ошибки, то здесь вообще трудно привести какие-либо примеры, даже для систем, обладающих доказанной криптостойко-стыо. Вследствие этого программная реализация рассматриваемой в работе криптосистемы также важна, но уже с точки зрения применения таких систем на практике.
На основании всего вышесказанного можно сделать заключение об актуальности данной работы.
Целью диссертационной работы является разработка и исследование на основе кода, корректирующего ошибки, системы шифрования, обладающей следующими свойствами: стойкость по отношению к известным методам криптоанализа, эффективность ее программной реализации.
Для достижения поставленной цели решались следующие задачи исследования.
Разработать и исследовать криптоалгоритм на основе кода, корректирующего ошибки, включающий использование вероятностного шифрования, имеющий приемлемые сложности шифрования и дешифрования, а также заданную крипто-стойкость.
Разработать модели внесения ошибок для решения следующих вопросов: моделирование канала связи с целью исследования эффективности схемы помехоустойчивого кодирования, реализация вероятностного шифрования.
Разработать и исследовать алгоритмы декодирования помехоустойчивых кодов, направленные на улучшение исправляющих способностей, с целыо повышения эффективности их использования в криптосистемах и системах обеспечения целостности информации.
4. Разработать и исследовать предлагаемую систему шифрования, а также оценить ее эффективность с учетом требований к современным криптографическим системам.
Объектом исследования являются системы шифрования на основе помехоустойчивых кодов. Данное направление предполагает использование материалов следующих областей знаний: помехоустойчивое кодирование, криптография, криптоанализ, моделирование.
Предметом исследования являются симметричные системы шифрования, использующие коды, корректирующие ошибки. Рассматривается недостаточно исследованный в современной науке класс криптосистем - системы на основе каскадного кодирования. В целях повышения эффективности криптоалгоритмов в работе отдельно исследуются и совершенствуются различные составляющие процессов шифрования и дешифрования, а именно: непосредственно кодирование (в данном случае - многоключевое шифрование, использующее гаммирование, подстановку, перемежение и т.д.), процесс внесения ошибок, декодирование помехоустойчивых кодов.
Методологическую и теоретическую основу исследования составили научные труды отечественных и зарубежных авторов [1,4,5,18,23,27,32,40,41,43,56,57,58,85,86] в области тех отраслей и направлений науки, к которым относится тема диссертации. В работе используются такие методы исследования, как системный анализ, статистические методы, компьютерное моделирование и различные математические методы. Основу математических методов, главным образом, составили исследования в области теории групп и конечных полей. В настоящее время теория групп представляет собой фундамент теоретической информатики, который является основой для различных направлений: теория кодирования, криптография, теория генераторов случайных чисел, теория быстрых умножителей и т.д. В теории информации и кодирования отметим значимость работ следующих авторов: Кернер Я., Кузьмин И.В., Самсонов Б.Б., Хемминг Р.В., Чисар И., Шеннон К. и др.
Теоретическую основу исследований в области помехоустойчивого кодирования и эффективности функционирования сетей связи составили материалы, опубликованные следующими авторами: Блейхут Р., Гилберт Э.Н., Дадаев Ю.Г., Золотарев
B.B., Коржик В.И., Питерсон Р., Рид И.С., Соломон Г., Уэлдон Э., Финк Л.М., Форни Д. и многие другие.
В качестве персоналий, причастных к исследованиям систем шифрования на основе кодов, корректирующих ошибки, следует указать следующие имена: МакЭлис Р., Нидеррайтер X., Сидельников В.М. Кроме того, нельзя не отметить работы Агиба-лова Г.П., Прониной И.В., Ростовцева А.Г., Сидельникова В.М. и широко известные в международных кругах работы Андельмана Д. и Ридса Д., Бихэма Е. и Шамира А., Мацуи М. и др., посвященные криптоанализу.
В общем, методологическую и теоретическую основу исследования составила достаточно обширная информационная база. В числе информационных источников диссертации использованы: научные источники в виде данных и сведений из книг, журнальных статей, научных докладов и отчетов, материалов научных конференций, семинаров, а также результаты собственных расчетов и проведенных экспериментов.
Научная новизна работы состоит в следующем:
разработана и исследована система шифрования на основе каскадного кодирования, которая не имеет на сегодняшний день аналогов как в плане теоретических исследований, так и практической реализации;
теоретически обосновано наличие класса криптосистем, обладающих гарантированной криптостойкостью за счет оптимизации процесса внесения ошибок, а также совместного использования симметричной схемы шифрования и специально разработанного каскадного кода;
доказана эффективность использования в системах вероятностного шифрования следующих методов и алгоритмов: использование канала со стираниями, адаптивное декодирование, "идеальная" модель внесения ошибок;
разработаны новые методы и инструменты исследования систем кодирования: методы криптоанализа, каскадного кодирования в системах шифрования, декодирования помехоустойчивых кодов и др.
Практическая ценность работы состоит в следующем:
с использованием разработанных методов и алгоритмов программно реа
лизована симметричная система шифрования, использующая двухуровневое каскад-
ное кодирование, позволяющая при их применении обеспечить безопасность в системах передачи, обработки и хранения информации;
разработан и программно реализован алгоритм адаптивного декодирования итеративного кода, повышающий эффективность функционирования системы за счет высоких показателей обнаруживающей и исправляющей способностей;
разработана модель канала связи, отражающая процессы группирования ошибок в каналах связи и позволяющая производить тестирование систем передачи информации в условиях, максимально приближенных к реальным.
Материалы диссертационной работы использовались в учебном процессе на кафедре Информационной безопасности ДВГУ при чтении курса лекций и проведении практических занятий по дисциплине «Программные методы защиты информации». Программная реализация системы шифрования использована в Автоматизированной библиотечной информационной системе Зональной библиотеки ДВГУ. Данные факты отражены в виде соответствующих актов внедрения.
Результаты работы докладывались и обсуждались на следующих семинарах и конференциях.
Дальневосточная конференция студентов и аспирантов по математическому моделированию, Владивосток, 1999.
Научная конференция ИФИТ в рамках Дня науки ДВГУ, Владивосток, 2000.
Региональная конференция студентов, аспирантов и молодых ученых по физике, Владивосток, 2000-2005.
Межвузовская научно-техническая конференция "Проблемы и методы разработки и эксплуатации вооружения военной техники ВМФ", Владивосток, 2001.
Семинары кафедры информационной безопасности ДВГУ, Владивосток, 2000-2005.
Всероссийская межвузовская научно-техническая конференция, Владивосток, ТОВМИ, 2004,2005.
Диссертация состоит из введения, трех глав и заключения. В первой главе сначала рассматриваются основные классы помехоустойчивых кодов и полезная для исследования общая теория кодирования. Далее описываются
системы шифрования на основе кодов, корректирующих ошибки, исходя из характеристик которых определены актуальные направления исследования таких систем. В конце главы даны задачи диссертационной работы, отражающие основные ее этапы.
Вторая глава посвящена теоретическому исследованию возможности использования определенного рода каскадных кодов в системе шифрования. Рассматриваются симметричная и несимметричная криптосистемы. Оценивается сложность процессов шифрования и дешифрования. На основе вероятностных характеристик криптограммы вводится класс гарантированно стойких криптоалгоритмов. Рассматриваются энтропийные качества систем, а также возможные методы криптоанализа предлагаемых алгоритмов шифрования.
В третьей главе рассмотрены вопросы программной реализации криптосистемы. Во-первых, вводится система каскадного кодирования, использующая внутренний итеративный и внешний элементный коды. Рассмотрены две схемы внесения ошибок: "идеальная" и модель канала связи. Последняя использована для тестирования адаптивного декодера, принцип функционирования которого описан в одном из параграфов главы. Приводятся данные по быстродействию и энтропийным характеристикам системы. Исследуются вопросы, связанные с реализацией процесса управления ключами. Кратко рассматривается программная реализация криптосистемы.
В заключении сформулированы основные результаты и выводы всей диссертационной работы.
Известные системы шифрования на основе кодов, корректирующих ошибки
Известно несколько криптосистем, которые строятся на основе линейных кодов, исправляющих ошибки. Подобно остальным, такие криптосистемы делятся на два класса - симметричные, или использующие закрытые ключи, и несимметричные, использующие пару открытый и закрытый ключи.
Методы построения симметричных криптосистем являются наиболее очевидными. Шифрование в симметричной кодовой криптосистеме над полем Fq описывается следующим уравнением: b=aG + e, (1.9) где aeF - вектор, являющийся сообщением; beF- вектор, являющийся криптограммой; G - порождающая матрица линейного (пД)-кода (исправляющего t ошибок) размера кхп, являющаяся закрытым ключом; ее Fq"-случайный вектор, для которого выполняется условие со{ё) t.
Такие криптосистемы привлекательны простотой реализации, но не криптостойкостыо. Достаточно подробно метод криптоанализа симметричной системы шифрования, построенной в кодовой системе линейного кода над полем GF(2), изложен в [45]. Алгоритм криптоанализа, предложенный в [45] использует вероятностный алгоритм (правильное заключение выдается только с некоторой вероятностью) нахождения закрытого ключа при возможности выбора открытого текста. Оценочная вероятность нахождения некоторой строки матрицы G в этом случае составляет: Р СІР Ц-РУ4, (1.10) где р - вероятность принятия компонентой вектора ё значения 1, s = 2r + l- число имеющихся в распоряжении шифртекстов для одного и того же открытого текста, г 1, t n/2. Кроме того в [45] представлена таблица, содержащая конкретные значения Р при определенных s, t и п, из анализа которой следует вывод о достаточной эффективности предложенного метода криптоанализа.
Системы открытого шифрования на основе кодов, корректирующих ошибки, являются более сложными, чем симметричные системы, подобные описанным выше. Наиболее известными несимметричными системами в данной области являются: система МакЭлиса [85] и система Нидеррайтера [86].
Идея шифрования в системе МакЭлиса состоит в следующем. Пусть G -фиксированная порождающая матрица линейного кода с параметрами [и, , /], размера кхп. Ансамбль Aq(n,d) порождающих матриц обобщенного кода [я, , /], определим как множество всех матриц вида h-G-PD, где h - матрица из множества невырожденных кхк матриц над Fq, Р - множество всех перестановочных матриц размера яхи, D = diag(zl,z2,-,zn) - множество диагональных матриц с г, є/ Xjo}. Матрицы h, Р, D маскируют матрицу G. Таким образом, получаем множество кодов {К}, определяющееся ансамблем Aq(n,d).
Для генерации открытого и закрытого ключа абонент % производит следующие действия. Случайно и равновероятно в соответствующем множестве абонент % выбирает матрицы hx, Dx, Р% и вычисляет матрицу Gx = hxGPxDx из ансамбля Aq(n,d). Матрица Gx является открытым ключом, а матрицы hx, Dx, Рх - секретным ключом абонента %. Если а ((/-значный вектор длины к) является открытым текстом, который необходимо зашифровать и передать абоненту %, то в системе МакЭлиса необходимо сформировать вектор b=aG x+e, (1.11) где b - вектор длины п или криптограмма, а ё -случайный вектор ошибок длины п, для которого выполняется условие 0){ё) t.
Абонент х, получив вектор b , восстанавливает кодовый вектор а следующим образом. Сначала строится вектор b =bD 1P i. Затем с помощью известного алгоритма декодирования [n,k,d]q-KOjxa. находится вектор а , который удовлетворяет условию b =a G + e , где co\e ) t, по которому вычисляется вектор а в виде a = a h 1.
В системе Нидеррайтера [86], в отличие от системы МакЭлиса, рассматривается ансамбль Bq{n,d) проверочных матриц [н,, /],-кода, который определяется как множество всех матриц вида Н =h-H D-P, где Н- фиксированная проверочная матрица [и, k,d\ -кода, h - матрица из множества невырожденных п-кхп-к матриц над F , Р - множество всех перестановочных матриц размера пхп, D - множество диагональных матриц с ненулевыми на диагонали элементами. В данном случае открытым ключом абонента % является матрица Н х, выбранная случайным образом из ансамбля Bq{n,d), а секретным - матрицы hx, Dx, Рх.
Отметим, что существует матрица Gx такая, что HxGj = О .Шифрованная информация с, предназначенная абоненту % в системе Нидеррайтера представляет собой g-значный вектор длины п-к и вида с = ёН], (1.12) где ё является вектором длины п и веса, не превосходящего t, который несет конфиденциальную информацию. Абонент %, получив сообщение с, находит какой-либо вектор Ъ , который является решением уравнения хНх - с (линейное уравнение с п-к уравнениями и п неизвестными). Вектор 6 является вектором вида b =aGx+e, при некотором неизвестном а. Затем декодируется вектор bP lD x =b =аG + e , но вместо а находится вектор е = F -a G, а затем и вектор ё = ё PXDX. Системы МакЭлиса и Нидеррайтера обладают одинаковой криптостойкостыо, так как криптоанализ одной системы может быть легко трансформирован в криптоанализ другой [54].
В рассмотренных системах конечные криптограммы представляются для криптоанализа как тексты, кодированные при помощи кодов общего положения -кодов с отсутствием в проверочной матрице или в самом коде какой-либо структуры. Криптостойкость таких систем определяется сложностью декодирования.
Актуальные направления изучения криптосистем. Цели и задачи исследования
Вывод, который можно сделать исходя из материала, изложенного в п. 1.1 и п. 1.2, состоит в том, что далеко не весь спектр помехоустойчивых кодов рассматривается как основа для построения криптосистем. Большинство работ посвящено рассмотрению конкретного класса линейных блочных кодов. Совершенно не рассматривается потенциал таких классов кодовых структур, как, например, алгебро-геометрические, сверточные и каскадные коды. В данном контексте считается актуальным построение и анализ систем шифрования подобного рода, не рассмотренных в научной литературе и не реализованных на практике. Идея построения стойкой системы шифрования на основе каскадного кодирования является одной из основных в данной работе. При этом имеет смысл рассмотреть как симметричную, так и несимметричную системы, так как способы их построения довольно схожи.
Как известно [88], кодовые криптосистемы на основе корректирующих кодов имеют большую скорость шифрования по сравнению с подобными системами, например, с системой RSA. Сложность шифрования для симметричной системы и системы МакЭлиса составляет о(кп), а для системы Нидеррайтера о((п-к)хп), что меньше, чем 0[п2) - сложность операций по открытому ключу в системе RSA, где п -длина ключа в соответствующей системе. Основанием этому служит неравенство \ к п, однако, если учесть, что в среднем к п/2, то преимущество в скорости (особенно при больших п) не столь существенно. Что касается сложности декодирования, то здесь будет полезно сформулировать следующее утверждение.
Утверждение 2. Любой линейный код К с параметрами [n,k,d]q, d nll, имеет алгоритм декодирования в пределах его кодового расстояния, сложность которого не выше 0\ \\n\iqk,п . С п)), где t = (d-1)/2.
Как правило, к и t пропорциональны п, а следовательно данное утверждение оценивает сверху сложность алгоритма декодирования как экспоненциальную. Однако, существует ряд работ [18,36,50], указывающих на существование алгоритмов, время работы которых не превосходит 0[п2) и менее, что также не показывает заметные преимущества перед тем же RSA, для которого количество операций по закрытому ключу составляет 0\пъ). Как результат, можно считать, что для повышения эффективности криптосистем и самих корректирующих кодов, одним из главных направлений является разработка алгоритмов кодирования и декодирования. Одна из задач данной работы - разработка и исследование адаптивного алгоритма декодирования линейного кода.
Практически все рассмотренные системы шифрования на основе помехоустойчивых кодов имеют ряд недостатков. Во-первых, это низкая скорость передачи, по крайней мере, она всегда меньше 1 (обычно меньше 1/2). Скорость для определенного кода определяется соотношением к/п. Отметим, что в тех случаях, когда к/п - малое число, то скорость передачи системы Нидерайтера всегда выше по сравнению с системой МакЭлиса. В общем случае, при к t скорость выше в системе МакЭлиса, при k t - в системе Нидеррайтера. Поэтому при реализации криптосистем подобного рода часто ставится задача об использовании сжатия.
Во-вторых, ключ в рассматриваемых криптосистемах имеет размеры примерно в к раз (для симметричных систем и системы МакЭлиса) или п - к раз больший, чем у упомянутой системы RSA, не говоря уже о системах открытого шифрования, основанных на проблеме дискретного логарифма и эллиптических кривых или систем симметричного шифрования ГОСТ 28147-89, DES и т.п. В данной ситуации (при использовании базовых криптосистем) уменьшение п будет неизбежно приводить к снижению криптостойкости алгоритма. Для кодов Рида-Соломона данный факт подтверждает зависимость числа различных обобщенных кодов А данного рода от параметров [n,k,d\, задаваемую выражением [54]: \{n,d) ,_, jfr"1)" ,_, (1.13) (q -l)(q -q)..(q -q ) К примеру, при n 100, d n/2, q 2 это число больше 1077. С уменьшением п уменьшается и Aq(n,d) или множество возможных ключей, что непосредственно ведет к снижению криптостойкости. Вместе с тем, при росте п значительно увеличивается и сложность процедуры декодирования, о чем уже говорилось выше. Таким образом, оптимальным было бы нахождение таких параметров кода [n,k,d\, которые при минимальной сложности декодирования обеспечивали бы достаточную криптостойкость.
Анализ работ в области систем шифрования на основе кодов, корректирующих ошибки, показывает, что в них упущен один из основных моментов, а именно процесс внесения ошибок или генерация вектора ё. Хотя именно он является одной из отличительных особенностей таких криптосистем, на которых базируется идея криптостойкости. Эта идея заключается в том, что криптоаналитику порождающая или проверочная матрицы представляются как матрицы общего положения. Поэтому для нахождения решения уравнения (1.11) или (1.12) в соответствии с Утверждением 1 необходимо проделать экспоненциальное от п число операций. Вследствие этого одним из важных вопросов в данной области можно считать оптимизацию процесса внесения ошибок с целью повышения криптостойкости.
Идея совершенствования процесса внесения "шума" в шифрованное сообщение определяет следующее направление в работе: описание спектра кодов, которые будут обладать доказанной криптостойкостыо вследствие использования модели внесения ошибок, действующей на грани исправляющей способности корректирующего кода. В качестве такой модели можно использовать две структуры: идеальную модель и модель канала связи. В случае идеальной модели рассматривается случайный и равновероятный вектор е с весом о)(ё) = s, где s - максимальная комбинация ошибок для канала со стираниями и трансформациями с учетом заданной исправляющей способности декодера. Модель канала связи применительно к шифрованию рассматривается при условии внесения максимального числа ошибок, исправляемых декодером. Специфический случайный характер внесения ошибок при использовании модели канала связи, как предполагается, может послужить фактором, усложняющим криптоатаку.
Из задачи построения криптосистемы естественно вытекает вопрос о возможности создания эффективных методов ее криптоанализа. Предполагается рассмотреть возможные методы криптоанализа в случае использования каскадных кодов определенного класса.
Криптоалгоритмы на основе каскадного кода. Оценка сложности процессов шифрования и дешифрования. Гарантированно стойкие криптоалгоритмы
. Будем считать, что открытый текст Т, который необходимо зашифровать, является некоторой последовательностью значений из элементов конечного поля Fq. В качестве решения первой задачи диссертационной работы предлагается базовый алгоритм шифрования для построения криптосистемы на основе каскадного кодирования. Данный алгоритм можно представить в виде следующей последовательности действий.
1. Линейное кодирование. Текст Т кодируется линейным блочным кодом с параметрами [n,,flf] : b=aG, где a ={ava2,...,ak) - блок текста Т размером к, а,, є Fq,ae Fq"; b ={bx,b2,...,bn) - кодовое слово (иД)-кода или блок текста 77, bt є Fq, be Fq;G-порождающая матрица (n,k)-кодаразмера kxn.
2. Гаммирование текста 77: T2(i) = Tl(i) + U, где U = (ui,u1,...,uv) - гамма размером v, UjEFq; Т1{ї) и 72(0 - блоки соответствующих текстов длиной v. Сложение Uj с элементами текста ТІ производится по модулю q.
3. Перемежение текста 72 с помощью матрицы А размера NxM . Здесь каждый і-й символ из текста 72 переходит на у-ю позицию текста ТЗ в соответствии с выражением (2.2).
4. Внешнее кодирование. Значения с,- є Fq текста ТЗ отображаются во внешний элементный код X = (x(0),x(l),...,x(q-l)), где х(]) = (х[,х 2,...,х т) - булев вектор с т компонентами, т.е. х) є GF(2), x(j) є GF(2m), причем x(i) x(j) при і Ф j. Таким образом, получается текст Т4, состоящий из значений х(с,).
5. Гаммирование текста Т4 структурой Y = {yl,y2,...,yl) размером m-l бит, у І eGF(2m). Текст T5 находится сложением по модулю 2 компонент т-битных векторов последовательностей Т4 и Y: x(ci) + yim0 i(l_l), где (с,.) - /-е слово из Т4.
6. Внесение ошибок. Каждый /-й m-битный блок текста Т5 преобразуется в аналогичных размеров блок шифртекста Т6 следующим образом: zi=x(ci) + yimodil,l)+e, где е - секретный булев вектор ошибок длиной т, случайно и равновероятно выбранный в соответствии исправляющими способностями декодера.
Текст Т6 является шифртекстом для открытого текста Т, шифрованного посредством алгоритма, описанного выше, с использованием ключевых параметров K = {U,N,M,XJ).
Процесс дешифрования тривиален и представляет преобразование текста Т6 в соответствии с этапами №1-5 криптоалгоритма в обратном порядке, при наличии ключа К и использовании соответствующих декодеров (внешнего и внутреннего). При декодировании внешнего кода (этап №4) возникают стирания и трансформации, которые потом корректируются декодером линейного кода (этап №1).
Процесс внесения ошибок (этап №6) задан не совсем определенно, вследствие специфики используемого метода каскадного кодирования. Отметим, что количественные параметры ошибок, поступающих на декодер внутреннего кода, не должны превышать значений, задаваемых соотношениями (1.3),(1.4),(1.5). Более подробно вопросы, касающиеся процесса внесения ошибок и его оптимизации, рассмотрены в п.2.4 и п.3.2 настоящей работы.
Криптостойкость предложенного алгоритма шифрования обусловлена утверждением 1 (п. 1.2). Гаммировапие, перемежеиие и внесение ошибок позволяют изменить алгебраическую структуру кода так, что его декодирование не может быть осуществлено за полиномиальное время. Мощность множества ключей {К} для базового криптоалгоритма равна ( ).( , -N M ), (2.3) где qv - количество возможных значений гаммы U, 2ml - количество возможных значений гаммы Y, Bq(m,d) - число различных кодов X с параметрами q, m, d\ Nm„ .Nmi„ Mm,„ Л/тіп - максимальные и минимальные значения NnM соответственно. ІШЛ Пип ГПал ПИП
При условии, что критерием отбора x(j), ./ = 0,1,..., -1, является только x(i) x(j) при ІФ j, получаем, что Bq(m,d) = B9(m) = f[{2m-i). (2.4) /=0
Сложность генерации ключевых параметров {U,N,M,Y} составляет 0(п), где п - длина {U,N,M,Y}. Сложность генерации X не выше 0(q). Последнее обусловлено выполнением процесса нахождения q векторов из GF(2m) при генерации X. Если же необходимо сравнение векторов хе X между собой, с целью определения удовлетворяет код X критериям отбора (кодовое расстояние d) или нет, то сложность генерации Хне выше 0\ J}/(2m -/) . Размер ключа L в битах информации определяется соотношением L = vlog2 + log2(iVmax-iV J + log M -Mmin) + m(/ + ) или L = m(l + q) + \og2qv(NmM -Л ДМ -Мш). (2.5)
Сложность шифрования и дешифрования в зависимости от длины ключа составляет 0(1), т.е. постоянна. Сложность шифрования определяется только сложностью внутреннего кодирования, которая для линейного (п, к) -кода составляет 0(кхп). Что касается процесса дешифрования, верхняя оценка его сложности может быть задана утверждением 2 (п. 1.3) для алгоритмов декодирования линейных кодов. В тоже время, обыкновенный алгоритм синдромного декодирования имеет сложность 0((п-к)хп).
Предложенный алгоритм шифрования, в отличие от большого числа известных и используемых в настоящее время симметричных блочных шифров (DES, ГОСТ 28147-89 и др.), не использует для преобразования блоков открытого текста сеть Фейстеля [1]. В этом качестве выступают обратимые, зависящие от ключа, преобразования. В ходе шифрования применяется всего один цикл, вместо нескольких итераций над каждой половиной блока текста (сеть Фейстеля), что позволяет существенно повысить скорость работы алгоритма с условием удовлетворения требованиям стойкости.
Декодирование помехоустойчивых кодов. Адаптивное декодирование
Анализируя таблицу 3.6., нетрудно заметить значительное превосходство в быстродействии каскадной схемы шифрования. А именно, количество процессорных циклов меньше: в 10 + 30 раз по сравнению с DES и его модификациями, в 3 + 6 раз по сравнению с AES (и это без учета алгоритма обработки ключа) и в среднем в 1,5 раза по сравнению с ГОСТ 28147-89. Отчасти это связано с тем, что все эти алгоритмы используют для преобразования либо сеть Фейстеля, либо просто большое количество итераций с обратимыми преобразованиями. В то время как система шифрования на основе каскадного кодирования использует всего один раунд преобразований над блоком информации, состоящий из нескольких элементарных схем кодирования, не требующих большого количества процессорного времени.
Быстродействие предложенной схемы шифрования (как и самого каскадного кода) можно значительно повысить, используя таблицу декодирования вместо адаптивного декодера. Эта таблица должна находиться в ОП и содержать искаженные итеративные группы и соответствующие им правильно декодированные информационные группы. Исследования показали, что размеры данной таблицы столь велики (десятки гигабайт), что при современных вычислительных ресурсах эффективность применения такого метода повышения быстродействия является сомнительной. Несмотря на это, вышеприведенные оценки быстродействия каскадного алгоритма позволяют говорить о возможности реализации системы шифрования, значительно превосходящей в скорости современные системы.
Проведем оценку эффективности реализуемого метода шифрования на основе каскадного кода с учетом требований к современным криптографическим системам. Для современных криптографических систем защиты информации сформулированы следующие общепринятые требования:
1. Знание алгоритма шифрования не должно сниэ/сать криптостойкостъ шифра. В данной работе оценки криптостойкости производятся с учетом "открытости" алгоритма шифрования. Основными способами повышения эффективности и криптостойкости являются применение новых решений в области шифрования, заимствованные из теории помехоустойчивого кодирования.
2. Зашифрованное сообщение должно поддаваться чтению только при наличии ключа. Реализованная система шифрования использует систему симметричных ключей, преобразующих открытый текст в соответствии с алгоритмом, исключающим бесключевое чтение шифрованного текста.
3. Шифр должен быть стойким даже в случае, если нарушителю известно достаточно большое количество исходных данных и соответствующих им зашифрованных данных. Во-первых, используемый криптоалгоритм, даже в базовой конфигурации, требует для вычисления ключевой информации достаточно большое количество пар открытый-шифрованный текст. Нижние оценки этого количества определены в п.2.3. Во-вторых, внесение ошибок в процессе шифрования значительно улучшает эти оценки, т.к. в этом случае применяются вероятностные методы криптоанализа, дающие верный результат лишь с некоторой вероятностью.
4. Число операций, необходимых для расшифровывания информации путем перебора всевозможных ключей, должно иметь строгую нижнюю оценку и выходить за пределы возможностей современных компьютеров. Подробно данный аспект рассмотрен в п.3.5, где отмечено соответствие ключевых параметров системы шифрования современным требованиям.
5. Незначительное изменение ключа должно приводить к существенному изменению вида зашифрованного сообщения даже при использовании одного и того оке ключа. В системах шифрования на основе кодов, корректирующих ошибки, данное требование обеспечивается за счет внесения случайных ошибок.
Шифрованный текст принимает каждый раз различный вид даже при шифровании одного и того же сообщения одним ключом.
6. Не должно быть простых и легко устанавливаемых зависимостей между ключами, последовательно используемыми в процессе шифрования. Каждая компонента ключа K = {G,U,N,M,X,Y) генерируется отдельно и независимо от других компонент.
7. Любой ключ из множества возможных должен обеспечивать надежную защиту информации. На данный момент не существует причин, позволяющих утверждать, что рассматриваемая криптосистема не удовлетворяет этому требованию. Единственно, что следует отметить, - это наличие так называемых "псевдоключей" для последовательности {U,X,Y}. Данный факт говорит только об уменьшении количества возможных ключей, но не о наличии ненадежных ключей.
На основании вышесказанного можно заключить, что построенная симметричная система шифрования на основе каскадного кодирования удовлетворяет всем требованиям, предъявляемым к современным криптосистемам. Основными преимуществами рассматриваемого криптоалгоритма являются: вероятностное шифрование (шифртексты различны даже для одинаковых открытых текстов, шифрованных на одном ключе), простота реализации (используются блоки помехоустойчивого кодирования, перемежения, гаммирования и ГСЧ), скорость работы (п.3.6). Наиболее эффективно система может быть использована в области телекоммуникационных систем, однако, нельзя исключать и системы хранения информации.
