Развитие информационных технологий и средств обработки, хранения и передачи информации привело к необходимости защищать данные на всех этапах информационного обмена. Для обеспечения защиты информации необходимо обеспечить ее конфиденциальность, целостность и доступность.
Защиту данных можно осуществлять правовыми и организационно-техническими методами. Организационно-технические методы представлены физическим, аппаратным, программным и математическим (криптографическим) уровнями. Криптографический уровень защиты информации является своего рода «последней линией обороны», т.к. позволяет защищать информацию даже после получения к ней доступа злоумышленником. При этом обеспечивается определенный уровень криптографической стойкости, т. е. способности криптографического алгоритма противостоять возможным атакам на него. Стойким считается алгоритм, для успешной атаки на который злоумышленнику необходимы недостижимые вычислительные ресурсы, недостижимый объём перехваченных открытых и зашифрованных сообщений или же такое время раскрытия, что по его истечению защищенная информация будет уже не актуальна. Стойкость криптографических алгоритмов доказывается в условиях определенных математических моделей безопасности.
Известны различные виды моделей безопасности, классифицирующиеся по ряду критериев, например, по защищаемому объекту (модели безопасности доступа). Под моделями безопасности криптографических примитивов понимаются формализованные модели поведения вероятного злоумышленника при попытке нарушения стойкости криптографических алгоритмов.
Появление в 1976 г. асимметричной криптографии (У. Диффи и М. Хеллман) значительно расширило возможности криптографии и положило начало разработке большого количества криптографических алгоритмов. С математической точки зрения стойкость асимметричных криптоалгоритмов основана на сложности решения известных математических задач, таких как, например, задач факторизации целого числа и дискретного логарифмирования в конечном поле. Алгоритмы решения данных задач имеют субэкспоненциальную сложность, поэтому при определенных размерах ключей их решение полагается невозможным на современном этапе развития вычислительной техники.
Примерами асимметричных алгоритмов являются стандарт США на цифровую подпись DSS (Digital Signature Standard) и российские стандарты на ЭЦП ГОСТ Р34.10 94 и ГОСТ Р34.10 2001.
В 90-е гг. XX в. получили распространение асимметричные криптоалгоритмы на основе эллиптических кривых. Данные алгоритмы строятся с помощью преобразования семейства алгоритмов Эль-Гамаля, а их стойкость основана на сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой. Известно, что задача дискретного логарифмирования в конечном поле не сложнее задачи дискретного логарифмирования в группе точек эллиптической кривой, заданной над конечным полем.
В 2000 г. А. Жу был предложен первый билинейный алгоритмасимметричный криптоалгоритм ключевого соглашения на основе билинейных спариваний в группе точек эллиптической кривой. Стойкость билинейных криптоалгоритмов основана на сложности решения билинейных проблем Диффи-Хеллмана. В настоящее время не существует эффективных математических алгоритмов решения данных проблем. С помощью билинейного спаривания также были построены эффективные алгоритмы на основе идентификационных данныхкриптоалгоритмы, в которых открытый ключ абонента получается явным образом из его идентификатора. Криптоалгоритмы на основе идентификационных данных позволяют упростить инфраструктуру открытых ключей.
К настоящему времени разработан ряд билинейных криптографических алгоритмов, таких как: алгоритм шифрования на основе идентификационных данных (Д. Боне, М. Франклин), алгоритм избирательного шифрования (Д. Боне, Г. Крещенцо, Р. Островски, Г. Персиано), алгоритм подписи (Д. Боне, Б. Линн, X. Шахем), алгоритм слепой подписи (А. Болдырева), алгоритм мультиподписи (А. Болдырева), алгоритм короткой подписи (Ф. Занг, Р. Сафави-Наини, В. Сусило), алгоритм распределения ключа (Р. Сакаи, К. Огиши, М. Казахара), алгоритмы шифроподписи на основе идентификационных данных (Д. Мэлони-Ли и Б. Либерт, Д. Квисквотер). Данные алгоритмы обеспечивают безопасность информации при её обмене несколькими абонентами.
В случае группового обмена информацией билинейные алгоритмы могут быть использованы при условии разбиения группы абонентов на подгруппы из нескольких абонентов и последовательного применения данных алгоритмов к каждой подгруппе. Данный метод приводит к повышению вычислительной и связной сложности обеспечения безопасности информации для всей группы.
Для решения задачи обеспечения безопасного группового информационного обмена в 2002 г. Д. Боне и А. Сильверберг были предложены первые мультилинейные алгоритмы — алгоритм ключевого соглашения и алгоритм широковещательного шифрования. В данных алгоритмах было использовано мультилинейное отображение, являющееся обобщением билинейного спаривания до случая п аргументов. Также в 2002 г. Х. К. Ли, Х. С. Ли, Я. Р. Ли было предложено семейство мультилинейных алгоритмов ключевого соглашения. Стойкость данных алгоритмов основана на сложности решения мультилинейных проблем Диффи-Хеллмана.
Актуальность темы
Предложенные мультилинейные алгоритмы имеют ряд недостатков, связанных со стойкостью, а именно: для алгоритма широковещательного шифрования Д. Боне и А. Сильверберг не показана стойкость к адаптивным атакам с выбором шифротекста, для алгоритмов ключевого соглашения Х. К. Ли, Х. С. Ли, Я. Р. Ли не предусмотрена возможность выявления злоумышленника. Также, для ряда криптографических примитивов «(таких, как шифрование на основе идентификационных данных, избирательное шифрование и шифроподпись) до настоящего времени не было предложено групповых (многосторонних) алгоритмов, что усложняет использование данных примитивов для групп абонентов.
Поэтому в настоящее время возникла трудность построения многосторонних алгоритмов, являющихся более эффективными для группы абонентов, чем многократное применение алгоритмов для подгрупп из нескольких абонентов. При этом стойкость данных алгоритмов не должна быть ниже, чем стойкость схемы многократного применения алгоритмов для подгрупп из нескольких абонентов.
Таким образом, тема проводимого в данной работе исследования является актуальной. Из актуальности темы работы следует ее цель.
Цель работы. Разработка семейства многосторонних мультилинейных алгоритмов, являющихся доказуемо стойкими в условиях различных моделей безопасности.
Решаемые задачи. Для достижения поставленной цели решались следующие задачи:
1. построение математических моделей безопасности многосторонних криптографических примитивов;
2. разработка многосторонних алгоритмов широковещательного шифрования, избирательного шифрования, подписи, слепой подписи, распределения ключа, шифроподписи и ключевого соглашения;
3. доказательство стойкости и оценка сложности разработанных многосторонних алгоритмов.
Научная новизна полученных результатов заключается в следующем.
1. Разработаны более сильные математические модели безопасности для многосторонних криптографических примитивов;
2. Предложены многосторонние мультилинейные алгоритмы, позволяющие использовать билинейные криптографические примитивы в случае большого количества абонентов;
3. Доказаны стойкость к адаптивной атаке с выбранным открытым текстом базового алгоритма широковещательного шифрования на основе идентификационных данных, стойкость к адаптивной атаке с выбранным шифротекстом полного алгоритма широковещательного шифрования на основе идентификационных данных и стойкость алгоритма ключевого соглашения на основе идентификационных данных с выявлением злоумышленника в расширенной модели безопасности ключевого соглашения;
4. Разработаны математические проблемы, обеспечивающие приемлемый уровень сложности для обеспечения стойкости многосторонних алгоритмов.
Основными результатами данной работы являются следующие результаты.
1. Построено семейство многосторонних алгоритмов с применением математического аппарата мультилинейных отображений, а именно, алгоритмы широковещательного шифрования на основе идентификационных данных, избирательного шифрования, подписи, слепой подписи, шифроподписи, ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника.
2. Разработаны математические модели безопасности и математические проблемы, на сложности решения которых может быть основана стойкость многосторонних алгоритмов будущего.
3. Доказано, что алгоритм МКШОИД обладает стойкостью к адаптивным атакам с выбором шифротекста при предположении сложности проблемы 1УГОН. Для обеспечения безопасного группового обмена информацией алгоритм МКШОИД является вычислительно и связно более эффективным, чем многократное применение билинейного алгоритма Боне и Франклина.
4. Предложен алгоритм ключевого соглашения на основе идентификационных данных. Преимуществом данного алгоритма является использование идентификационных данных абонентов и возможность выявления злоумышленника во время выполнения алгоритма. Показана стойкость предложенного алгоритма ключевого соглашения в расширенной модели безопасности ключевого соглашения. Проведена программная реализация алгоритма для случая 3-х абонентов.
В данной работе также были получены дополнительные результаты.
1. Проведена оценка вычислительной эффективности всех предложенных алгоритмов.
2. Алгоритм подписи построен в модели кичного дерева.
3. Исследована возможность использования мультилинейных алгоритмов в случае невозможности построения пмультилинейных отображений для любых значений п.
Научная апробация. Полученные результаты докладывались на региональной научно-технической конференции «Знание, творчество, профессионализм» (Владивосток, 2005), 3-й и 4-й Международных научно-практических конференциях «Интеллектуальные технологии в образовании, экономике и управлении» (Воронеж, 2006;2007), Региональной конференции студентов, аспирантов и молодых ученых по физике (Владивосток, 2006), конференции «Информационная безопасность в открытом образовании» (Магнитогорск, 2007), 48-й, 50-й и 51-й Всероссийских научных конференциях ТОВМИ (Владивосток, 2005, 2007;2008), Российской школесеминаре «Синтаксис и семантика логических систем» (Владивосток, 2008), Всероссийских конференциях студентов, аспирантов и молодых ученых по физике ДВГУ (Владивосток, 2007, 2009), XXXIII Дальневосточной математической школе-семинаре имени академика Е. В. Золотова (Владивосток, 2008), Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых (Томск, 2009), семинаре кафедры информационной безопасности ДВГУ (Владивосток, 2009), семинаре Института автоматики и процессов управления ДВО РАН (Владивосток, 2009).
Публикации. По материалам диссертации опубликовано 18 работ, в том числе 2 в журналах, рекомендуемых ВАК.
1. Гончаров С. М., Косолапов Д. О., Харин Е. А. Выработка уникальных псевдослучайных последовательностей на основе клавиатурного почерка // Информационная безопасность в открытом образовании, под ред. Е. В. Зеркиной, Г. Н. Чусавитиной. — Магнитогорск: МаГУ, 2007. — С. 65−66.
2. Гончаров С. М., Косолапов Д. О., Харин Е. А. Мультилинейная схема шифрования Боне-Франклина на основе идентификационных данных // Информационная безопасность в открытом образовании, под ред. Е. В. Зеркиной, Г. Н. Чусавитиной. — Магнитогорск: МаГУ, 2007. — С. 67−69.
3. Гончаров С. М., Косолапов Д. О. Использование мультилинейных отображений для построения безопасных систем группового обмена данными // Российская школа-семинар «Синтаксис и семантика логических систем». Тезисы докладов. — Владивосток: Изд-во Дальнаука, 2008. — С. 13−16.
4. Корнюшин П. Н., Гончаров С. М., Косолапов Д. О. Схема короткой групповой подписи в модели k-ичного дерева // Материалы 51-й всероссийской научной конференции. — Владивосток: ТОВМИ, 2008. — С. 79−81.
5. Косолапов Д. О., Гончаров С. М., Корнюшин П. Н. Хеш-цепи в многосторонних платежах // Материалы XLVIII Всероссийской межвузовской научно-технической конференции. — Владивосток: ТОВМИ, 2005. — С. 75−76.
6. Косолапов Д. О. Многосторонние микроплатежи и ведение счета клиента в мобильной сети // Сборник докладов региональной научно-технической конференции «Знание, творчество, профессионализм». — Владивосток: МГУ им. адм. Г. И. Невельского, 2005. — С. 418−422.
7. Косолапов Д. О., Гончаров С. М., Корнюшнн П. Н. Криптосистемы на основе идентификационных данных для обеспечения безопасности информационного обмена в мобильной телефонии // Материалы 3-й Международной Научно-практической конференции «Интеллектуальные технологии в образовании, экономике и управлении». — Воронеж: ВИЭСУ, 2006. — С. 271−273.
8. Косолапов Д. О., Гончаров С. М. Оптимизация билинейного Тейт-спаривания в группе точек эллиптической кривой на базе алгоритма Миллера // Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. -Владивосток: ДВГУ, 2006. — С. 168−169.
9. Косолапов Д. О. Возможности построения криптосистем на основе мультилинейных форм // Всероссийская конференция студентов, аспирантов и молодых ученых по физике. 14−16 ноября 2007. Материалы конференции. -Владивосток: ДВГУ, 2007. — С. 120−121.
10. Косолапов Д. О., Гончаров С. М., Корнюшин П. Н. Мультилинейные отображения и возможности построения новых криптосистем // Материалы 50-й Всероссийской научной конференции. Т. 2. — Владивосток: ТОВМИ, 2007. — С. 39−40.
11. Косолапов Д. О., Корнюшин П. Н. Обобщение билинейных криптосистем шифрования и подписи // Материалы IV международной научно-практической конференции «Интеллектуальные технологии в образовании, экономике и управлении 2007». — Воронеж: ВИЭСУ, 2007. — С. 285−288.
12. Косолапов Д. О., Гончаров С. М. Групповая мультилинейная схема электронно-цифровой подписи // XXXIII Дальневосточная математическая школа-семинар имени академика Е. В. Золотова: тезисы докладов. — Владивосток: Изд-во Дальнаука, 2008. — С. 18.
13. Косолапов Д. О., Харин Е. А., Гончаров С. М., Корнюшин П. Н. Генерация ключевых последовательностей на основе рисунка радужной оболочки глаза // Проблемы правовой и технической защиты информации: сб. научных статей. -Барнаул: Изд-во Алт. Ун-та, 2008. — С. 145−150.
14. Косолапов Д. О., Харин Е. А., Гончаров С. М., Корнюшин П. Н. Использование рисунка радужной оболочки глаза для генерации ключевой пары // Доклады Томского государственного университета систем управления и радиоэлектроники, 2(18), часть 1. — Томск: Изд-во ТГУСУР, 2008. — С. 30−31.
15. Косолапов Д. О., Харин Е. А., Гончаров С. М., Корнюшин П. Н. Мультилинейные протоколы в асимметричной криптографии // Доклады Томского государственного университета систем управления и радиоэлектроники, 2(18), часть 1. — Томск: Изд-во ТГУСУР, 2008. — С. 51−53.
16. Косолапов Д. О., Харин Е. А., Корнюшин П. Н. Мультилинейные криптосистемы шифрования, подписи и распределения ключей // Проблемы правовой и технической защиты информации: сб. научных статей. — Барнаул: Изд-во Алт. Унта, 2008. — С. 116−120.
17. Косолапов Д. О., Гончаров С. М., Корнюшин П. Н. Протокол ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника // Всероссийская конференция студентов, аспирантов и молодых ученых по физике. 27−29 апреля 2009. Материалы конференции. — Владивосток: ДВГУ, 2009.-С. 109−111.
18. Косолапов Д. О. Протокол ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника // Материалы докладов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых 12−15 мая 2009 г, Тематический выпуск «Системная интеграция и безопасность», ч. 3. — Томск: В-Спектр, 2009. — С. 277−283.
Личный вклад автора. Все основные результаты, представленные в диссертационной работе, получены автором самостоятельно. Работы [6, 9, 18] выполнены автором самостоятельно. В работах [2−5, 7, 8, 10−12, 15−17] автор участвовал в постановке проблемы, провел необходимые теоретические исследования, связанные с построением математических моделей безопасности и разработкой мультилинейных алгоритмов, и соответствующие вычисления, связанные с доказательством стойкости предложенных алгоритмов для решения задачи обеспечения безопасности группового информационного обмена. В работах [1, 13, 14] автор сформулировал возможность использования в многосторонних алгоритмах ключевых последовательностей на основе клавиатурного почерка и рисунка радужной оболочки глаза.
Теоретическая и практическая значимость работы. В работе предложены математические модели безопасности широковещательного шифрования при адаптивной атаке с выбором шифротекста и открытого текста, расширенная модель безопасности ключевого соглашения, многосторонние математические проблемы, проведено строгое доказательство стойкости предложенных криптографических алгоритмов в условиях разработанных математических моделей безопасности.
Использование мультилинейных отображений позволит снизить связную и вычислительную сложность многосторонних алгоритмов, усилив их стойкость. Предложенные мультилинейные алгоритмы могут быть использованы при построении многосторонних криптосистем для обеспечения конфиденциальности и аутентичности информационного обмена группы абонентов.
Методы исследования. В диссертации применяются методы современной алгебры конечных полей, теория вероятностей, теория сложности алгоритмов, математические модели безопасности криптографических примитивов.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 67 наименований. Содержание работы изложено на 138 страницах текста. Работа содержит 2 таблицы и 2 рисунка.
Заключение
.
В связи со значительным расширением масштабов информационного обмена актуальной является разработка стойких и эффективных многосторонних алгоритмов, т. е. алгоритмов, осуществляющих криптографическое преобразование для группы абонентов. Предложенное Боне и Сильвербсрг обобщение билинейного спариваниямультилинейное отображение, позволяет упростить большинство многосторонних алгоритмов и построить некоторые из них на основе соответствующих билинейных алгоритмов.
Данные мультилинейные алгоритмы явились предметом исследования в данной работе.
Перечислим основные результаты диссертации:
1. Построено семейство многосторонних алгоритмов с применением математического аппарата мультилинейных отображений, а именно, алгоритмы широковещательного шифрования на основе идентификационных данных, избирательного шифрования, подписи, слепой подписи, шифроподписи, ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника.
2. Разработаны математические модели безопасности и математические проблемы, на сложности решения которых может быть основана стойкость многосторонних алгоритмов будущего.
3. Доказано, что алгоритм МКШОИД обладает стойкостью к адаптивным атакам с выбором шифротекста при предположении сложности проблемы МБН. Для обеспечения безопасного группового обмена информацией алгоритм МКШОИД является вычислительно и связно более эффективным, чем многократное применение билинейного алгоритма Боне и Франклина.
4. Предложен алгоритм ключевого соглашения на основе идентификационных данных. Преимуществом данного алгоритма является использование идентификационных данных абонентов и возможность выявления злоумышленника во время выполнения алгоритма. Показана стойкость предложенного алгоритма ключевого соглашения в расширенной модели безопасности ключевого соглашения. Проведена программная реализация алгоритма для случая 3-х абонентов.
Перечислим дополнительные результаты диссертации.
1. Проведена оценка вычислительной эффективности всех предложенных алгоритмов.
2. Проведен анализ возможности использования мультилинейных алгоритмов с учетом результата Боне и Сильверберг о построении мультилинейных отображений высоких порядков мультилинейности.
3. Мультилинейный алгоритм подписи построен в модели /с-ичного дерева.
Все результаты, представленные в диссертационной работе, получены автором самостоятельно. Лемма 3.4, теоремы 3.1, 3.7 и 4.1 сформулированы и доказаны автором диссертации. Автором диссертации показана корректность использования для мультилинейного случая утверждений 3.2, 3.3, 3.5, 3.9, 3.10 и 3.11. Остальные утверждения, используемые в работе, были сформулированы и доказаны другими авторами.
Из дополнительных результатов наиболее важным является оценка возможности построения мультилинейных алгоритмов из условия невозможности построения гмультилинейных отображений для любых порядков мультилинейности г. Возможна модификация существующих мультилинейных алгоритмов добавлением фиктивных абонентов до ближайшего возможного значения г. После этапа инициализации алгоритма первые г-п абонентов берут на себя функции эмуляции недостающих абонентов, где г — ближайшее допустимое количество абонентов, преальное количество абонентов, г>п.
Также один из предложенных алгоритмов мультилинейной подписи был реализован в модели кичного дерева. На его примере можно сделать вывод о том, что аналогичным образом в модели А:-ичного дерева можно построить и другие мультилинейные алгоритмы, предложенные в диссертации и многосторонние мультилинейные алгоритмы, которые будут разрабатываться в будущем.
Результаты проведенной работы позволяют построить эффективную и безопасную систему многостороннего обмена информацией для группы абонентов, что является актуальной задачей в области информационной безопасности настоящего времени.
Использование мультилинейных криптографических отображений позволит значительно уменьшить связную сложность многосторонних алгоритмов, сократив объем передаваемой информации, и потенциально может снизить вычислительную сложность алгоритмов при построении эффективно вычислимых мультилинейных отображений. До настоящего времени не удалось построить криптографические мультилинейные отображения со степенью мультилинейности выше 2. Исследования по разработке таких отображений являются одним из предметов дальнейших научных изысканий.
