Построение и исследование систем защиты информации на основе кодов в проектных метриках тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Самохина, Марина Андреевна

• Самохина, Марина Андреевна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Самохина, Марина Андреевна

Список используемых сокращений.

Введение

1 Необходимые сведения о системах защиты информации и теории кодирования

1.1 Основные понятия криптографии

1.1.1 Симметричные криптосистемы.

1.1.2 Алгоритмы с открытым ключом.

1.1.3 Криптоанализ.

1.1.4 Стойкость криптосистем.

1.2 Основные понятия теории кодирования.

1.2.1 Блоковое и поточное кодирование.

1:2.2 Нормы, метрики и кодовые расстояния.

1.2.3 Линейные коды.

1.2.4 Ранговые коды.

1.2.5 Стирания.

2 Классические криптосистемы, построенные на линейных кодах

2.1 Криптосистема МакЭлиса.

2.2 Криптоанализ системы МакЭлиса.

2.3 Криптосистема Нидеррайтера.

2.4 Атака па криптосистему Нидеррайтера.

2.5 Сравнение систем МакЭлиса и Нидеррайтера.

3 Проективные метрики

3.1 Проективные метрики.

3.2 Примеры проективных метрик.

3.3 Коды в проективных метриках.

3.3.1 Коды в метрике на основе матрицы Вандермонда

3.3.2 Коды в метрике на основе матрицы Фробепиуса

3.3.3 Декодирование в метрике на основе матрицы Фробениуса.

Анализ модификаций криптосистем на линейных кодах

4.1 Модификация криптосистемы МакЭлиса.

4.1.1 Криптосистема ГПТ.

4.1.2 Криптоанализ системы ГПТ

4.1.3 Атака Гибсона.

4.1.4 Атака Овербека.

4.2 Модификации классической схемы

Нидеррайтера.

4.2.1 Криптосистема с дополнительной шумовой матрицей

4.2.2 Криптоанализ системы с дополнительной шумовой матрицей

4.2.3 Криптосистема на основе метрики Вандермонда

4.2.4 Криптоанализ системы, основанной на метрике Вандермонда.

Новая криптосистема на основе метрики, ассоциированной с матрицей Фробениуса

5.1 Структура повой криптосистемы.

5.2 Алгоритм реализации новой криптосистемы

5.2.1 Модуль инициализации.

5.2.2 Модуль шифрования.

5.2.3 Модуль расшифрования.

5.3 Моделирование криптосистемы на основе метрики Фробениуса.

5.4 Криптоанализ новой системы.

Построение системы передачи и защиты от несанкционированного доступа

6.1 Новая криптосистема в канале с шумами.

6.2 Ограничения работы криптосистемы при исправлении ошибок канала.

6.3 Сравнение с комплексом систем

6.4 Применение новой интегрированной системы для защиты передаваемых видеоизображений

6.4.1 Результаты применения алгоритмов новой криптосистемы.

6.4.2 Согласование новой системы со стандартами

6.4.3 Возможные способы увеличения быстродействия

6.4.4 Применение симметричного алгоритма

ГОСТ 28147

6.4.5 Применение симметричного алгоритма AES.

Введение диссертации (часть автореферата) на тему «Построение и исследование систем защиты информации на основе кодов в проектных метриках»

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

Для достижения поставленной цели в работе рассматриваются следующие ЗАДАЧИ.

1. Исследование и криптоанализ существующих модификаций системы Нидеррайтера.

2. Моделирование и исследование новой криптосистемы, построенной по принципу криптосистемы Нидеррайтера. • |

3. Разработка, реализация и оценка эффективности криптографических атак на предлагаемую новую криптосистему.

4. Моделирование новой криптосистемы в составе экспериментальной интегрированной системы защиты от помех и несанкционированного доступа.

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

Для решения поставленных задач в работе использовались МЕТОДЫ теории информации, дискретной математики, а также имитационного моделирования, линейной алгебры и теории алгебраического кодирования.

ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ

Научная новизна результатов, полученных в диссертации, заключается в следующем:

1. Введен класс проективных метрик, позволяющих модернизировать криптосистемы, основанные на линейных кодах.

2. Выбрана новая метрика, используемая при построении криптосистемы с открытым ключом, усиливающая криптостойкость этой системы.

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

4. Разработан алгоритм, позволяющий использовать особенности новой криптосистемы для исправления ошибок канала.

5. Получены характеристики интегрированной системы помехо- и крип-тозащиты применительно к передаче видеоизображений.

Полученные в работе результаты внедрены и использованы в рамках следующих научно-исследовательских работ:

1. Проект №3969 аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы, 2006-2008 гг.».

2. Контракт помер 32/07 от 18.05.2007, заключенный с Институтом проблем управления имени акад. A.A. Харкевича во исполнение государственного контракта номер 02.514.11.4025 от 1 мая 2007 г. на выполнение научно-исследовательских работ между Федеральным агентством по науке и инновациям и Институтом проблем управления имени акад. A.A. Харкевича.

Результаты диссертационной работы используются в учебном процессе на кафедре радиотехники МФТИ (ГУ) в рамках курса «Защита Информации».

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

Новая криптосистема в широком диапазоне параметров в рамках интегрированной системы передачи данных более эффективна по сравнению со стандартными системами. Дополнительное увеличение крипто-стойкости в бесшумном канале может быть достигнуто за счет совместного применения симметричных алгоритмов.

АПРОБАЦИЯ РАБОТЫ. Основные результаты диссертации были доложены и обсуждены на следующих конференциях и семинарах:

1. Международная конференция «International Symposium on Communication Theory and Applications» (ISTA)2005, Ambleside, Lake District, UK, July, 2005.

2. Конференция «Математика и безопасность информационных технологий» (МаБИТ-05). МГУ им. М.В. Ломоносова (2005 г., г. Москва).

3. Конференция Российской криптографической ассоциации «РусКрипто 2008» (2008 г., г. Москва).

4. Научные конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» (в 2004-2008 гг., г. Долгопрудный).

5. Научные семинары кафедры радиотехники МФТИ (в 2004-2008 гг., г. Долгопрудный).

ПУБЛИКАЦИИ. По теме работы опубликовано 11 работ, из них 4 статьи в журналах и сборниках научных статей, 7 тезисов докладов на научных конференциях. Две статьи в рецензируемых журналах, утвержденных в перечне ВАК.

НАУЧНЫЕ ПОЛОЖЕНИЯ, выносимые на защиту

1. Описание и исследование новой метрики и построение кодов в этой метрике.

2. Алгоритмы шифрования и расшифрования новой криптосистемы, построенной по принципу Нидеррайтера.

3. Криптоанализ новой криптосистемы. Выбор параметров криптосистемы.

4. Интегрированная система защиты от множественных помех и несанкционированного доступа.

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

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

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

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

Криптосистема Нидеррайтера лишена описанных выше недостатков системы МакЭлиса и также основана на линейных кодах. Несмотря на все достоинства система Нидеррайтера оказалась нестойкой и была взломана Сидельниковым и Шестаковым [16]. Криптоаналитикам удалось по открытому ключу построить матрицы, схожие по структуре с матрицами закрытого ключа за небольшое количество операций. Этого оказалось достаточно для восстановления открытого текста из шифртекста.

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

В первом параграфе главы дается определение нормы и расстояния в проективной метрике. Рассмотрены примеры проективных метрик, особое внимание уделено метрике, ассоциированной с матрицей Фробениу-совского типа.

Далее в главе дается определение кода, оптимального в проективной метрике, а также родительского кода. На основании примеров проективных метрик рассмотрены примеры кодов в метриках на основе матрицы Вандермопда и Фробепиуса. Приведено подробное описание алгоритма быстрого декодирования кода в метрике, ассоциированной с матрицей

Фробениуса.

В четвертой главе подробно описываются основные подходы к модификации кррштосистемы Нидеррайтера.

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

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

Пятая глава посвящена описанию повой криптосистемы на основе метрики, ассоциированной с матрицей Фробениуса.

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

Далее проводится криптоанализ предлагаемой новой криптосистемы. К рассмотренной криптосистеме применимы два основных вида атак: прямые и структурные атаки. Структурные атаки - это различные модификации атаки Гибсона, адаптированные к модификациям криптосистемы, и варианты атаки Сидельникова-Шестакова. При оценке трудоемкости каждой из атак необходимо учитывать размер открытого ключа.

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

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

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

Новая криптосистема использована в работе над контрактом номер 32/07 от 18.05.2007 в главе «Разработка и исследование сигнально-кодовых конструкций для передачи и защиты меняющихся изображений». В работе показано, что криптосистема может успешно применяться как часть системы с открытым ключом для передачи и защиты меняющихся изображений.

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

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

Заключение диссертации по теме «Теоретические основы информатики», Самохина, Марина Андреевна

Основные результаты, полученные в работе.

• Разработан алгоритм построения новой криптосистемы, использующий принцип Нидеррайтера и новую метрику, ассоциированную с матрицей Фробениуса. Криптосистема обеспечивает высокую скорость шифрования при высокой стойкости криптосистемы.

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

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

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

Заключение

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Самохина, Марина Андреевна, 2009 год

1. Шнайер Брюс. Прикладная криптография. М.: Триумф, 2002. 816 с. - ISBN 5-89392-055-4.

2. Чмора A.JI. Современная прикладная криптография. 2-е издание. М.: Гелиос АРВ, 2002. 256 с. - ISBN 5-85438-046-3

3. McEliece R.J. A Public-Key Cryptosystem Based on ALgebraic Coding Theory. DGN Progress Report 42-44, Jet Propulsi on Lab., Pasadena, CA, Janary-Febrary, 1978. P. 114-116.

4. Niederreiter H. Knapsack-Type Cryptosystem and Algebraic Coding Theory // Probl. Control and Inform. Theory, 1986. V. 15. - P. 19-34.

5. Габидулин Э.М. Теория кодов с максимальным ранговым расстоянием // Проблемы передачи информации. 1985. Т. XXI, вып.1. С. 3-16.

6. Габидулин Э.М., Афанасьев В.Б. Кодирование в радиоэлектронике. М.: Радио и связь, 1986.

7. Галлагер Р. Теория информации и надежная связь. США, 1968 г. Пер. с англ., под ред. М.С. Пинскера и B.C. Цыбакова, М.: Советское радио, 1974. 720 с.

8. Knudsen L.R. Block Ciphers Analysis, Design,Applications, Ph.D. dissertation, Aarhus University, November 1994.

9. Сытник Д.А., Габидулип Э.М. Ранговые коды в системе связи с ортогональным частотным уплотнением. // Электронный журнал «Исследовано в России», 155, с. 1673-1690, 2004 г., // http://zhurnal.ape.relarn.ru/articles/2004/155.pdf

10. Габидулин Э.М., Обернихин В.А. Коды в F-метрике Вандермонда и их применение // Proc. Eighth Int. Workshop on Algebraic and Combinatorial Coding Theory // Tsarskoe Selo M. 2002. - P. 124-127.

11. Gabidulin E., Ourivski A., Pavlouchkov V. On the modified Niederreiter cryptosystem // Proc. Information Theory and Networking Workshop, Metsovo, Greece, 1999. P. 50.

12. Gabidulin E.M., Simonis J. Metrics Generated by Families of Subspaces 11 IEEE Trans. Inf. Theory, 1998, V. 44, no. 5. P. 1336-1341.

13. Беззатеев С.В. Алгоритм декодирования кода Голея (24, 12, 8) // Пробл. передачи' информ., 1986. Т. 22, вып. 3, с. 109-112.

14. Сидельников В.М., Шестаков С.О. О системе шифрования, основанной па обобщенных кодах Рида-Соломона // М.: Дискретная математика. 1992. Т. 3. Вып. 3.

15. Уривский А.В. Система шифрования с открытым ключом на основе расширенных ранговых кодов // Тезисы докладов XLII научной конференции МФТИ, Часть II. Москва Долгопрудный, 1999. С.6.

16. Сидельников В'.М. Открытое шифрование на основе двоичных кодов Рида-Маллера // Дискретная математика, 1994. Т. 6, вып. 2. С. 320, 71, 95, 153.

17. Janwa Н., Moreno О. McEliece Public Key Cryptosystems Using Algebraic- Geometric Codes // Designs, Codes and Cryptography, 1996. V. 8. P. 293-307.

18. Monico C., Rosenthal J., Shokrollahi A. Using Low Density Parity Check Codes in the McEliece Cryptosystem. // Proceedings of the IEEE International Symposium on Information Theory ISIT-00, 2000. P. 215.

19. Diffie W. E., Helman M.E. New directions in Cryptography // IEEE Trans. Inform Theory, 1976. Vol. 22, N. 6. P. 644-645.

20. Gabidulin E. M. A Fast Matrix Decoding Algorithm for Rank-Error-Correcting Codes. In: Algebraic Coding // Ed. By G.Cohen, S. Litsyn, A. Lobstein, G. Zemor, LNCS 573, 1992. P. 126-133.

21. Lee R.I., Brickell E.F. An Observation of the McEliece Public Key Cryptosystem // Advances in Cryptology EUROCRYPT'88.

22. Krüh E.A. Code Based Public Key Cryptosystems. Prospective Methods for Telecommunication and Integrated Communication Systems. P. 6269, Moscow, 1992

23. Kruk E.A. Bounds for Decoding Complexity of Any Linear Block Code 11 Problem Information Transm., V. 25, N. 3. P. 103-107, 1989.

24. Gabidulin E.M. Public Key Cryptocsystem Based on Linear Codes Over Large Alphabets: Efficiency and Weakness. Codes and Chipers: Cryptology and coding IV // Ed. By PG. Farrell.- Formara Limited, Southend-on-Sea, Essex, 1995. P. 17-32.

25. Gabidulin E.M., Ourivski A. Improved GPT Public Key Cryptosystems. Proceedings of the 5th International Symposium on Communication Theory and Applications.- Ambleside, UK, 1999.- P. 232.

26. Gabidulin E.M., Ourivski A. Improved GPT Public Key Cryptosystems.- In: Coding, Communications and Broadcasting / Ed. By P. Farrell, M. Darnell, B. Honary. London: Research Studies Press, England, 2000. P. 73-102.

27. Heim,an R., Shamir A. On the Security of Cryptosystems Based on Linear Error-Correcting Codes // Applied Mathematics. Weizmann Institute of Science, Rehovot, Israel, 1987. P. 77.

28. Loidreau P., Sendrier N. Weak Keys in McEliece Public-Key Cryptosystem // IEEE Trans. Inform. Theory, 2001. V. 47, 3. P. 12071211.

29. Gibson J.K. The Security of the Gabidulin Public Key Cryptosystem. Advances in Cryptology EUROCRYPT' 96. Ed. By U.M. Maurer, LNCS 1070, 1996. P. 212-223.

30. Berger Т., Loidreau P. Niderrciter version of the GPT eryptosystem // Progress in Cryptology. 2004. INDOCRYPT.

31. Canteaut A., Chabaud F. A New Algorithm For Finding Minimum-Weight Words in a Linear Code: Application to MCEliece's Cryptosystem and to Narrow-Sense BCH Codes of Length 511 // IEEE Trans. Inform. Theory, 1998. V. 44. 1. P. 367-378.

32. McEliece R.J. A public Key Cryptosystem Based on Algebraic Coding Theory // JPL DSL Progress Report 42-44, Jan-Feb. 1978. P. 114-116.

33. Menezes A. J., Application Of Finite Fields. Boston: Kluwer Academic Publishers, 1993.

34. Loidreau P. Strengthening McEliece Cryptosystem // Advances in Cryptology-ASIACRYPT-2000. Ed. by T. Okamoto, LNCS 1976, 2000. P. 585-598.

35. Overbeck Raphael. A New Structural Attack for GPT and Variants // Progress in Cryptology Mycrypt 2005 - Springer Berlin. Heidelberg 2005, V. 3715/2005. P.50-63.

36. Самохина (Чурусова) М.А., Габидулин Э.М. Модификация криптосистемы Нидеррайтера, основанная на новой метрике // Научный вестник Московского государственного института радиотехники, электроники и автоматики, М., 2005. С. 27-29

37. Самохина М.А. Применение модификаций криптосистем Нидеррайтера в системах исправления ошибок и защиты от несанкционированного доступа // Моделирование и обработка информации. Сборник научных трудов. М., 2008. С. 127-136.

38. Самохина М.А. Криптоанализ систем, основанных на линейных кодах // Проблемы информационной безопасности. Компьютерные системы, N. 2, 2008 г. СПб., 2008. С. 94-103.

39. Gabidulin Ernst М. Attacks and counter-attacks on the GPT public key cryptosystem, Designs, Codes and Cryptography, Springer Netherlands, DOI 10.1007/sl0623-007-9160-8. Online: 30 January 2008. V. 48, N. 2. August 2008. P. 171-177.

40. Самохина M.A., Применение модификации крипто-системы Нидде-райтера для защиты информации при передаче видеоизображений. // Информационно-управляющие системы. СПб., 2009. С. 41-46.

41. Federal Information Processing Standards Publication 197 November 26, 2001 Specification for the ADVANCED' ENCRYPTION STANDARD (AES).